Рерізу областей істинності цих предикатів.

Цю формулу ми записали обгрунтовуючи діаграму Ейлера_

Венна, спираючись на означення кон’юнкції предикатів.

Наведемо її строге доведення, тобто покажемо, що множи_

ни, які стоять в лівій та правій частинах рівності, справді рівні.

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

множини перебувають у відношенні рівності тоді і тільки тоді,

коли кожна із них є підмножиною іншої.

(А=В ⇔ А⊂В ∧ В⊂А, де А,В _ множини).

Отже, для доведення формули потрібно показати, що

1) Т А(х) ∧ В(х) ⊂ (ТА(х) ∩ ТВ(х)), а, в свою чергу,

2) (ТА(х) ∩ ТВ(х)) ⊂ Т А(х)∧В(х).

Доведення: 1. Виберемо довільний елемент а множини Х, який

належить до області істинності кон’юнкції предикатів А(х) ∧ В(х).

а є Х, а є Т А(х)∧В(х).

З цього випливає, що предикат А(х) ∧ В(х) перетворюється в

істинне висловлення при х= а, тобто висловлення А(а) ∧ В(а) _

істинне. А згідно означення кон’юнкції висловлень, вона істинна

лише тоді, коли обидва висловлення істинні. Отже, А(а) і В(а) _

істинні висловлення. Це означає, що елемент а належить і до

області істинності предиката А(х), і до області істинності пре_

диката В(х), тобто а є ТА(х) і а є ТВ(х).

З теорії множин (з означення перерізу) відомо, що якщо еле_

мент належить до двох множин одночасно, то він належить і до

їх перерізу.

Тому а є (ТА(х) ∩ ТВ(х)).

X

TA(x)

TB(x)

Отже, а є ТА(х) ∧ а є ТВ(х) ⇒ а є (ТА(х) ∩ ТВ(х)).

Оскільки елемент а вибрано довільно з області істинності

кон’юнкції предикатів _ ТА(х) ∧ В(х), то такі міркування можна про_

вести відносно кожного елемента множини ТА(х) ∧ В(х), що при_

водить до висновку: всі елементи множини ТА(х)∧В(х) належать

до множини ТА(х) ∩ ТВ(х). За означенням відношення включення

між множинами випливає, що ТА(х) ∧ В(х) ⊂ (ТА(х) ∩ ТВ(х)). Першу

частину доведення завершено.

2. Виберемо тепер довільний елемент b з множини Х, який

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

них предикатів.

b є Х, b є (ТА(х) ∩ ТВ(х)).

За означенням перерізу множин це означає, що елемент b

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

дикатів:

b є ТА(х) і b є ТВ(х), тобто

b є (ТА(х) ∩ ТВ(х)) ⇒ (b є ТА(х) ∧ b є ТВ(х)).

За означенням області істинності предиката останні

співвідношення означають, що при значенні х= b обидва преди_

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

(b є ТА(х) ⇒ А(b) _ істинне висловлення;

b є ТВ(х) ⇒ В(b) _ істинне висловлення).

Оскільки при х= b обидва предикати перетворюються одно_

часно в істинне висловлення, то за означенням кон’юнкції двох

висловлень висловлення А(b) ∧ В(b) також істинне. А це озна_

чає, що при х= b кон’юнкція предикатів А(х) ∧ В(х) перетворюєть_

ся в істинне висловлення, а отже, елемент b належить до області

істинності кон’юнкції предикатів:

b є Т А(х) ∧ В(х).

Оскільки міркування проводились відносно довільно вибра_

ного елемента b з множини ТА(х) ∩ ТВ(х), то такі міркування можна

провести відносно кожного елемента цієї множини. На основі

цього можна стверджувати, що всі елементи множини ТА(х) ∩ТВ(х)

є одночасно елементами множини ТА(х)∧В(х).

За означенням відношення включення між множинами вип_

ливає, що (ТА(х) ∩ ТВ(х)) ⊂ ТА(х) ∧ В(х).

Довели другу частину формули. Скористаємось означенням

рівності множин, на основі чого остаточно отримаємо:

(ТА(х)∧В(х) ⊂ (ТА(х) ∩ ТВ(х))) ∧ ((ТА(х) ∩ ТВ(х)) ⊂ ТА(х)∧В(х)) ⇒

⇒ТА(х)∧В(х) = ТА(х) ∩ ТВ(х).

Отже, формула, що виражає область істинності кон’юнкції

двох предикатів, доведена.

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

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

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

Утворіть кон’юнкцію даних предикатів і визначте область

істинності її.

Розв ’ язування. Областю визначення предиката_кон’юнкції є

також множина Х, яку задамо переліком елементів.

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

Сформулюємо кон’юнкцію даних предикатів:

А(х)∧В(х): “число х _ кратне 3 і парне”.

Щоб визначити область істинності кон’юнкції предикатів, по_

трібно визначити спочатку область істинності кожного з преди_

катів.

ТА(х)={x/x є Х ∧ А(х)}={3,6,9,12,15}.

ТВ(х)={x/x є Х ∧ В(х)}={2,4,6,8,10,12,14}.

За формулою ТА(х)∧В(х) = ТА(х) ∩ ТВ(х) дістаємо:

Т А(х)∧В(х) = {3,6,9,12,15} З {2,4,6,8,10,12,14}= {6,12}.

Отже, ТА(х)∧В(х) = {6,12}. Областю істинності кон’юнкції даних

предикатів на множині Х є множина парних чисел, кратних трьом.

в) Диз’юнкція двох предикатів.

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

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

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

Ловлення лише при тих значеннях змінної х з області

Визначення Х, при яких хоча б один з предикатів пе)

Ретворюється в істинне висловлення.

Виразимо область істинності складеного предиката, який є

диз’юнкцією даних предикатів, через області істинності даних

предикатів. За означенням, дані предикати і предикат, утворе_

ний в результаті диз’юнкції, мають одну й ту саму облаcть виз_

начення Х.

Запишемо символічно їх області істинності:

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

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

Зобразимо діаграмою Ейлера_Венна область визначення Х

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

За означенням диз’юнкції предикат

А(х)∨В(х) перетворюється в істинне вислов_

лення лише при тих значеннях змінної х, при

яких хоча б один з предикатів перетворюєть_

ся в істинне висловлення. Це означає, що до

області істинності предиката_диз’юнкції належатимуть ті елемен_

ти х з області визначення Х, які належать хоча б до однієї з обла_

стей істинності даних предикатів _ ТА(х) або ТВ(х), а отже, до їх

об’єднання. Як очевидно з діаграми Ейлера_Венна, область

істинності диз’юнкції предикатів можна виразити так:

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

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

(Область, заштрихована на діаграмі).

Отже, ТА(х)∨В(х) = ТА(х) ∪ ТВ(х).

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

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

Дорівнює об’єднанню областей істинності даних

Предикатів.

Наведемо строге доведення цієї формули, яке аналогічне до

доведення формули для кон’юнкції предикатів.

Для доведення рівності, достатньо показати, що кожна з

множин є підмножиною іншої, тобто:

1) ТА(х)∨В(х) ⊂ (ТА(х)∪ТВ(х))

2) (ТА(х) ∪ ТВ(х)) ⊂ ТА(х)∨В(х).

Доведення:1) Виберемо довільний елемент а з множини Х,

який належить до області істинності диз’юнкції предикатів.

а є Х, а є ТА(х)∨В(х).

З цього випливає, що при х= а предикат А(х)∨В(х) перетво_

рюється в істинне висловлення, тобто А(а)∨ В(а) _ істинне вис_

ловлення. Оскільки диз’юнкція висловлень, згідно означення,

істинна тоді, коли хоча б одне з висловлень істинне, тобто або

А(а) істин не, або В(а). Якщо істинне А(а), то це означає, що

X

TA(x) TB(x)

елемент а належить до області істинності предиката А(х), тобто

а є ТА(х), і згідно означення об’єднання множин а є (ТА(х) ∪ ТВ(х)).

Якщо істинне висловлення В(а), то, міркуючи аналогічно, при_

ходимо до висновку, що елемент а належить до області істин_

ності предиката В(х), тобто а є ТВ(х), і згідно означення об_

’єднання множин а є (ТА(х)∪ТВ(х)). Оскільки елемент а вибирали

довільно з множини ТА(х)∨В(х) _ області істинності предиката_диз_

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

ного елемента цієї множини, на основі чого можна стверджува_

ти, що всі елементи множини ТА(х)∨В(х) _ області істинності пре_

диката_диз’юнкції належать і до множини ТА(х) ∪ ТВ(х), тобто до

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

ченням відношення включення множин з цього випливає, що

ТА(х)∨В(х) ⊂ (ТА(х)∪ТВ(х)).

Першу частину доведення завершено.

2. Виберемо довільний елемент b з множини Х, який нале_

жить до множини ТА(х)∪ТВ(х), що є об’єднанням областей істин_

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

b є Х, b є (ТА(х)∪ТВ(х)).

За означенням об’єднання це означає, що елемент b нале_

жить хоча б до однієї з множин, тобто b є ТА(х) або

b є ТВ(х). Якщо b є ТА(х), то за означенням області істинності

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

висловлення, тобто А(b) _ істинне висловлення. Якщо ж b є ТВ(х)

, то аналогічно міркуючи, дістанемо, що висловлення В(b) _ істин_

не. Оскільки хоча б одне з висловлень А(b) або В(b) _ істинне, то

за означенням диз’юнкції висловлень буде істинним і вислов_

лення А(b)∨ В(b). Останнє означає, що при х= b предикат

А(х) ∨ В(х) перетворюється в істинне висловлення, а отже, еле_

мент b належить до області істинності предиката_диз’юнкції (b

є ТА(х)∨В(х)). Оскільки елемент b вибирали довільно з множини

ТА(х)∪ТВ(х), то аналогічні міркування можна провести відносно

будь_якого (кожного) елемента цієї множини і на основі цього

стверджувати, що всі елементи множини ТА(х)∪ТВ(х) належать і

до множини ТА(х)∨ В(х). За означенням відношення включення мно_

жин виходить, що

(ТА(х)∪ТВ(х)) ⊂ ТА(х)∨В(х).

Другу частину доведення завершено. Тепер на основі озна_

чення рівності множин остаточно маємо:

(ТА(х)∨В(х) ⊂ (ТА(х)∪ТВ(х)))∧((ТА(х)∪ТВ(х))⊂ ТА(х)∨В(х).) ⇒

⇒ТА(х)∨В(х). = (ТА(х)∪ТВ(х)).

Отже, формула, що виражає область істинності диз’юнкції

двох предикатів, доведена.

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

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

Утворіть диз’юнкцію даних предикатів і визначте область

істинності її.

Розв’язування. Множина Х є областю визначення даних пре_

дикатів і складеного предиката, утвореного в результаті диз’_

юнкції. Задамо множину Х переліком елементів:

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

Утворимо диз’юнкцію даних предикатів:

А(х) ∨ В(х): “число х кратне 3 або парне”.

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

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}.

Визначимо область істинності складеного предиката_диз’_

юнкції, скориставшись формулою:

TA(x)∨B(x) = TA(x) ∪ TB(x).

Отже, в даному випадку маємо:

TA(x) ∨B(x) ={3,6,9,12,15}∪{2,4,6,8,10,12,14}=

={2,3,4,6,8,9,10,12,14,15}.

Отримали множину, де кожен елемент її є або числом, крат_

ним 3, або парним числом.

г) Імплікація двох предикатів.