ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


У ній відсутні кон'юнкти до складу яких входить змінна і її заперечення.

Щоб привести формулу до СКНФ необхідно виконати такі дії:

1) отримати із вихідної формули КНФ;

2) співставити отриману КНФ із ознаками СКНФ;

До отриманого виразу послідовно застосовувати «закони виявлення» і «закони поглинання».

Завдяки СКНФ розв'язують задачузнаходження всіх простих наслідків із кон'юнкції заданих формул.

Наприклад, знайдемо всі прості наслідки із таких формул:

А É`В, А Ú С, B Ù C

Для цього, спочатку поєднаємо наведені формули за допомогою кон’юнкції і отримаємо вираз:

(A É`B) Ù (A Ú C) Ù (B Ù C)

Отриманий вираз приведемо до КНФ:

(`A Ú`B) Ù (A Ú C) Ù (`B Ú`C)

Отриману КНФ співставляємо із ознаками СКНФ.

Потім до отриманої КНФ послідовно застосуємо спочатку «закон виявлення»

(А Ú В) Ù (`А Ú С) º (А Ú В) Ù (`А Ú С) Ù (В Ú С):

(`A Ú`B) Ù (A Ú C) Ù (`B Ú`C) Ù (`В Ú С) Ù (А Ú`В)

А потім «закон поглинання»(А Ú В) Ù (`А Ú В) º В:

(`A Ú`B) Ù (A Ú C) Ù (`B Ú`C) Ù (`В Ú С) Ù (А Ú`В)

1 2 3 4 5

У результаті застосування «закону поглинання» ми скоротили 1 і 5 підформули і отримали `В, 3 і 4 підформули і також отримали `В. Підформула (А Ú С) залишилася непоглинутою.

Отже, врешті решт, ми отримали таку СКНФ(А Ú С) Ù`В, де кожен із кон’юнктів є простим наслідком:

1. (А Ú С) ;

2. `В;

3. (А Ú С) Ù`В.

Диз'юнктивною нормальною формою (ДНФ) даної формули називається диз'юнкція елементарних кон'юнкцій: (A Ù B) Ú (`B Ù C) Ú A тощо.

Щоб привести формулу доДНФнеобхідно виконати такі дії:

1) за допомогою відповідних законів послідовно звільнитися від сильної диз’юнкції “Ú” , еквіваленції “«”, імплікації “É” , якщо вони є у вихідній формулі ;

2) за допомогою законів де Моргана позбавитися загального заперечення;

До отриманої формули застосувати «закон дистрибутивності кон'юнкції по відношенню до диз'юнкції».

ДНФ дозволяє встановити чи є довільна формула тотожно-хибною чи ні.

Наприклад, приведемо до ДНФ таку формулу:

[ (A É B) Ù (C É D) Ù (A Ú C) ] É (B Ú D)

Спочатку звільнимося від імплікації за вже відомим нам «законом виключення імплікації»А É В º`А Ú В:


[ (A É B) Ù (C É D) Ù (A Ú C) ] Ú (B Ú D)

Після чого, виконаємо таку саму операцію відносно імплікацій, які знаходиться у підформулах досліджуваної формули:

 


[ (`AÚ B) Ù (`C Ú D) Ù (A Ú C) ] Ú (B Ú D)

Наступним кроком буде звільнення від загального заперечення за «другим законом де Моргана»А Ú В º`А Ù`В:

 


[ (`AÚ B) Ù (`C Ú D) Ù (A Ú C) ] Ù (B Ú D)

За «законом подвійного заперечення»`А º А, позбавимося загального заперечення:

[ (`AÚ B) Ù (`C Ú D) Ù (A Ú C) ] Ù (B Ú D)

Знову ж таки за «другим законом де Моргана» звільнимося від загального заперечення підформули:

1 2 3

[ (`AÚ B) Ù (`C Ú D) Ù (A Ú C) ] Ù`B Ù`D

Для підформул 1 і 2 у квадратних дужках застосовуємо «закон дистрибутивності кон’юнкції по відношенню до диз’юнкції»

А Ù (В Ú С) º (А Ù В) Ú (А Ù С):

3

[ ((`А Ù`С) Ú (`А Ù D) Ú (B Ù`C) Ú (B Ù D)) Ù (A Ú C) ] Ù`B Ù`D

Далі до отриманого результату і формули 3 також застосовуємо цей самий закон:

[(`A Ù`C Ù A) Ú (`A Ù D Ù A) Ú (B Ù`C Ù A) Ú (B Ù D Ù A) Ú

Ú (`A Ù`C Ù C) Ú (`A Ù D Ù C) Ú (B Ù`C Ù C) Ú (B Ù D Ù C)] Ù`B Ù`D

І, нарешті, до отриманого результату у квадратних дужках і підформули `В Ù`D застосовуємо «закон комутативност»і отримуємо:

(`A Ù`C Ù A Ù`B Ù`D) Ú (`A Ù D Ù A Ù`B Ù`D) Ú

(B Ù`C Ù A Ù`B Ù`D) Ú (B Ù D Ù A Ù`B Ù`D) Ú

Ú (`A Ù`C Ù C Ù`B Ù`D) Ú (`A Ù D Ù C Ù`B Ù`D) Ú

Ú (B Ù`C Ù C Ù`B Ù`D) Ú (B Ù D Ù C Ù`B Ù`D)

Отже, ми отримали ДНФ у якій кожен диз'юнкт у своєму складі має змінну одночасно із її запереченням, а це означає, що дана формула є тотожно-хибною.

Досконалою диз'юнктивною нормальною формою (ДДНФ) деякої формули називається її ДНФ, яка задовольняє такі умови:

1) у ній немає двох однакових диз'юнктів;

