Операція диз’юнкції над висловленнями

5.1. Розглянемо два висловлення: а=„число 2 просте” і в=„число 2 – парне”. Утворимо з цих двох простих висловлень за допомогою сполучника „або” нове висловлення і з'ясуємо його істинність: „число 2 – просте або парне”. Воно істинне. У математичній логіці таке нове висловлення називають диз'юнкцією (грецьк. disjunction - роз'єднання, розрізнення) даних висловлень і позначають так: аÚb. Символічний запис аÚb читають так: „а або b”, або „а в диз'юнкції з b”, або „диз'юнкція а і b”. Тепер сформулюємо строге математичне означення цієї операції над висловленнями.

Означення: диз'юнкцією двох висловлень а і b називають таке нове висловлення аÚb, яке хибне тоді і тільки тоді коли хибні обидва висловлення.

Крім наведеного означення операцію диз’юнкції можна задати з допомогою іншого означення чи таблиці істинності (див. таблицю № 2.5.).

а	в	аÚв

Таблиця № 2.5. Таблиця істинності для операції диз’юнкції.

Означення: диз'юнкцією двох висловлень а і b називають таке нове висловлення аÚb, яке істинне тоді і тільки тоді, коли істинне хоча б одне із висловлень а і b.

Яку операцію над числами нагадує нам означення диз’юнкції двох висловлень задане таблицею істинності? – певним чином операцію додавання чисел. Саме тому операцію диз'юнкції називають логічним додаванням. Означення операції диз'юнкції двох висловлень можна поширити на три, чотири та на будь-яке скінченне число висловлень. Наприклад: диз’юнкцією висловлень а, b, с називається таке нове висловлення, яке хибне тоді і тільки тоді, коли хибне кожне з висловлень а, b і с, тобто аÚbÚс=(аÚb)Ú с. Враховуючи сказане, зазначимо, що всі твердження, які ми будемо доводити для двох висловлень щодо диз’юнкції, будуть, майже завжди, істинними для будь-якого скінченого числа висловлень.

Безпосередньо із означення диз’юнкції двох висловлень легко переконатися у справедливості таких властивостей (законів): 1) аÚ1=1; 2) аÚ0=а; 3) аÚа=а – закон ідемпотентності. Крім вказаних законів, операція диз’юнкції висловлень підкоряється таким законам:

3. аÚв=вÚа –комутативний (переставний) закон.

4. (аÚв)Úс=аÚ(вÚс) – асоціативний (сполучний) закон.

5. аÙ(вÚс)=(аÙв)Ú(аÙс) – дистрибутивний (розподільний) закон операції кон’юнкції відносно диз’юнкції.

6. аÚ(вÙс)=(аÚв)Ù(аÚс) – дистрибутивний (розподільний) закон операції диз’юнкції відносно кон’юнкції (п’ятий та шостий закони пов’язують операції кон’юнкції та диз’юнкції).

7. аÙв=āÚв.

8. аÚв=āÙв - закони де Моргана, які пов’язують операції заперечення, кон’юнкції та диз’юнкції.

Закони 3-8 потребують доведення. Його проводять, використовуючи таблиці істинності. Покажемо це на прикладі останнього закону де Моргана (див. таблицю № 2.6.). Кількість стовпців таблиці істинності дорівнює 7, а кількість рядків – 2²+1=5 (як це визначили?). Заповнення стовпців виконаємо аналогічно до того, як це робилося при побудові таблиці істинності у попередньому пункті.

А	b	a	в	аÚв	аÚв	āÙв

Таблиця № 2.6. Доведення закону де Моргана.

Дата добавления: 2014-01-05