Нормальні форми та засоби побудови нормальних форм числення висловлювань

• виразІ при будь-якому розподілі значень

пропозиціональних змінних приймає логічне значення істина;

• вираззавжди приймає логічне значення

неправда;

• виразне істинний, а й не є неправдою, він

зветься нейтральним.

Таким чином, у алгебрі логіки зустрічаються три види виразів:

1. загальнозначущі - такі вирази, які при кожному наборі значень своїх пропозиціональних змінних приймають лише значення істина. Загальнозначущі вирази називають законами логіки висловлень;

2. протиріччя - вирази, які при будь-якому наборі пропозиціональних змінних приймають лише значення неправда;

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

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

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

Перетворення форм

Імплікація (якнаведено в таблиці 2) може бути перетворена в диз’юнкціятому що обидві мають однаковий порядок

значень.

Таблиця 2

Є цілий ряд перетворень імплікацій, наприклад:

Для перетворень імплікацій у диз’юнкцію достатньо запам’ятати правило: вираз ~ р v q завжди можна одержати з

1.

2. —> - константа імплікації замінюється константою v для диз’юнкції;

3. q - консеквент імплікації береться без зміни.

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

Таблиця З

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

Таблиця 4

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

1. через кон’юнкцію й імплікацію еквівалентністю

2. через кон’юнкцію, диз’юнкцію і заперечення еквівалентністю

3.

З визначення відношень еквівалентності безпосередньо випливає, що воно рефлексивно, симетрично, транзитивне.

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

Наприклад:

Якщо необхідно досліджувати еквіваленцікто

її перетворюють у дві імплікації, які досліджуються окремо. Спочатку розглянемо імплікацію

Припустимо, що консеквент (р —> q) невірний, тому р істинно, q невірно. Через хибність q антицендент невірний. Отже, цей вираз загальнозначущий. Роздивимося імплікацію (р —> q) —> (р л q). Є три набори значень істинності, при яких консеквент невірний. Серед них є один набір значень, коли антецедент також невірний (якщо р істинно, а q невірно). Але це ще не говорить про те, що вираз загальнозначущий. Існують два будь-яких набори значень, при яких усі вирази невірні:

1. коли р невірно, та q істинно;

2. коли р та q обидва помилкові.

Досліджувана еквіваленція була б загальнозначущою, якби обидві імплікації були загальнозначущі. Лише перша імплікація є загальнозначущою.

2.4.2.