2) у жодному диз'юнкті не має змінної і її заперечення;

3) жоден диз'юнкт не має двох однакових змінних;

Кожен диз'юнкт містить всі змінні, що наявні у вихідній формулі.

Щоб привести формулу до ДДНФ необхідно виконати такі дії:

1) звести формулу до ДНФ;

2) співставити отриману ДНФ з ознаками ДДНФ;

3) якщо в якомусь диз'юнкті не вистачає змінної, яка є у вихідній формулі, то до нього потрібно кон'юнктивно приписати диз'юнкцію цієї змінної і її заперечення (Х Ú`Х).

За допомогою ДДНФ розв'язують задачу огляду всіх гіпотез даної формули.

Наприклад, приведемо до ДДНФ такуформулу:

(А É В) Ù (`B É A)

Спочатку приведемо її до ДНФ, тобто позбавимося імплікації відповідно до «закону виключення імплікації»А É В º`А Ú В:


(`A Ú B) Ù (`B Ú A)

Потім звільнимося від подвійного заперечення за допомогою «закону зняття подвійного заперечення» і отримаємо вираз:

(`A Ú B) Ù (B Ú A)

Застосуємо до нього «закон дистрибутивності кон’юнкції по відношенню до диз’юнкції»А Ù (В Ú С) º (А Ù В) Ú (А Ù С):

(`A Ù B) Ú (`A Ù A) Ú (B Ù B) Ú (A Ù B)

Отримана формула є ДНФ вихідної формули.

Якщо співставити її з ознаками ДДНФ, то стає очевидним, що під формула А Ù`А скорочується, оскільки відповідно до ознак жоден диз'юнкт не може мати змінної одночасно із її запереченням.

Підформула В Ù В також скорочується відповідно до ознак ДДНФ, оскільки жоден диз’юнкт не повинен мати двох однакових змінних і після її скорочення залишається В (вироджена диз’юнкція):

(`A Ù B) Ú B Ú (А Ù В)

Ще однією ознакою ДДНФ є те, що у кожному її диз’юнкті наявні усі змінні, які є у вихідній формулі. Тобто, відповідно до цієї ознаки у другому диз’юнкті В не вистачає змінної А. Тому необхідно приписати за допомогою кон’юнкції до диз’юнкта В диз’юнкцію А Ú`А:

(`A Ù B) Ú [B Ù (A Ú `A)] Ú (А Ù В)

Після чого застосовуємо у квадратних дужках «закон дистрибутивності кон’юнкції по відношенню до диз’юнкції»А Ù (В Ú С) º (А Ù В) Ú (А Ù С) і отримуємо формулу:

(`A Ù B) Ú (В Ù А) Ú (В Ù`А) Ú (А Ù В)

Отриману формулу знову співставляємо із ознаками ДДНФ і скорочуємо схожі формули, оскільки у ДДНФ неможе бути двох однакових диз’юнктів:

(`A Ù B) Ú (В Ù А) Ú (В Ù`А) Ú (А Ù В)

І в резутаті отримуємо таку формулу:

(`A Ù B) Ú (В Ù А)

Із цієї формули ДДНФ очевидно, що вихідна формула має 3 гіпотези:

1. (`A Ù B)

2. (В Ù А)

3. (`A Ù B) Ú (В Ù`А)

Якщо будь-яку із гіпотез приєднати за допомогою імплікації до вихідної формули, то отримаємо тавтологію.

Перевіримо це на нашому прикладі:

(`A Ù B) É [(A É B) Ù (`B É A)]

Для перевірки цього факту зведемо дану формулу до КНФ:

(`A Ù B) Ú [(`A Ú B) Ù (`B Ú A)]

`A Ú`B Ú [(`A Ú B) Ù ( B Ú A)]

(А Ú`В Ú`А Ú В) Ù (А Ú`В Ú В Ú А)

Кожен кон'юнкт отриманої КНФ має змінну і її заперечення, а це означає, що `АÙ B дійсно є гіпотезою для вихідної формули.

Скороченою диз'юнктивною нормальною формою (СДНФ) даної формули називається така її ДНФ, яка задовольняє такі умови:

1) у жодному диз'юнкті немає двох однакових кон'юнктів;

2) якщо є два однакових диз'юнкти, то один з них скорочується;

Жоден диз'юнкт не містить змінної і її заперечення.

Для того, щоб привести формулу до СДНФ необхідно виконати такі дії:

1) привести вихідну формулу до ДНФ;

2) співставити отриману ДНФ із ознаками СДНФ;

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти