Съединителна нормална форма на логическа функция. Нормални форми на логически функции

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

Енциклопедичен YouTube

• 1 / 5

  Формули в KNF:

  ¬ A ∧ (B ∨ C), (\displaystyle \neg A\клин (B\vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E) , (\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge ( D\vee\neg E),) A∧B. (\displaystyle A\wedge B.)

  Формули не в KNF:

  ¬ (B ∨ C) , (\displaystyle \neg (B\vee C),) (A ∧ B) ∨ C , (\displaystyle (A\wedge B)\vee C,) A ∧ (B ∨ (D ∧ E)) . (\displaystyle A\клин (B\vee (D\клин E)).)

  Но тези 3 формули, които не са в CNF, са еквивалентни на следните формули в CNF:

  ¬ B ∧ ¬ C , (\displaystyle \neg B\wedge \neg C,) (A ∨ C) ∧ (B ∨ C) , (\displaystyle (A\vee C)\wedge (B\vee C),) A ∧ (B ∨ D) ∧ (B ∨ E) . (\displaystyle A\клин (B\vee D)\клин (B\vee E).)

  Изграждане на CNF

  Алгоритъм за конструиране на CNF

  1) Отървете се от всички логически операции, съдържащи се във формулата, като ги замените с основните: конюнкция, дизюнкция, отрицание. Това може да се направи с помощта на еквивалентни формули:

  A → B = ¬ A ∨ B , (\displaystyle A\rightarrow B=\neg A\vee B,) A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B) . (\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \neg B).)

  2) Заменете знака за отрицание, отнасящ се до целия израз, със знаци за отрицание, отнасящи се до отделни променливи изрази въз основа на формулите:

  ¬ (A ∨ B) = ¬ A ∧ ¬ B , (\displaystyle \neg (A\vee B)=\neg A\wedge \neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B . (\displaystyle \neg (A\wedge B)=\neg A\vee \neg B.)

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

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

  Пример за конструкция на CNF

  Нека пренесем формулата в CNF

  F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) . (\displaystyle F=(X\дясна стрелка Y)\клин ((\neg Y\дясна стрелка Z)\дясна стрелка \neg X).)

  Нека трансформираме формулата F (\displaystyle F)към формула, която не съдържа → (\displaystyle \rightarrow ):

  F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ Y ∨ Z) ​​​​∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\клин (\neg (\neg Y\rightarrow Z)\vee \neg X)=(\neg X\vee Y)\клин (\neg (\neg \ neg Y\vee Z)\vee \neg X).)

  В получената формула прехвърляме отрицанието към променливите и намаляваме двойните отрицания:

  F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X).)

  Например следната формула е написана на 2-CNF:

  (A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . (\displaystyle (A\или B)\земя (\neg B\или C)\земя (B\или \neg C).)

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

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

  веднъж.

  Дизюнктивна нормална форма(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 и SCNF.

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

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

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

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

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

  Пример 10.Доведете KNF до SKNF:

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

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

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

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

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

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

  Пример 12.Намерете SDNF и SCNF, като използвате таблицата на истината за формулата от пример 6.

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

  Таблица 14

  х	г	z

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

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

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

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

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

  Например,– ДНФ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  Методи за намиране на SDNF

  1-ви метод

  2-ри метод

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

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

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

  Методи за намиране на SCNF

  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 и следователно ще бъде желаната перфектна конюнктивна нормална форма (PCNF):

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

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

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

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

  а) ;

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

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

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

  б) ;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  или

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

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

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

  г) преход от КНФ към СКНФ

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

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

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

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

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

  Тук ще се обадим буквален променлива 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 може да се установи от следните съображения. Да предположим, че всяка от трите стандартни бизнес функции е представима с формула върху F . Тогава по теорема 1.3 тъждеството F ще бъде пълно.

  Пример 1.3.Наборът от операции по модул 2 събиране, умножение и константа 1 се извиква Zhegalkin основа . Събирането по модул 2 и умножението са основните операции на пръстена Z2; изразите, съставени с тяхна помощ, са полиноми върху пръстена Z2. Константата 1 в този случай е необходима за запис на свободния термин. Тъй като xx = 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.Основата, състояща се от една функция, стрелката на Пърс, също е завършена. Тестът за това е подобен на случая с инсулт на Schaeffer. Това заключение обаче може да се направи и въз основа на принципа на двойствеността за симетричните полупръстени.

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