 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Досконала кон’юнктивна нормальна форма
Нехай складне висловлювання задане таблицею істинності. Виберемо інтерпретації, у яких значення висловлювання є «хиба» (F). Для кожної такої інтерпретації побудуємо диз’юнкцію атомарних формул або їх заперечень: якщо значення атома – F, то він входить у кон’юнкцію без заперечення, в іншому випадку – з. Побудовану КНФ називають досконалою кон’юнктивною нормальною формою (ДКНФ).
Приклад 2.7. Нехай формула 
задана таблицею істинності (таблиця 2.1). Побудувати ДКНФ.
Таблиця 2.1
Таблиця істинності для
| p | q | r |
|
| T | T | T | F |
| T | T | F | T |
| T | F | T | T |
| T | F | F | T |
| 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.2
Таблиця істинності для елементарних диз’юнкцій
| p | q | R | g1 | g2 | g3 | g4 | g5 | g6 | g7 | g8 |
| T | T | T | T | T | T | T | T | T | T | F |
| T | T | F | T | T | T | T | F | T | T | T |
| T | F | T | T | T | T | T | T | F | T | T |
| T | F | F | T | F | T | T | T | T | T | T |
| F | T | T | T | T | T | T | T | T | F | T |
| F | T | F | T | T | F | T | T | T | T | T |
| F | F | T | T | T | T | F | T | T | T | T |
| F | F | F | F | T | T | T | T | T | T | T |
Для отримання ДКНФ вибираємо інтерпретації, у яких f 1 рівна FALSE (1, 5, 8 рядок).
Розглянемо першу з вибраних трьох інтерпретацій. Для заданої інтерпретації значення атомарних формул 
. З таблиці 2.2 видно, що елементарною диз’юнкцією, значення якої FALSE при відповідних значеннях атомарних формул, є g8 = – тобто значення атомарних формул входять у диз’юнкцію із запереченням. Аналогічно елементарною диз’юнкцією для другої вибраної інтерпретації буде g7 = , а для третьої – g1 = .
Отже, формула 
є ДКНФ для .▲
Приклад 2.8. Побудувати висловлювання з елементів p, q, r, яке набуває значення F тільки у трьох випадках, коли r – істинне, а p і q – фальшиві, коли r і p – істинне, а q – фальшиве, p, r і q – фальшиві.
Таблиця 2.3
Таблиця істинності для f
| p | q | r | F |
| F | F | F | F |
| F | F | T | F |
| F | T | F | T |
| F | T | T | T |
| T | F | F | T |
| T | F | T | F |
| T | T | F | T |
| T | T | T | T |
Використаємо досконалу кон'юнктивну нормальну форму.
Для отримання ДКНФ вибираємо інтерпретації, у яких f 1 рівна FALSE (1, 2, 6 рядок).
Розглянемо першу з вибраних трьох інтерпретацій. Для заданої інтерпретації значення атомарних формул 
, отже, у відповідну елементрану диз’юнкцію вони входять без заперечень, отже, отримаємо . Аналогічно елементарною диз’юнкцією для другої вибраної інтерпретації буде , а для третьої – .
Отже, наша формула f = 
. ▲
Поиск по сайту: