Диз’юнктивні нормальні форми.

Відомо, що:

- головним завданням математики логіки є вивчення математичних законів;

- існує простий універсальний метод (табличний), який дозволяє для будь-якої формули алгебри висловлень скінченним числом дій визначити чи є вона логічним законом;

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

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

Наприклад:

 

 

На наборі 1,0 формула набирає значення істинності, тому вона називається здійсненною.

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

За допомогою таблиць легко виявити характер логічної формули.

Якщо останній рядок таблиці істинності формули:

1) містить хоча б одну одиницю, то ця формула здійсненна;

2) складається з одних одиниць, то вона завжди істинна (логічний закон)

3) складається лише з нулів, то вона тотожно хибна (нездійсненна)

Логічний закон – це формула, яка істинна на будь-якому наборі.

 

До основних логічних законів належать:

1) Закон тотожності - (якщо Х, то Х)

 

2) Закон суперечності - (не можуть однозначно бути істинними і )

 

 

3) Закон виключеного третього - (з висловлень або хоча б одне істинне)

 

 

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

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

1) містить тільки основні логічні операції: диз’юнкцію, кон`юнкцію і заперечення;

2) кожен знак заперечення стосується тільки основного висловлення (окремої букви).

Приклади: ; ; ; _{1 2 1 3} – це попередні форми;

- знак заперечення стосується складної формули;

- не попередні форми, містить не основні операції.

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

- якщо над виразом стоїть кілька рисок заперечення, то їх можна відкинути, якщо їх число парне і залишити одну, якщо їх число не парне (це випливає із закону подвійного заперечення)

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

Завдання: звести логічні формули до попередньої форми.

1/

2/

3/

4)

5)

6)

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

Зауваження: одна буква не може зустрічатися в ньому більше одного разу.

Приклади: -елементарні добутки.

- не є елементарними добутками.

Теорема: Елементарний добуток дорівнює 1 на одному наборі, коли змінним із запереченням присвоєний нуль, а змінним без заперечення 1.

│ │

Логічна функція, яка подається диз’юнкцією (сумою) елементарних добутків називається диз’юнктивною нормальною формою (ДНФ).

* ДНФ відносно висловлень називається формула кожного з трьох типів:

1) елементарний добуток

2) диз`юнкція різних елементарних добутків відносно

3) тотожна хибність .

Для кожної формули алгебри висловлень існує ДНФ, яка може бути знайдена за допомогою скінченого числа дій.

Алгоритм з ведення логічної формули до ДНФ:

1) зводимо до трьох основних операцій: ¯;

2) якщо є добутки диз’юнкції, то застосовують дистрибутивні закони:

3) на підставі закону тавтології викреслюємо повторні множники або зайві додатки, а також додатки типу (на основі закону суперечності).

Після таких скорочень залишається або елементарний добуток або диз’юнкція різних елементарних добутків відносно або нічого, бо все скоротиться.

Звести до ДНФ:

а)

= =

 

б) =

= - тотожна хибніст

в)