Рішення виразів символічної логіки за допомогою нормальних форм. Числення висловлювань

Для рішення деякого виразу символічної логіки (тобто для встановлення до якого класу він належить) його спочатку призводять до нормальної форми. Нормальна форма повинна задовольняти таким умовам:

1.

2. в зв’язку з логікою висловлень, в ній повинні утримуватися лише знаки заперечення, кон’юнкції та диз’юнкції;

3. знаки заперечення, що зустрічаються, повинні ставитися лише до пропозиціональних змінних, але не до складних виразів.

Приведемо до нормальної форми вираз:

Насамперед, необхідно подбати про виконання другої умови, а вже потім проводити перетворення, для виконання третьої умови. Для цього спочатку необхідно усунути знаки імплікації з виразу (4). Перетворення імплікації в диз’юнкцію призводить до такого виду:

Перетворення імплікації в диз’юнкцію призвело до того, що лівий член заперечиться двічі. Відповідно до правила, вираз може бути зведено до такого:

Тепер правий член необхідно перетворити так, щоб було виконано умову про відношення знаків заперечення лише до пропозиціональних змінних. Для цього правий член виразу перетворимо в диз’юнкцію:

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

Вираз (8) є нормальною формою виразу(4).

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

1. від р V (q л г) можна перейти доі навпаки.

Обидва вирази мають той самий розподіл значень істинності;

2. від р a (q vr) можна перейти до

Правила дистрибутивності гарантують, що вираз, отриманий з їх допомогою, семантично еквівалентний первісному. За допомогою правил дистрибутивності з будь-якого виразу алгебри логіки після приведення до нормальної форми, можна одержати його кон’юнкцію і диз’юнкцію нормальної форми. Кон’юнктивна нормальна форма виразу (pvq)Λ(pvr)- кон’юнктивна диз’юнкція, яка виконує усі умови нормальної форми. Члени диз’юнкцій (із запереченнями або без них) є пропозиціональними змінними. Кон’юнктивна нормальна форма дає змогу дізнатися, є вираз загальнозначущим або ні.

Дослідимо вираз:Спочатку складемо нормальну

форму:

Вираз складається з диз’юнкції і кон’юнкції. Але нам необхідна кон’юнкція диз’юнкцій. Візьмемо перше правило дистрибутивності. Замість р введемоодержимо:

Вирази _семантично

еквівалентної. їх можна переписати у виді:

q). Кон’юнкція диз’юнкцій еквівалентна початковому виразу, її члени є пропозиціональними змінними.

Якщо з кон’юнктивної нормальної форми виразу можна дізнатися, чи є він загальнозначущим, то диз’юнктивна нормальна форма дає змогу визначити, чи є вираз суперечливим.

Приведемо вираз _jt_ до диз’юнктивної

нормальної форми. Приймемо, що р лишається незмінним, підставляється замість q, замість r підставляєтьсяОдержимо:

Обидві кон’юнкції містять вираз виду р л ~ р. Вони при будь- якому наборі значень змінних помилкові, тобто є протиріччями, тому що кон’юнкція містить помилковий член. Обидва члени диз’юнкції є протиріччями. Таким чином, вона і сама є протиріччям. Отже, і початковий вираз також суперечення.

Вирази алгебри логіки є протиріччям, якщо в кожній кон’юнкції, яка складає диз’юнктивну нормальну форму, деяка пропозиціональна змінна входить один раз із запереченням, а іншим разом без нього. Якщо ж цього немає хоча б в одній кон’юнкції, то вираз не є протиріччям, тобто він загальнозначущий або нейтральний.

2.5.