2.1.4. Форми подання висловлювань
1. Форма А1ÚА2Ú.ÚАn. де Аi, - елементарне висловлювання або заперечення елементарного висловлювання (буквальний), називається елементарною диз'юнкцією.
2. Форма B1 × B2 ×. × Bn. де Bi - літерал, називається елементарної кон'юнкція.
3. Форма D1 × D2 ×. × Dn. де Dj - елементарна диз'юнкція, називається кон'юнктівной нормальною формою (КНФ).
4. Форма K1ÚK2Ú.ÚKn. де Kj - елементарна кон'юнкція, називається диз'юнктивній нормальною формою (ДНФ).
Завжди справжнє (на будь-яких наборах значень назв елементарних висловлювань) складне висловлювання називається тавтологією.
Завжди помилкове (на будь-яких наборах значень назв елементарних висловлювань) висловлювання називається протиріччям.
Досконалої КНФ (СКНФ) називається така КНФ, що кожна входить в неї елементарна диз'юнкція містить всі елементарні висловлювання прямо або з інверсією строго по одному разу. Ні повторюваних диз'юнкцій. Будь-яке складне висловлювання, крім тавтології, має єдину СКНФ.
Досконалої ДНФ (СДНФ) називається така ДНФ, що кожна входить в неї елементарна кон'юнкція містить всі елементарні висловлювання прямо або з інверсією строго по одному разу. Ні повторюваних кон'юнкція. Будь-яке складне висловлювання, крім суперечності, має єдину СДНФ.
2.1.5. перетворення висловлювань
Складне висловлювання, представлене в довільному вигляді за допомогою рівносильних з 11 по 16, а також з використанням законів Де Моргана можуть бути перетворені до нормальної форми.
Перетворення КНФ в СКНФ.
Схематично основну ідею перетворення можна представити так:
Перетворення ДНФ в СДНФ.
Схематично основну ідею перетворення можна представити так:
Перетворення СДНФ в СКНФ.
Розглянемо на прикладі:
Візьмемо логічну функцію f (складне висловлювання) в СДНФ і побудуємо заперечення цієї функції, т. Е. Функцію f, шляхом виписування всіх констітуєнт одиниці, що не входять в f.
Нехай має вигляд
Мнемонічний прийом - приписати конституентов числа, які виходять, якщо подивитися на констітуенти як на двійкові числа.
Заперечення функціонально отримаємо виписуванням відсутніх констітуєнт (відсутніх двійкових чисел).
А тепер застосуємо заперечення до функції.