Logical consequence relations in logics of quasiary predicates
Logical consequence is one of the most fundamental concepts in logic. A wide use of partial (sometimes many-valued as well) mappings in programming makes important the investigation of logics of partial and many-valued predicates and logical consequence relations for them. Such relations are a seman...
Gespeichert in:
| Datum: | 2018 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
PROBLEMS IN PROGRAMMING
2018
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/166 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-166 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/d6/425e72a89483b582a16ba20493b3b9d6.pdf |
| spelling |
pp_isofts_kiev_ua-article-1662025-11-16T14:46:27Z Logical consequence relations in logics of quasiary predicates Отношения логического следствия в логиках квазиарных предикатов Відношення логічного наслідку в логіках квазіарних предикатів Shkilniak, O.S. logic; predicate; semantics; logical consequence UDC 004.42:510.69 логика; предикат; семантика; логическое следствие УДК 004.42:510.69 логіка; предикат; семантика; логічний наслідок УДК 004.42:510.69 Logical consequence is one of the most fundamental concepts in logic. A wide use of partial (sometimes many-valued as well) mappings in programming makes important the investigation of logics of partial and many-valued predicates and logical consequence relations for them. Such relations are a semantic base for a corresponding sequent calculi construction. In this paper we consider logical consequence relations for composition nominative logics of total single-valued, partial single-valued, total many-valued and partial many-valued quasiary predicates. Properties of the relations can be different for different classes of predicates; they coincide in the case of classical logic. Relations of the types T, F, TF, IR and DI were in-vestigated in the earlier works. Here we propose relations of the types TvF and С for logics of quasiary predicates. The difference between these two relations manifests already on the propositional level. Properties of logical consequence relations are specified for formulas and sets of formulas. We consider partial cases when one of the sets of formulas is empty. It is shown that relations P|=TvF and R|=С are non-transitive, some properties of decomposition of formulas are not true for R|=С, but at the same time the latter can be modelled through R|=TF. A number of examples demonstrates particularities and distinctions of the defined relations. We also establish a relationship among various logical consequence relations.Prombles in programming 2016; 1: 29-43 Изучаются отношения логического следствия в логиках тотальных одно-значных, частичных однозначных, то-тальных неоднозначных и частичных неоднозначны предикатов. Наряду из ранее рассмотренными отношениями типов T, F, TF, IR, DI, для логик ква-зиарных предикатов предлжены и исследованы отношения типов TvF и С. Описаны свойства отношений логиче-ского следствия. Приведены примеры, свидетельствующие о различии рас-смотренных отношений. Показана нетранзитивность отношений типов TvF и С, возможность моделирования отношений типа С с помощью отноше-ний типа TF. Установлены соотношения между различными отношениями логического следствия.Prombles in programming 2016; 1: 29-43 Вивчаються відношення логічного наслідку в логіках тотальних однозначних, часткових однозначних, тотальних неоднозначних та часткових неоднозначних предикатів. Поряд із розглянутими раніше відношеннями типів T, F, TF, IR, DI, для логік квазіарних предикатів запропоновано і досліджено відношення типів TvF та С. Описано властивості відношень логічного наслідку. Наведено приклади, які засвідчують відмінності розглянутих відношень. Показана нетранзитивність відношень типів TvF та С, можливість моделювання відношень типу С за допомогою відношень типу TF. Встановлено співвідношення між різними відношеннями логічного наслідку.Prombles in programming 2016; 1: 29-43 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2018-11-21 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/166 10.15407/pp2016.01.029 PROBLEMS IN PROGRAMMING; No 1 (2016); 29-43 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2016); 29-43 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2016); 29-43 1727-4907 10.15407/pp2016.01 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/166/160 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2025-11-16T14:46:27Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
logic predicate semantics logical consequence UDC 004.42:510.69 |
| spellingShingle |
logic predicate semantics logical consequence UDC 004.42:510.69 Shkilniak, O.S. Logical consequence relations in logics of quasiary predicates |
| topic_facet |
logic predicate semantics logical consequence UDC 004.42:510.69 логика предикат семантика логическое следствие УДК 004.42:510.69 логіка предикат семантика логічний наслідок УДК 004.42:510.69 |
| format |
Article |
| author |
Shkilniak, O.S. |
| author_facet |
Shkilniak, O.S. |
| author_sort |
Shkilniak, O.S. |
| title |
Logical consequence relations in logics of quasiary predicates |
| title_short |
Logical consequence relations in logics of quasiary predicates |
| title_full |
Logical consequence relations in logics of quasiary predicates |
| title_fullStr |
Logical consequence relations in logics of quasiary predicates |
| title_full_unstemmed |
Logical consequence relations in logics of quasiary predicates |
| title_sort |
logical consequence relations in logics of quasiary predicates |
| title_alt |
Отношения логического следствия в логиках квазиарных предикатов Відношення логічного наслідку в логіках квазіарних предикатів |
| description |
Logical consequence is one of the most fundamental concepts in logic. A wide use of partial (sometimes many-valued as well) mappings in programming makes important the investigation of logics of partial and many-valued predicates and logical consequence relations for them. Such relations are a semantic base for a corresponding sequent calculi construction. In this paper we consider logical consequence relations for composition nominative logics of total single-valued, partial single-valued, total many-valued and partial many-valued quasiary predicates. Properties of the relations can be different for different classes of predicates; they coincide in the case of classical logic. Relations of the types T, F, TF, IR and DI were in-vestigated in the earlier works. Here we propose relations of the types TvF and С for logics of quasiary predicates. The difference between these two relations manifests already on the propositional level. Properties of logical consequence relations are specified for formulas and sets of formulas. We consider partial cases when one of the sets of formulas is empty. It is shown that relations P|=TvF and R|=С are non-transitive, some properties of decomposition of formulas are not true for R|=С, but at the same time the latter can be modelled through R|=TF. A number of examples demonstrates particularities and distinctions of the defined relations. We also establish a relationship among various logical consequence relations.Prombles in programming 2016; 1: 29-43 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2018 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/166 |
| work_keys_str_mv |
AT shkilniakos logicalconsequencerelationsinlogicsofquasiarypredicates AT shkilniakos otnošeniâlogičeskogosledstviâvlogikahkvaziarnyhpredikatov AT shkilniakos vídnošennâlogíčnogonaslídkuvlogíkahkvazíarnihpredikatív |
| first_indexed |
2025-07-17T09:49:04Z |
| last_indexed |
2025-11-17T02:17:21Z |
| _version_ |
1850410489582977024 |
| fulltext |
Теоретичні та методологічні основи програмування
© О.С. Шкільняк, 2016
ISSN 1727-4907. Проблеми програмування. 2016. № 1 29
УДК 004.42:510.69
О.С. Шкільняк
ВІДНОШЕННЯ ЛОГІЧНОГО НАСЛІДКУ В ЛОГІКАХ
КВАЗІАРНИХ ПРЕДИКАТІВ
Вивчаються відношення логічного наслідку в логіках тотальних однозначних, часткових однозначних,
тотальних неоднозначних та часткових неоднозначних предикатів. Поряд із розглянутими раніше від-
ношеннями типів T, F, TF, IR, DI, для логік квазіарних предикатів запропоновано і досліджено відно-
шення типів TF та С. Описано властивості відношень логічного наслідку. Наведено приклади, які за-
свідчують відмінності розглянутих відношень. Показана нетранзитивність відношень типів TF та С,
можливість моделювання відношень типу С за допомогою відношень типу TF. Встановлено співвідно-
шення між різними відношеннями логічного наслідку.
Ключові слова: логіка, предикат, семантика, логічний наслідок.
Вступ
Розвиток інформаційних технологій
зумовлює розширення сфери застосування
математичної логіки. Створено багато різ-
номанітних логічних систем, які успішно
використовуються в інформатиці й про-
грамуванні. Ці системи зазвичай базують-
ся на класичній логіці предикатів. Водно-
час принципові обмеження класичної логі-
ки спонукають необхідність розробки но-
вих, програмно-орієнтованих логічних фо-
рмалізмів. Такими є композиційно-номіна-
тивні логіки (КНЛ), збудовані на базі спі-
льного для логіки й програмування компо-
зиційно-номінативного підходу.
КНЛ вивчались, зокрема, в [1–4].
Фундаментальним поняттям логіки
є поняття логічного наслідку. Широке ви-
користання в програмуванні часткових ві-
дображень, які можуть бути неоднознач-
ними, робить актуальною проблему дослі-
дження логік із нетрадиційними семанти-
ками та відношень логічного наслідку для
цих логік. Такі відношення є семантичною
основою побудови числень секвенційного
типу. Для пропозиційної логіки нестандар-
тні семантики та відношення логічного на-
слідку розглянуто в [5]. Для чистих пер-
шопорядкових КНЛ (ЧКНЛ) такі відно-
шення вивчались в [2–4].
Мета даної роботи – це дослідження
відношень логічного наслідку для КНЛ
тотальних однозначних, часткових одноз-
начних, тотальних неоднозначних та част-
кових неоднозначних предикатів. Поряд із
розглянутими в [2–4] відношеннями типів
T, F, TF, Cl (в нових позначеннях IR), Cm
(в нових позначеннях DI), для КНЛ пропо-
нуються і вивчаються відношення типів
TF та С. Описано властивості таких від-
ношень, наведено низку прикладів, які за-
свідчують відмінності одних відношень
від інших. Показана нетранзитивність від-
ношень типів TF і С, можливість моде-
лювання
R
|=С за допомогою
R
|=TF. Встанов-
лено співвідношення між різними відно-
шеннями логічного наслідку.
Невизначені в даній роботі поняття
тлумачимо в сенсі [1, 2].
1. Квазіарні предикати, їх
різновиди. Алгебри предикатів
Під V-A-квазіарним предикатом бу-
демо розуміти довільну часткову неодно-
значну функцію вигляду P :
V
A{T, F}.
Тут
V
A – клас V-A-іменних множин,
{T, F} – множина істиннісних значень.
V-A-іменна множина (V-A-ІМ) – це
часткова однозначна функція d : V A.
Трактуємо V і A як множини предметних
імен (змінних) і предметних значень.
Позначимо через P(d) множину тих
значень, які P може прийняти на d
V
А.
Маємо P(d) {T, F}, тому P(d) може бути
одним із значень: {}, {T}, {F}, {T, F}.
Області істинності та хибності пре-
диката P :
V
A {T, F} – це множини
T(P) = {d
V
A | TP(d)},
F(P) = {d
V
A | FP(d)}.
Теоретичні та методологічні основи програмування
30
Ми трактуємо часткові неоднозначні
квазіарні предикати як відношення між
V
A
та {T, F}. Їх називають [2] предикатами
реляційного типу, або R-предикатами.
V-A-квазіарний предикат P:
– однозначний, якщо T(P)F(P) = ;
– тотальний, якщо T(P)F(P) =
V
A.
Часткові однозначні предикати на-
звемо P-предикатами, тотальні – T-преди-
катами, тотальні однозначні – TS-предика-
тами. Класи часткових неоднозначних, час-
ткових однозначних, тотальних, тотальних
однозначних V-A-квазіарних предикатів
позначимо V
APrR , V
APrP , V
APrT , V
APrTS .
V-A-квазіарний предикат P:
– неспростовний (частково істинний), як-
що F(P) = ;
– виконуваний, якщо T(P) ;
– тотально істинний, якщо T(P) =
V
А;
– тотально хибний, якщо F(P) =
V
А;
– тотожно істинний, якщо
T(P) =
V
А та F(P) = ;
– тотожно хибний, якщо
T(P) = та F(P) =
V
А;
– всюди невизначений, якщо
T(P) = та F(P) = ;
– тотально насичений (повне бінарне від-
ношення), якщо T(P) =
V
А та F(P) =
V
А.
Кожний неспростовний та кожний
невиконуваний предикат є однозначними.
Всюди невизначений V-A-квазіар-
ний предикат позначимо як V
A , тотожно
істинний – як V
AT , тотожно хибний – як
V
AF , тотально насичений – як V
A . Якщо V
та А маються на увазі, предикати V
A , ,TV
A
V
AF , V
A позначаємо як , T, F, .
V-A-квазіарний предикат P
~
дуаль-
ний до V-A-квазіарного предиката P, якщо
)()
~
( ;)()
~
( PTPFPFPT .
Із визначень випливає:
Q – P-предикат Q
~
– T-предикат;
Q – T-предикат Q
~
– P-предикат;
якщо Q – TS-предикат, то QQ
~
.
Задамо відображення дуалізації
V
A
V
A PrRPrR : наступним чином:
PP
~
)( для кожного V
APrRP .
Для класів предикатів маємо:
;( ,( V
A
V
A
V
A
V
A PrPPrTPrTPrP
V
A
V
A
V
A
V
A PrTSPrTSPrRPrR ( ,( ;
}{})({ },{})({ V
A
V
A
V
A
V
A .
Розглянемо тепер композиції квазі-
арних предикатів.
На пропозиційному рівні компози-
ції працюють лише з істиннісними значен-
нями, які вироблені предикатами. Тради-
ційна їх назва – логiчні зв’язки. Основни-
ми є 1-арна композиція заперечення та
2-арні композиції диз’юнкція , кон’юнк-
ція &, імплікація , еквіваленція .
Пропозиційні композиції задамо че-
рез області істинності й хибності відповід-
них предикатів. Предикати (P), (P, Q),
(P, Q), &(P, Q), (P, Q) традиційно поз-
начаємо як P, PQ, PQ, P&Q, PQ.
Предикати P та PQ задамо так:
T(P) = F(P); F(P) = T(P);
T(PQ) = T(P)T(Q); F(PQ) = (P)F(Q).
та – це базові пропозиційні
композиції. Композиції , &, є похід-
ними, вони виражаються через та :
PQ = PQ;
P&Q = (P Q);
PQ = (PQ)&(QP).
На рівні ЧКНЛ до пропозиційних
композицій додаємо композиції реноміна-
ції та квантифікації. Спочатку опишемо
необхідні для цього операції над V-A-ІМ.
Операцію накладки задаємо так:
= [va | vasn()].
Тут asn(d) = {vV | vad}.
Параметризовану за множиною пар
імен операцію AA VVvv
xx
n
n
:r
,...,
,...,
1
1
реномінації
задаємо так:
Теоретичні та методологічні основи програмування
31
)](),...,([)(r 11
,...,
,...,
1
1
nn
vv
xx
xdvxdvddn
n
.
Замість nyy ,...,1 далі пишемо y .
Задамо композицію реномінації
v
xR : ))(r())((R dPdP v
x
v
x для кожного
d
V
А.
Параметричні композиції квантифі-
кації x і x можна задати через області
істинності та хибності відповідних преди-
катів. При цьому композиція х є похід-
ною.
Дамо визначення предиката xP:
T(xP) = {d
V
A | TР[dxa] для
деякого aA};
F(xP) = {d
V
A | FР[dxa] для
всіх aA}.
Композицію х задаємо умовою
хР = хР.
Композиції , , ,R v
x x називають
базовими композиціями ЧКНЛ.
Властивості композицій квазіарних
предикатів описано в [1–4].
Зокрема, , , ,Rv
x x зберігають од-
нозначність і тотальність квазіарних пре-
дикатів. Звідси випливає, що класи P-
предикатів, T-предикатів, TS-предикатів
замкнені відносно композицій , , ,Rv
x x.
Для предикатів та маємо:
= , = , )(Rv
x , x() = ,
= ; = ; )(R v
x ; x() = .
Отже, 1-елементні множини {} та
{} замкнені відносно , , ,Rv
x x.
Алгебра ),( CQPrRQR V
A
V
A , де
CQ = {, , ,R v
x
x}, називається чистою
першопорядковою композиційною алгеб-
рою квазіарних предикатів. Можна виділи-
ти наступні підалгебри алгебри V
AQR :
),( CQPrPQP V
A
V
A – алгебра P-предикатів,
),( CQPrTQT V
A
V
A – алгебра T-предикатів,
),( CQPrTSQTS V
A
V
A – алгебра TS-пре-
дикатів.
Виділяємо сингулярні підалгебри
V-A )},({ CQV
A та V-A = )},({ CQV
A .
Нехай – відображення дуалізації.
Алгебри ),Pr( 1 CQ та ),Pr( 2 CQ дуа-
льні, якщо )(Pr1 2Pr та )(Pr2 1Pr .
Маємо пару дуальних алгебр V
AQP
та V
AQT , алгебри V
AQR та V
AQTS автодуа-
льні. Дуальними є V-A та V-A.
2. Мови та семантичні моделі
Семантичними моделями ЧКНЛ є
[1, 2] чисті першопорядкові композиційні
системи квазіарних предикатів. Вони ма-
ють вигляд ),Pr,( CQA .
Композиційна система ),Pr,( CQA
задає алгебру даних )Pr,(A та компози-
ційну алгебру предикатів ),Pr( CQ . Терми
композиційної алгебри трактуємо як фор-
мули мови ЧКНЛ.
Алфавiт мови ЧКНЛ:
– множина },,,{ xRCs v
x символів ба-
зових композицій;
– множина Ps предикатних символів;
– множина V предметних імен (змінних), в
якій виділена множина U
V тотально
неістотних [2] імен.
Четвірку = (V, U, Cs, Ps) назвемо
розширеною сигнатурою мови.
Дамо індуктивне визначення мно-
жини Fr формул:
– Ps Fr; формули pPs – атомарні;
– , Fr , Ф, ,v
xR xFr.
Для зручності далі пишемо скоро-
чення формул (див. [1, 2]), користуючись
символами похідних композицій та інфік-
сною формою запису для , , , .
Інтерпретуємо мову на композицій-
них системах вигляду CS = ),Pr,( CQA .
Iмена xV позначають елементи множини
базових даних A, символи композицій –
композиції із CQ . Символи Рs позначають
базові предикати в множині Pr . Для опису
Теоретичні та методологічні основи програмування
32
цього позначення задамо тотальне одноз-
начне відображення I : Ps Pr. Відобра-
ження інтерпретації формул I : Fr Pr за-
дамо як розширення відображення
I : Ps Pr згідно побудови формул із про-
стіших за допомогою символів Cs:
– I() = (I()),
– I() = (I(), I()),
– ));((R))(( IRI v
x
v
x
– I(x) = x(I()).
Трійку J = (CS, , I) називатимемо
інтерпретацією мови ЧКНЛ сигнатури .
Cкорочено інтерпретації позначаємо (A, I).
Предикат J() – значення формули
при інтерпретації J – позначимо J.
Виділення підалгебр квазіарних
предикатів виділяє відповідні класи інтер-
претацій. Маємо загальний клас R-інтер-
претацій та підкласи P-інтерпретацій, T-ін-
терпретацій, TS-інтерпретацій. Такі класи
інтерпретацій назвемо семантиками, буде-
мо їх позначати відповідно , , , .
Отже, далі можна говорити про R-
семантику, T-семантику, P-семантику, TS-
семантику логік квазіарних предикатів.
Логіки R-предикатів, T-предикатів,
P-предикатів, TS-предикатів назвемо логі-
ками з R-семантикою, T-семантикою, P-се-
мантикою, TS-семантикою відповідно.
Семантики , , в [2] названо не-
окласичною, пересиченою, загальною.
Для семантик , , , маємо:
, .
Відображення дуалізації продов-
жимо на класи інтерпретацій.
Інтерпретація (J) = (A, I ) дуальна
до інтерпретації J = (A, I), якщо для кож-
ного Ps маємо )()( )( JJ FT та
)()( )( JJ TF . Тоді J дуальна до (J):
)()( )(JJ FT та )()( )(JJ TF .
Виділення дуальних пар алгебр ква-
зіарних предикатів індукує виділення дуа-
льних пар класів інтерпретацій. Зокрема:
() = , () = , () = , () = .
Отже, P-семантика і T-семантика
дуальні, а R-семантика і TS-семантика ав-
тодуальні.
Нехай інтерпретації J та дуальні.
Тоді (див. [2]) для всіх Fr маємо:
)()( FT J та )()( JTF .
Для кожної J можна побудувати
систему тотальних розширень . Це
означає: для кожного pPs маємо
T(pJ) T(p) =
V
A та F(pJ) F(p) =
V
A.
Згідно теореми про розширення [1] тоді
T(J) T() =
V
A та F(J) F() =
V
A
для кожної Fr.
Нехай – клас інтерпретацій.
Формула неспростовна при інте-
рпретації J, або J-неспростовна (позн.
J |=
), якщо предикат J – неспростовний.
Формула неспростовна в (позн.
|=
), якщо J |=
для кожної J.
Формула виконувана при інтерп-
ретації J, або J-виконувана, якщо J – ви-
конуваний предикат.
Формула виконувана в , якщо
J-виконувана при деякій J.
Кожна формула буде виконуваною
в та в (беремо інтерпретацію, задану
сингулярною алгеброю V-A).
Отже, поняття виконуваної форму-
ли змістовне лише для P-інтерпретацій.
Формула тотально істинна при
інтерпретації J (позн. J
|
), якщо J –
тотально істинний предикат.
Формула тотально iстинна в
(позн. |
), якщо J
|
для кожної J.
Формула тотожно істинна при ін-
терпретації J, якщо J = T.
Формула тотожно iстинна в ,
якщо тотожно істинна при кожній J.
Подібним чином даємо визначення:
– тотально хибної при інтерпретації J та
тотально хибної в формули;
– тотожно хибної при інтерпретації J та
тотожно хибної в формули.
Теоретичні та методологічні основи програмування
33
Теорема 1. 1) для R-семантики кла-
си неспростовних, тотально істинних і то-
тожно істинних формул порожні;
2) для P-семантики класи тотально
істинних і тотожно істинних формул по-
рожні;
3) для T-семантики класи неспросто-
вних і тотожно істинних формул порожні;
4) для TS-семантики класи неспрос-
товних, тотально істинних і тотожно іс-
тинних формул збігаються.
Відповідні твердження теореми 1
можна сформулювати для класів тотально
хибних та тотожно хибних формул.
Твердження 1.
P
|=
T
|
.
J буде неспростовним при J
тотально істинний при дуальній .
Твердження 2.
P
|=
неви-
конувана в .
Справді,
P
|=
F(J) = для ко-
жної J T(J) = для кожної
J невиконувана.
Теорема 2.
P
|=
тотожно іс-
тинна в .
Доводимо . Якщо не є тотожно
істинною в , то F(J) для деякої
J, тому
P
|
в силу .
Доводимо . Якщо
P
|
, то маємо
F(J) для деякої J. Візьмемо для J
систему тотальних розширень . Тоді
F(J) F(), звідки F() , тому
не є тотожно істинною в .
Наслідок 1. тотожно істинна в
P
|=
T
|
.
Поняття тавтології для ЧКНЛ вво-
димо традиційним чином (див. [1]).
Формула пропозиційно нерозклад-
на, якщо вона атомарна або має вигляд
x чи R v
x . Нехай Fr0 – множина пропо-
зиційно нерозкладних формул. Істиннiсна
оцiнка мови – це тотальне відображення
: Fr0 {T, F}. Таке продовжуємо [1] до
відображення : Fr {T, F} згідно дії ком-
позицій та на предикати.
Формула тавтологiя, якщо
() = T для кожної істиннісної оцінки .
Теорема 3. тавтологія тото-
жно істинна в .
Нехай утворена із пропозиційно
нерозкладних формул 1, …, n. Припус-
тимо, що не тотожно істинна в , тоді
(d) = F для деяких J = (A, I) та d
V
A.
Візьмемо істиннiсну оцiнку : (i) = iJ(d).
Тоді () = F, тому не тавтологія.
Наслідок 2. Пропозиційна формула
є тавтологія тотожно істинна в
неспростовна в тотально
істинна в .
3. Відношення логічного
наслідку
На основі різних співвідношень між
областями істинності та хибності предика-
тів можна ввести низку відношень на
множині формул мови ЧКНЛ.
Спочатку вводимо (див. [2]) відно-
шення наслідку для двох формул при інте-
рпретації на фіксованій інтерпретації J.
1. Істиннісний, або T-наслідок J|=T :
J|=T T(J) T(J).
2. Хибнісний, або F-наслідок J|=F :
J|=F F(J) F(J).
3. Cильний, або TF-наслідок J|=TF :
J|=TF T(J) T(J) та F(J) F(J).
4. Неспростовнісний, або IR-наслідок
J|=IR : J|=IR T(J)F(J) = .
5. Дуальний до IR, або DI-наслідок
J|=DI : J|=DI F(J)T(J) =
V
A.
До цих “природних” відношень на-
слідку, досліджених в [2–4], додамо ще
два.
6. С-наслідок J|=С :
J|=С T(J)F(J) F(J)T(J).
7. TF-наслідок J|=TF :
J|=TF T(J) T(J) або F(J) F(J).
Теоретичні та методологічні основи програмування
34
С-наслідок для пропозиційної логі-
ки розглянуто в [5]. Дослідити TF-нас-
лідок запропонував М.С. Нікітченко.
Відповідні відношення логічного
наслідку в семантиці визначаємо за схе-
мою:
|= , якщо J|= для кожної J.
Твердження 3. Усі визначені вище
відношення рефлексивні.
Твердження 4. Маємо:
J|=IR J|=С, J|=DI J|=С;
J|=TF J|=T J|=TF, J|=TF J|=F J|=TF .
У випадках класичної логіки та ло-
гіки TS-предикатів маємо ( ) ( )J JT F та
( ) ( )J JF T . Для цих логік усі наведені
відношення логічного наслідку втрачають
відмінності, вони збігаються і фактично
стають єдиним логічним наслідком. Для
логіки TS-предикатів таке відношення ло-
гічного наслідку позначимо
TS
|= . Отже:
Теорема 4.
TS
|=TF =
TS
|=T =
TS
|=F =
=
TS
|=IR =
TS
|=DI =
TS
|=C =
TS
|=TF =
TS
|=.
Твердження 5.
P
|=DI =
T
|=IR = .
Візьмемо P-інтерпретацію, задану
алгеброю V-A, на ній усі формули інтерп-
ретуються як . Звідси маємо
P
|=DI = .
Візьмемо T-інтерпретацію, задану
алгеброю V-A, на ній усі формули інтерп-
ретуються як . Звідси маємо
T
|=IR = .
Наслідок 3.
R
|=IR =
R
|=DI = .
У випадку J маємо
J|=T J|=IR та J|=F J|=IR.
Справді, для , Fr із умов
T(J) T(J) та T(J) F(J) = маємо
T(J)F(J) = ; із умов F(J) F(J) та
T(J) F(J) = маємо T(J)F(J) = .
У випадку J маємо
J|=T J|=DI та J|=F J|=DI.
Справді, для , Fr із умов
F(J) T(J) =
V
A та T(J) T(J) маємо
F(J)T(J) =
V
A; із F(J) T(J) =
V
A та
F(J) F(J) маємо F(J)T(J) =
V
A.
Таким чином, маємо.
Теорема 5.
P
|=T
P
|=IR,
P
|=F
P
|=IR;
T
|=T
T
|=DI,
T
|=F
T
|=DI .
Наслідок 4.
P
|=
TS
|= та
T
|=
TS
|=.
Справді, та .
Теорема 6. Маємо
P
|=IR =
TS
|=.
Згідно наслідку 4 маємо
P
|=IR
TS
|=.
Покажемо
TS
|=
P
|=IR .
Нехай супротивне:
TS
|=
P
|=IR . Тоді
для деяких ,Fr та J маємо
TS
|=
та J|IR . Останнє означає, що
T(J) F(J) . Візьмемо для J систему
тотальних розширень . Тоді
T(J) T() та F(J) F(), звідки
T() F() , тому |IR . Звідси
випливає
TS
| – суперечність.
Теорема 7. Нехай інтерпретації A
та B дуальні. Тоді маємо:
1) A|=T B|=F та
A|=F B|=T ;
2) A|=TF B|=TF ;
3) A|=TF B|=TF ;
4) A|=IR B|=DI та
A|=DI B |=IR ;
5) A|=С B|=С .
Зауважимо, що пп. 1, 2, 4 теореми
доведено в [2]. Тому доведемо пп. 3, 5.
Доводимо п. 3. A|=TF
A|=T або A|=F (за п. 1) B|=F
або B|=T B|=TF .
Доводимо п. 5. Маємо A|=С
T(A)F(A) F(A)T(A)
( ) ( ) ( ) ( )B B B BF T T F
( ) ( )B BF T ( ) ( )B BT F
T(B)F(B) F(B)T(B) B|=С .
Теорема 8. Маємо (див. також [2]):
R
|=T
R
|=F
R
|=TF .
Покажемо: |=T |=TF .
Нехай супротивне: |=T , проте
|TF . Тоді T(J) T(J) для кожної і J,
проте A|TF для деякої A. Тоді непра-
вильно F(A) F(A), тому для дуальної B
Теоретичні та методологічні основи програмування
35
неправильно T(B) T(B), а це супере-
чить |=T .
Аналогічно |=F |=TF .
Із теорем 4, 6–8 маємо:
Наслідок 5.
R
|=T =
R
|=F =
R
|=TF ;
P
|=IR =
T
|=DI =
P
|=С =
T
|=С =
TS
|= ;
P
|=T =
T
|=F ;
P
|=F =
T
|=T ;
P
|=TF =
T
|=TF ;
P
|=TF =
T
|=TF .
Отже, із перелічених вище відно-
шень різними можуть бути лише такі:
P
|=IR,
P
|=T,
P
|=F,
P
|=TF,
P
|=TF,
R
|=С,
R
|=TF.
Твердження 6. Відношення J|=T,
J|=F, J|=TF та відношення
P
|=T,
P
|=F,
P
|=TF,
R
|=TF є транзитивними.
Складніше із транзитивністю J|=IR,
J|=DI, J|=C, J|=TF та
P
|=IR,
P
|=TF,
R
|=C.
Приклад 1. Нехай A, p, q, sPs.
Задамо предикат pA як T, qA – як , sA – як
F. Тоді p A|=IR q та q A|=IR s, проте p A|IR s.
Отже, відношення A|=IR нетранзити-
вне. Звідси для дуальної інтерпретації B
маємо нетранзитивність B|=DI. Проте для
відношення
P
|=IR ситуація нормалізується.
Теорема 9.
P
|=IR транзитивне.
Нехай маємо супротивне:
P
|=IR ,
P
|=IR , проте
P
|IR . Тоді для деякої
A, маємо T(A)F(A) . Візьмемо
для A деяку інтерпретацію тотальних роз-
ширень M, тоді T(A) T(M) та
F(A) F(M), звідки T(M)F(M) .
Предикати M, M, M тотальні, звідки
отримуємо
T(M)F(M) = T(M)F(M) =
= T(M)F(M) =
V
A, тоді умови
P
|=IR
та
P
|=IR дають T(M) T(M) та
T(M) T(M), звідки T(M) T(M), що
суперечить T(M)F(M) .
Приклад 2. Нехай p, qPs, – це
формула p (qq), – це p (qq).
Для кожної A маємо:
T(A) = T(pA) (T(qA)F(qA)) = T(pA),
F(A) = F(pA) (T(qA)F(qA)) F(pA),
T(A) = T(pA) (T(qA)F(qA)) T(pA),
F(A) = F(pA) (T(qA)F(qA)) = F(pA).
Отже, A|=T p та p A|=F для кож-
ного A, тому
P
|=TF p та p
P
|=TF .
Водночас маємо p
P
|=TF та
P
|=TF p, тому p
P
|=TF та
P
|=TF p.
Задамо інтерпретацію B таку:
T(B) = T(pB) (T(qB)F(qB)) T(pB),
F(B) = F(pB) (T(qB)F(qB)) F(pB).
Проте T(B) = T(pB), F(B) = F(pB),
звідки
P
|T та
P
|F , тому
P
|TF .
Отже, отримуємо наступну теорему.
Теорема 10.
P
|=TF нетранзитивне.
Для довільних формули та інтер-
претації J далі позначаємо T(J)F(J) як
J, а T(J)F(J) як J.
Приклад 3. Нехай p, qPs, – це
формула p (qq), – це формула
p (qq). Для довільної A маємо:
T(A) = T(pA)qA, F(A) = F(pA)qA,
T(A) = T(pA)qA, F(A) = F(pA)qA ;
T(A) F(pA) = (T(pA)qA) F(pA) =
= (T(pA)F(pA)) (F(pA)qA),
F(A) T(pA) = (F(pA)qA) T(pA).
Проте F(pA)qA F(pA)qA,
T(pA)F(pA) T(pA), звідки T(A) F(pA)
F(A) T(pA), тому A|=C p.
Тепер маємо T(pA) F(A) = T(pA)
(F(pA)qA) = (T(pA)F(pA))(T(pA)qA),
F(pA) T(A) = F(pA) (T(pA)qA).
Водночас T(pA)qA T(pA)qA,
T(pA)F(pA) F(pA), звідки T(pA) F(A)
F(pA) T(A), тому p A|=C .
Таким чином,
R
|=C p та p
R
|=C .
Проте p
R
|=TF та
R
|=TF p, тому
p
R
|=С та
R
|=С p.
Задамо інтерпретацію B таку:
T(pB) = F(pB) , T(qB) = F(qB),
T(pB)T(qB) = . Тоді:
T(B) F(B) = (T(pB)qB) (F(pB)
qB) = T(pB)qB ,
F(B) T(B) = (F(pB)qB) (T(pB)qB)
= = .
Теоретичні та методологічні основи програмування
36
Отже, B|C , тому
R
|C .
Таким чином, отримуємо.
Теорема 11.
R
|=C нетранзитивне.
Отже, відношення
P
|=TF та
R
|=C ма-
ють не зовсім прийнятні властивості. Вони
не задовольняють постулату Тарського про
транзитивність логічного наслідку.
Наведемо визначення тавтологічно-
го наслідку для пари формул (див. [1, 2]).
є тавтологічним наслідком
(позн. |=t ), якщо – тавтологія.
Відношення |=t рефлексивне і тран-
зитивне.
Для пропозиційних формул умова
TS
|= означає, що |=t . Справді,
TS
|= тотожно істинна в
(наслідок 2) є тавтологія |=t .
Теорема 12. 1) для пропозиційних
формул маємо:
P
|=IR
T
|=DI
P
|=C
T
|=C
TS
|= |=t ;
2) у випадку класичної семантики
пропозиційної логіки усі описані вище від-
ношення збігаються.
Зауважимо, що в монографії
О.Д. Смирнової ([5] стор. 190) неточно
сказано, що відношення типу [f] в релеван-
тній семантиці (в наших термінах термінах
відношення
R
|=С) формалізується класич-
ною логікою, проте це не так: згідно прик-
ладу 3 маємо p (qq)
R
|C p (qq),
хоча p (qq) p (qq) – тавтологія.
Ще одна неточність: там же сказано, що
відношення типу [a], [b], [c] в релевантній
семантиці (в наших термінах відношення
R
|=T,
R
|=F,
R
|=TF) не є еквівалентними, хоча
(наслідок 5)
R
|=T =
R
|=F =
R
|=TF .
Відношення логічного наслідку
P
|=IR,
P
|=T,
P
|=F,
P
|=TF,
R
|=TF індукують відпо-
відні відношення логічної еквівалентності
P
IR,
P
T,
P
F,
P
TF,
R
TF.
Визначаємо їх за такою схемою:
, якщо
|= та |= .
Подібним чином визначаємо від-
ношення тавтологічної еквівалентності t :
t , якщо |=t та |=t .
Твердження 7. Відношення
P
IR,
P
T,
P
F,
P
TF,
R
TF, t рефлексивні, транзи-
тивні та симетричні.
Можна визначити (див. [2]) відно-
шення еквівалентності формул при інтер-
претації J за наступною схемою:
J , якщо J|= та J|= .
Твердження 8.
J
для кожної J.
Для відношення JTF отримуємо:
JTF T(J) = T(J) та F(J) = F(J).
Отже, JTF означає, що J = J.
Відношення T, JF, JTF, JTF тран-
зитивні, проте JIR нетранзитивне:
Справді, нехай A, p, q, sPs. За-
дамо pA як T, qA – як , sA – як F. Тоді
p AIR q та q A s, проте неправильно p AIR s.
Твердження 9. Логічна зв’язка
узгоджується з відношенням
P
IR :
P
IR
P
|=
.
Твердження 10. 1) для пропозицій-
них формул умова
, де
– одне з
визначених вище відношень логічної екві-
валентності, означає, що тоді t ;
2) для класичної семантики пропо-
зиційної логіки усі описані вище відно-
шення логічної еквівалентності збігаються.
Введемо відношення
P
TF та
R
С.
Відношення
P
TF визначаємо так:
P
TF
P
|=TF та
P
|=TF .
Задамо відношення JTF так:
JTF J|=TF та J|=TF .
Тоді
P
TF JTF для ко-
жної J.
Твердження 11. Відношення JTF
та
P
TF нетранзитивні.
Для формул прикладу 2 для кожної
A маємо ATF p та p ATF , тому ма-
ємо ATF p та p ATF . Проте для інтер-
претації B прикладу 2 маємо B|TF та
B|TF , тому неправильно BTF та
Теоретичні та методологічні основи програмування
37
неправильно
P
TF .
Отже, JTF та
P
TF не є відношен-
нями еквiвалентності.
Відношення
R
С визначимо так:
R
С
R
|=С та
R
|=С .
Задамо відношення JС так:
JС J|=С та J|=С .
Тоді
R
С JС для кожної
J.
Твердження 12. Відношення JС та
R
С нетранзитивні.
Для формул прикладу 3 для кожної
A маємо AС p та p AС , тому маємо
AС p та p AС . Проте для інтерпретації
B прикладу 3 маємо B|С та B|С ,
тому неправильно BС та неправильно
R
С .
Таким чином, JС та
R
С теж не є ві-
дношеннями еквiвалентності.
4. Відношення логічного наслідку
для множин формул
Нехай Fr, J – інтерпретація.
Скорочено позначимо
)( JT як T(J),
)( JF як F(J),
)( JT як T(J),
)( JF як F(J).
є IR-наслідком при J (позн.
J|=IR ), якщо T(J) F
(J) = .
є DI-наслідком при J (позн.
J|=DI ), якщо F(J) T
(J) =
V
A.
є T-наслідком при J (позн.
J|=T ), якщо T(J) T
(J).
є F-наслідком при J (позн.
J|=F ), якщо F(J) F
(J).
є TF-наслідком при J (позн.
J|=TF ), якщо J|=T та J|=F .
Відповідні відношення логічного
наслідку в семантиці визначаємо за схе-
мою:
|= , якщо J|= для кожної J.
є тавтологічним наслідком
(позн. |=t ), якщо для кожної істиннiсної
оцiнки : Fp{T, F} із умови () = T для
всіх маємо: (Ψ) = T для деякої Ψ.
Відношення наслідку та логічного
наслідку для множин формул рефлексивні
та нетранзитивні (див. [1, 2]).
Розглянуті в попередньому розділі
відношення наслідку та логічного наслідку
для формул є окремими випадками відпо-
відних відношень для множин формул, їх
позначення та властивості (окрім транзи-
тивності) переносяться на випадок відпо-
відних відношень для множин формул.
Відношення наслідку та логічного
наслідку для логік квазіарних предикатів
(окрім введених тут відношень типу TF
та С) вивчались в [1–4]. Розглянемо основ-
ні властивості цих відношень.
Теорема 13. Нехай інтерпретації J
та дуальні. Тоді:
1) J|=T |=F та
J|=F |=T ;
2) J|=TF |=TF ;
3) J|=IR |=DI та
J|=DI |=IR ;
4) J|=TF |=TF ;
5) J|=С |=С .
Серед розглянутих відношень логі-
чного наслідку для множин формул різни-
ми можуть бути лише такі:
P
|=IR,
P
|=T,
P
|=F,
P
|=TF,
P
|=TF,
R
|=С,
R
|=TF, |=t .
Розглянемо наслідки, коли одна з
множин формул порожня.
J|= означає T J|= ,
J|= означає J|= F.
Звідси маємо наступне.
|=t означає, що – тавтологія;
|=t означає: – суперечність;
J|=IR та J|=F означають
F(J) = , тобто J |= ;
J|=DI та J|=T означають
T(J) =
V
A, тобто J | ;
Теоретичні та методологічні основи програмування
38
J|=TF означає: T(J) =
V
A або
F(J) = , тобто J | або J |= ;
J|=C означає F(J) T(J);
J|=TF означає T(J) =
V
A та
F(J) = , тобто J = T;
J|=IR та J|=T означають
T(J) = ;
J|=DI та J|=F означають
F(J) =
V
A;
J|=TF означає: T(J) = або
F(J) =
V
A;
J|=C означає T(J) F(J);
J|=TF означає: T(J) = та
F(J) =
V
A.
Звідси отримуємо:
P
|=IR та
P
|=F означають: для
всіх J маємо J|=IR , тобто
P
|= ;
P
|=C теж означає
P
|= ;
T
|=DI та
T
|=T означають: для
всіх J маємо J|=DI , тобто
T
| ;
T
|=C теж означає
T
| ;
P
|=TF означає: T(J) =
V
A або
F(J) = , для всіх J, звідки
P
|= ;
T
|=TF означає: T(J) =
V
A або
F(J) = , для всіх J, звідки
T
| ;
не існує Fr таких, що
R
|=С
або
P
|=TF або
T
|=TF або
R
|=TF ;
P
|=IR ,
P
|=F ,
P
|=C та
P
|=TF означають
P
|= ;
T
|=DI ,
T
|=T ,
T
|=C та
T
|=TF означають
T
| ;
не існує Fr таких, що
R
|=С
або
P
|=TF або
T
|=TF або
R
|=TF .
Враховуючи наслідок 1, отримуємо.
Теорема 14.
P
|=C
P
|=IR
P
|=F
T
|=C
T
|=DI
T
|=T
P
|=
T
| ;
P
|=C
P
|=IR
P
|=F
T
|=C
T
|=DI
T
|=T
P
|=
T
| .
Властивості контрапозиції:
1)
P
|=IR
P
|=IR ;
2)
P
|=TF
P
|=TF та
R
|=TF
R
|=TF ;
3)
P
|=TF
P
|=TF ;
4)
R
|=C
R
|=C ;
5)
P
|=T
P
|=F та
P
|=F
P
|=T .
Водночас неправильні такі твер-
дження:
1)
P
|=T
P
|=T ;
2)
P
|=F
P
|=F .
Справді, візьмемо p, q, sPs та інте-
рпретацію J: F(qJ) T(pJ)F(pJ),
T(qJ) T(sJ)F(sJ). Тоді p&p
P
|=T q та
q J|T pp, q
P
|=F ss та s&s J|F q.
Розглянемо можливість перенесен-
ня формули з лівої частини логічного нас-
лідку в праву і навпаки.
Теорема 15. Маємо:
1)
P
|=IR , ,
P
|=IR та
P
|=IR , ,
P
|=IR ;
2)
R
|=С , ,
R
|=С та
R
|=С , ,
R
|=С ;
3)
P
|=T , ,
P
|=T та
P
|=T , ,
P
|=T ;
4) ,
P
|=F
P
|=F , тa
,
P
|=F
P
|=F , .
Теорема 16. Можливо:
1) ,
P
|=T та
P
|T , ;
,
P
|=T та
P
|T , ;
2)
P
|=F , та ,
P
|F ;
P
|=F , та ,
P
|F ;
3) ,
P
|=TF та
P
|TF , ;
P
|=TF , та ,
P
|TF ;
4) ,
R
|=TF та
R
|TF , ;
R
|=TF , та ,
R
|TF ;
5) ,
P
|=TF та
P
|TF , ;
P
|=TF , та ,
P
|TF .
Теоретичні та методологічні основи програмування
39
Доводимо п. 1. Візьмемо J таку:
T(J) = F(J) = , T(J) . Маємо
,
P
|=T , однак J|T , ; маємо
,
P
|=T , але
P
|T , .
Доводимо п. 2. Візьмемо J таку:
T(J) = F(J) = , F(J) . Маємо
P
|=F , , проте ,
P
|F ;
маємо
P
|=F , , але ,
P
|F .
Доводимо п. 4. Завжди маємо
,
R
|=TF , однак
R
|T , , якщо
взяти J таку: T(J) = F(J) = , T(J) .
Маємо
R
|=TF , , проте
,
R
|F , якщо взяти J таку:
T(J) = F(J) = , F(J) .
Аналогічно доводимо п. 3.
Доводимо п. 5. Нехай p, qPs, –
це формула p (qq), – це p (qq).
Тоді маємо ,
P
|=T :
T(
) = F()T() =
= F(p (qq))T(p (qq)) =
= F(p)T(p) = .
Далі маємо
P
|=F , :
F() = F()T() = .
Звідси маємо ,
P
|=TF та
P
|=TF ,
, але (приклад 3)
P
|TF .
Отже, для
P
|=IR та
R
|=С можна роби-
ти перенесення формули з лівої частини
логічного наслідку в праву і навпаки; а
для
P
|=T,
P
|=F,
P
|=TF,
P
|=TF,
R
|=TF – не можна.
Теорема 17. Маємо:
1) , ,
P
|=T , проте , ,
P
|F ;
2)
P
|=F , , , але
P
|T , , ;
3) , ,
P
|=TF , , ;
4) , ,
R
|TF , , .
Для п. 1 візьмемо , та інтерпре-
тацію J: T(J) = F(J) = та F(J) .
Тоді , J|F , тому ,
P
|F .
Для п. 2 візьмемо , та інтерпре-
тацію J: T(J) = F(J) = та T(J) .
Тоді J|T , , тому
P
|T , .
Доведемо п. 3. Для кожної J ма-
ємо T(J)F(J) = та F(J)T(J) = ,
звідки , ,
P
|=T , , та
, ,
P
|=F , , , тому отримуємо
, ,
P
|=TF , , .
Для п. 4 візьмемо , та інтерпре-
тацію J таку: T(J) = F(J) =
V
A та
T(J) = F(J) = . Тоді & J |TF ,
тому ,
R
|TF , .
Відношення
R
|=С зводиться до
R
|=TF .
Для Fr введемо позначення:
= { | }.
Теорема 18. Маємо
R
|=С
,
R
|=TF ,
.
Для J та множини
маємо:
T(
J) =
)()( JJ FT F(J),
T(
J) =
)()( JJ FT F(J),
F(
J) =
)()( JJ TF T(J),
F(
J) =
)()( JJ TF T
(J).
Для кожної J тоді маємо:
J|=С T(J)F(J) F
(J)T(J)
T(J)T(
J) T
(
J)T(J)
F(
J)F(J) F
(J)F(
J)
, J|=T ,
, J|=F ,
, J|=TF ,
.
Звідси отримуємо
R
|=С
,
R
|=TF ,
.
Зокрема, для , Fr маємо:
R
|=C ,
R
|=TF , .
Приклад 4. Маємо
(PP) (QQ)
R
|=C S S та
(PP) (QQ)
P
|TF S S.
Формули (PP) (QQ) та
S S позначимо та .
Для кожної J маємо:
T(J) = (T(J)PJ)QJ;
Теоретичні та методологічні основи програмування
40
F(J) = (F(J)PJ)QJ =
= (F(J)QJ)(PJQJ);
T(J) = (T(J)F(SJ))T(SJ);
F(J) = (F(J)T(SJ))F(SJ).
Тоді T(J)F(J) = ((T(J)PJ)QJ)
(F(J)T(SJ))F(SJ) =
= (T(J)PJF(J)F(SJ))
(T(J)PJSJ)(QJF(J)F(SJ))
(QJSJ) (T(J)F(SJ))T(SJ)
(F(J)QJ)(PJQJ) = T(J)F(J),
тобто
J|=C . Отже,
R
|=C .
Візьмемо A таку: PA QA = ;
(PA QA) SA = ; T(A) ;
F(A) (при цьому PA = QA = ).
Маємо T(A) = T(A)PA PA,
F(A) = F(A)QA QA ;
T(A) = (T(A)F(SA))T(SA) SA ;
F(A) = (F(A)T(SA))F(SA) SA .
Згідно (PA QA) SA = тоді
T(A) T(A) та F(A) F(A), звідки
A|T та A|F . Отже,
P
|TF .
Приклад 5. Маємо
(PP) (QQ)
P
|=T ,
(PP) (QQ)
P
|F та
(PP) (QQ)
R
|C .
(PP) (QQ) позначимо .
Для кожної J маємо T(J) =
= T(J)PJPJ = T(J), звідки J
P
|=T .
Візьмемо B таку: F(B) ,
PB = QB = . Тоді маємо F(B) =
= F(B) PB QB = . Отже,
F(B) F(B), тому B|F та
P
|F .
Візьмемо A таку:
PA = PA, QA = QA, PA QA = ;
T(A) , F(A) , T(A)F(A) = ;
тоді F(A) = F(A) PA QA = , звідки
отримуємо F(A)T(A) = T(A).
Тепер T(A)F(A) T(A) = F(A)T(A),
звідки A|С , тому
R
|C .
Приклад 6. Маємо
P
|=F (PP) (QQ),
P
|T (PP) (QQ) та
R
|C (PP) (QQ).
Показується аналогічно прикладу 5.
Приклад 7. Маємо
PP
P
|=TF () (PP) та
PP
R
|C () (PP).
Формули PP та
() (PP) позначимо та .
Для кожної інтерпретації J маємо:
T(J) = J PJ, F(J) = J PJ,
T(J) = J PJ, F(J) = J PJ .
Звідси T(J) = F(J), F(J) = T(J).
Тепер для кожної B маємо
T(B) = та F(B) = , тому
B|=T та
B|=F . Звідси
P
|=TF .
Візьмемо A таку:
A , PA , A PA = .
Тоді T(A) F(A) = A PA ,
F(A) T(A) = A PA = . Звідси
A|C , тому
R
|C .
Зведемо результати щодо наявності
відповідного наслідку для випадків, роз-
глянутих в теоремі 15 та прикладах 2–7, в
таблицю. В усіх наведених прикладах ма-
ємо
P
|=IR та не маємо
R
|=TF.
Bведемо такі скороченi позначення.
LC1: , , |= ;
LC2: |= , , ;
LC3: , , |= , , ;
LC4: (QQ) |= ;
LC5: |= (QQ);
LC6: (QQ) |= (QQ);
LC7: (PP) (QQ) |= ;
LC8: |= (PP) (QQ);
LC9: PP |= () (PP);
LC10: (PP) (QQ) |= S S.
Теоретичні та методологічні основи програмування
41
Таблиця. Наявність логічного наслідку
P
|=TF
P
|=T
P
|=F
P
|=TF
R
|=C
LC1 + + – – +
LC2 + – + – +
LC3 + + + + +
LC4 + + – – +
LC5 + – + – +
LC6 – – – – –
LC7 + + – – –
LC8 + – + – –
LC9 + + + + –
LC10 – – – – +
Отже, отримуємо наступну теорему.
Теорема 19. Маємо такі співвідно-
шення між розглянутими відношеннями:
P
|=TF
P
|=T
P
|=TF,
P
|=TF
P
|=F
P
|=TF,
P
|=TF
P
|=IR ;
R
|=TF
P
|=TF,
R
|=TF
R
|=С
P
|=IR ;
P
|=T
P
|=F,
P
|=F
P
|=T,
P
|=TF
R
|=С,
R
|=С
P
|=TF ;
|=t
P
|=IR ;
P
|=TF |=t ,
R
|=C |=t .
Властивості відношень логічного
наслідку для множин формул є семантич-
ною основою побудови секвенційних чис-
лень для відповідних класів логік квазіарних
предикатів. Такі числення збудовано для ві-
дношень
P
|=IR,
P
|=T,
P
|=F,
P
|=TF,
R
|=TF .
Розглянемо особливості побудови
секвенційних числень для
P
|=TF та
R
|=С .
Відмінності відношень логічного
наслідку проявляються вже на пропози-
ційному рівні, тому розглянемо лише про-
позиційні властивості декомпозиції фор-
мул.
Властивості, пов’язані з реноміна-
ціями і кванторами, досліджено в [2–4].
Для відношень
P
|=IR,
P
|=T,
P
|=F,
P
|=TF
та
R
|=TF маємо (див. [2–4]) такі властивості
(тут |= – одне з цих відношень):
L) , |= , |= ;
R) |= , |= , ;
L) , |= , |= та , |= ;
R) |= , |= , , ;
L) (), |= , , |= ;
R) |= , () |= , та
|= , .
Згідно теореми 15, для
P
|=IR та
R
|=С
додатково справджуються:
L) ,
P
|=IR
P
|=IR , ;
R)
P
|=IR , ,
P
|=IR .
Згідно теореми 16, для
P
|=T,
P
|=F,
P
|=TF та
R
|=TF ці властивості неправильні.
Розглянемо властивості, які гаран-
тують наявність логічного наслідку.
Для кожного з наслідків маємо:
С) , |= , .
Додатково гарантують наявність ві-
дповідного логічного наслідку такі власти-
вості (їх виділення зайве для відношень
P
|=IR та
R
|=С в силу властивостей L та R):
СL) , ,
P
|=T ;
СR)
P
|=F , , ;
СLR) , ,
P
|=TF , , ;
СLR) , ,
P
|=TF або
P
|= TF , , .
З’ясуємо, чи правильні властивості
декомпозиції формул для
P
|=TF та
R
|=С.
Для всіх наслідків властивості L,
R, R, L випливають із визначень.
Теорема 20. Для
P
|=TF неправиль-
ними є властивості L та R.
Для кожної J маємо:
, J|=TF
(T(J)T(J))T(J) T(J) або
F(J) (F(J)F(J))F(J)
(T(J)T(J))(T(J)T(J)) T(J) або
F(J) (F(J)F(J))(F(J)F(J))
(T(J)T(J) T(J) та T(J)T(J) T(J))
або (F(J) (F(J)F(J)) та
F(J) F(J)F(J)) (, J|=T та
, J|=T ) або (, |=F та , |=F )
(, J|=TF та , J|=TF ) або
Теоретичні та методологічні основи програмування
42
(, |=TF та , |=TF ) , J|=TF
та , J|=TF .
Отже, ,
P
|=TF
,
P
|=TF та ,
P
|=TF .
Подібним чином показуємо
P
|=TF , ()
P
|=TF , та
P
|=TF , .
Покажемо: з умови ,
P
|=TF та
,
P
|=TF не випливає ,
P
|=TF .
Формули S (PP), S (QQ),
S (QQ) (PP) позначимо , , .
Покажемо:
P
|=F та
P
|=T , тому
P
|=TF та
P
|=TF , проте
P
|TF .
Для кожної J маємо:
T(J) = T(SJ) PJ, F(J) = F(SJ);
T(J) = T(SJ) QJ, F(J) = F(SJ);
T(J) = T(SJ) QJ, F(J) = F(SJ) QJ ;
T(J) = T(J)T(J) = T(SJ) (PJ QJ);
F(J) = F(J) F(J) = F(SJ) QJ .
Звідси F(J) = F(J) та T(J) = T(J),
що дає
P
|=F та
P
|=T .
Візьмемо A таку: PA QA = ,
T(SA) , F(SA) , PA , QA ,
T(SA)QA , F(SA)PA .
Тоді T(A) = T(SA) (PA QA)
T(SA) QA = T(A), тому T(A) T(A);
F(A) = F(SA) F(SA) QJ = T(J), отже
F(A) F(A). Звідси A|T , A|F ,
що дає A|TF , тому й
P
|TF .
Для інтерпретації A також маємо
A|T та A|F , звідки
P
|T та
P
|F .
Подібним чином показуємо:
P
|=F та
P
|=T , водночас
A|TF (), тому
P
|TF ().
Отже, із умови
P
|=TF , та
P
|=TF , не випливає
P
|=TF , ().
Твердження 13. Для
R
|=С неправи-
льними є властивості L та R.
Маємо P(Q&Q)(S&S)
R
|С P
за прикладом 5. Проте P(Q&Q)
R
|=С P.
Справді, для кожної J маємо:
T(P(Q&Q)J)F(PJ) =
= (T(PJ)(F(QJ)T(QJ)))F(PJ) =
= (T(PJ)F(PJ))(F(QJ)T(QJ)F(PJ))
T(PJ)((F(QJ)T(QJ))F(PJ)).
Аналогічно P(S&S)
R
|=С P.
Таким чином, на додаток до того,
що
P
|=TF та
R
|=С нетранзитивні, для них
стають неправильними деякі властивості
декомпозиції формул, що не дає змоги
безпосередньо будувати для них cеквен-
ційні числення. Проте для відношення
R
|=С
таку неприємність можливо обійти зве-
денням
R
|=С до
R
|=TF . Справді, за теоремою
18 маємо:
R
|=С
,
R
|=TF ,
. Це
означає, що немає необхідності будувати
cеквенційне числення для формалізації
R
|=С, адже
R
|=С секвенція |–
, |–, –
|, –|
вивідна в численні для
R
|=TF .
Висновки
В роботі досліджено відношення
логічного наслідку в логіках тотальних од-
нозначних, часткових однозначних, тота-
льних неоднозначних та часткових неод-
нозначних квазіарних предикатів. Поряд із
розглянутими раніше відношеннями типів
T, F, TF, IR і DI, для логік квазіарних пре-
дикатів тут запропоновано відношення ти-
пів TF та С. Описано властивості відно-
шень логічного наслідку для формул та
множин формул. Розглянуто окремі випад-
ки відношень, коли одна із множин фор-
мул порожня. Наведено приклади, які за-
свідчують відмінності одних відношень
від інших. Показано, що відношення
P
|=TF,
та
R
|=С нетранзитивні, для
R
|=С та
P
|=TF не-
правильні деякі властивості декомпозиції
формул, проте
R
|=С моделюється за допо-
могою
R
|=TF. Встановлено співвідношення
між різними відношеннями логічного нас-
лідку.
1. Нікітченко М.С., Шкільняк С.С. Матема-
тична логіка та теорія алгоритмів. – К.:
ВПЦ Київський університет, 2008. – 528 с.
Теоретичні та методологічні основи програмування
43
2. Нікітченко М.С., Шкільняк С.С. Прикладна
логіка. – К.: ВПЦ Київський університет,
2013. – 278 с.
3. Нікітченко М.С., Шкільняк О.С., Шкільняк
С.С. Першопорядкові композиційно-
номінативні логіки із узагальненими рено-
мінаціями // Проблеми програмування. –
2014. – № 2–3 – C. 17–28.
4. Nikitchenko М., Shkilniak S. Semantic Pro-
perties of Logics of Quasiary Predicates //
Workshop on Foundations of Informatics:
Proceedings FOI-2015. – Chisinau, Moldova.
– P. 180–197.
5. Смирнова Е.Д. Логика и философия. – М.:
РОССПЕН, 1996. – 304 с.
References
1. Nikitchenko M. Shkilniak S. (2008). Mathe-
matical logic and theory of algorithms. –
Кyiv: VPC Кyivskyi Universytet (in Ukrai-
nian).
2. Nikitchenko M. and Shkilniak S. (2013).
Applied logic. Кyiv: VPC Кyivskyi Univer-
sytet (in Ukrainian).
3. Nikitchenko M., Shkilniak O. and Shkilniak S.
(2014). First-order composition-nominative
logics with generalized renominations // In
Problems in Progamming. N 2–3, P. 17–28 (in
Ukrainian).
4. Nikitchenko M. and Shkilniak S. (2015).
Semantic Properties of Logics of Quasiary
Predicates // In Workshop on Foundations of
Informatics: Proceedings FOI-2015. –
Chisinau, Moldova, P. 180–197.
5. Smirnova E. (1996). Logic and Philosophy.
Moscow: ROSSPEN (in Russian).
Одержано 12.11.2015
Про автора:
Шкільняк Оксана Степаніна,
кандидат фізико-математичних наук,
доцент, доцент кафедри інформаційних
систем.
Кількість наукових публікацій в
українських виданнях – 76, у тому числі
у фахових виданнях – 28.
Кількість наукових публікацій в
іноземних виданнях – 8.
http://orcid.org/0000-0003-4139-2525.
Місце роботи авторa:
Київський національний університет
імені Тараса Шевченка,
01601, Київ, вул. Володимирська, 60.
Тел.: (044) 2590511 (роб.),
(067) 8879978.
E-mail: me.oksana@gmail.com
|