Реферат на тему:

Формули. Рiвносильнiсть формул. Тотожно iстиннi формули

Наведемо iндуктивне означення поняття формули

логiки предикатiв (предикатної формули
абопросто формули
) на предметнiй областi M
.

1. Усi предикати P
(x
₁
,x
₂
,...,x_n

) на множинi M
є формулами. Такi формули називають елементарними

, або атомарними

.

2. Якщо A
i B
- формули, то (ØA
), (ØB
), (A
ÙB
), (A
ÚB
), (A
®B
), (A
~B
) теж є формулами.

3. Якщо A
- формула, а x
- вiльна змiнна в A
, то ("x
(A
)) i ($x
(A
)) теж формули.

4. Iнших формул, крiм утворених за правилами 1-3, немає.

Це означення дозволяє твердити, що усi формули алгебри висловлень є формулами логiки предикатiв, оскiльки висловлення - це нульмiснi предикати.

За допомогою наведеного означення неважко також переконатись, що вирази ("x
($y
(A
(x
,y
))®(B
(x
)Ú($z
(C
(x
,z
))))) i ("x
("y
(A
(x
,y
)ÙB
(x
))®($y
(C
(x
,y
)))) є формулами логiки предикатiв, а вираз ("x
(A
(y
)®($x
(B
(x
))))) не є формулою, оскiльки у виразi (A
(y
)®($x
(B
(x
)))), який є правильною формулою, змiнна x
є зв'язаною, тобто не є вiльною змiнною i квантор "x
до неї застосувати не можна.

Для зручностi можна запровадити такi умови скорочення кiлькостi дужок у формулах. По-перше, залишимо всi умови скорочення числа дужок, якi було прийнято в алгебрi висловлень, виходячи з прiоритету логiчних операцiй. По-друге, опускатимемо всi зовнiшнi дужки. Вважатимемо, що квантори мають бiльший прiоритет, нiж логiчнi операцiї. Опускатимемо також дужки, що позначають область дiї квантора, якщо остання є елементарною формулою. Нарештi, не писатимемо дужки мiж кванторами, що слiдують один за одним. При цьому виконання таких кванторних операцiй вiдбувається в порядку, зворотньому до їх написання (справа налiво).

Нехай F
(x
₁
,x
₂
,...,x_n

) - деяка формула логiки предикатiв на множинi M
. При логiчнiй (iстинностнiй) iнтерпретацiї формули F
можливi такi три основнi ситуації.

1. Iснує набiр значень змiнних, для якого формула F
перетворюється на iстинне висловлення. У цьому разi формула F
називається виконуваною в областi

M
.

Якщо для F
iснує область M
, в якiй F
є виконуваною, то формула F
називається просто виконуваною

.

2. Якщо формула F
приймає значення 1 (тобто є виконуваною) для всiх наборiв значень з M
, то вона називається тотожно iстинною в

M
. Формула, тотожно iстинна у будь-яких M
, називається тотожно iстинною

або логiчно загальнозначущою

(скорочено - лзз

).

3. Якщо формула F
є невиконуваною в M
, то вона називається тотожно хибною в

M
. Формула, невиконувана в усiх M
, називається тотожно хибною

, або суперечнiстю

.

Приклад 5
.7. Формула $xA
(x
,y
)®"xA
(x
,y
) є виконуваною i вона ж є тотожно iстинною в усiх одноелементних областях M
. Формула F
(x
₁
,x
₂
,...,x_n

)ÚØF
(x
₁
,x
₂
,...,x_n

) тотожно iстинна, а формула F
(x
₁
,x
₂
,...,x_n

)ÙØF
(x
₁
,x
₂
,...,x_n

) тотожно хибна. Тотожно iстинними будуть формули "xP
(x
)®P
(y
) i P
(y
)®$xP
(x
).

Формули F
₁
i F
₂
називаються рiвносильними

(еквiвалентними

), якщо при всiх можливих пiдстановках значень замiсть їх змiнних вони набувають однакових значень; позначається F
₁
= F
₂
.

Наприклад, усi тотожно iстиннi (усi тотожно хибнi) формули рiвносильнi мiж собою. Очевидно також, що коли F
₁
i F
₂
рiвносильнi, то формула F
₁
~F
₂
є тотожно iстинною, і навпаки.

Множина тотожно iстинних формул логiки предикатiв є складовою частиною усiх формальних математичних теорiй, тому її дослiдження i опис є важливою задачею математичної логiки. Значення цiєї множини пiдтверджує той факт, що їй, як було зазначено вище, належать усi рiвносильнi спiввiдношення (тотожностi) логiки предикатiв.

Як i в логiцi висловлень постають двi проблеми. Перша - опис або побудова множини всiх тотожно iстинних формул, друга - перевiрка тотожної iстинностi заданої формули логiки предикатiв.

Якщо iснує процедура розв’язання другої з цих проблем, то на її основi можна сформулювати такий тривiальний алгоритм, що породжує шукану множину T
тотожно iстинних формул. Послiдовно будуємо всi формули, кожну з них за вiдомою процедурою перевiряємо на тотожну iстиннiсть i вносимо до множини T
тi, для яких результат перевiрки є позитивним.

Однак на вiдмiну вiд логiки висловлень, де така процедура iснує i зводиться до обчислення значень даної формули на скiнченнiй множинi значень її параметрiв, у логiцi предикатiв областi визначення предметних i предикатних змiнних формул є, взагалi кажучи, нескiнченними (злiченними або навiть незлiченними).

Метод обчислення значення формули шляхом пiдстановки значень замiсть змiнних i послiдовного виконання вказаних дiй є зручним для встановлення виконуваності заданої формули або доведення нерiвносильностi певних формул. Для цього достатньо пiдiбрати одну вiдповiдну пiдстановку. Застосовувати цей метод можна також, коли предметна область M
є скiнченною. Пов’язано це з тим, що для скiнченної множини M
= {a
₁
,a
₂
,...,a_n

} кванторнi формули можна перетворити у рiвносильнi їм звичайнi формули логiки висловлень:

"xP
(x
) = P
(a
₁
)ÙP
(a
₂
)Ù ... ÙP
(a_n

),

$xP
(x
) = P
(a
₁
)ÚP
(a
₂
)Ú ... ÚP
(a_n

).

Замiнивши усi квантори за допомогою наведених спiввiдношень, будь-яку формулу логiки предикатiв можна перетворити у рiвносильну пропозицiйну форму або формулу логiки висловлень. Iстиннiсть останньої на скiнченнiй множинi M
перевiряється за скiнченну кiлькiсть пiдстановок i обчислень.

Для доведення ж рiвносильностi предикатних формул, що заданi на нескiнченних предметних областях, прямий перебiр виключається i доводиться використовувати рiзнi опосередкованi методи.

Наприклад, вище шляхом простих мiркувань було доведено рiвносильнiсть формул, що описує переставнiсть однойменних кванторiв у двомiсних предикатах, тобто доведено iстиннiсть формул

"x
"yA
(x
,y
)~"y
"xA
(x
,y
) i $x
$yA
(x
,y
)~$y
$xA
(x
,y
).

Аналогiчними мiркуваннями доведемо рiвносильнiсть, що описує дистрибутивнiсть квантора "x
вiдносно кон’юнêцiї:

"x
(A
(x
)ÙB
(x
)) = "xA
(x
)Ù"xB
(x
).

Нехай лiва частина цього співвiдношення є iстинною для деяких предикатiв A
i B
. Тодi для будь-якого a
ÎM
iстинною буде кон’юнкцiя A
(a
)ÙB
(a
), тому A
(a
) i B
(a
) одночасно iстиннi для довiльних a
, отже, формула "xA
(x
)Ù"xB
(x
) є iстинною. Якщо ж лiва частина хибна, то це означає, що для деякого a
ÎM
хибним є або A
(a
), або B
(a
). Тому хибним буде або "xA
(x
), або "xB
(x
), а отже, хибною буде i права частина.

Подiбним методом можна довести дистрибутивнiсть квантора $x
вiдносно диз’юнкцiї:

$x
(A
(x
)ÚB
(x
)) = $xA
(x
)Ú$xB
(x
).

У той же час аналогiчнi простi мiркування дозволяють переконатись, що квантори "x
i $x
є, взагалi кажучи, недистрибутивними вiдносно диз’юнкцiї i кон’юнкцiї вiдповiдно. Насправдi, iстинними є лише такi iмплiкацiї:

"xA
(x
)Ú"xB
(x
)®"x
(A
(x
)ÚB
(x
)),

$x
(A
(x
)ÙB
(x
))®$xA
(x
)Ù$xB
(x
).

Якщо один з предикатiв A
(x
) чи B
(x
) є тотожно iстинним, то лiва i права частини першої iмплiкацiї одночасно будуть iстинними. Якщо ж iснуватимуть такi значення a
,b
ÎM
, що A
(a
) i B
(b
) є хибними, то лiва частина буде хибною, а права - може бути хибною або iстинною. Для її iстинностi достатньо, щоб для кожного a
ÎM
iстинним був принаймнi один з предикатiв. Це означає, що знак iмплiкацiї ® не можна замiнити на знак еквiвалентностi ~, отже, лiва i права частини першої iмплiкацiї не є рiвносильними.

Пропонуємо самостiйно проаналiзувати другу iмплiкацiю i довести її iстиннiсть.

Доведемо ще одне корисне i популярне в логiцi i математицi рiвносильне спiввiдношення: Ø($xP
(x
)) = "x
(ØP
(x
)).

Нехай для деякого предиката P
i предметної областi M
лiва частина iстинна. Тодi не iснує a
ÎM
, для якого P
(a
) iстинно. Отже, для всiх a
ÎM
P
(a
) хибне, тобто ØP
(a
) iстинно. Таким чином, права частина є iстинною. Якщо ж лiва частина хибна, то iснує b
ÎM
, для якого P
(b
) iстинно, тобто ØP
(b
) - хибне. Отже, права частина буде також хибною.

Аналогiчно доводиться рiвносильнiсть

Ø("xP
(x
)) = $x
(ØP
(x
)).

Наведемо без доведень ще декiлька важливих рiвносильних спiввiдношень. Нехай B
предикатна формула, що не мiстить вiльних входжень змiнної x
, тодi справедливi такi рiвносильностi:

"x
(A
(x
)ÚB
) = "xA
(x
)ÚB
, B
®"xA
(x
) = "x
(B
®A
(x
)),

$x
(A
(x
)ÚB
) = $xA
(x
)ÚB
, B
®$xA
(x
) = $x
(B
®A
(x
)),

"x
(A
(x
)ÙB
) = "xA
(x
)ÙB
, "xA
(x
)®B
= $x
(A
(x
)®B
),

$x
(A
(x
)ÙB
) = $xA
(x
)ÙB
, $x
A
(x
)®B
= "x
(A
(x
)®B
).

Цi спiввiдношення означають, що формулу, яка не мiстить вiльних входжень x
, можна виносити за межi областi дiї квантора, що зв’язує x
. З iншого боку цi ж рiвносильностi дозволяють включати або вносити вiдповiдну формулу B
до областi дiї квантора за змiнною x
, вiд якої B
не залежить.

Можливiсть проведення зазначених рiвносильних перетворень для предикатних формул дозволяє означити в логiцi предикатiв поняття певної канонiчної
або нормальної
форми.

Формула, що має вигляд Q
₁
x
₁
Q
₂
x
₂
...Q_n
x_n
F
, де Q
₁
,Q
₂
,...,Q_n

- квантори, а F
формула, яка не мiстить кванторiв i є областю дiї всiх n
кванторiв, називається випередженою

(пренексною

) нормальною формулою

, або формулою у випередженiй формi
.

Формула, яка знаходиться в пренекснiй формi i рiвносильна формулi P
, називається випередженою

(пренексною

) формою

P
.

Використовуючи останнi вісім рiвносильних спiввiдношеннь та деякi iншi, iндукцiєю за числом логiчних операцiй можна довести, що для кожної формули P
логiки предикатiв iснує випереджена нормальна форма P
.