Конюнктивна нормална форма на логическа функция. „Учебник по дискретна математика dnf, sdnf, knf, sknf

За всяка логическа формула с помощта на идентични трансформации е възможно да се конструират безкрайно много еквивалентни на нея формули. В алгебрата на логиката една от основните задачи е търсенето на канонични форми (тоест формули, изградени според едно правило, канон).

Ако логическата функция се изразява чрез дизюнкция, конюнкция и отрицание на променливи, тогава тази форма на представяне се нарича нормална.

Сред нормалните форми се разграничават съвършените нормални форми (такива форми, в които функциите са написани по уникален начин).

Перфектна дизюнктивна нормална форма (SDNF)

Определение. Формулата се нарича елементарна конюнкция, ако е образувана от конюнкцията на редица променливи или техните отрицания.

Примери: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

Определение. Формулата се нарича дизюнктивна нормална форма (DNF), ако е дизюнкция от неповтарящи се елементарни съюзи.

DNF се записва в следната форма: F 1 ∨ F 2 ∨ ... ∨ F n, където F i е елементарна конюнкция

Примери: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3, ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Определение. Логическа формула в k променливи се нарича идеална дизюнктивна нормална форма (SDNF), ако:
1) формулата е DNF, в която всяка елементарна конюнкция е конюнкция от k променливи x 1, x 2, ..., x k и на i-то мястотази връзка е или променливата x i, или нейното отрицание;
2) всички елементарни конюнкции в такъв DNF са двойно различни.

Пример: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)

Перфектна конюнктивна нормална форма (SKNF)

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

Примери: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

Определение. Формулата се нарича конюнктивна нормална форма (CNF), ако е съвкупност от неповтарящи се елементарни дизюнкции.

CNF се записва в следната форма: F 1 ∧ F 2 ∧ ... ∧ F n, където F i е елементарна дизюнкция

Примери: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

Определение. Логическа формула в k променливи се нарича перфектна конюнктивна нормална форма (CDNF), ако:
1) формулата е CNF, в която всяка елементарна дизюнкция е дизюнкция на k променливи x 1, x 2, ..., x k, а на i-то място на тази дизюнкция е или променливата x i, или нейното отрицание;
2) всички елементарни дизюнкции в такава CNF са двойно различни.

Пример: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)

забележи това всяка логическа функция, която не е идентично равна на 0 или 1, може да бъде представена като SDNF или SKNF.

Алгоритъм за изграждане на SDNF според таблицата на истинността

1. Изберете всички редове в таблицата, в които стойността на функцията е равна на единица.
2. За всеки такъв ред напишете конюнкцията на всички променливи, както следва: ако стойността на някаква променлива в този набор е равна на 1, тогава включваме самата променлива в конюнкцията, в противен случай - нейното отрицание.
3. Свързваме всички получени конюнкции чрез дизюнкционни операции.

Алгоритъм за конструиране на SKNF според таблицата на истинността

1. Изберете всички редове в таблицата, в които стойността на функцията е равна на нула.
2. За всеки такъв ред напишете дизюнкцията на всички променливи, както следва: ако стойността на някаква променлива в този набор е равна на 0, тогава включваме самата променлива в конюнкцията, в противен случай - нейното отрицание.
3. Свързваме всички получени дизюнкции чрез операции на конюнкции.

Анализът на алгоритмите показва, че ако в повечето редове на таблицата на истинността стойността на функцията е равна на 0, тогава за получаване на нейната логическа формула е по-добре да се построи SDNF, в противен случай - SKNF.

Пример: Дадена е таблица на истинността на логическа функция от три променливи. Изграждане логическа формулаизпълнение на тази функция.

Защото на повечето редове от таблицата на истинността, стойността на функцията е 1, тогава конструираме SKNF. В резултат на това получаваме следната логическа формула:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Нека проверим получената формула. За да направите това, нека изградим таблицата на истинността на функцията.

Сравнявайки оригиналната таблица на истината и тази, изградена за логическата формула, отбелязваме, че колоните на стойностите на функцията са еднакви. Това означава, че логическата функция е изградена правилно.

Нормална форма логическата формула не съдържа признаци на импликация, еквивалентност и отрицание на неелементарни формули.

Нормалната форма се предлага в две форми:

конюнктивна нормална форма (CNF)- съединяване на няколко дизюнкции, например $ \ left (A \ vee \ overline (B) \ vee C \ надясно) \ wedge \ left (A \ vee C \ right) $;

дизюнктивна нормална форма (DNF)- дизюнкция на няколко конюнкции, например $ \ вляво (A \ клин \ над линия (B) \ клин C \ дясно) \ vee \ left (B \ клин C \ надясно) $.

SKNF

Перфектна конюнктивна нормална форма (SKNF) е CNF, който отговаря на три условия:

не съдържа идентични елементарни дизюнкции;

нито една от клаузите не съдържа същите променливи;

всяка елементарна дизюнкция съдържа всяка променлива от дадена CNF.

Всяка булева формула, която не е идентично вярна, може да бъде представена в SKNF.

Правила за конструиране на SKNF според таблицата на истинността

За всеки набор от променливи, за които функцията е 0, се записва сумата, а променливите, които имат стойност 1, се вземат с отрицание.

SDNF

Перфектна дизюнктивна нормална форма (SDNF) е DNF, който отговаря на три условия:

не съдържа идентични елементарни съюзи;

нито един от съюзите не съдържа същите променливи;

всяка елементарна конюнкция съдържа всяка променлива от дадения DNF, при това в същия ред.

Всяка булева формула, която не е идентично фалшива, може да бъде представена в SDNF, освен това, по уникален начин.

Правила за изграждане на SDNF според таблицата на истинността

За всеки набор от променливи, за които функцията е равна на 1, се записва произведението, а променливите, които имат стойност 0, се приемат с отрицание.

Примери за намиране на SKNF и SDNF

Пример 1

Напишете логическа функция според нейната таблица на истинността:

Снимка 1.

Решение:

Нека използваме правилото за изграждане на SDNF:

Фигура 2.

Получаваме SDNF:

Нека използваме правилото за конструиране на SKNF.

прост съчетание Наречен съчетание един или няколко променливи, в това всеки един променлива отговаря не Повече ▼ един пъти (или себе си, или нея отрицание).

Например, е прост съюз,

Дизюнктивно нормално форма(DNF) Наречен дизюнкция просто съюзи.

Например, изразът е DNF.

Перфектно дизюнктивно нормално форма(SDNF) Наречен така дизюнктивно нормално форма, в който v всеки съчетание са включени всичко променливи дадено списък (или себе си, или техен отричания), освен това v един и сила на звука същотодобре.

Например, изразът е DNF, но не и SDNF. Изразяване е SDNF.

Подобни дефиниции (със замяна на конюнкция с дизюнкция и обратно) са валидни за CNF и SKNF. Ето точните формулировки.

прост дизюнкция Наречен дизюнкция един или няколко променливи, в това всеки един променлива влиза не Повече ▼ един пъти (или себе си, или нея отрицание) Например изразът е проста дизюнкция,

Конюнктив нормално форма(CNF) Наречен съчетание просто дизюнкции(например изразът е CNF).

Перфектната конюнктивна нормална форма (SCNF) е CNF, в която всяка проста дизюнкция съдържа всички променливи от дадения списък (или сами, или техните отрицания) и в същия ред.

Например изразът е SKNF.

Ето алгоритмите за преходи от една форма в друга. Естествено, в конкретни случаи (при определен творчески подход) използването на алгоритми е по-трудоемко от простите трансформации, използващи специфичен тип от тази форма:

а) преход от DNF към CNF

Алгоритъмът за този преход е следният: поставяме две отрицания над DNF и, използвайки правилата на де Морган (без да докосваме горното отрицание), връщаме отрицанието на DNF обратно към DNF. В този случай трябва да отворите скобите, като използвате правилото за усвояване (или правилото на Блейк). Отрицанието (горната част) на получения DNF (отново според правилото на де Морган) веднага ни дава CNF:

Имайте предвид, че CNF може да се получи и от първоначалния израз, ако извадим визвън скобите;

б) преход от CNF към DNF

Този преход се извършва чрез просто отваряне на скобите (в този случай отново се използва правилото за усвояване)

Така получихме DNF.

Обратният преход (от SDNF към DNF) е свързан с проблема за минимизиране на DNF. Това ще бъде разгледано по-подробно в Разд. 5, тук ще покажем как да опростим DNF (или SDNF) според правилото на Блейк. Този DNF се нарича съкратено DNF;

в) съкращение на DNF (или SDNF) от правило Блейк

Прилагането на това правило се състои от две части:

Ако сред несвързаните членове в DNF има термини , след това към цялата дизюнкция добавяме термина ДА СЕ 1 ДА СЕ 2. Извършваме тази операция няколко пъти (може да бъде последователна, може и едновременно) за всички възможни двойки термини и след това прилагаме обичайното усвояване;

Ако добавеният термин вече се съдържаше в DNF, тогава той може да бъде изхвърлен изцяло, напр.

или

Разбира се, съкратеният DNF не е еднозначно дефиниран, но всички те съдържат еднакъв брой букви (например има DNF , след като приложите правилото на Блейк към него, можете да стигнете до DNF, еквивалент на това):

в) преход от DNF към SDNF

Ако в някой прост съюз липсва променлива, напр. z, вмъкнете израза в него и след това разширете скобите (в този случай ние не пишем повтарящи се несвързани термини). Например:

г) преход от CNF към SKNF

Този преход се извършва по начин, подобен на предишния: ако на обикновена дизюнкция липсва някаква променлива (напр. z, след това добавяме израз към него (това не променя самата дизюнкция), след което разширяваме скобите, използвайки закона за разпределение):

Така SKNF се получава от CNF.

Имайте предвид, че минималната или съкратената CNF обикновено се получава от съответния DNF.

Нека представим понятието елементарна дизюнкция.

Елементарната дизюнкция е израз на формата

Конюнктивната нормална форма (CNF) на логическа функция е конюнкцията на всеки краен набор от различни по двойки елементарни дизюнкции. Например логически функции

са съюзите на елементарните дизюнкции. Следователно те са написани в конюнктивна нормална форма.

Произволна логическа функция, дадена от аналитичен израз, може да бъде сведена до CNF чрез извършване на следните операции:

Използване на правилото за инверсия, ако операцията за отрицание се прилага към булев израз;

Използвайки аксиомата на разпределението по отношение на умножението:

Употреби на абсорбционната операция:

Изключения при дизюнкции на повтарящи се променливи или техните отрицания;

Премахване на всички същите елементарни дизюнкции, с изключение на едно;

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

Валидността на изброените операции следва от основните аксиоми и тъждествени отношения на алгебрата на логиката.

Конюнктивна нормална форма се нарича съвършена, ако всяка елементарна дизюнкция, включена в нея, съдържа в пряка или обратна форма всички променливи, от които зависи функцията.

Преобразуването на CNF в перфектен CNF се извършва чрез извършване на следните операции:

Допълнения към всяка елементарна дизюнкция на конюнкции на променливи и техните отрицания, ако не са включени в тази елементарна дизюнкция;

Използване на аксиомата на дистрибутивността;

Премахване на всички еднакви елементарни дизюнкции, с изключение на едно.

Всяка логическа функция може да бъде представена в перфектен CNF, освен

идентично равно на едно(). Отличително свойство на перфектната CNF е, че представянето на логическа функция в нея е уникално.

Елементарните дизюнкции, включени в перфектната CNF функция, се наричат ​​нулеви съставки. Всяка съставка на нула, включена в перфектната CNF, изчезва при единичен набор от стойности на променливите, който е нулевият набор на функцията. Следователно, броят на нулевите набори на логическата функция съвпада с броя на нулевите съставки, включени в нейната перфектна CNF.

Константата на логическата функция от нула в перфектен CNF е представена от конюнкцията 2n константа на нула. Нека формулираме правило за компилиране на SCNF на логическа функция според таблица за съответствие.

За всеки ред от справочната таблица, в която функцията е равна на нула, се компилира елементарна дизюнкция на всички променливи. В този случай самата променлива се включва в дизюнкцията, ако нейната стойност е равна на нула, или отрицание, ако стойността й е равна на единица. Получените елементарни дизюнкции се обединяват от знака за свързване.

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

За първия ред на таблицата, който съответства на нулевия набор на функцията 000, намираме съставната на нула. След като извършихме подобни операции за втория, третия и петия ред, ние дефинираме желаната перфектна CNF функция:

Трябва да се отбележи, че за функции, чийто брой набори от единици надвишава броя на нулевите набори, е по-компактно да ги запишете под формата на SKNF и обратно.

Нормални форми на логически функции Представянето на булева функция под формата на дизюнкция на конюнктивни членове на съставните части на единицата Ki 2.7 се нарича дизюнктивна нормална форма на DNF на тази функция. съдържат точно една по една всички логически променливи, взети с отрицания или без тях, тогава тази форма на представяне на функцията се нарича идеалната дизюнктивна нормална форма на SDNF на тази функция. Както можете да видите, когато компилирате функцията SDNF, трябва да направите дизюнкция на всички митерми, за които функцията приема стойност 1.

Ако тази работа не ви устройва, в долната част на страницата има списък с подобни произведения. Можете също да използвате бутона за търсене

Лекция 1.xx

Нормални форми на логически функции

Представяне на булева функция под формата на дизюнкция на конюнктивни термини (съставна единица)К и

, (2.7)

Наречен дизюнктивна нормална форма(DNF) на тази функция.

Ако всички конюнктивни термини в DNF саминтерми , тоест те съдържат точно една по една всички логически променливи, взети с отрицания или без тях, тогава тази форма на представяне на функцията се наричаперфектна дизюнктивна нормална форма(SDNF ) на тази функция. SDNF се наричаперфектно защото всеки член в дизюнкция включва всички променливи;дизюнктивно тъй като основната операция във формулата е дизюнкция. Концепцията "нормална форма„Означава недвусмислен начин за писане на формула, която изпълнява дадена функция.

С оглед на горното, теорема 2.1 предполага следната теорема.

Теорема 2. Всяка булева функция(не е идентично равно на 0) могат да бъдат изпратени на SDNF, .

Пример 3. Нека имаме функция, дефинирана от таблица f (x 1, x 2, x 3) (Таблица 10).

Таблица 10

Въз основа на формула (2.6) получаваме:

Както можете да видите, когато компилирате функцията SDNF, трябва да съставите дизюнкция от всички митерми, за които функцията приема стойност 1.

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

, (2.8)

Наречен конюнктивна нормална форма(CNF) тази функция.

Ако всички дизюнктивни CNF термини са makstermas , т.е. съдържат точно една логична функционални променлививзети със или без отрицания, тогава такъв CNF се наричаперфектен конюнктив нормална форма(SKNF) тази функция.

Теорема 3. Всяка булева функция(не е еднакво идентично 1) може да бъде представен в SKNF, освен това такова представяне е единственото.

Доказателството на теоремата може да се извърши подобно на доказателството на теорема 2.1 въз основа на следната лема на Шанън относно конюнктивното разлагане.

Лемата на Шанън ... Всяка булева функция f (x 1, x 2, ..., x m) от m променливите могат да бъдат представени по следния начин:

. (2.9)

Трябва да се отбележи, че и двете форми на представяне на логическа функция (DNF и CNF) са теоретично еднакви по своите възможности: всяка логическа формула може да бъде представена както в DNF (с изключение на идентичната нула), така и в CNF (с изключение на идентичната единица ). В зависимост от ситуацията представянето на функцията в една или друга форма може да бъде по-кратко.

На практика най-често се използва DNF, тъй като тази форма е по-позната на човек: от детството той е по-свикнал да добавя произведения, отколкото да умножава суми (в последният случайтой интуитивно има желание да отвори скобите и по този начин да отиде в DNF).

Пример 4. За функцията f (x 1, x 2, x 3 ) дадено от табл. 10, напишете го на SKNF.

За разлика от SDNF, когато компилирате SCNF в таблицата на истинността на логическа функция, трябва да разгледате комбинациите от променливи, за които функцията приема стойността 0, и да съставите конюнкцията от съответните максимални термини,но променливите трябва да се вземат с обратна инверсия:

Трябва да се отбележи, че е невъзможно да се премине директно от функцията SDNF към нейния SKNF или обратно. Опитът за такива трансформации води до обратни функции на желаните. Изразите за функциите SDNF и SKNF могат да бъдат получени директно само от неговата таблица на истинността.

Пример 5. За функцията f (x 1, x 2, x 3 ) дадено от табл. 10, опитайте се да преминете от SDNF към SKNF.

Използвайки резултата от пример 2.3, получаваме:

Както можете да видите, при общата инверсия се получава SKNF на логическата функция, която е обратна по отношение на функцията, получена в пример 2.4:

тъй като съдържа всички maxterms, които не са в израза за SKNF на разглежданата функция.

1. Използвайки свойствата на операциите (виж Таблица 9) идентичност (), сума по модул 2 (), импликация (), преминаваме към операциите И, ИЛИ, НЕ (в булева база).

2. Използвайки свойствата на отрицанието и законите на де Морган (виж Таблица 9), постигаме, че операциите на отрицание се отнасят само до отделни променливи, а не до цели изрази.

3. Използвайки свойствата на логическите операции И и ИЛИ (виж Таблица 9), получаваме нормалната форма (DNF или CNF).

4. Ако е необходимо, отидете на перфектните форми (SDNF или SKNF). Например, за да получите SKNF, често трябва да използвате свойството:.

Пример 6. Преобразуване на булева функция в SKNF

Изпълнявайки стъпките от горния алгоритъм по ред, получаваме:

Използвайки свойството на абсорбция, получаваме:

Така получихме CNF функциите f (x 1, x 2, x 3 ). За да получите неговия SKNF, трябва да повторите всяка дизюнкция, в която липсва променлива, два пъти - с тази променлива и с нейното отрицание:

2.2.6. Минимизиране на булевите функции

Тъй като същата логическа функция може да бъде представена катос лични формули, след което намиране на най-простото фоР mule, който дефинира булева функция, опростява логическата схема, която реализира булева функция.към ция. Минимална форма lО геоложка функцияв някаква основа можем да приемем, че съдържа минималния брой суперпозиции на функциятаДа се основа, включително скоби. Трудно е обаче да се изгради ефективен ал алгоритъм за такова минимизиране с получаване на минималната скобар ние.

Нека разгледаме по-прост проблем за минимизиране при синтеза на комбинационни схеми, в който се търси не минималната форма на скоба на функция, а нейната минимална DNF. Има прости, ефективни алгоритми за тази задача.

Методът на Куайн

Функцията, която трябва да бъде минимизирана, е представена в SDNF и към нея се прилагат всички възможни операции на непълно залепване

, (2.10)

и след това усвояване

, (2.11)

и тази двойка стъпки се прилага многократно. По този начин е възможно да се понижи ранга на термините. Тази процедура се повтаря, докато не остане термин, който може да бъде залепен към друг термин.

забележи това лява странаУравненията (2.10) могат незабавно да бъдат минимизирани по по-прост и по-очевиден начин:

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

Трябва да се отбележи, че методът на Куайн отнема доста време, така че вероятността от грешки по време на трансформациите е доста висока. Но предимството му е, че на теория може да се използва за произволен брой аргументи и с увеличаване на броя на променливите преобразуванията стават по-малко сложни.

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

Методът на Карно карти (таблици) е по-визуален, по-малко трудоемък и надежден начин за минимизиране на логическите функции, но използването му е практически ограничено до функции от 3-4 променливи, максимум - 5-6 променливи.

Карно Карно Представлява двуизмерна таблична форма за представяне на таблицата на истинността на булева функция, която ви позволява лесно да намерите минималния DNF от логически функции в графична визуална форма. Всяка клетка от таблицата е свързана с минимизираната функция на SDNF, така че всяка ос на симетрия на таблицата съответства на зони, които са взаимно инверсни във всяка променлива. Това подреждане на клетките в таблицата улеснява определянето на залепващите SDNF термини (различни по знака на инверсия само на една променлива): те са подредени симетрично в таблицата.

Таблици на истинността и карти на Karnot за функциите И и ИЛИ на две лентид променливите са показани на фиг. 8. Във всяка клетка на картата е изписан знака функция на аргумента, съответстващ на тази клетка n Другарю

А) И б) ИЛИ

Ориз. осем. Пример за карти на Карно за функции на две променливи

Има само една 1 в картата на Karnot за функцията And, така че тя не може да бъде залепена към нищо. Изразът за минималната функция ще съдържа само термина, съответстващ на това 1:

f = x y.

В картата на Karnot за функцията OR вече има три 1 и е възможно да се направят две двойки залепване, като 1 съответства на термина xy , се използва два пъти. В израза за минималната функция трябва да напишете термините за двойките, които ще бъдат залепени, като оставите в тях всички променливи, които не се променят за тази двойка, и премахнете променливите, които променят стойността си. За хоризонтално залепване получавамех , а за вертикално -г , като резултат получаваме израза

f = x + y.

На фиг. 9 показва таблици на истинност на две функции на три променливи (а ) и техните карти на Karnot (б и в). Функция f 2 се различава от първия по това, че не е дефиниран за три набора от променливи (това е обозначено с тире в таблицата).

При определяне на минималния DNF на функция се използват следните правила. Всички клетки, съдържащи 1, се обединяват в затворени правоъгълни области, които се наричат k -кубове, където k = log 2 K, K - количество 1 в правоъгълна площ. Освен това всяка област трябва да бъде правоъгълник с 2 клетки k, където k = 0, 1, 2, 3,…. За k = 1 правоъгълник се наричаедното е куб и съдържа 2 1 = 2 единици; за k = 2 правоъгълник съдържа 2 2 = 4 единици и се наричадва кубчета; за k = 3 областта на 2 3 = 8 единици се наричатри куб ; и т. н. Могат да бъдат извикани единици, които не могат да бъдат комбинирани в правоъгълницинулеви кубчета които съдържат само една единица (2 0 = 1). Както можете да видите, с дорик площите могат да бъдат квадратни (но не е необходимо) и за нечетник - само правоъгълници.

Ориз. 9. Пример за карти на Карно за функции на три променливи

Тези области могат да се припокриват, тоест могат да влизат едни и същи клетки различни области... Тогава минималният DNF на функцията се записва като дизюнкция на всички конюнктивни термини, съответстващи на k - кубчета.

Всеки от посочените региони на картата на Karnot е представен в минималния DNF чрез конюнкция, броят на аргументите в която ек по-малко от общия брой аргументи на функциятам , тоест това число е равно нам - к ... Всяка конюнкция на минималния DNF се състои само от онези аргументи, които за съответната област на картата имат стойности или без инверсии, или само с инверсии, тоест не променят стойностите си.

По този начин, когато покривате клетките на картата със затворени области, трябва да се стремим да гарантираме, че броят на областите е минимален и всяка област съдържа възможно най-голям брой клетки, тъй като в този случай броят на членовете в минималния DNF ще бъде минимален и броят на аргументите в съответната връзка ще бъде минимален.

За функцията Karnot map на фиг. 9,намираме

тъй като за горната затворена област променливитех 1 и х 2 материя без инверсии, за нисшитех 1 въпроси с инверсия и x 3 - няма инверсия.

Недефинираните стойности в картата на фиг. 9, v може да бъде удължен, като го замените с нула или единица. За тази функция може да се види, че е по-изгодно двете недефинирани стойности да се заменят с 1. В този случай се образуват два региона, които са различни видове 2 кубчета. Тогава изразът за минималната DNF функция ще бъде както следва:

При конструиране на затворени зони е позволено да се свие картата на Карно в цилиндър както хоризонтално, така и вертикално.Р тичните оси с обединението на противоположните ръбове наР вие, тоест единиците, разположени в краищата на картата на симетрията на Карноз но може и да се комбинира.

Картите на Karnaugh могат да бъдат начертани по различни начини (Фигура 10).

а б

Ориз. 10. Различни начини за рисуване на карти на Карно
за функция от 3 променливи

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

а б

Ориз. единадесет. Най-удобното изображение на Karnot Maps
за функции 3 (а) и 4 (б) променливи

За функции от 5 и 6 променливи, методът, показан на фиг. 10, v .

Ориз. 12. Изображение на картата на Karnot за функция от 5 променливи

Ориз. тринадесет. Изображение на картата на Карно за функция от 6 променливи