Карти Карно

Означення 3.1. Диз’юнкція всіх простих імплікант називається скороченою ДНФ функції.

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

Прикладом скороченої ДНФ є .

Означення 3.2. Найкоротша (мінімальна) диз’юнктивна нормальна форма – це ДНФ, що має найменшу довжину серед всіх еквівалентних їй ДНФ.

Скорочену ДНФ можна отримати з довільної ДНФ, використовуючи процедуру, що називається методом Блейка:

1. Застосовувати, скільки можливо, закон поглинання

зліва направо за умови, що кон'юнкція () несуперечлива, тобто не містить одночасно деяку змінну та її заперечення. (Зауважимо, що на цьому етапі число елементарних кон'юнкція в ДНФ, взагалі кажучи, збільшується).

2. Застосовувати, скільки можливо, правило поглинання

Потім видалити повторні входження кон'юнкцій.

ТЕОРЕМА 3.1. У результаті використання методу Блейка для довільної ДНФ через скінченне число кроків буде отримана еквівалентна їй скорочена ДНФ.

Приклад 3.1. Використовуючи метод Блейка для досконалої ДНФ функції f (p, q, r), що приймає значення TRUE для (F,F,T), (F,T,F), (F,T,T), (T,F,T), побудувати скорочену.

Досконала ДНФ:

.

Застосуємо закон поглинання:

Застосуємо правило поглинання:

.

Отже, скороченою ДНФ для функції f є .

Означення 3.3. Тупикова диз’юнктивна нормальна форма – це ДНФ, у якій відкидання будь-якої кон’юнкції приводить до нееквівалентної ДНФ. Мінімальна ДНФ є тупиковою, але не всяка тупикова є мінімальною.

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

Картою Карно є матриця розмірності (n = k + l) з 2 ⁿ клітинками, у якій кожен рядок однозначно відповідає деякій елементарній кон’юнкції перших k змінних, а кожний стовпчик – елементарній кон’юнкції решти l змінних, таким чином, що сусідні елементи (мають спільну границю, перший і останній рядки (стовпці) вважаються сусідніми) в кожному рядку та в кожному стовпчику відрізняються лише одним літералом. Кожна клітинка відповідає деякій елементарній кон’юнкції. Нуль або одиниця у клітинці таблиці визначає значення функції на даній інтерпретації.

Приклад 3.2. Структура карт Карно для функцій від двох n =2, k =1, l =1 (табл. 3.1) і трьох n =3, k =1, l =2 (табл. 3.2) змінних наведена нижче.

Таблиця 3.1

Карта Карно для функції двох змінних

p q

Таблиця 3.2

Карта Карно для функції троьх змінних

Поиск по сайту: