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

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

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

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

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

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

Крім наведеного означення операцію диз’юнкції можна задати з допомогою іншого означення чи таблиці істинності (див. таблицю № 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	в	аÚв	аÚв	āÙв

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

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

При оперуванні із складенимипредикатами доводиться знаходити їх множини істинності. Знайдемо множину істинності предиката А(х)ÚВ(х). Позначимо область визначення предикатів через Х, множину істинності предиката А(х) через Т_А, а множину істинності предиката В(х) – через Т_В. Щоб знайти множину істинності предиката А(х)ÚВ(х), тобто Т_АÚ_В, на діаграмі Ейлера-Венна зафарбуємо спочатку множину істинності предиката А(х), а потім - множину істинності предиката В(х). Тоді множина істинності предиката А(х)ÚВ(х) буде зображатися тією частиною множини Х, яка зафарбована (див. діаграму № 2.5.).

Таким чином, множина істинності предиката А(х)ÚВ(х) є об’єднанням множин істинності предикатів А(х) і В(х), тобто справедлива рівність Т_АÚ_В=Т_АÈТ_В. Операція диз’юнкції предикатів підкоряється тим же самим законам, що і операція диз’юнкції висловлень. Пропонуємо студентам записати відповідні закони самостійно.

Діаграма № 2.5. Множина істинності диз’юнкції предикатів Т_А_Ú_В=Т_АÈТ_В.

6. Операція імплікації над висловленнями та предикатами. Її таблиця істинності. Основні властивості (закони) операції імплікації.

<== попередня сторінка	\|	наступна сторінка ==>
Операція кон'юнкції предикатів.	\|	Операція імплікації предикатів.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.