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

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

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

Лекция 1.xx

Нормални форми на булеви функции

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

, (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 i

, (2.8)

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

Ако всички дизюнктивни термини на CNF са maxterms , т.е. съдържат точно една по една всички логически променливи на функцията, взети със или без отрицания, тогава такава 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, когато компилирате SKNF, в таблицата на истината на логическа функция трябва да разгледате комбинации от променливи, за които функцията приема стойност 0, и да направите връзка на съответните maxterms,но променливите трябва да се вземат с обратна инверсия:

Трябва да се отбележи, че е невъзможно да се премине директно от 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, което дефинира булева функция, опростява логическата схема, която имплементира булевата функцияда tsyu. Минимална форма lО логическа функцияв някакъв базис, можем да разгледаме такъв базис, който съдържа минималния брой суперпозиции на funcДа се основа, допускане и скоби. Въпреки това е трудно да се изгради ефективенл алгоритъмът на такова минимизиране с получаване на минималната скоба fo r ние.

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

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

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

, (2.10)

и след това абсорбция

, (2.11)

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

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

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

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

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

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

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

Таблици на истината и карти на Карно за И и ИЛИ функции на две лентид Променливите са представени на фиг. 8. Във всяка клетка на картата се записва стойност.А стойността на функцията върху набора от стойности на аргумента, съответстващ на тази клетка n тов.

А) И б) ИЛИ

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

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

f = x y .

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

f = x + y.

На фиг. 9 показва таблиците на истината на две функции на три променливи (А ) и техните карти на Karnot ( b и c). Функция 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 - кубчета.

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

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

За функцията според картата на Карно на фиг. 9, b намираме

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

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

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

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

а б

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

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

а б

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

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

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

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

стандартна основа. Елементарните формули са литерали. Елементарна конюнкция (дизюнкция). Дизюнктивна (конюнктивна) нормална форма и перфектна форма. Теорема: всяка булева функция, различна от 0 (от 1), може да бъде представена като SDNF (SKNF). Пълнота на стандартната основа. Примери за пълни бази: базата на Жегалкин, ударът на Шефър, стрелата на Пиърс.

Стандартна основа е набор от три първоначални операции на булева алгебра: събиране (обединение), умножение (пресичане) и отрицание.

Тук ще се обадим буквален променлива x или нейното отрицание x и означаваме xˆ. Булева пресечна точка на множество литерали, дефинирани от различни променливи, т.е. израз от вида X = xˆ 1 xˆ 2 . . . xˆ l, се нарича елементарен съюз . Изискването всички променливи да са различни се дължи на следното. Ако връзката включва няколко еднакви литерала, тогава поради комутативността, асоциативността и идемпотентността на връзката, преминавайки към еквивалентна формула, можем да оставим само един литерал (например x 1 x 1 = x 1). Ако връзката включва променлива и нейното отрицание, тогава формулата е еквивалентна на константата 0, тъй като x x = 0 и за всяка формула Y имаме Y x x = 0.

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

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5.

Ако съставът на променливите във всяка елементарна връзка на дадена DNF е еднакъв, тогава DNF се нарича перфектен . Даденият пример е DNF, който не е съвършен. Напротив, формулата

x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4

е идеалната форма.

Тъй като в булевата алгебра събирането и умножението са симетрични операции и човек винаги може да тълкува събирането като умножение и умножението като събиране, има и двойна концепция - конюнктивна нормална форма (KNF ), което е конюнкция на елементарни дизюнкции и перфектна съчинителна форма (SKNF ). От принципа на двойствеността за симетричните полупръстени следва, че всяко твърдение за DNF съответства на двойствено твърдение за CNF, което се получава чрез замяна на добавяне (дизюнкция) с умножение, умножение (конюнкция) със събиране, константа 0 с константа 1, константа 1 чрез константа 0, връзка на реда чрез двойна (обратна) в ред. Следователно по-нататък ще се съсредоточим върху изучаването само на DNF.

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

◀Нека се съгласим с x σ да означаваме формулата x, ако σ = 1, и формулата x, ако σ = 0. Нека функцията f(y 1 , . . . , y n) приеме стойност 1 на вектора (t 1 , . . ., t n ) (такъв вектор се нарича съставна единица ). Тогава елементарната конюнкция също приема стойност 1 в това множество, но изчезва във всички други n-мерни булеви вектори. Помислете за формулата

в която сумата (обединението) се простира върху всички набори (t 1, . . . , t n) от стойности на аргументи, върху които дадената функция приема стойност 1. Имайте предвид, че наборът от такива набори не е празен, така че сборът съдържа поне един член.

Лесно се вижда, че формулата Φ се превръща в 1 за тези и само за тези стойности на променливите, за които разглежданата функция се превръща в 1. Следователно формулата Ψ представлява функцията f.

Следствие 1.1.Стандартната основа е завършена.

◀ Наистина, ако дадена функция не е константа 0, тогава тя може да бъде представена или като SDNF, което е формула върху стандартен базис. Константата 0 може да бъде представена например чрез формулата f(x 1 , x 2 , . . . , x n) = x 1 x 1 .

Пример 1.2.Да разгледаме функция от три променливи m(x 1 , x 2 , x 3) (Таблица 1.4), наречена мажоритарна функция ̆. Тази функция дава оценка на 1, ако повече от половината от нейните аргументи имат стойност 1. Поради това често се нарича функция за гласуване. Нека изградим SDNF за него.

Пълнотата на стандартната основа позволява да се изберат други пълни системи от функции. Пълнотата на множеството F може да се установи от следните съображения. Да предположим, че всяка от трите стандартни функции на buzzis е представима с формула върху F . Тогава, по силата на теорема 1.3, другостта на F ще бъде пълна.

Пример 1.3.Наборът от операции по модул 2 събиране, умножение и константа 1 се извиква основата на Жегалкин . Събиране и умножение по модул 2 са основните операции на пръстена Z2, изразите, съставени с тяхна помощ, са полиноми над пръстена Z2. Константата 1 в този случай е необходима за запис на свободния член. Тъй като xx \u003d x, тогава всички фактори в полинома имат степен 1. Следователно, когато пишете полином, можете да правите без концепцията за степен. Примери за формули над основата на Жегалкин:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Всяка такава формула се нарича полином на Жегалкин. Всъщност полиномът на Жегалкин е полином над пръстена Z2.

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

x+y=x⊕y⊕xy, x=x⊕1.

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

(по-точно до реда на термините). Коефициентите на полинома на Жегалкин с малък брой променливи могат да бъдат намерени по метода на неопределените коефициенти.

Пример 1.4.Помислете за набор от една единствена функция - щрихът на Шефер*. Този набор е пълен, което следва от следните лесно проверени самоличности:

x=x|x, xy=x|y=(x|y)|(x|y), x+y=x |y=(x|x)|(y|y).

Пример 1.5.Основата, състояща се от една единствена функция, стрелката на Пиърс, също е завършена. Проверката на това е подобна на случая с простото число на Шефер. Това заключение обаче може да се направи и въз основа на принципа на дуалността за симетричните полупръстени.

*Щрихът на Шафер е двоична операция, но не и асоциативна. Ето защо, когато използвате инфикс формата, трябва да внимавате: резултатът зависи от реда, в който се извършват операциите. В този случай се препоръчва изрично да се посочи редът на операциите, като се използват скоби, например напишете (x | y) | z, а не x | y | z, въпреки че и двете форми са еквивалентни.

Определение 1.Съединителен моном (елементарна връзка)от променливи се нарича конюнкция на тези променливи или техните отрицания.

Например, е елементарен съюз.

Определение 2.Дизюнктивен моном (елементарна дизюнкция)от променливи се нарича дизюнкция на тези променливи или техните отрицания.

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

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

Например,- DNF.

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

Например, – KNF.

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

Алгоритъм за построяване на нормални форми

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

Отървете се от двойните негативи.

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

2.6. Перфектни дизюнктивни и перфектни конюнктивни нормални форми

Всяка булева функция може да има много DNF и CNF представяния. Специално място сред тези представяния заемат перфектната DNF (SDNF) и перфектната CNF (SKNF).

Определение 1. Перфектна дизюнктивна нормална форма(SDNF) е DNF, в който всеки конюнктивен моном съдържа всяка променлива от множеството точно веднъж и влиза или самият той, или неговото отрицание.

Структурно SDNF за всяка формула на пропозиционалната алгебра, редуцирана до DNF, може да се дефинира, както следва:

Определение 2. Перфектна дизюнктивна нормална форма(SDNF) на формула на пропозиционална алгебра се нарича нейната DNF, която има следните свойства:

Определение 3. Перфектен конюнктив нормална форма(SKNF) е CNF, в която всеки дизюнктивен моном съдържа всяка променлива от множеството точно веднъж и влиза или самият той, или неговото отрицание.

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

Определение 4. Перфектен конюнктив нормална форма(SKNF) на дадена формула на пропозиционална алгебра е нейната CNF, която удовлетворява следните свойства.

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

Начини за намиране на SDNF

1-ви начин

2-ри начин

изберете редовете, където формулата приема стойност 1;

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

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

Начини за намиране на SKNF

1-ви начин– с помощта на еквивалентни трансформации:

2-ри начин- използване на таблици на истината:

изберете редовете, където формулата приема стойност 0;

съставяме конюнкция от дизюнкции, при условие че ако променливата е включена в дизюнкцията със стойност 0, тогава записваме тази променлива, ако със стойност 1, тогава нейното отрицание. Получаваме SKNF.

Пример 1Начертайте CNF функциите.

Решение

Елиминирайте връзката "", като използвате законите за трансформация на променливи:

= /законите на де Морган и двойното отрицание/ =

/разпределителни закони/ =

Пример 2Преобразувайте формулата в DNF.

Решение

Ние изразяваме логическите операции по отношение на и:

= /Свържете отрицанието с променливите и намалете двойните отрицания/ =

= /закон за дистрибутивност/ .

Пример 3Напишете формулата в DNF и SDNF.

Решение

Използвайки законите на логиката, свеждаме тази формула до форма, съдържаща само дизюнкции на елементарни връзки. Получената формула ще бъде желаната DNF:

За да изградим SDNF, ще съставим таблица на истината за тази формула:

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

ред 1: ;

ред 3: ;

ред 5: .

Дизюнкцията на тези три формули ще приеме стойност 1 само върху наборите от променливи в редове 1, 3, 5 и следователно ще бъде необходимата идеална дизюнктивна нормална форма (PDNF):

Пример 4Донесете формулата на SKNF по два начина:

а) с помощта на еквивалентни трансформации;

б) използване на таблица на истината.

Решение:

Преобразуваме втората елементарна дизюнкция:

Формулата изглежда така:

б) съставете таблица на истинност за тази формула:

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

ред 2: ;

ред 6: .

Конюнкцията на тези две формули ще приеме стойност 0 само за наборите от променливи в редове 2 и 6 и следователно ще бъде желаната перфектна конюнктивна нормална форма (CKNF):

Въпроси и задачи за самостоятелно решаване

1. Използвайки еквивалентни трансформации, приведете формулите към DNF:

2. Използвайки еквивалентни трансформации, пренесете формулите в CNF:

3. Използвайки втория закон за разпределение, преобразувайте DNF в CNF:

а) ;

4. Преобразувайте дадените DNF в SDNF:

5. Преобразувайте дадения CNF в SKNF:

6. За дадените логически формули конструирайте SDNF и SKNF по два начина: с помощта на еквивалентни трансформации и с помощта на таблицата на истината.

б) ;

Дизюнктивни и конюнктивни нормални форми на пропозиционалната алгебра.За всяка функция на пропозиционалната логика може да се състави таблица на истината. Обратната задача също винаги е разрешима. Нека въведем няколко определения.

Елементарни съюзи (съюзни)се наричат ​​конюнкции на променливи или техните отрицания, в които всяка променлива се среща най-много

веднъж.

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

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

Съединителна нормална форма(CNF) е формула, която има формата на конюнкция на елементарни дизюнкции.

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

Алгоритъм за изграждане на DNF:

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

2. Преминете към формули с близки отрицания, т.е. към формула, в която отрицанията са разположени не по-високо от над променливите - приложете законите на де Морган.

3. Отворете скобите - приложете законите на дистрибутивността.

4. Повтарящи се термини, за да вземе едно време - законът за идемпотентността.

5. Приложете законите на абсорбцията и полу-абсорбцията.

Пример 6Намерете DNF формули: .

В Булевата алгебра, принцип на дуалността. Тя е следната.

Функцията се извиква двойственкъм функцията if . Тези. за да се намери функция, двойствена на дадена, е необходимо да се конструира отрицанието на функцията от отрицанията на аргументите.

Пример 7Намерете функцията, двойна на .

Сред елементарните функции на алгебрата на логиката 1 е двойствена към 0 и обратно, x е двойствена към x, е двойствена към , е двойствена към и обратно.

Ако във формулата F 1, представяща функцията, всички съюзи са заменени

върху дизюнкция, дизюнкция върху конюнкция, 1 върху 0, 0 върху 1, тогава получаваме формулата F *, представляваща функцията *, двойствена.

Конюнктивната нормална форма (CNF) е двойна концепция за DNF, така че може лесно да бъде конструирана според схемата:

Пример 8Намерете CNF формули: .

Използвайки резултата от Пример 6, имаме

Перфектни дизюнктивни и перфектни конюнктивни нормални форми.Във всеки от видовете нормални форми (дизюнктивни и конюнктивни) може да се отдели клас перфектни форми на SDNF и SKNF.

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

Всеки DNF може да бъде намален до SDNF чрез разделяне на конюнкции, които не съдържат всички променливи, т.е. добавката за липсващата променлива x i се умножава с помощта на закона за разпределение

Пример 9Намерете SDNF за DNF пример 6

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

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

Пример 10 .Преобразувайте CNF в SKNF:

За да конструирате SKNF, можете да използвате схемата

Пример 11.Намерете SKNF за формулата от пример 6.

Всяка функция има SDNF и освен това е единствената. Всяка функция има SKNF и освен това един .

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

За да се конструира SDNF, е необходимо да се изберат редове, в които F приема стойност 1 и да се запишат перфектни елементарни конюнкции за тях. Ако стойността на променливата в желания ред на таблицата на истината е равна на единица, тогава в перфектния конюнкт тя се приема без отрицание, ако е нула, тогава с отрицание. След това перфектните конюнкти (техният брой е равен на броя на единиците в таблицата) се свързват със знаци за дизюнкция.

За да се изгради SKNF според таблицата на истината, е необходимо да се изберат редове в нея, където F=0, и да се запишат идеални елементарни дизюнкции, след което да се свържат със знаци за връзка. Ако в необходимия ред на таблицата на истината (F=0) стойността на променливата съответства на нула, тогава в перфектния дизюнкт тя се взема без отрицание, ако е равна на единица, тогава с отрицание.

Пример 12.Намерете SDNF и SKNF според таблицата на истината за формулата от пример 6.

Таблица 14 показва само крайната стойност F=10101101. Валидността на това твърдение трябва да бъде проверена независимо чрез конструиране на разширена таблица на истината.

Таблица 14

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

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

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

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

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

Примери: 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 променливи се нарича перфектна дизюнктивна нормална форма (PDNF), ако:
1) формулата е DNF, в която всяка елементарна конюнкция е конюнкция на k променливи x 1 , x 2 , ..., x k , а i-тото място на тази връзка е или променливата x i, или нейното отрицание;
2) всички елементарни конюнкции в такава ДНФ са по двойки различни.

Пример: (¬ 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 променливи се нарича перфектна конюнктивна нормална форма (KDNF), ако:
1) формулата е CNF, в която всяка елементарна дизюнкция е дизюнкция на k променливи x 1 , x 2 , …, x k , а i-тото място на тази дизюнкция е или променливата x i, или нейното отрицание;
2) всички елементарни дизюнкции в такава КНФ са по двойки различни.

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

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

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

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

Алгоритъм за конструиране на СКНФ по таблицата на истината

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

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

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

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

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

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