Se numește forma normală conjunctivă a unei funcții logice. Forme normale de funcții logice

Formă normală formula logică nu conține semne de implicație, echivalență și negare a formulelor neelementare.

Forma normală se prezintă în două forme:

formă normală conjunctivă (CNF)- conjuncția mai multor disjuncții, de exemplu, $ \ left (A \ vee \ overline (B) \ vee C \ right) \ wedge \ left (A \ vee C \ right) $;

formă normală disjunctivă (DNF)- o disjuncție a mai multor conjuncții, de exemplu, $ \ left (A \ wedge \ overline (B) \ wedge C \ right) \ vee \ left (B \ wedge C \ right) $.

SKNF

Formă normală conjunctivă perfectă (SKNF) este un CNF care îndeplinește trei condiții:

nu conține disjuncții elementare identice;

niciuna dintre clauze nu conține aceleași variabile;

fiecare disjuncție elementară conține fiecare variabilă din CNF dat.

Orice formulă booleană care nu este identică în mod identic poate fi reprezentată în SKNF.

Reguli pentru construirea SKNF conform tabelului adevărului

Pentru fiecare set de variabile pentru care funcția este 0, se scrie suma, iar variabilele care au valoarea 1 sunt luate cu negație.

SDNF

Forma normală disjunctivă perfectă (SDNF) este un DNF care îndeplinește trei condiții:

nu conține conjuncții elementare identice;

nici una dintre conjuncții nu conține aceleași variabile;

fiecare conjuncție elementară conține fiecare variabilă din DNF dat, în plus, în aceeași ordine.

Orice formulă booleană care nu este identică falsă poate fi reprezentată în SDNF, în plus, într-un mod unic.

Reguli pentru construirea SDNF conform tabelului adevărului

Pentru fiecare set de variabile pentru care funcția este egală cu 1, se scrie produsul, iar variabilele care au valoarea 0 sunt luate cu negație.

Exemple de găsire a SKNF și SDNF

Exemplul 1

Scrieți o funcție logică în conformitate cu tabelul său de adevăr:

Imaginea 1.

Decizie:

Să folosim regula pentru construirea SDNF:

Figura 2.

Obținem SDNF:

Să folosim regula pentru construirea SKNF.

Forme normale ale funcțiilor logice Reprezentarea unei funcții booleene sub forma unei disjuncții a termenilor conjunctivi ai constituenților unității Ki 2.7 se numește forma normală disjunctivă a DNF a acestei funcții. conține exact una câte una toate variabilele logice luate cu negații sau fără ele, atunci această formă a reprezentării funcției se numește forma normală disjunctivă perfectă a SDNF a acestei funcții. După cum puteți vedea, atunci când compilați funcția SDNF, trebuie să faceți o disjuncție a tuturor mintermelor pentru care funcția preia valoarea 1.

Distribuiți munca pe rețelele sociale

Dacă această lucrare nu vi s-a potrivit în partea de jos a paginii, există o listă de lucrări similare. De asemenea, puteți utiliza butonul de căutare

Lectura 1.xx

Forme normale de funcții logice

Reprezentarea unei funcții booleene sub forma unei disjuncții a termenilor conjunctivi (unitate constitutivă) K i

, (2.7)

numit forma normală disjunctivă(DNF) al acestei funcții.

Dacă toți termenii conjunctivi din DNF sunt minterms , adică conțin exact una câte una toate variabilele logice, luate cu negative sau fără ele, atunci această formă de reprezentare a funcției se numeșteforma normală disjunctivă perfectă(SDNF ) a acestei funcții. SDNF se numește perfect deoarece fiecare termen în disjuncție include toate variabilele; disjunctiv deoarece operația principală din formulă este disjuncția. Conceptul "formă normală”Înseamnă un mod neechivoc de a scrie o formulă care implementează o funcție dată.

Având în vedere cele de mai sus, Teorema 2.1 implică următoarea teoremă.

Teorema 2. Orice funcție booleană(nu identic egal cu 0) poate fi trimis la SDNF, .

Exemplul 3. Să avem o funcție definită în tabel f (x 1, x 2, x 3) (Tabelul 10).

Tabelul 10

			f (x 1, x 2, x 3)

Pe baza formulei (2.6), obținem:

După cum puteți vedea, atunci când compilați funcția SDNF, trebuie să compuneți o disjuncție a tuturor mintermelor pentru care funcția preia valoarea 1.

Reprezentarea unei funcții booleene sub forma unei conjuncții de termeni disjunctivi (constituent al zero) D i

, (2.8)

numit formă normală conjunctivă(CNF) această funcție.

Dacă toți termenii CNF disjunctivi sunt makstermas , adică conțin exact una câte una toate variabilele logice ale funcției, luate cu negații sau fără ele, atunci un astfel de CNF se numeșteforma normală conjunctivă perfectă(SKNF) această funcție.

Teorema 3. Orice funcție booleană(nu este identic identic 1) poate fi reprezentat în SKNF, în plus, o astfel de reprezentare este singura.

Dovada teoremei poate fi efectuată în mod similar demonstrației teoremei 2.1 pe baza următoarei leme Shannon privind descompunerea conjunctivă.

Lema lui Shannon ... Orice funcție booleană f (x 1, x 2, ..., x m) de la m variabilele pot fi reprezentate după cum urmează:

. (2.9)

Trebuie remarcat faptul că ambele forme de reprezentare a unei funcții logice (DNF și CNF) sunt teoretic egale în capacitățile lor: orice formulă logică poate fi reprezentată atât în ​​DNF (cu excepția zero identic), cât și în CNF (cu excepția unității identice ). În funcție de situație, reprezentarea funcției într-o formă sau alta poate fi mai scurtă.

În practică, DNF este cel mai des folosit, întrucât această formă este mai familiară unei persoane: din copilărie este mai obișnuit să adauge lucrări decât să înmulțească sume (în acest din urmă caz, are în mod intuitiv dorința de a deschide parantezele și de a merge astfel la DNF).

Exemplul 4. Pentru funcția f (x 1, x 2, x 3 ) dat de tabel. 10, scrieți-l la SKNF.

Spre deosebire de SDNF, atunci când compilați SCNF în tabelul de adevăr al unei funcții logice, trebuie să vă uitați la combinațiile de variabile pentru care funcția ia valoarea 0 și să compuneți conjuncția maxtermelor corespunzătoare,dar variabilele trebuie luate cu inversare inversă:

Trebuie remarcat faptul că este imposibil să treci direct de la funcția SDNF la SKNF sau invers. Încercarea unor astfel de transformări are ca rezultat funcțiile inverse ale celor dorite. Expresiile pentru funcțiile SDNF și SKNF pot fi obținute direct numai din tabelul său de adevăr.

Exemplul 5. Pentru funcția f (x 1, x 2, x 3 ) dat de tabel. 10, încercați să treceți de la SDNF la SKNF.

Folosind rezultatul Exemplului 2.3, obținem:

După cum puteți vedea, sub inversiunea generală, se obține SKNF a funcției logice, care este inversă față de funcția obținută în exemplul 2.4:

deoarece conține toate maxtermii care nu sunt prezenți în expresia pentru SKNF a funcției luate în considerare.

1. Folosind proprietățile operațiilor (vezi Tabelul 9) identitate (), sum mod 2 (), implicație (), trecem la operațiile ȘI, SAU, NU (în baza booleană).

2. Folosind proprietățile negației și legile lui de Morgan (vezi Tabelul 9), realizăm că operațiile de negare se referă doar la variabile individuale și nu la expresii întregi.

3. Folosind proprietățile operațiilor logice AND și OR (vezi Tabelul 9), obținem forma normală (DNF sau CNF).

4. Dacă este necesar, mergeți la formularele perfecte (SDNF sau SKNF). De exemplu, pentru a obține SKNF, trebuie adesea să utilizați proprietatea :.

Exemplul 6. Convertiți funcția booleană în SKNF

Efectuând pașii algoritmului de mai sus în ordine, obținem:

Folosind proprietatea de absorbție, obținem:

Astfel, am obținut funcțiile CNF f (x 1, x 2, x 3 ). Pentru a obține SKNF, trebuie să repetați fiecare disjuncție, căreia îi lipsește orice variabilă, de două ori - cu această variabilă și cu negația sa:

2.2.6. Minimizarea funcțiilor booleene

Deoarece una și aceeași funcție logică poate fi reprezentată de s formule personale, găsind apoi cel mai simplu pho R mule, care definește o funcție booleană, simplifică circuitul logic care implementează funcția booleană. la tion. Forma minimă l despre funcția geologicăîntr-o anumită bază, putem presupune că conține numărul minim de suprapuneri ale funcției la bază, inclusiv paranteze. Cu toate acestea, este dificil să construiești un efectiv l un algoritm pentru o astfel de minimizare cu obținerea parantezei minime noi.

Să luăm în considerare o problemă de minimizare mai simplă în sinteza circuitelor combinaționale, în care nu se caută forma paranteză minimă a unei funcții, ci DNF-ul său minim. Există algoritmi simpli și eficienți pentru această sarcină.

Metoda lui Quine

Funcția care trebuie minimizată este reprezentată în SDNF și i se aplică toate operațiunile posibile de lipire incompletă

, (2.10)

și apoi preluare

, (2.11)

iar această pereche de pași se aplică de mai multe ori. Astfel, este posibilă scăderea rangului termenilor. Această procedură se repetă până când nu rămâne niciun termen care să poată fi lipit de niciun alt termen.

Rețineți că partea stângă a ecuației (2.10) ar putea fi imediat minimizată într-un mod mai simplu și mai evident:

Această metodă este proastă prin faptul că, cu o astfel de minimizare directă, termenii conjunctivi fie dispar, deși există încă cazuri de utilizare a acestora pentru lipire și absorbție cu termenii rămași.

Trebuie remarcat faptul că metoda lui Quine consumă destul de mult timp, deci probabilitatea de a greși în timpul transformărilor este destul de mare. Dar avantajul său este că, în teorie, poate fi folosit pentru orice număr de argumente și, pe măsură ce numărul variabilelor crește, conversiile devin mai puțin complicate.

Metoda hărții Karnaugh

Metoda hărților (tabelelor) Karnaugh este o modalitate mai vizuală, mai puțin laborioasă și mai fiabilă de minimizare a funcțiilor logice, dar utilizarea sa este practic limitată la funcții de 3-4 variabile, maxim - 5-6 variabile.

Harta Carnot Este o formă tabulară bidimensională de reprezentare a tabelului de adevăr al unei funcții booleene, care vă permite să găsiți cu ușurință DNF minim al funcțiilor logice într-o formă vizuală grafică. Fiecare celulă a tabelului se potrivește cu termenul de funcție SDNF care urmează să fie minimizat, astfel încât orice axă de simetrie a tabelului să corespundă zonelor care sunt reciproc inverse într-o anumită variabilă. Această dispunere a celulelor din tabel face mai ușoară determinarea termenilor de lipire SDNF (diferind în semnul de inversare al unei singure variabile): sunt aranjate simetric în tabel.

Tabelele de adevăr și hărțile Karnaugh pentru funcțiile ȘI ȘI SAU pe două benzi e variabilele sunt prezentate în Fig. 8. În fiecare celulă a cardului, este scris un semn dar funcționează pe argumentul corespunzător acestei celule n tovarăș

A) ȘI b) SAU

Smochin. opt. Un exemplu de hărți Karnot pentru funcțiile a două variabile

Există doar un 1 în harta Karnot pentru funcția ȘI, deci nu poate fi lipit de nimic. Expresia pentru funcția minimă va conține doar termenul corespunzător acestui 1:

f = x y.

În harta Karnot pentru funcția SAU, există deja trei 1 și puteți face două perechi de lipire, cu 1 corespunzător termenului X y , este folosit de două ori. În expresia funcției minime, trebuie să scrieți termenii pentru perechile care trebuie lipite, lăsând în ele toate variabilele care nu se modifică pentru această pereche și eliminând variabilele care își schimbă valoarea. Pentru lipirea orizontală obținem X , și pentru vertical - y , ca rezultat, obținem expresia

f = x + y.

În fig. 9 prezintă tabele de adevăr cu două funcții din trei variabile ( dar ) și hărțile lor Karnot ( b și c). Funcția f 2 diferă de prima prin faptul că nu este definită pe trei seturi de variabile (acest lucru este indicat de o liniuță în tabel).

La determinarea DNF minim al unei funcții, sunt utilizate următoarele reguli. Toate celulele care conțin 1 sunt combinate în zone dreptunghiulare închise numite k -cuburi, unde k = log 2 K, K - numărul 1 într-o zonă dreptunghiulară. Mai mult, fiecare zonă ar trebui să fie un dreptunghi cu 2 celule k, unde k = 0, 1, 2, 3,…. Pentru k = 1 dreptunghi se numește unul este un cub și conține 2 1 = 2 unități; pentru k = 2 dreptunghi conține 2 2 = 4 unități și se numește două-cub; pentru k = 3 regiunea 2 3 = 8 unități se numește trei-cub ; și așa mai departe. Unitățile care nu pot fi combinate în dreptunghiuri pot fi numite zero-cuburi care conțin o singură unitate (2 0 = 1). După cum puteți vedea, cu egal k zonele pot fi pătrate (dar nu sunt necesare) și pentru un ciudat k - doar dreptunghiuri.

						b c

Smochin. nouă. Un exemplu de hărți Karnot pentru funcțiile a trei variabile

Aceste zone se pot suprapune, adică aceleași celule pot intra în zone diferite. Atunci DNF minim al funcției este scris ca o disjuncție a tuturor termenilor conjunctivi corespunzători k - cuburi.

Fiecare dintre regiunile indicate pe harta Karnot este reprezentată în DNF minim printr-o conjuncție, numărul de argumente în care este k mai puțin decât numărul total de argumente funcționale m , adică acest număr este egal cu m - k ... Fiecare conjuncție a DNF minim este compusă numai din acele argumente care pentru aria corespunzătoare a hărții au valori fie fără inversiuni, fie numai cu inversiuni, adică nu le schimbă valorile.

Astfel, atunci când acoperim celulele hărții cu zone închise, trebuie să ne străduim să ne asigurăm că numărul de zone este minim și fiecare zonă conține cel mai mare număr posibil de celule, deoarece în acest caz numărul de membri din DNF minim va fi să fie minim, iar numărul argumentelor în conjuncția corespunzătoare va fi minim.

Pentru funcția de hartă Karnot din Fig. nouă, găsim

întrucât pentru zona închisă superioară variabilele x 1 și x 2 materie fără inversiuni, pentru cea inferioară x 1 contează cu inversarea și x 3 - fără inversare.

Valorile nedefinite din harta din Fig. nouă,în poate fi extins prin înlocuirea acestuia cu zero sau unul. Pentru această funcție, se poate observa că este mai avantajos să înlocuiți ambele valori nedefinite cu 1. În acest caz, se formează două regiuni care sunt diferite tipuri de 2 cuburi. Apoi, expresia pentru funcția DNF minimă va fi după cum urmează:

Când se construiesc zone închise, este permisă prăbușirea hărții Karnaugh într-un cilindru atât orizontal cât și vertical. R axe tice cu uniunea marginilor opuse ale R tu, adică unitățile situate la marginile hărții de simetrie Carnot h dar, poate fi combinat și.

Hărțile Karnaugh pot fi desenate în moduri diferite (Figura 10).

									x 2 x 3

a b

Smochin. 10. Diferite moduri de a desena hărți Karnaugh
pentru o funcție de 3 variabile

Dar cele mai convenabile variante ale hărților Karnot pentru funcții de 2-4 variabile sunt prezentate în Fig. 11 tabele, pentru că în ele, pentru fiecare celulă, dar toate variabilele sunt sub formă directă sau inversă.

a b

Smochin. unsprezece. Cea mai convenabilă imagine a hărților Karnot
pentru funcțiile 3 ( a) și 4 (b) variabile

Pentru funcții de 5 și 6 variabile, metoda prezentată în Fig. 10,în.

Smochin. 12. Imagine a hărții Karnot pentru o funcție de 5 variabile

Smochin. 13. Imagine a hărții Karnot pentru o funcție de 6 variabile

Alte lucrări similare care vă pot interesa
9020.		PRINCIPIU DE DUALITATE. EXTINDEREA FUNCȚIILOR BOOLEANE ÎN VARIABILE. FORME NORMALE DISJUNCTIVE ȘI CONJUNCTIVE PERFECTE	96,34 KB
	Această teoremă este de natură constructivă, deoarece permite fiecărei funcții să construiască o formulă care o implementează sub forma unui DN perfect. f. Pentru a face acest lucru, în tabelul adevărului pentru fiecare funcție, marcăm toate liniile în care
6490.		Descrierea și minimizarea funcțiilor logice	187,21 KB
	În formă verbală, se exprimă relația dintre argumentele unei funcții și valorile acesteia. Exemplu: O funcție de trei argumente ia o valoare atunci când oricare dintre două sau mai multe dintre argumentele funcției sunt egale. Constă în construirea unui tabel de adevăr care conține valorile funcției pentru toate seturile de valori ale argumentelor. În acest exemplu, conform tabelului adevărului, obținem o astfel de intrare sub forma DNF ...
6707.		Proiectarea bazelor de date relaționale. Probleme de proiectare în abordarea clasică. Principii de normalizare, forme normale	70,48 KB
	Ce este un proiect de bază de date relațională Acesta este un set de relații interdependente în care sunt definite toate atributele, sunt specificate cheile principale ale relației și sunt specificate unele proprietăți suplimentare ale relației care se referă la principiile menținerii integrității. Prin urmare, proiectarea bazei de date trebuie să fie foarte precisă și verificată. De fapt, proiectul bazei de date este fundamentul viitorului pachet software care va fi folosit mult timp și de mulți utilizatori.
4849.		Forme și metode de exercitare a funcțiilor de stat	197,3 KB
	Termenul „funcție” are departe de același sens în literatura științifică rusă și străină. În termeni filosofici și sociologici generali, este considerat ca „o manifestare externă a proprietăților unui obiect într-un sistem dat de relații”; ca un set de acțiuni obișnuite sau specifice ale indivizilor sau organelor
17873.		Formarea UUD logic la elevii de clasa a 3-a	846,71 KB
	Aspecte psihologice și pedagogice ale problemei formării acțiunilor logice universale la școlarii primari.Metode de evaluare a formării UUD logice. Dezvoltarea unui concept pentru dezvoltarea activităților educaționale universale în sistemul de învățământ general răspunde noilor nevoi sociale. Cea mai importantă sarcină a sistemului de învățământ modern este formarea acțiunilor UUD educaționale universale. Formarea acțiunilor educaționale universale este cheia pentru prevenirea dificultăților școlare.
2638.		Implementarea tehnică a conexiunilor logice în sistemele de autoblocare	1,04 MB
	Implementarea tehnică a conexiunilor logice în sistemele de autoblocare Implementarea tehnică a algoritmilor de control pentru AB cu trei cifre și patru cifre poate fi realizată utilizând elemente logice discrete și integrale fără contact și releu fără contact ...
10203.		APLICAREA CONCEPTULUI DE ABORDARE ORIENTATĂ LA RISCURI PENTRU CONSTRUCȚIA MODELELOR STRUCTURAL-LOGICE DE APARIȚIE ȘI DEZVOLTARE A URGENȚEI	70,8 KB
	Analiza generală a riscurilor Mediul de lucru este saturat de sisteme și tehnologii tehnologice puternice care fac munca umană productivă și mai puțin dificilă din punct de vedere fizic, dar mai periculoasă. Riscul se caracterizează prin neașteptarea și brusca debutul unei situații periculoase. În fiecare zi ne confruntăm cu numeroase riscuri, dar cele mai multe dintre ele rămân potențiale.Teoria riscului oferă o evaluare cantitativă a impactului negativ asupra unei persoane, precum și a daunelor asupra sănătății și vieții sale.
11576.		Concept, tipuri și forme de tranzacții. Consecințele nerespectării formei solicitate de tranzacții	49,82 KB
	Recunoașterea unei tranzacții tipuri nevalide de tranzacții nevalide. Valoarea aplicată a cursului constă în simplificarea conceptului de tranzacție, adică prezentarea sa publică într-o formă mai accesibilă.
6213.		Aproximarea funcției	3,08 MB
	Prima constă în înlocuirea unei funcții, dată analitic sau tabelar, cu o altă funcție apropiată de cea originală, dar mai simplă și mai convenabilă pentru calcule. De exemplu, înlocuirea unei funcții cu un polinom vă permite să obțineți formule simple pentru integrare și diferențiere numerică; înlocuirea tabelului cu o funcție de aproximare vă permite să obțineți valori în punctele sale intermediare. Apare, de asemenea, a doua problemă a recuperării unei funcții pe un anumit segment din valorile funcției date pe acest segment într-un set discret de puncte. Răspunsul la această întrebare ...
14058.		Evoluția funcțiilor de stare	29,99 KB
	Statul rus ca fenomen juridic trebuie să asigure în primul rând punerea în aplicare a scopului statului, precum și principalele sale caracteristici constituționale ca stat democrat federal social social laic, cu o formă republicană de guvernare. Scopul principal al statului este determinat de art.

Disjuncție simplă(disjuncție inclusiv) sau disjunct(Engleză disjunct) este o disjuncție a uneia sau mai multor variabile sau a negațiilor acestora și fiecare variabilă apare nu mai mult de o dată.

Disjuncție simplă

• complet dacă fiecare variabilă (sau negația ei) apare în ea exact o dată;
• monoton dacă nu conține negative variabile.

Formă normală conjunctivă, CNF(eng. conjunctive normal form, CNF) formă normală, în care o funcție booleană are forma unei conjuncții a mai multor clauze simple.

Exemplu CNF:$ f (x, y) = (x \ lor y) \ land (y \ lor \ neg (z)) $

SKNF

Formă normală conjunctivă perfectă, SKNF(forma normală conjunctivă perfectă, PCNF) este un CNF care îndeplinește următoarele condiții:

• nu are aceleași disjuncții simple
• fiecare disjuncție simplă este completă

Exemplu SKNF:$ f (x, y, z) = (x \ lor \ neg (y) \ lor z) \ land (x \ lor y \ lor \ neg (z)) $

Teorema: Pentru orice funcție booleană $ f (\ vec (x)) $, care nu este egală cu unitatea de identitate, există un SKNF care o definește.

Dovezi: Deoarece inversul funcției $ \ neg (f) (\ vec x) $ este egal cu unul pe acele tupluri pe care $ f (\ vec x) $ este egal cu zero, atunci SDNF pentru $ \ neg (f) (\ vec x) $ poate fi scris după cum urmează:

$ \ neg (f) (\ vec x) = \ bigvee \ limits_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ wedge x_ (2) ^ (\ sigma_ (2)) \ wedge ... \ wedge x_ (n) ^ (\ sigma_ (n ))) $, unde $ \ sigma_ (i) $ denotă prezența sau absența negației pentru $ x_ (i) $

Să găsim inversul laturilor stângi și drepte ale expresiei:

$ f (\ vec x) = \ neg ((\ bigvee \ limits_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ wedge x_ (2) ^ (\ sigma_ (2)) \ wedge ... \ wedge x_ (n) ^ (\ sigma_ (n ))))) $

Aplicând regula lui Morgan de două ori la expresia obținută pe partea dreaptă, obținem: $ f (\ vec x) = \ bigwedge \ limits_ (f (x ^ (\ sigma_1), x ^ (\ sigma_2), \ dots , x ^ (\ sigma_n)) = 0) $ $ (\ neg (x_1 ^ (\ sigma_1)) \ vee \ neg (x_2 ^ (\ sigma_2)) \ vee \ dots \ vee \ neg (x_n ^ (\ sigma_n ))) $

Ultima expresie este SKNF. Deoarece SKNF este obținut din SDNF, care poate fi construit pentru orice funcție care nu este identică zero, teorema este dovedită.

Algoritm pentru construirea SKNF conform tabelului adevărului

• În tabelul adevărului marchăm acele seturi de variabile pe care valoarea funcției este egală cu 0 $ $.
• Pentru fiecare set marcat, scriem disjuncția tuturor variabilelor conform următoarei reguli: dacă valoarea unei variabile este de $ 0 $, atunci includem variabila însăși în disjuncție, altfel negarea acesteia.
• Conectăm toate disjuncțiile rezultate prin operații de conjuncție.

Un exemplu de construire a SKNF pentru mediană

unu). În tabelul adevărului marchăm acele seturi de variabile pe care valoarea funcției este egală cu 0 $ $.

X	y	z	$ \ langle x, y, z \ rangle $
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

2). Pentru fiecare set marcat, scriem conjuncția tuturor variabilelor conform următoarei reguli: dacă valoarea unei variabile este de $ 0 $, atunci includem variabila însăși în disjuncție, altfel negarea acesteia.

X	y	z	$ \ langle x, y, z \ rangle $
0	0	0	0	$ (x \ lor y \ lor z) $
0	0	1	0	$ (x \ lor y \ lor \ neg (z)) $
0	1	0	0	$ (x \ lor \ neg (y) \ lor z) $
0	1	1	1
1	0	0	0	$ (\ neg (x) \ lor y \ lor z) $
1	0	1	1
1	1	0	1
1	1	1	1

3). Conectăm toate disjuncțiile rezultate prin operații de conjuncție.

$ \ langle x, y, z \ rangle = (x \ lor y \ lor z) \ land (\ neg (x) \ lor y \ lor z) \ land (x \ lor \ neg (y) \ lor z) \ land (x \ lor y \ lor \ neg (z)) $

Exemple SKNF pentru unele funcții

Săgeata lui Pierce: $ x \ downarrow y = (\ neg (x) \ lor (y)) \ land ((x) \ lor \ neg (y)) \ land (\ neg (x) \ lor \ neg (y) ) $

Exclusiv sau: $ x \ oplus y \ oplus z = (\ neg (x) \ lor \ neg (y) \ lor z) \ land (\ neg (x) \ lor y \ lor \ neg (z)) \ land (x \ lor \ neg (y) \ lor \ neg (z)) \ land (x \ lor y \ lor z) $

Baza standard. Formulele elementare sunt literale. Conjuncție elementară (disjuncție). Forma normală disjunctivă (conjunctivă) și forma perfectă. Teorema: orice funcție booleană alta decât 0 (de la 1) poate fi reprezentată ca SDNF (SKNF). Completitudinea bazei standard. Exemple de baze complete: baza Zhegalkin, lovitura lui Schaeffer, săgeata lui Peirce.

Baza standard este un set de trei operații inițiale ale algebrei booleene: adunare (unire), multiplicare (intersecție) și negație.

Aici vom suna literal variabila x sau negația ei x și denotă xИ. Intersecția booleană a literelor multiple definite de diferite variabile, adică expresia formei X = xИ 1 xИ 2. ... ... xИ л se numește conjuncție elementară ... Cerința ca toate variabilele să fie diferite este condiționată de următoarele. Dacă conjuncția conține mai mulți literali identici, atunci în virtutea comutativității, asociativității și idempotenței conjuncției, este posibil, trecând la o formulă echivalentă, să se lase un singur literal (de exemplu, x 1 x 1 = x 1). Dacă conjuncția include o variabilă și negarea acesteia, atunci formula este echivalentă cu constanta 0, deoarece x x = 0 și pentru orice formulă Y avem Y x x = 0.

Se numește o disjuncție a mai multor conjuncții elementare forma normală disjunctivă , sau DNF ... De exemplu,

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

Dacă compoziția variabilelor din fiecare conjuncție elementară a unui DNF dat este aceeași, atunci se numește DNF perfect ... Exemplul dat este DNF, care nu este perfect. Dimpotrivă, formula

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

există o formă perfectă.

Deoarece în algebra booleană adunarea și multiplicarea sunt operații simetrice și puteți oricând să interpretați adunarea ca multiplicare și înmulțirea ca adunare, există și un concept dual - formă normală conjunctivă (CNF ), care este o conjuncție de disjuncții elementare și forma conjunctivă perfectă (SKNF ). Din principiul dualității pentru semirings simetrice rezultă că orice afirmație despre DNF corespunde unei afirmații duale despre CNF, care se obține prin înlocuirea adunării (disjuncției) cu înmulțire, înmulțire (conjuncție) cu adunare, constantă 0 cu constantă 1, constantă 1 constanta 0, relatia de ordine prin ordin dual (invers). Prin urmare, în continuare ne vom concentra asupra studierii numai a DNF.

Teorema 1.4. Orice funcție booleană alta decât constanta 0 poate fi reprezentată ca SDNF.

◀ Să fim de acord cu x σ pentru a însemna o formulă x dacă σ = 1 și o formulă x dacă σ = 0. Fie funcția f (y 1, ..., Yn) să ia valoarea 1 pe vector (t 1 , ..., Tn) (un astfel de vector se numește constituent al unității ). Apoi, conjuncția elementară ia valoarea 1 pe acest set, dar dispare pe toți ceilalți vectori booleni n-dimensionali. Luați în considerare formula

în care suma (uniunea) se extinde la toate acele seturi (t 1, ..., tn) de valori ale argumentelor pe care funcția dată ia valoarea 1. Rețineți că setul acestor seturi nu este gol, astfel încât suma să conțină cel puțin un termen.

Este ușor de văzut că formula Φ devine 1 pentru aceștia și numai pentru acele valori ale variabilelor pentru care funcția considerată devine 1. Prin urmare, formula Ψ reprezintă funcția f.

Corolar 1.1. Baza standard este completă.

◀ Într-adevăr, dacă o funcție nu este o constantă 0, atunci poate fi reprezentată fie sub forma SDNF, care este o formulă peste o bază standard. Constanta 0 poate fi reprezentată, de exemplu, prin formula f (x 1, x 2, ..., X n) = x 1 x 1.

Exemplul 1.2. Luați în considerare o funcție de trei variabile m (x 1, x 2, x 3) (Tabelul 1.4), numită funcție majoritară ̆. Această funcție evaluează la 1 dacă mai mult de jumătate din argumentele sale sunt 1. Prin urmare, este adesea numită funcția de vot. Să construim un SDNF pentru acesta.

Integritatea bazei standard permite selectarea altor sisteme complete de funcții. Completitudinea setului F poate fi stabilită din următoarele considerații. Să presupunem că fiecare dintre cele trei funcții busis standard este reprezentabilă printr-o formulă peste F. Apoi, conform teoremei 1.3, setul F este complet.

Exemplul 1.3. Se numește setul de operații de adunare modulo 2, multiplicare și constantă 1 baza Zhegalkin ... Adunarea și multiplicarea modulului 2 sunt operații de bază ale inelului Z2, expresiile compuse cu ajutorul lor sunt polinoame peste inelul Z2. Constanta 1 în acest caz este necesară pentru a scrie membrul liber. Deoarece xx = x, toți factorii din polinom au gradul 1. Prin urmare, atunci când scriem un polinom, se poate renunța la conceptul de grad. Exemple de formule pe baza Zhegalkin:

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

Orice astfel de formulă se numește polinomul Zhegalkin. De fapt, polinomul Zhegalkin este un polinom peste inelul Z2.

Nu este dificil să construim formule peste baza Zhegalkin, reprezentând operațiile de adunare și negare a bazei standard (înmulțirea celor două baze este comună):

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

Prin urmare, baza Zhegalkin este un set complet.
Se poate arăta că pentru orice funcție booleană polinomul Zhegalkin este determinat în mod unic

(mai precis, până la ordinea termenilor). Coeficienții polinomului Zhegalkin pentru un număr mic de variabile pot fi găsiți prin metoda coeficienților nedefiniți.

Exemplul 1.4. Luați în considerare un set de funcții unice, cursa Schaeffer *. Acest set este complet, care rezultă din următoarele identități ușor verificabile:

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

Exemplul 1.5. Baza constând dintr-o singură funcție, săgeata Pierce, este, de asemenea, completă. Verificarea acestui lucru este similară cu cazul loviturii Schaeffer. Cu toate acestea, această concluzie poate fi făcută și pe baza principiului dualității pentru semirings simetrice.

* Lovitura lui Schaeffer este o operație binară, dar nu asociativă. Prin urmare, atunci când utilizați formularul infix, ar trebui să fiți atenți: rezultatul depinde de ordinea în care sunt efectuate operațiile. În acest caz, se recomandă indicarea explicită a ordinii operațiilor folosind paranteze, de exemplu, scrie (x | y) | z, nu x | y | z, deși ambele forme sunt echivalente.

Forma normală conjunctivă este convenabilă pentru demonstrarea automată a teoremelor. Orice formulă booleană poate fi convertită în CNF. Pentru a face acest lucru, puteți utiliza: legea dublei negații, legea lui Morgan, distributivitatea.

Colegiat YouTube

• 1 / 5

  Formule în KNF:

  ¬ A ∧ (B ∨ C), (\ displaystyle \ neg A \ wedge (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.)

  Formule nu în KNF:

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

  Dar aceste 3 formule care nu sunt în CNF sunt echivalente cu următoarele formule din 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 \ wedge (B \ vee D) \ wedge (B \ vee E).)

  Construirea CNF

  Algoritm pentru construirea CNF

  1) Scăpați de toate operațiile logice conținute în formulă, înlocuindu-le cu cele principale: conjuncție, disjuncție, negare. Acest lucru se poate face folosind formule echivalente:

  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) Înlocuiți semnul de negare, referindu-vă la întreaga expresie, cu semnele de negare, referindu-vă la enunțuri variabile individuale bazate pe formule:

  ¬ (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) Scapă de semnele de dublă negație.

  4) Aplicați, dacă este necesar, la operațiile de conjuncție și disjuncție proprietățile distributivității și formula de absorbție.

  Un exemplu de construire a unui CNF

  Să aducem la CNF formula

  F = (X → Y) ∧ ((¬ Y → Z) → ¬ X). (\ displaystyle F = (X \ rightarrow Y) \ wedge ((\ neg Y \ rightarrow Z) \ rightarrow \ neg X).)

  Să transformăm formula F (\ displaystyle F) la o formulă care nu conține → (\ displaystyle \ rightarrow):

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

  În formula rezultată, transferăm negația la variabile și reducem negativele duble:

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

  De exemplu, următoarea formulă este scrisă în 2-CNF:

  (A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C). (\ displaystyle (A \ lor B) \ land (\ neg B \ lor C) \ land (B \ lor \ neg C).)