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

7.2. Для того, щоб визначити операцію еквіваленції предикатів, розглянемо на множині абітурієнтів два предикати: А(х): „х – склав всі екзамени” і В(х): „х – набрав прохідний бал”. Як можна назвати предикат „для того, щоб х – склав всі екзамени, необхідно і достатньо, щоб він набрав прохідний бал” – еквіваленцією заданих предикатів. Отже, приймемо таке означення.

а	в	a↔b
0	0	1
1	0	0
0	1	0
1	1	1

Таблиця № 2.10. Таблиця істинності еквіваленції висловлень.

Означення: еквіваленцією двох предикатів А(х) і В(х), заданих на одній і тій самій множині Х, називається такий новий предикат А(х)↔В(х), який визначений на тій самій множині Х і який істинний при всіх тих хХ, при яких значення істинності предикатів А(х) і В(х) співпадають.

Оскільки при оперуванні із складеними предикатами доводиться знаходити їх множини істинності, то знайдемо множину істинності предиката А(х)↔В(х). Позначимо область визначення предикатів через Х, множину істинності предиката А(х) через Т_А, а множину істинності предиката В(х) – через Т_В. Щоб знайти множину істинності предиката А(х)↔В(х), тобто Т_А↔_В, можна використати міркування або діаграми Ейлера-Венна. Зазначимо, що міркуваннями множину істинності Т_А↔_В можна знайти, використавши рівність А(х)↔В(х)=((Ā(х)В(х))(В(х)А(х))). Отже, маємо: Т_А↔_В=(Т_АТ_В)(Т_ВТ_А). Оскільки відомо, що предикат А(х)↔В(х) буде істинним для тих значень хєХ, для яких предикати А(х) і В(х) одночасно істинні або хибні, тобто на множинах Т_АТ_В і Т_АТ_в. Отже, множиною істинності предиката А(х)↔В(х) – є об'єднання цих множин, тобто Т_А↔_В=(Т_АТ_В)(Т_АТ_в) (див. діаграму № 2.7.).

Діаграма № 2.7. Множина істинності еквіваленції предикатів.

8. Логічні формули. Порядок виконання логічних операцій у формулах. Рівносильні формули. Тотожньо істинні формули (логічні закони). Відношення логічного слідування та рівносильності на множині предикатів.

8. Із шкільного курсу математики відомо, що вирази отримують за допомогою цифр, букв, знаків арифметичних дій та дужок. Аналогічно можна отримувати вирази або формули у математичній логіці. Для того, щоб однозначно розуміти відповідні формули та в однаковому порядку виконувати дії над висловленнями та предикатами, виробили наступні правила виконання операцій: заперечення, кон’юнкція, диз’юнкція, імплікація та еквіваленція:

1) порядок виконання логічних операцій регулюють дужками, починаючи виконання з операції, яка стоїть у самих внутрішніх дужках;

2) вираз, якій міститься під знаком операції заперечення, в дужки не береться, але його вважають таким, що знаходиться в дужках, а тому обчислюють окремо;

3) якщо у формулі немає дужок, то порядок виконання логічних операцій такий: а) заперечення; б) кон’юнкція; в) диз’юнкція; г) імплікація; д) еквіваленція. Застосування вказаних правил проілюструємо на наступній вправі.

В права: спростити вираз (abcd)(abcd)(abc)(ab)ā=(abc)(dd)(abc)(ab)ā=(abc)1(abc)(ab)ā=(abc)(abc)(ab)ā=(ab)(сс)(ab)ā=(ab)1(ab)ā=(ab)(ab)ā=a(b b)ā=a1ā=aā=0.

Побудуємо таблицю істинності для двох формул: a↔b і a→b.

а	b	a↔b	a→b
0	0	1	1
0	1	0	1
1	0	0	0
1	1	1	1

Таблиця № 2.11.

Аналіз таблиці № 2.11. дозволяє зробити висновок про те, що формула a→b набуває значення 1 при тих значеннях логічних змінних, при яких формула a↔b також набуває значення 1. В цьому випадку говорять, що формула a→b логічно випливає з формули a↔b. Символічно це позначають так a↔b╞a→b, а читають цей запис наступним чином: формула a→b логічно випливає з формули a↔b.

Означення: формула b називається логічним наслідком формули а (або формула b логічно випливає з формули а), якщо формула b набуває значення 1 при всіх тих наборах значень логічних змінних, при яких формула а також набуває значення 1.

Нехай на множині Х задано предикати А(х) і В(х) такі, що їх множини істинності Т_А і Т_В знаходяться у відношенні Т_АТ_В. З’ясуємо, якою буде імплікація А(х)→В(х) при певних значеннях хєХ. Виберемо довільне аєХ. При цьому можливі два випадки: 1) аєТ_А. Тоді аєТ_В, а тому А(а)=1 і В(а)=1, тобто А(а)→В(а)=1→1=1; 2) аєТ_А. Тоді А(а)=0, а імплікація А(а)→В(а)=0→В(а)=1. В таких випадках також говорять, предикат В(х) логічно випливає або логічно слідує із предиката А(х). Символічно це позначають так: А(х)╞ В(х).

Означення: якщо предикати А(х) і В(х) задані на одній множині Х, то кажуть, що предикат А(х) логічно випливає із предиката В(х), тоді і тільки тоді, коли Т_АТ_В.

Означення: якщо імплікація А(х)→В(х)=1 при всіх хєХ, то говорять, що предикат В(х) логічно слідує з предиката А(х).

Про такі предикати говорять, що вони знаходяться у відношення логічного слідування. Як же визначити чи знаходяться предикати у відношенні логічного слідкування? – слід дотримуватися такого алгоритму: 1) з’ясувати, чи на одній множині задані обидва предикати; 2) знайти множини істинності кожного з предикатів; 3) виявити співвідношення між множинами істинності предикатів; 4) якщо одна з множин істинності є підмножиною іншої, то зробити висновок про відношення логічного слідування між предикатами. Проілюструємо сказане на наступному прикладі.

Вправа: з’ясувати, чи знаходяться предикати А(х): «натуральне число х ділиться на 4» і В(х): «натуральне число х- парне» у відношенні логічного слідування.