 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Досконала диз’юнктивна нормальна форма
Нехай складне висловлювання задане таблицею істинності. Виберемо інтерпретації, у яких значення висловлювання є «істина» (Т). Для кожної такої інтерпретації побудуємо кон’юнкцію атомарних формул або їх заперечень: якщо значення атома – F, то він входить у кон’юнкцію із запереченням, в іншому випадку – без. Побудовану ДНФ називають досконалою диз’юнктивною нормальною формою (ДДНФ).
Приклад 2.13. Нехай формула 
задана таблицею істинності (табл. 2.3). Побудувати ДДНФ.
Таблиця 2.4
Таблиця істинності для
| P | q | r |
|
| T | T | T | F |
| T | T | F | F |
| T | F | T | T |
| T | F | F | F |
| F | T | T | F |
| F | T | F | T |
| F | F | T | T |
| F | F | F | F |
Позначимо всеможливі елментарні кон’юнкції трьох змінних: g1 = 
, g2 = 
, g3 = 
, g4 = 
, g5 = 
, g6 = 
, g7 = 
, g8 = 
та побудуємо таблицю істинності для всіх gi.
Таблиця 2.5
Таблиця істинності для елементарних кон’юнкцій
| p | q | r | g1 | g2 | g3 | g4 | g5 | g6 | g7 | g8 |
| T | T | T | T | F | F | F | F | F | F | F |
| T | T | F | F | F | F | T | F | F | F | F |
| T | F | T | F | F | T | F | F | F | F | F |
| T | F | F | F | F | F | F | F | F | T | F |
| F | T | T | F | T | F | F | F | F | F | F |
| F | T | F | F | F | F | F | F | T | F | F |
| F | F | T | F | F | F | F | T | F | F | F |
| F | F | F | F | F | F | F | F | F | F | T |
Для отримання ДДНФ вибираємо інтерпретації, у яких f 1 рівна TRUE (3, 6, 7 рядок).
Розглянемо першу з вибраних трьох інтерпретацій. Для заданої інтерпретації значення атомарних формул 
. З таблиці 2.5 видно, що елементарною кон’юнкцією, значення якої TRUE при відповідних значеннях атомарних формул, є g3 = – тобто значення атомарних формул 
входять у кон’юнкцію без заперечення, а значення атомарної формули 
входить у кон’юнкцію із запереченням. Аналогічно елементарною кон’юнкцією для другої вибраної інтерпретації буде g6 = , а для третьої – g5 = .
Отже, формула 
є ДДНФ для .▲
Приклад 2.14. Побудувати висловлювання з елементів p, q, r, яке набуває значення T тільки тоді, коли p – істинне, а r і q – фальшиві, або у випадку коли p - фальш, а q, r – істинні.
Таблиця 2.6
Таблиця істинності для f
| p | q | r | f |
| F | F | F | F |
| F | F | T | F |
| F | T | F | F |
| F | T | T | T |
| T | F | F | T |
| T | F | T | F |
| T | T | F | F |
| T | T | T | F |
Використаємо досконалу диз'юнктивну нормальну форму.
Для отримання ДДНФ вибираємо інтерпретації, у яких f 1 рівна TRUE (4,5 рядок).
Розглянемо першу з вибраних двох інтерпретацій. Для заданої інтерпретації значення атомарних формул 
, отже, у відповідну елементрану кон’юнкцію вони входять без заперечень, а атомарна формула 
входить в відповідну елементарну кон’юнкцію із запереченням, тому отримаємо . Аналогічно елементарною кон’юнкцією для другої вибраної інтерпретації буде .
Отже, формула 
є ДДНФ для .▲
!Увага Під час вибору досконалої форми запису логічної функції варто пам’ятати, що ДКНФ є більш доцільною, якщо число наборів, де функція дорівнює TRUE, перевищує число наборів, де функція дорівнює FALSE. У протилежному варто розглядати ДДНФ.
Поиск по сайту: