Кон'юнктивною нормальною формою логічної функції. «підручник з дискретної математики днф, сднф, кнф, скнф

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

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

Серед нормальних форм виділяються досконалі нормальні форми (такі форми, у яких функції записуються єдиним чином).

Досконала диз'юнктивна нормальна форма (СДНФ)

Визначення. Формулу називають елементарною кон'юнкцією, якщо вона утворена кон'юнкцією певної кількості змінних або їх заперечень.

Приклади: y, ¬ y, х 1 ∧ ¬ х 2 ∧ х 3 ∧ х 4

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

ДНФ записується в наступній формі: F 1 ∨ F 2 ∨ ... ∨ F n , де F i - елементарна кон'юнкція

Приклади: ¬ х 1 ∧ х 2 ∨ х 1 ∧ ¬ х 2 ∨ х 1 ∧ ¬ х 2 ∧ х 3 , ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Визначення. Логічна формула від k змінних називається досконалою диз'юнктивною нормальною формою (СДНФ), якщо:
1) формула є ДНФ, в якій кожна елементарна кон'юнкція є кон'юнкція k змінних х 1, х 2, …, х k, причому на i-му місціцієї кон'юнкції стоїть або змінна х i або її заперечення;
2) всі елементарні кон'юнкції у такій ДНФ попарно різні.

Приклад: (¬ х 1 ∧ х 2 ∧ х 3) ∨ (х 1 ∧ ¬ х 2 ∧ х 3) ∨ (х 1 ∧ х 2 ∧ ¬ х 3)

Досконала кон'юнктивна нормальна форма (СКНФ)

Визначення. Формулу називають елементарною диз'юнкцією, якщо вона утворена диз'юнкцією певної кількості змінних або їх заперечень.

Приклади: х 3 , х 1 ∨ х 2 , х 1 ∨ х 2 ∨ х 3

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

КНФ записується в наступній формі: F 1 ∧ F 2 ∧ ... ∧ F n , де F i - елементарна диз'юнкція

Приклади: (х 1 ∨ ¬ х 2) ∧ х 3 , (х 1 ∨ х 2) ∧ (¬ х 1 ∨ х 2 ∨ х 3) ∧ (х 1 ∨ ¬ х 2 ∨ ¬ х 3)

Визначення. Логічна формула від k змінних називається досконалою кон'юнктивною нормальною формою (КДНФ), якщо:
1) формула є КНФ, в якій кожна елементарна диз'юнкція є диз'юнкція k змінних х 1, х 2, …, х k, причому на i-му місці цієї диз'юнкції стоїть або змінна х i, або її заперечення;
2) всі елементарні диз'юнкції у такій КНФ попарно різні.

Приклад: (х 1 ∨ х 2 ∨ х 3) ∧ (¬ х 1 ∨ ¬ х 2 ∨ х 3)

Зауважимо, що будь-яку логічну функцію, не рівну тотожно 0 або 1, можна подати у вигляді СДНФ або СКНФ.

Алгоритм побудови СДНФ за таблицею істинності

1. Вибрати всі рядки таблиці, в яких значення функції дорівнює одиниці.
2. Для кожного такого рядка записати кон'юнкцію всіх змінних наступним чином: якщо значення деякої змінної в цьому наборі дорівнює 1, то кон'юнкцію включаємо саму змінну, в іншому випадку - її заперечення.
3. Усі отримані кон'юнкції пов'язуємо операціями диз'юнкції.

Алгоритм побудови СКНФ за таблицею істинності

1. Вибрати всі рядки таблиці, в яких значення функції дорівнює нулю.
2. Для кожного такого рядка записати диз'юнкцію всіх змінних наступним чином: якщо значення деякої змінної в цьому наборі дорівнює 0, то кон'юнкцію включаємо саму змінну, в іншому випадку - її заперечення.
3. Усі отримані диз'юнкції пов'язуємо операціями кон'юнкції.

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

Приклад: Дано таблицю істинності логічної функції від трьох змінних. Побудувати логічну формулу, Що реалізує цю функцію.

Т.к. більшості рядків таблиці істинності значення функції дорівнює 1, то побудуємо СКНФ. В результаті отримаємо наступну логічну формулу:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Перевіримо отриману формулу. Для цього збудуємо таблицю істинності функції.

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

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

Нормальна форма існує у двох видах:

нормальна кон'юнктивна форма (КНФ)-- кон'юнкція декількох диз'юнкцій, наприклад, $ \ left (A \ vee \ overline (B) \ vee C \ right) \ wedge \ left (A \ vee C \ right) $;

диз'юнктивна нормальна форма (ДНФ)-- диз'юнкція декількох кон'юнкцій, наприклад, $ \ left (A wedge \ overline (B) \ wedge C \ right) \ vee \ left (B \ wedge C \ right) $.

СКНФ

Досконала кон'юнктивна нормальна форма (СКНФ) -- це КНФ, яка задовольняє трьома умовами:

не містить однакових елементарних диз'юнкцій;

жодна з диз'юнкцій не містить однакових змінних;

кожна елементарна диз'юнкція містить кожну змінну з тих, що входять до цієї КНФ.

Будь-яка булева формула, яка не є тотожно істинною, може бути подана у СКНФ.

Правила побудови СКНФ за таблицею істинності

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

СДНФ

Досконала диз'юнктивна нормальна форма (СДНФ) -- це ДНФ, яка задовольняє трьома умовами:

не містить однакових елементарних кон'юнкцій;

жодна з кон'юнкцій не містить однакових змінних;

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

Будь-яка булева формула, яка не є тотожно хибною, може бути представлена ​​в СДНФ, до того ж єдиним чином.

Правила побудови СДНФ за таблицею істинності

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

Приклади знаходження СКНФ та СДНФ

Приклад 1

Записати логічну функцію за її таблицею істинності:

Малюнок 1.

Рішення:

Скористаємося правилом побудови СДНФ:

Малюнок 2.

Отримаємо СДНФ:

Скористаємося правилом побудови СКНФ.

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

Наприклад, є простою кон'юнкцією,

диз'юнктивної нормальною формою(ДНФ) називається диз'юнкція простих кон'юнкцій.

Наприклад, вираз є ДНФ.

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

Наприклад, вираз є ДНФ, але не СДНФ. Вираз є СДНФ.

Аналогічні визначення (із заміною кон'юнкції на диз'юнкцію та навпаки) правильні для КНФ та СКНФ. Наведемо точні формулювання.

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

Кон'юнктивний нормальною формою(КНФ) називається кон'юнкція простих диз'юнкцій(Наприклад вираз - КНФ).

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

Наприклад, вираз є СКНФ.

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

а) перехід від ДНФ до КНФ

Алгоритм цього переходу наступний: ставимо над ДНФ два заперечення та за допомогою правил де Моргана (не чіпаючи верхнього заперечення) наводимо заперечення ДНФ знову до ДНФ. У цьому доводиться розкривати дужки з допомогою правила поглинання (чи правила Блейка). Заперечення (верхнє) отриманої ДНФ (знову за правилом де Моргана) відразу дає нам КНФ:

Зауважимо, що КНФ можна отримати і з первісного виразу, якщо винести уза дужки;

б) перехід від КНФ до ДНФ

Цей перехід здійснюється простим розкриттям дужок (при цьому використовується правило поглинання)

Таким чином отримали ДНФ.

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

в) скорочення ДНФ (або СДНФ) за правилу Блійка

Застосування цього правила складається із двох частин:

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

Якщо додане доданок вже містилося в ДНФ, його можна відкинути зовсім, наприклад,

або

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

в) перехід від ДНФ до СДНФ

Якщо в якійсь простій кон'юнкції немає змінної, наприклад, z, вставляємо в неї вираз ,після чого розкриваємо дужки (при цьому повторювані диз'юнктні доданки не пишемо). Наприклад:

г) перехід від КНФ до СКНФ

Цей перехід здійснюється способом, аналогічним до попереднього: якщо в простій диз'юнкції не вистачає якоїсь змінної (наприклад, z, то додаємо в неї вираз (це не змінює самої диз'юнкції), після чого розкриваємо дужки з використанням розподільчого закону):

Таким чином, із КНФ отримано СКНФ.

Зауважимо, що мінімальну чи скорочену КНФ зазвичай одержують із відповідної ДНФ.

Введемо поняття елементарної диз'юнкції.

Елементарною диз'юнкцією називається вираз виду

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

є кон'юнкцією елементарних диз'юнкцій. Отже, вони записані у кон'юнктивній нормальній формі.

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

використання правила інверсії, якщо операція заперечення застосована до логічного виразу;

Використання аксіоми дистрибутивності щодо множення:

Використання операції поглинання:

Винятки в диз'юнкціях змінних, що повторюються, або їх заперечень;

Вилучення всіх однакових елементарних диз'юнкцій, крім однієї;

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

Справедливість перерахованих операцій випливає з основних аксіом та тотожних співвідношень алгебри логіки.

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

Перетворення КНФ до досконалої КНФ здійснюється шляхом виконання наступних операцій:

Додатки до кожної елементарної диз'юнкції кон'юнкцій змінних та їх заперечень, якщо вони не входять до цієї елементарної диз'юнкції;

використання аксіоми дистрибутивності;

Видалення всіх однакових елементарних диз'юнкцій, крім однієї.

У досконалій КНФ може бути представлена ​​будь-яка логічна функція, крім

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

Елементарні диз'юнкції, що входять до досконалої КНФ функції, звуться конституент нуля. Кожна конституента нуля, що входить до досконалої КНФ, звертається в нуль на єдиному наборі значень змінних, що є нульовим набором функції. Отже, число нульових наборів логічної функції збігається з числом конституентів нуля, що входять до її досконалої КНФ.

Логічна функція константа нуля у досконалій КНФ є кон'юнкцією 2nконституент нуля. Сформулюємо правило складання СКНФ логічної функції таблиці відповідності.

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

Приклад 3.4.Для логічної функції z(x), заданою таблицею відповідності 2.2, визначимо досконалу кон'юнктивну форму.

Для першого рядка таблиці, що відповідає нульовому набору функції 000, знаходимо конституенту нуля. Виконавши аналогічні операції для другого, третього та п'ятого рядків, визначимо шукану досконалу КНФ функції:

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

Нормальні форми логічних функцій Подання булевої функції у формі диз'юнкції кон'юнктивних термів конституент одиниці Ki 2.7 називається нормальною диз'юнктивною формою ДНФ цієї функції. містять точно по одній всі логічні змінні взяті з запереченнями або без них така форма подання функції називається досконалою диз'юнктивною нормальною формою СДНФ цієї функції. Як видно при складанні СДНФ функції потрібно скласти диз'юнкцію всіх мінтермів, при яких функція набуває значення 1.

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

Лекція 1.хх

Нормальні форми логічних функцій

Подання булевої функції у формі диз'юнкції кон'юнктивних термів (конституент одиниці) K i

, (2.7)

називається диз'юнктивною нормальною формою(ДНФ) цієї функції.

Якщо всі кон'юнктивні терми в ДНФ ємінтермами , тобто містять точно по одній всі логічні змінні, взяті з запереченнями або без них, то така форма подання функції називаєтьсядосконалою диз'юнктивною нормальною формою(СДНФ ) цієї функції. СДНФ називаєтьсядосконалою тому, що кожен терм у диз'юнкції включає всі змінні;диз'юнктивної , Тому що головна операція у формулі - диз'юнкція. Поняття “нормальної форми” означає однозначний спосіб запису формули, що реалізує задану функцію.

З урахуванням сказаного вище теореми 2.1 випливає наступна теорема.

Теорема 2. Будь-яка бульова функція(не рівна тотожно 0) може бути представлена ​​в СДНФ, .

приклад 3. Нехай маємо таблично задану функцію f (x 1, x 2, x 3) (табл. 10).

Таблиця 10

На підставі формули (2.6) отримуємо:

Як бачимо, під час упорядкування СДНФ функції необхідно скласти диз'юнкцію всіх мінтермів, у яких функція приймає значення 1.

Подання булевої функції у формі кон'юнкції диз'юнктивних термів (конституент нуля) D i

, (2.8)

називається кон'юнктивною нормальною формою(КНФ) цієї функції.

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

Теорема 3. Будь-яка бульова функція(не рівна тотожно 1) може бути представлена ​​в СКНФ, причому таке уявлення єдине.

Доказ теореми може бути проведений аналогічно доказу теореми 2.1 на підставі наступної леми Шеннона про кон'юнктивне розкладання.

Лемма Шеннона . Будь-яка бульова функція f (x 1, x 2, …, x m) від m змінних може бути представлена ​​так:

. (2.9)

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

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

Приклад 4. Для функції f (x 1 x 2 x 3 ), заданою табл. 10, написати її СКНФ.

На відміну від СДНФ, при складанні СКНФ у таблиці істинності логічної функції потрібно дивитися комбінації змінних, при яких функція набуває значення 0, і скласти кон'юнкцію відповідних макстермів,але змінні потрібно брати зі зворотною інверсією:

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

Приклад 5. Для функції f (x 1 x 2 x 3 ), заданою табл. 10, спробувати перейти від СДНФ до СКНФ.

Використовуючи результат прикладу 2.3 отримаємо:

Як видно, під загальною інверсією вийшла СКНФ логічної функції, яка є зворотною по відношенню до функції, отриманої у прикладі 2.4:

т. до. містить всі макстерми, яких немає у виразі для СКНФ цієї функції.

1. Використовуючи властивості операцій (див. табл. 9) тотожність (), сума за модулем 2 (), імплікація (), переходимо до операцій І, АБО, НЕ (в базис Буля).

2. Використовуючи властивості заперечення та закони де Моргана (див. табл. 9) домагаємося, щоб операції заперечення відносилися лише до окремих змінних, а не до цілих виразів.

3. Використовуючи властивості логічних операцій І та АБО (див. табл. 9), отримуємо нормальну форму (ДНФ або КНФ).

4. При необхідності переходимо до досконалих форм (СДНФ чи СКНФ). Наприклад, щоб одержати СКНФ часто необхідно використовувати властивість: .

Приклад 6. Перетворити на СКНФ логічну функцію

Виконуючи по порядку кроки наведеного вище алгоритму, отримаємо:

Використовуючи властивість поглинання, отримаємо:

Таким чином, ми отримали КНФ функції f (x 1 x 2 x 3 ). Щоб отримати її СКНФ, потрібно кожну диз'юнкцію, в якій не вистачає будь-якої змінної, повторити двічі – з цією змінною та її запереченням:

2.2.6. Мінімізація логічних функцій

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

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

Метод Квайна

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

, (2.10)

а потім поглинання

, (2.11)

і ця пара етапів застосовується багаторазово. Таким чином, вдається знизити ранг термів. Ця процедура повторюється до тих пір, поки не залишиться жодного терму, що допускає склеювання з будь-яким іншим термом.

Зауважимо, що ліву частинурівняння (2.10) відразу можна було мінімізувати більш простим та очевидним способом:

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

Слід зазначити, що метод Квайна є досить трудомістким, тому ймовірність припущення помилок під час перетворень досить велика. Але його перевагою є те, що теоретично його можна використовувати для будь-якої кількості аргументів і зі збільшенням кількості змінних перетворення ускладнюються не так сильно.

Метод карт Карно

Метод карт (таблиць) Карно є наочнішим, менш трудомістким і надійним способом мінімізації логічних функцій, та його використання практично обмежена функціями 3-4 змінних, максимум – 5-6 змінних.

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

Таблиці істинності та карти Карно для функцій І та АБО двох пере менних представлені на рис. 8. У кожну клітинку картки записується зна чення функції на відповідному цій клітині наборі значень аргумен тов.

А ) І б ) АБО

Мал. 8. Приклад карт Карно для функцій двох змінних

У карті Карно для функції І лише одна 1, тому її ні з чим неможливо склеїти. У виразі для мінімальної функції буде тільки терм, що відповідає цій 1:

f = x y.

У карті Карно для функції АБО вже три 1 і можна скласти дві пари, що склеюються, при цьому 1, відповідна терму xy використовується двічі. У виразі для мінімальної функції потрібно записати терми для пар, що склеюються, залишаючи в них всі змінні, які для цієї пари не змінюються, і прибираючи змінні, які змінюють своє значення. Для горизонтального склеювання отримаємо x , а для вертикальної – y , в результаті отримаємо вираз

f = x + y.

На рис. 9 наведено таблиці істинності двох функцій трьох змінних (а ) та їх карти Карно (б і в). Функція f 2 відрізняється від першої тим, що у трьох наборах змінних вона визначена (у таблиці це позначено прочерком).

При визначенні мінімальної ДНФ функції використовуються такі правила. Усі клітини, що містять 1, об'єднуються у замкнуті прямокутні області, які називаються k-кубами, де k = log 2 K, K – кількість 1 у прямокутній області. При цьому кожна область повинна бути прямокутником з числом клітин 2 k , де k = 0, 1, 2, 3, …. Для k = 1 прямокутник називаєтьсяодин-куб і містить 21 = 2 одиниці; для k = 2 прямокутник містить 2 2 = 4 одиниці і називаєтьсядва-куб; при k = 3 область із 2 3 = 8 одиниць називаєтьсятри-куб ; і т. д. Одиниці, які неможливо об'єднати у прямокутники, можна назватинуль-кубами , які містять лише одну одиницю (2 0 = 1). Як видно, при парному k області можуть мати форму квадрата (але не обов'язково), а при непарному k - Тільки прямокутників.

Мал. 9. Приклад карт Карно для функцій трьох змінних

Ці області можуть перетинатися, т. е. одні й самі клітини можуть входити в різні області. Потім записується мінімальна ДНФ функції як диз'юнкція всіх кон'юнктивних термів, що відповідають k – кубам.

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

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

Для функції карти Карно на рис. 9,б знаходимо

оскільки для верхньої замкнутої області змінні x 1 та x 2 мають значення без інверсій, для нижньої x 1 має значення з інверсією, а x 3 – без інверсії.

Невизначені значення в карті на рис. 9,в можна визначити, замінивши нулем або одиницею. Для цієї функції видно, що обидва невизначені значення вигідніше замінити 1. При цьому утворюються дві області, що є різними видами 2-кубів. Тоді вираз для мінімальної ДНФ функції буде наступним:

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

Карти Карно можна малювати у різний спосіб (рис. 10).

а б

Мал. 10. Різні способи зображення карт Карно
для функції 3 змінних

Але найзручнішими варіантами карт Карно для функцій 2-4 змінних є показані на рис. 11 таблиці, тому що в них для кожного осередку показа ні всі змінні у прямому чи інверсному вигляді.

а б

Мал. 11. Найбільш зручне зображення карт Карно
для функцій 3 (а) та 4 (б) змінних

Для функцій 5 і 6 змінних найбільше підходить спосіб, показаний на рис. 10,в.

Мал. 12. Зображення картки Карно для функції 5 змінних

Мал. 13. Зображення картки Карно для функції 6 змінних