Лабораторна робота №5 на тему Алгебра висловлювань, зведення формул до ДНФ та КНФ
« Назад
ЛАБОРАТОРНА РОБОТА №5ТЕМА РОБОТИ: «Алгебра висловлювань. Зведення формул до ДНФ та КНФ»МЕТА РОБОТИ: набути знань та практичних навичок побудови роботи з формулами та їх зведення до ДНФ та КНФ. ХІД РОБОТИ Збережіть цей файл з ім’ям zvit_lab_4 у своїй папці на сервері. Відкрийте його для роботи. ЗАВДАННЯ 1. Уважно перегляньте методичні рекомендації 1. Диз'юнкти́вна нормальна форма (ДНФ) в булевій логіці - нормальна форма, в якій булева формула має вид диз'юнкції декількох кон'юнктів (де кон'юнктами називаються кон'юнкції декількох символів або їх заперечень). Довільна булева формула може бути приведена до ДНФ за допомогою наступного алгоритму: Крок 1 : Усі логічні зв'язки виразити через кон'юнкцію, диз'юнкцію і заперечення. Крок 2 : Скасувати всі подвійні заперечення і використати, де можливо, закони де Моргана. Крок 3: Використати де можливо дистрибутивність кон'юнкції, тобто замінити. 2. Кон'юнкти́вна нормальна форма (КНФ) в булевій логіці - нормальна форма в якій булева формула має вид кон'юнкції декількох диз'юнктів (де диз'юнктами називаються диз'юнкції декількох символів або їх заперечень). Довільна булева формула може бути приведена до КНФ за допомогою наступного алгоритму: Крок 1: Усі логічні зв'язки виразити через кон'юнкцію, диз'юнкцію і заперечення. Крок 2: Скасувати всі подвійні заперечення і використати, де можливо, правила де Моргана. Крок 3: Використати де можливо дистрибутивність диз'юнкції, тобто замінити. ЗАВДАННЯ 2. Уважно вивчіть ПРИКЛАДИ розв’язання задач Задача 1. Записати формулу у диз’юнктивній нормальній формі (ДНФ) та кон’юнктивній нормальній формі (КНФ). Розв’язання. Застосовуючи формулу (тричі), закон де Моргана, закон подвійного заперечення та асоціативний закон, маємо. В результаті цих перетворень отримали формулу, рівносильну даній і записану у ДНФ. Для того, щоб дістати КНФ, продовжимо перетворення, застосувавши закон дистрибутивності та ідемпотентності. Задача 2. Надворі може бути вітер або тиха погода. Якщо надворі вітер, то дерева хитаються. Дерева не хитаються. Чи означає це, що надворі тиха погода. Розв’язання. Виділимо прості висловлювання і введемо позначення: “надворі вітер", “надворі тиха погода», “дерева хитаються”. Тоді дані в умові задачі міркування можна записати у вигляді: , (це наші посилки). Потрібно з’ясувати, чи буде логічним наслідком цих трьох посилок. Скористаємось означенням логічного наслідку і побудуємо таблицю істинності. З таблиці істинності видно, що при всіх інтерпретаціях, при яких всі посилки приймають істинносне значення 1 (у нашому випадку існує лише одна така інтерпретація), істинносне значення висновку теж дорівнює 1. Отже, є логічним наслідком трьох даних посилок. Зауважимо, що істинносне значення висновку можна не обчислювати (у таблиці стоїть знак “─”), якщо хоча б одна посилка є хибною. Задача 3. Якщо надворі йде дощ, то на небі є хмари. На небі є хмари. Чи означає це, що надворі йде дощ. Розв’язання. Як і в попередній задачі, виділимо прості висловлювання і введемо позначення: “надворі йде дощ”, “на небі є хмари”. Маємо посилки: . З’ясуємо, чи буде логічним наслідком цих посилок. Побудуємо таблицю істинності. З таблиці істинності видно, що існує дві інтерпретації, при яких обидві посилки приймають істинносне значення 1, але на одній з них висновок має істинносне значення 0. Отже, не є логічним наслідком вказаних двох посилок. Задача 4. Звести формулу до диз’юнктивної нормальної форми (ДНФ). Розв’язання. Використовуючи означення операцій “стрілка Пірса” та “штрих Шеффера”, маємо. ЗАВДАННЯ 3. РОЗВ’ЯЖІТЬ ЗАДАЧІ
З повагою ІЦ “KURSOVIKS”! |