Означення. Імплікацією двох предикатів А(х) і В(х),

Заданих на множині Х, називається такий новий пре)

дикат А(х) ⇒ В(х) (читають: “Якщо А(х), то В(х)”), який

перетворюється в хибне висловлення при тих зна)

Ченнях змінної х з області визначення Х (х є Х), при

яких предикат А(х) перетворюється в істинне вислов)

Лення, а В(х)) в хибне. А(х) називають умовою, а В(х)

) висновком (наслідком) імплікації.

Виразимо область істинності імплікації даних предикатів

А(х)⇒В(х) через їх області істинності. Згідно означення, мно_

жина Х є областю визначення імплікації. Запишемо символ_

ічно області істинності даних предикатів:

ТА(х) = { х/х є Х, А(х) }, ТА(х) ⊂ Х,

ТВ(х) = { х/х є Х, В(х) }, ТВ(х) ⊂ Х.

Зобразимо їх діаграмою Ейлера_Венна і, аналізуючи

означення, виявимо і заштрихуємо на діаграмі область

істинності предиката А(х)⇒В(х).

Для проведення міркувань позна_

чимо утворені чотири області, на які

розбита множина Х, в послідовності

зліва направо так, як показано на діаг_

рамі: І, II, III, IV.

Виберемо довільний елемент а з

області І. При х= а предикати А(х) і В(х)

перетворюються в хибні висловлення, бо а не належить до жод_

ної з областей істинності.

Отже, А(а)=0 і В(а)=0. (Нагадаємо, що 0 означає хибне

висловлення). Утворимо імплікацію цих висловлень:

А(а)⇒В(а). Отримане висловлення істинне, бо 0⇒0 = 1 (див.

таблицю значень логічної вартості імплікації висловлень).

Це означає, що при кожному елементі х= а з області І імпліка_

ція предикатів А(х)⇒В(х) перетворюється в істинне вислов_

лення. А тому елементи цієї області (І), яка є доповненням

до об’єднання областей істинності даних предикатів, нале_

жать до області істинності їх імплікації _ ТА(х)⇒В(х) (заштрихує_

мо область І).

Виберемо тепер довільний елемент b з області ІІ. При

х= b предикат А(х) перетворюється в істинне висловлення,

а предикат В(х) _ в хибне, тобто А(b)=1 і В(b)=0. Імплікація

цих висловлень А(b)⇒В(b) є хибним висловленням, бо

1⇒0 = 0. А отже, при кожному елементові х= b з області ІІ

імплікація предикатів А(х)⇒В(х) перетворюється в хибне

висловлення. Тому елементи цієї області не належать до

області істинності імплікації предикатів _ ТА(х)⇒В(х). (Не заш_

триховуємо її).

Виберемо далі довільний елемент с з області ІІІ. При х= с обид_

ва предикати А(х) і В(х) перетворюються в істинні висловлення,

тобто А(с)=1 і В(с)=1. Імплікація цих висловлень А(с)⇒В(с) _ істин_

не висловлення, бо 1⇒1 = 1. А це означає, що при будь_якому

I X

II d

III IV

TA(x) c

B TB(x)

a

значенні х= с з області ІІІ імплікація предикатів А(х)⇒В(х) пере_

творюється в істинне висловлення. Тому елементи області ІІІ на_

лежать до області істинності імплікації предикатів ТА(х)⇒В(х). (За_

штрихуємо область ІІІ).

Нарешті виберемо довільний елемент d з області ІV. При

х= d предикат А(х) перетворюється в хибне висловлення, а пре_

дикат В(х) _ в істинне, тобто А(d)=0 і В(d)=1. Імплікація цих

висловлень А(d)⇒В(d) є висловленням істинним, бо 0⇒1 = 1.

Це означає, що при кожному елементі х= d з області ІV імпліка_

ція предикатів А(х)⇒В(х) перетворюється в істинне висловлен_

ня. Тому всі елементи області ІV належать до області істинності

імплікації предикатів _ ТА(х)⇒В(х). (Заштрихуємо цю область).

Отже, як очевидно з діаграми, областю істинності імплікації

предикатів є вся область визначення Х без області ІІ (на діаграмі).

Як виразити цю область ТА(х)⇒В(х) за допомогою формули?

Скористаємось для цього виведеними вище формулами обла_

стей істинності складених предикатів. Крім цього, відзначимо,

що імплікація предикатів зв’язана з операціями диз’юнкції і за_

перечення так само, як і імплікація висловлень:

A ⇒ B = A ∨ B (для висловлень);

А(х)⇒В(х) = А (х) ∨В(х) (для предикатів).

Виведемо формулу для області істинності імплікації преди_

катів:

Т А(х)⇒В(х) = {x/x є X, А(х)⇒В(х)} =

застосуємо вище наведену формулу

= {x/x є Х, А (х) ∨ В(х)} =

застосуємо формулу для знаходження області істинності

диз’юнкції предикатів

= {x/x є Х, А (х)} ∪ {x/x є Х, В(х)}=

застосуємо формулу для знаходження області істинності

заперечення предиката

= { x x є X, A (x)}∪ {x/x є Х, В(х)}= Т А (х) ∪ ТВ(х).

Отже, остаточно отримали формулу

Т А(х)⇒__________В(х) = Т А (х) ∪ ТВ(х),

яку читають так:

Область істинності імплікації предикатів дорівнює

Об’єднанню доповнення до області істинності пре)

диката)умови з областю істинності предиката)вис)

Новку.

Приклад. На множині Х= {x/x є N, x ≤ 15} задано два предика_

ти

А(х): “число х кратне 3”

В(х): “число х _ парне”.

Утворити імплікацію предикатів А(х)⇒В(х) і визначити її об_

ласть істинності.

Розв ’ язування. Задамо переліком область визначення Х да_

них предикатів і утвореного в результаті операції імплікації но_

вого складеного предиката А(х)⇒В(х): “Якщо число х кратне 3,

то воно парне”.

Х= {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}.

Запишемо області істинності даних предикатів:

TA(x) = { x/x є X, A(x)} = {3,6,9,12,15};

TB(x) = { x/x є X, B(x)} = {2,4,6,8,10,12,14}.

За формулою знаходження області істинності імплікації пре_

дикатів маємо:

Т А(х)⇒В(х) = Т А (х) И ТВ(х).

Визначимо спочатку Т А (х):

Т А (х) =Х \ ТА(х).

Т А (х) ={x/x ∈ Х ∧ х ∉TА(х)}=

={1,2,4,5,7,8,10,11,13,14}.

Підставимо значення у формулу, дістанемо:

ТА(х)⇒В(х)={1,2,4,5,7,8,10,11,13,14}∪{2,4,6,8,10,12,14}=

={1,2,4,5,6,7,8,10,11,12,13,14}.

Примітка: На самому початку ми вказували, що формальна і

математична логіка розглядає структуру тверджень незалежно

від змісту. Попередній приклад, власне, передбачає розгляд

імплікативної структури незалежно від логічного зв’язку між

змістом окремих предикатів.

Звичайно в математиці найчастіше розглядаються тверд_

ження, які логічно пов’язані між собою змістом і мають імпліка_

тивну структуру. Відношення між такими предикатами назива_

ють відношенням логічного слідування. (Ми розглянемо їх у

наступній темі).

д) Еквіваленція двох предикатів.

Означення. Еквіваленцією двох предикатів А(х) і В(х),

Заданих на множині Х, називається такий новий пре)

дикат А(х) ⇔ В(х) (читають: “А(х) тоді і тільки тоді, коли

В(х)” або “А(х) еквівалентне (рівносильне) В(х)”), який

перетворюється в істинне висловлення при тих зна)

Ченнях змінної х з області визначення Х, при яких

Обидва предикати одночасно перетворюються у вис)

Ловлення однакової вартості (або обидва істинні, або

Обидва хибні).

Запишемо символічно області істинності даних предикатів,

зобразимо їх діаграмою Ейлера_Венна і виведемо формулу

області істинності предиката_еквіваленції.

ТА(х) = { х/х є Х, А(х) }, ТА(х) ⊂ Х,

ТВ(х) = { х/х є Х, В(х) }, ТВ(х) ⊂ Х.

Спираючись на діаграму, обгрунтує_

мо, що являє собою область істинності

еквіваленції предикатів. Обидва преди_

кати А(х) і В(х) перетворюються одночасно в істинні висловлен_

ня на множині, яка є перерізом областей істинності даних пре_

дикатів (область I на діаграмі).

Справді для довільного елемента а з області I

А(а) = 1 і В(а) =1, а тому А(а)⇔В(а) _ істинне висловлення, бо

1⇔1=1.

А це означає, що складений предикат А(х)⇔В(х) перетво_

рюється в істинне висловлення при всіх значеннях х= а з області

I, яка дорівнює ТА(Х) ∩ТВ(Х). Ця множина включається в область

істинності еквіваленції предикатів, тобто

(ТА(х) ∩ТВ(х)) ⊂ ТА(х)⇔В(х). (Заштрихуємо на діаграмі).

На області II, яка є доповненням до об’єднання областей

істинності предикатів, обидва предикати перетворюються

одночасно в хибні висловлення. Справді, для довільного

елемента b з області II маємо: А(b)=0 і В(b)=0. Еквіваленція цих

X

ІII d

I IV

TA(x) а

С TB(x) ІІ

b

висловлень А(b)⇔В(b) є істинним висловленням, бо 0⇔0=1 (

див. таблицю значень логічної вартості еквіваленції). А це

означає, що складений предикат А(х)⇔В(х), який є еквіваленцією

даних предикатів, перетворюється в істинне висловлення на

області II, яка дорівнює за правилом де Моргана доповненню до

об’єднання областей істинності даних предикатів:

ТA (x) ∪ ТВ (x) = Т А (x) ∩ Т В (x).

(Заштрихуємо на діаграмі).

На області III предикат А(х) перетворюється в істинне

висловлення, а предикат В(х) в хибне. Справді для довільного

елемента с з цієї області маємо: А(с)=1, а В(с)=0. Еквіваленція

цих висловлень є висловленням А(с)⇔В(с) _ хибним, бо 1⇔0 =

0. А це означає, що при всіх значеннях х з області III предикат

А(х) ⇔В(х) перетворюється в хибне висловлення. Тому область

III не належить до області істинності еквіваленції предикатів _

ТА(х)⇔В(х) (її не заштриховуємо).

Аналогічно на області IV предикат А(х) перетворюється в

хибне висловлення, а предикат В(х) _ в істинне, бо для довільного

елемента d з цієї області маємо: А(d)=0, B(d)=1. Еквіваленція

цих висловлень є хибним висловленням: А(d)⇔В(d)=0, бо 0⇔1

= 0. Це означає, що для довільного значення х= d з області IV

предикат А(х)⇔В(х) перетворюється в хибне висловлення. Тому

область IV до області істинності еквіваленції не включається (її

не заштриховуємо).

Таким чином, область істинності еквіваленції двох предикатів

А(х) і В(х) являє собою об’єднання двох областей з множини Х:

Т А(х) ⇔В(х) = (Т А(Х) ∩ Т В(Х)) ∪ (Т А (x) ∩ Т В (x))

До цієї формули можна прийти, застосовуючи виведені вище

формули знаходження областей істинності складених преди_

катів.

Зауважимо, що в алгебрі предикатів має місце формула, яка

зв’язує операції еквіваленції і імплікації так само, як в алгебрі

висловлень:

А⇔В = (А ⇒ В) ∧ (В ⇒А) (в алгебрі висловлень),

А(х)⇔В(х)=(А(х)⇒В(х))∧(В(х)⇒А(х)) (в алгебрі

предикатів).

Застосуємо цю формулу до знаходження області істинності

еквіваленції предикатів:

Т А(х)⇔В(х)={х/х є Х, А(х) ⇔ В(х)}=

={х/х є Х, (А(х) ⇒ В(х)) ∧ (В(х) ⇒ А(х))}=

застосуємо формулу для знаходження області істинності кон’_

юнкції предикатів

= {х/х є Х, А(х) ⇒ В(х) }∩{х/х є Х, В(х) ⇒ А(х) }=

застосуємо формулу для знаходження області істинності

імплікації предикатів

=(Т А (x) ∪ Т В(х)) ∩ (Т В (x) ∪ Т А(х))=

виконаємо дії над множинами, використавши дистрибутивний

закон перерізу відносно об’єднання

=(Т А (x) ∩ Т В (x)) ∪ (Т А (x) ∩ Т А(х)) ∪ (Т В(х) ∩ Т В (x)) ∪

∪ (Т В(х) ∩ Т А(х))

З теорії множин відомо, що переріз множини з її доповнен_

ням дорівнює порожній множині. Тому

Т А(х) ⇔В(х) = (Т А (x) ∩ Т В (x)) ∪ ∅ ∪ ∅ ∪ (Т В(х) ∩ Т А(х)).

Застосуємо переставну властивість перерізу і об’єднання і

остаточно отримаємо:

Т А(х)⇔В(х) = (Т А(х) ∩ Т В(х)) ∪ (Т А (x) ∩ Т В (x)).

Цю формулу читають так: