Forma normală conjunctivă a unei funcții logice. „Manual de matematică discretă dnf, sdnf, knf, sknf

Exemplu. Găsiți formule CNF

~ ~

Forma normală disjunctivă perfectă a SDNF poate fi construită folosind următorul algoritm:

1. = 1. Algoritmul DNF

2. = 2. Algoritmul DNF

3. = 3. Algoritmul DNF

4. = 4. Algoritmul DNF

5. Omiteți termeni identic falși, adică termenii formei

6. Completați termenii rămași cu variabilele lipsă

7. Repetați punctul 4.

Exemplu. Găsiți formule SDNF.

Pentru a construi SCNF, puteți utiliza următoarea schemă:

Exemplu. Găsiți formule SDNF.

Se știe (Teoremele 2.11, 2.12) că SDNF și SCNF sunt definite în mod unic prin formulă și, prin urmare, pot fi construite folosind tabelul de adevăr al formulei.

Schema de construire a SDNF și SCNF conform tabelului de adevăr este dată mai jos, pentru formula ~ :

			~
			1 0 1 0 1 1 0 1	SDNF;

SKNF.

2.2. Exercita.

2.2.1 Mai jos sunt expresii logice. Simplificați expresiile variantei dvs. cât mai mult posibil folosind legile logicii lui Boole. Apoi utilizați tabelele de adevăr pentru a compara expresia simplificată cu cea originală.

2.2.2. Clarificați întrebarea echivalenței lui f 1 și f 2 reducându-le la SDNF (Tabelul 1).

№	2.2.3. Găsiți funcția duală pentru f 3 folosind principiul generalizat și boolean (Tabelul 1). Comparați rezultatele.	f 1	f 2

f 3

2.3. Întrebări de testare.

2.3.1. Definiți o declarație.

2.3.2. Enumerați principalele operațiuni dintr-o declarație.

2.3.3. Ce este un tabel de adevăr?

~ ~ ~ ;

2.3.4. Creați tabele de adevăr pentru următoarele formule:

;

2.3.5. Ținând cont de convențiile privind ordinea operațiilor, omiteți parantezele „extra” și semnul „ ” în formule:

2.3.7. 2.3.6. Folosind transformări echivalente, dovediți adevărul identic al formulelor:

)

Găsiți formule duale:

2.3.8. Reduceți următoarele formule la forma perfectă DNF (SDNF):

2.3.9. Reduceți următoarele formule la forma CNF perfectă (SCNF): № 3

Lucrări de laborator Subiect:

„Minimizarea funcțiilor booleene. Logică"Ţintă:

Dobândirea abilităților practice în lucrul cu metode de minimizare a funcțiilor booleene.

3.1. Informații teoretice.

Forme minime După cum sa arătat în, orice funcție booleană poate fi reprezentată în formă normală perfectă (disjunctivă sau conjunctivă). Mai mult decât atât, o astfel de reprezentare este primul pas în tranziția de la o specificație de tabel a unei funcții la ea expresie analitică

Problema canonică a sintetizării circuitelor logice pe o bază booleană se rezumă la minimizarea funcțiilor booleene, i.e. la reprezentarea lor în formă normală disjunctivă, care conține cel mai mic număr de litere (variabile și negațiile lor). Astfel de forme sunt numite minimale. În sinteza canonică, se presupune că atât semnalele, cât și inversiunile lor sunt furnizate la intrările circuitului.

Formula prezentată în formă normală disjunctivă este simplificată prin utilizarea repetată a operației de lipire și a operației de absorbție și (identitățile duale pentru forma normală conjunctivă au forma: și ). Aici, și poate fi înțeles ca orice formulă de algebră booleană. Ca rezultat, ajungem la o expresie analitică în care transformările ulterioare nu mai sunt posibile, adică. obținem o formă fără fund.

Printre formele de fund există și o formă disjunctivă minimă și poate să nu fie unică. Pentru a vă asigura că o anumită formă de blocare este minimă, trebuie să găsiți toate formele de fund și să le comparați după numărul de litere pe care le conțin.

Să fie, de exemplu, funcția dată în formă disjunctivă normală perfectă:

Grupând termenii și aplicând operația de lipire, avem .

Cu o altă metodă de grupare obținem:

Ambele forme de fund nu sunt minime. Pentru a obține forma minimă, trebuie să ghiciți să repetați un termen din formula originală (acest lucru se poate face întotdeauna, deoarece ). În primul caz, un astfel de membru poate fi . Apoi . Adăugând termenul , obținem: . După ce ați trecut prin toate opțiunile posibile, vă puteți asigura că ultimele două forme sunt minime.

Lucrul cu formule la acest nivel este ca și cum ai rătăci în întuneric. Procesul de căutare a formelor minimale devine mai vizual și mai intenționat dacă folosiți unele reprezentări și simboluri grafice și analitice special dezvoltate în acest scop.

Cub multidimensional

Fiecare vârf al unui cub -dimensional poate fi asociat cu un constituent al unei unități. Prin urmare, submulțimea de vârfuri marcate este o mapare pe -cub dimensional Funcția booleană a variabilelor în formă normală disjunctivă perfectă. În fig. 3.1 prezintă o astfel de mapare pentru funcția din clauza 3.7.

Fig. 3.1 Afișarea unei funcții prezentate în SDNF pe un cub tridimensional

Pentru a afișa o funcție de variabile prezentate în orice formă normală disjunctivă, este necesar să se stabilească o corespondență între minitermenii acesteia și elementele cubului -dimensional.

Un minitermen de rang (-1) poate fi considerat ca rezultat al lipirii a doi minitermeni de rang (component al unității), adică. , Pe un cub -dimensional, aceasta corespunde înlocuirii a două vârfuri, care diferă doar prin valorile coordonatei care leagă aceste vârfuri, cu o muchie (se spune că muchia acoperă vârfurile incidente cu acesta). Astfel, minitermenii de ordinul (-1) corespund muchiilor cubului -dimensional. În mod similar, corespondența minitermenilor de ordinul (-2) se stabilește cu fețele unui cub -dimensional, fiecare dintre ele acoperă patru vârfuri (și patru muchii).

Elementele unui cub -dimensional caracterizate prin dimensiuni se numesc -cuburi. Astfel, vârfurile sunt 0-cuburi, muchiile sunt 1-cuburi, fețele sunt 2-cuburi etc. Generalizând raționamentul de mai sus, putem presupune că un minitermen de ()-al-lea rang în formă normală disjunctivă pentru o funcție de variabile este reprezentat de un -cub, iar fiecare -cub acoperă toate acele -cuburi de dimensiune inferioară care sunt asociate cu vârfuri. Ca exemplu în Fig. 3.2 prezintă o funcție a trei variabile. Aici minitermenii corespund cu 1-cub (), iar minitermenul este reprezentat de un 2-cub ().

Fig.3.2 Acoperirea funcției

Deci, orice formă normală disjunctivă este mapată pe un cub -dimensional printr-un set de -cuburi care acoperă toate vârfurile corespunzătoare constituenților unității (0-cuburi). Afirmația inversă este, de asemenea, adevărată: dacă un anumit set de -cuburi acoperă mulțimea tuturor nodurilor corespunzătoare valorilor unitare ale unei funcții, atunci disjuncția minitermenilor corespunzătoare acestor -cuburi este o expresie a acestei funcții în normal disjunctiv. formă. Se spune că o astfel de colecție de -cuburi (sau minitermenii lor corespunzători) formează o acoperire a unei funcții.

Dorința unei forme minimale este înțeleasă intuitiv ca o căutare a unei astfel de acoperiri, al cărui număr de cuburi ar fi mai mic, iar dimensiunea lor ar fi mai mare. Acoperirea corespunzătoare formei minime se numește acoperire minimă. De exemplu, pentru funcția de acoperire din Fig. 3.3 îndeplinește formele minime Şi .

Orez. 3.3 Acoperiri de funcții.

stânga – ; corect –

Afișarea unei funcții pe un cub -dimensional este clară și simplă atunci când . Un cub cu patru dimensiuni poate fi reprezentat așa cum se arată în Fig. 3.4, care arată o funcție a patru variabile și acoperirea minimă a acesteia corespunzătoare expresiei . Folosirea acestei metode necesită atât de mult formațiuni complexe că toate avantajele sale sunt pierdute.

Orez. 3.4 Afișaj funcțional pe un cub cu patru dimensiuni

Hărți Carnot

O altă metodă pentru afișarea grafică a funcțiilor booleene folosește Hărți Carnot, care sunt tabele de corespondență special organizate. Coloanele și rândurile tabelului corespund tuturor seturilor posibile de valori a nu mai mult de două variabile, iar aceste seturi sunt aranjate într-o astfel de ordine încât fiecare dintre cele ulterioare diferă de precedentul prin valoarea uneia dintre variabile. . Datorită acestui fapt, celulele învecinate ale tabelului diferă pe orizontală și pe verticală prin valoarea unei singure variabile. Celulele situate la marginile tabelului sunt, de asemenea, considerate adiacente și au această proprietate. În fig. Figura 3.5 prezintă hărți Karnaugh pentru două, trei, patru variabile.

Orez. 3.5 Hărți Carnaugh pentru două, trei și patru variabile

Ca și în tabelele de adevăr obișnuite, celulele mulțimilor în care funcția ia valoarea 1 sunt umplute cu unu (zerourile de obicei nu se potrivesc, ele corespund celulelor goale). De exemplu, în Fig. 3.6, O arată o hartă Karnaugh pentru o funcție, a cărei afișare pe un cub cu patru dimensiuni este dată în Fig. 3.4. Pentru a simplifica lucrurile, rândurile și coloanele corespunzătoare valorilor de 1 pentru o variabilă sunt evidențiate cu o acoladă care indică acea variabilă.

Orez. 3.6 Afișarea unei funcții a patru variabile pe o hartă Carnaugh

(a) și acoperirea minimă a acesteia (b)

Între mapările funcțiilor la n-cubul dimensional și harta Carnot există o corespondență unu-la-unu. Pe harta Carnot s-un cub corespunde unui set de 2 celule invecinate asezate intr-un rand, coloana, patrat sau dreptunghi (tinand cont de apropierea marginilor opuse ale hartii). Prin urmare, toate prevederile expuse mai sus (a se vedea paragraful. cub multidimensional), sunt valabile pentru hărțile Karnaugh. Deci, în fig. 3.6, b arată acoperirea unităților hărții corespunzătoare formei disjunctive minime funcția în cauză.

Citirea termenilor de pe harta Karnaugh se realizează folosind regula simpla. Se formează celule s-cub, da miniter (n–s)- rangul, care le include pe acelea (n–s) variabile care păstrează aceleași valori pe aceasta s-cub, unde valoarea 1 corespunde variabilelor în sine, iar valoarea 0 corespunde negațiilor acestora. Variabile care nu își păstrează valorile pentru s-cub, sunt absente în miniterm. Diverse moduri citirile au ca rezultat reprezentări diferite ale funcției în formă normală disjunctivă (cea din extrema dreaptă este minimă) (Figura 3.7).

Utilizarea hărților Karnaugh necesită construcții mai simple în comparație cu cartografierea n-cub dimensional, mai ales în cazul a patru variabile. Pentru a afișa funcții a cinci variabile, sunt utilizate două hărți Karnaugh pentru patru variabile, iar pentru o funcție de șase variabile sunt folosite patru astfel de hărți. Odată cu o creștere suplimentară a numărului de variabile, hărțile Karnaugh devin practic inutilizabile.

Celebru în literatură Carduri Veitch ele diferă doar în ordinea diferită a seturilor de valori variabile și au aceleași proprietăți ca hărțile Karnaugh.

Complex de cuburi

Incoerența metodelor grafice când număr mare variabilele sunt compensate de diverse metode analitice reprezentări ale funcţiilor booleene. O astfel de reprezentare este complex de cuburi, folosind terminologia unui spațiu logic multidimensional în combinație cu simbolismul special dezvoltat.

). 0-cuburile corespunzătoare constituenților unității sunt reprezentate prin seturi de valori variabile pe care funcția este egală cu unitatea. Evident, în înregistrare

Orez. 3.8 Complex de cuburi ale unei funcții de trei variabile ( O) și reprezentarea sa simbolică ( b)

Se formează complexul de cuburi acoperire maximă a funcției. Excluzând din el pe toți cei s-cuburi care sunt acoperite de cuburi de dimensiune superioara, obtinem acoperiri corespunzatoare formelor de fund. Deci, pentru exemplul luat în considerare (Fig. 3.8) avem o acoperire fără fund

care corespunde funcţiei . În acest caz, această acoperire este minimă.

Pentru două funcții booleene, operația de disjuncție corespunde unirii complexelor lor de cuburi, iar operația de conjuncție corespunde intersecției complexelor lor de cuburi. Negația unei funcții corespunde complementului unui complex de cuburi, adică și este determinată de toate vârfurile la care funcția ia valoarea 0. Astfel, există o corespondență unu-la-unu (izomorfism) între algebra lui Funcții booleene și mulțimi booleene reprezentând complexe de cuburi.

Reprezentarea unei funcții sub formă de complexe de cuburi este mai puțin vizuală, dar cele mai importante avantaje ale acesteia sunt că restricțiile privind numărul de variabile sunt eliminate și codificarea informațiilor este facilitată atunci când se utilizează computere.

Minimizarea funcțiilor booleene

Enunțarea problemei. Minimizarea unui circuit pe o bază booleană se reduce la găsirea formei disjunctive minime care corespunde acoperirii minime. Numărul total de litere incluse în formularul normal este exprimat prin costul acoperirii , unde este numărul de cuburi care formează acoperirea unei funcții date de n variabile. Acoperirea minimă este caracterizată cea mai mică valoare prețurile sale.

De obicei, problema minimizării este rezolvată în doi pași. În primul rând, căutăm o husă redusă care să includă toate -cuburile de dimensiune maximă, dar să nu conțină un singur cub acoperit de niciun cub din această husă. Forma normală disjunctivă corespunzătoare se numește redusă, iar minitermenii ei sunt numiți implicanți simpli. Pentru o anumită funcție, acoperirea redusă este unică, dar poate fi redundantă datorită faptului că unele dintre cuburi sunt acoperite de colecții de alte cuburi.

La a doua etapă, se face o tranziție de la formele normale disjunctive reduse la forme normale disjunctive, din care sunt selectate formele minime. Formele de fund se formează prin excluderea din acoperirea redusă a tuturor cuburilor redundante, fără de care setul de cuburi rămas încă formează o acoperire a unei anumite funcții, dar cu excluderea ulterioară a oricăruia dintre cuburi, acesta nu mai acoperă setul de toate vârfurile corespunzătoare unor valori individuale ale funcției, adică încetează să mai fie o acoperire.

Un cub de acoperire redusă care acoperă vârfuri ale unei anumite funcții care nu sunt acoperite de niciun alt cub nu poate fi redundant și va fi întotdeauna inclus în acoperirea minimă. Un astfel de cub, ca și implicantul său corespondent, se numește extremal (implicant esențial), iar vârfurile pe care le acoperă sunt numite vârfuri anulate. Setul de extremale formează miezul învelișului este clar că atunci când se trece de la o acoperire redusă la una minimă, în primul rând, toate extremele trebuie izolate. Dacă setul de extremale nu formează o acoperire, atunci se completează pentru a se acoperi cu cuburi din învelișul redus.

Definițiile date sunt ilustrate în Fig. 3.9, unde acoperirea redusă (vezi Fig. 3.9a, ) iar acoperirile minime (Fig. 3.9b) și (vezi Fig. 3.9, b) sunt exprimate după cum urmează.

Definiția 1.Monomiul conjunctiv (conjuncție elementară) de variabile este conjuncția acestor variabile sau negațiile lor.

De exemplu, este o conjuncție elementară.

Definiția 2.Monomiul disjunctiv (disjuncția elementară) din variabile se numeşte disjuncţia acestor variabile sau negaţiile lor.

De exemplu, este o disjuncție elementară.

Definiția 3. O formulă care este echivalentă cu o formulă de algebră propozițională dată și este o disjuncție de monomii conjunctive elementare se numește forma normală disjunctivă(DNF) din această formulă.

De exemplu,– DNF.

Definiția 4. O formulă care este echivalentă cu o formulă de algebră propozițională dată și este o conjuncție de monomii disjunctive elementare se numește forma normală conjunctivă(CNF) din această formulă.

De exemplu, – KNF.

Pentru fiecare formulă de algebră propozițională se poate găsi un set de forme normale disjunctive și conjunctive.

Algoritm pentru construirea formelor normale

Folosind echivalentele algebrei logice, înlocuiți toate operațiile de bază din formula: conjuncție, disjuncție, negație:

Scapa de dublele negative.

Aplicați, dacă este necesar, proprietățile formulelor de distributivitate și absorbție la operațiile de conjuncție și disjuncție.

2.6. Formele normale disjunctive perfecte și conjunctive perfecte

Orice funcție booleană poate avea multe reprezentări sub formă de DNF și CNF. Un loc special printre aceste reprezentări îl ocupă DNF perfect (SDNF) și CNF perfect (SCNF).

Definiția 1. Forma normală disjunctivă perfectă(SDNF) este un DNF în care fiecare monom conjunctiv conține fiecare variabilă din mulțime exact o dată, fie el însuși, fie negația sa.

Din punct de vedere structural, SDNF pentru fiecare formulă de algebră propozițională redusă la un DNF poate fi definit după cum urmează:

Definiția 2. Forma normală disjunctivă perfectă(SDNF) a unei formule de algebră propozițională se numește DNF, care are următoarele proprietăți:

Definiția 3. Forma normală conjunctivă perfectă(SCNF) este un CNF în care fiecare monom disjunctiv conține fiecare variabilă din mulțime exact o dată și apare fie el însuși, fie negația sa.

Din punct de vedere structural, SCNF pentru fiecare formulă de algebră propozițională redusă la CNF poate fi definit după cum urmează.

Definiția 4. Forma normală conjunctivă perfectă(SCNF) a unei formule de algebră propozițională dată se numește CNF care satisface următoarele proprietăți.

Teorema 1. Fiecare funcție booleană a variabilelor care nu este identic falsă poate fi reprezentată în SDNF și într-un mod unic.

Metode de găsire a SDNF

1a metoda

a 2-a metoda

selectați liniile în care formula ia valoarea 1;

compunem o disjuncție de conjuncții cu condiția ca dacă o variabilă este inclusă în conjuncția cu valoarea 1, atunci notăm această variabilă dacă este cu valoarea 0, atunci negația ei; Primim SDNF.

Teorema 2. Fiecare funcție booleană a variabilelor care nu este identic adevărată poate fi reprezentată în SCNF și într-un mod unic.

Metode de găsire a SCNF

1a metoda– folosind transformări echivalente:

a 2-a metoda– folosind tabele de adevăr:

selectați liniile în care formula ia valoarea 0;

compunem o conjuncție de disjuncții cu condiția ca dacă o variabilă este inclusă în disjuncție cu valoarea 0, atunci notăm această variabilă dacă este cu valoarea 1, atunci negația ei; Primim SKNF.

Exemplul 1. Construiți funcții CNF.

Soluţie

Să eliminăm conectivul „” folosind legile de transformare a variabilelor:

= /legile lui de Morgan și dubla negație/ =

/legi distributive/ =

Exemplul 2. Dați formula lui DNF.

Soluţie

Să exprimăm operații logice folosind și:

= /să clasificăm negația ca variabile și să reducem dublele negative/ =

= /legea distributivității/ .

Exemplul 3. Scrieți formula în DNF și SDNF.

Soluţie

Folosind legile logicii, reducem această formulă la o formă care conține doar disjuncții ale conjuncțiilor elementare. Formula rezultată va fi DNF dorită:

Pentru a construi SDNF, să creăm un tabel de adevăr pentru această formulă:

Marcam acele rânduri ale tabelului în care formula (ultima coloană) ia valoarea 1. Pentru fiecare astfel de rând, scriem o formulă care este adevărată pe setul de variabile din acest rând:

linia 1: ;

linia 3: ;

linia 5: .

Disjuncția acestor trei formule va lua valoarea 1 numai pe seturile de variabile din rândurile 1, 3, 5 și, prin urmare, va fi forma normală disjunctivă perfectă dorită (PDNF):

Exemplul 4. Aduceți formula la SKNF în două moduri:

a) folosind transformări echivalente;

b) folosind un tabel de adevăr.

Soluţie:

Să transformăm a doua disjuncție elementară:

Formula arată astfel:

b) întocmește un tabel de adevăr pentru această formulă:

Marcam acele rânduri ale tabelului în care formula (ultima coloană) ia valoarea 0. Pentru fiecare astfel de rând, scriem o formulă care este adevărată pe setul de variabile din acest rând:

linia 2: ;

linia 6: .

Conjuncția acestor două formule va lua valoarea 0 numai pe seturile de variabile din rândurile 2 și 6 și, prin urmare, va fi forma normală conjunctivă perfectă dorită (PCNF):

Întrebări și sarcini pentru soluții independente

1. Folosind transformări echivalente, reduceți formulele la DNF:

2. Folosind transformări echivalente, aduceți formulele la CNF:

3. Folosind a doua lege distributivă, convertiți DNF în CNF:

O) ;

4. Convertiți DNF-urile date în SDNF-uri:

5. Convertiți CNF-ul dat în SCNF:

6. Pentru formule logice date, construiți SDNF și SCNF în două moduri: folosind transformări echivalente și folosind un tabel de adevăr.

b) ;

Forme normale ale funcţiilor logice Reprezentarea unei funcţii booleene sub forma unei disjuncţii de termeni conjunctivi ai constituenţilor unităţii Ki 2.7 se numeşte forma normală disjunctivă a DNF a acestei funcţii. conţin exact una dintre toate variabilele logice luate cu sau fără negaţii, atunci această formă de reprezentare a unei funcţii se numeşte forma normală disjunctivă perfectă SDNF a acestei funcţii. După cum puteți vedea, atunci când compuneți o funcție SDNF, trebuie să creați o disjuncție a tuturor mintermilor pentru care funcția ia valoarea 1.

Distribuiți-vă munca pe rețelele sociale

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

Cursul 1.xx

Forme normale de funcții logice

Reprezentarea unei funcții booleene sub forma unei disjuncții de termeni conjunctivi (constituent unitar) K i

, (2.7)

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

Dacă toți termenii conjunctivi din DNF sunt mintermii , adică conține exact una dintre toate variabilele logice, luate cu sau fără negații, atunci această formă de reprezentare a funcției se numeșteformă normală disjunctivă perfectă(SDNF ) această funcție. Se numește SDNF perfect , deoarece fiecare termen din disjuncție include toate variabilele; disjunctiv , deoarece operația principală din formulă este disjuncția. Conceptul "formă normală” înseamnă un mod clar de a scrie o formulă care implementează o funcție dată.

Ținând cont de cele de mai sus, din Teorema 2.1 rezultă următoarea teoremă.

Teorema 2. Orice funcție booleană(nu identic 0) poate fi prezentat în SDNF, .

Exemplul 3. Să avem o funcție dată de 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 compuneți o funcție SDNF, trebuie să creați o disjuncție a tuturor mintermilor pentru care funcția ia valoarea 1.

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

, (2.8)

numit forma normală conjunctivă(CNF) a acestei funcții.

Dacă toți termenii CNF disjunctivi sunt maxterms , adică conțin exact unul dintre toate logice funcții variabile, luat cu sau fără negații, atunci se numește un astfel de CNFforma normală conjunctivă perfectă(SKNF) a acestei funcții.

Teorema 3. Orice funcție booleană(nu este identic cu 1) poate fi transmis la SKNF, iar o astfel de reprezentare este singura.

Demonstrarea teoremei poate fi efectuată în mod similar cu demonstrația 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) din m variabilele pot fi reprezentate astfel:

. (2.9)

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

În practică, DNF este cel mai des utilizat, deoarece această formă este mai familiară unei persoane: încă din copilărie, el este mai obișnuit să adauge produse decât să înmulțească sume (în acest din urmă caz, intuitiv are dorința de a deschide parantezele și, astfel, de a trece 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 la care funcția ia valoarea 0 și să creați o conjuncție a termenilor maximi corespunzători,dar variabilele trebuie luate cu inversare inversă:

Trebuie remarcat faptul că este imposibil să treceți direct de la SDNF al unei funcții la SCNF-ul acesteia sau invers. Atunci când se încearcă astfel de transformări, rezultatele sunt funcții care sunt opuse celor dorite. Expresiile pentru funcțiile SDNF și SCNF 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ă comutați de la SDNF la SKNF.

Folosind rezultatul exemplului 2.3 obținem:

După cum puteți vedea, sub inversiunea generală am obținut SCNF-ul unei funcții logice, care este inversul funcției obținute în exemplul 2.4:

deoarece conține toți termenii max care nu sunt în expresia pentru SCNF a funcției luate în considerare.

1. Folosind proprietățile operațiilor (vezi Tabelul 9) identitate (), sumă modulo 2 (), implicație (), trecem la operațiile AND, OR, NOT (în baza booleană).

2. Folosind proprietățile negației și legile lui De Morgan (vezi Tabelul 9), ne asigurăm că operațiile de negație se aplică numai variabilelor individuale și nu expresiilor î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, treceți la formele perfecte (SDNF sau SKNF). De exemplu, pentru a obține SCNF trebuie adesea să utilizați proprietatea: .

Exemplul 6. Convertiți o funcție logică î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ția CNF f (x 1 , x 2 , x 3 ). Pentru a-și obține SCNF, trebuie să repeți fiecare disjuncție în care lipsește orice variabilă, de două ori cu această variabilă și cu negația ei:

2.2.6. Minimizarea funcțiilor logice

Deoarece aceeași funcție logică poate fi reprezentată ca h formule personale, apoi găsirea formei celei mai simple r mule care definește o funcție booleană, simplifică circuitul logic care implementează funcția booleană a tion. Forma minima l O functie logicaîn anumite baze putem considera unul care conține numărul minim de suprapuneri de distracție La de bază, permițând parantezele. Cu toate acestea, este dificil să construiți un eficient l algoritm pentru o astfel de minimizare pentru a obține paranteza minimă noi.

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

metoda lui Quine

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

, (2.10)

și apoi absorbția

, (2.11)

iar această pereche de pași se aplică în mod repetat. Astfel, este posibil să se reducă rangul termenilor. Această procedură se repetă până când nu mai rămâne niciun termen care să poată fi legat de orice 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ă deoarece, cu o astfel de minimizare directă, termenii conjunctivi fie dispar, deși există încă cazuri posibile de utilizare a acestora pentru lipire și absorbție cu termenii rămași.

Trebuie remarcat faptul că metoda lui Quine necesită multă muncă, astfel încât probabilitatea de a face greșeli în timpul transformărilor este destul de mare. Dar avantajul său este că teoretic poate fi folosit pentru orice număr de argumente și pe măsură ce numărul de variabile crește, transformările devin mai puțin complicate.

Metoda hărții Karnaugh

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

Harta Carnot aceasta este o formă tabelară bidimensională de reprezentare a tabelului de adevăr al unei funcții booleene, care vă permite să găsiți cu ușurință DNF-urile minime ale funcțiilor logice într-o formă vizuală grafică. Fiecare celulă a tabelului este asociată cu termenul SDNF al funcției care este minimizat și în așa fel încât orice axe de simetrie ale tabelului să corespundă zonelor care sunt reciproc inverse față de o variabilă. Această aranjare a celulelor în tabel face ușoară determinarea termenilor de lipire ai SDNF (diferă prin semnul de inversare a unei singure variabile): ei sunt localizați simetric în tabel.

Tabele de adevăr și hărți Carnaugh pentru funcțiile AND și SAU ale două benzi e Variabilele sunt prezentate în Fig. 8. În fiecare celulă a cardului este scrisă o valoare O Valoarea unei funcții din setul de valori ale argumentelor corespunzătoare acestei celule N Tovarăşe

A) ȘI b) SAU

Orez. 8. Exemplu de hărți Karnaugh pentru funcții a două variabile

În harta Karnaugh există un singur 1 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 Carnot pentru funcția SAU există deja trei 1-uri și puteți face două perechi de lipire, cu 1 corespunzător termenului xy , este folosit de două ori. În expresia funcției minime, trebuie să scrieți termenii perechilor care sunt lipite, lăsând în ele toate variabilele care nu se schimbă pentru această pereche și eliminând variabilele care își schimbă valoarea. Pentru lipirea orizontală obținem x , iar pentru verticală y , ca rezultat obținem expresia

f = x + y.

În fig. 9 arată tabelele de adevăr a două funcții a trei variabile ( O ) și hărțile lor Carnot ( b și c). Funcția f 2 diferă de prima prin faptul că nu este definită pe trei seturi de variabile (în tabel aceasta este indicată printr-o liniuță).

La determinarea funcției DNF minime, se folosesc următoarele reguli. Toate celulele care conțin 1 sunt combinate în zone dreptunghiulare închise numite k-cuburi, unde k = log 2 K, K cantitatea 1 într-o zonă dreptunghiulară. În acest caz, fiecare zonă ar trebui să fie un dreptunghi cu numărul de celule 2 k, unde k = 0, 1, 2, 3, …. Pentru k = Se numeste 1 dreptunghi 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ă cuburi; pentru k = 3 regiunea lui 2 3 = 8 unități se numesc trei cuburi ; etc. Pot fi numite unități care nu pot fi combinate în dreptunghiuri zero-cuburi , care conțin o singură unitate (2 0 = 1). După cum se vede, chiar și k zonele pot avea o formă pătrată (dar nu neapărat) și dacă sunt impare k doar dreptunghiuri.

						b c

Orez. 9. Exemplu de hărți Karnaugh pentru funcții a trei variabile

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

Fiecare dintre zonele indicate pe harta Karnaugh este reprezentată într-un DNF minim printr-o conjuncție, numărul de argumente în care este k Mai puțin numărul total argumente ale funcției m , adică acest număr este egal mk . Fiecare conjuncție a unui DNF minim este compusă numai din acele argumente care pentru zona corespunzătoare a hărții au valori fie fără inversiuni, fie numai cu inversiuni, adică nu își schimbă sensul.

Astfel, atunci când acoperiți celulele hărții cu zone închise, trebuie să ne străduim să vă asigurați că numărul de zone este minim și fiecare zonă conține cât mai multe celule posibil, deoarece în acest caz numărul de termeni din DNF minim va fi minim și numărul de argumente în conjuncția corespunzătoare va fi minim.

Pentru funcția conform hărții Karnaugh din Fig. 9, b găsim

întrucât pentru regiunea închisă superioară variabilele x 1 și x 2 au valori fara inversiuni, pentru cele mai mici x 1 contează cu inversiunea și x 3 fără inversare.

Valori nedefinite în harta din Fig. 9, V poate fi definit în continuare prin înlocuirea acestuia cu zero sau unu. Pentru această funcție este clar că este mai profitabil să înlocuiți ambele valori nedefinite cu 1. În acest caz, se formează două zone, care sunt diverse tipuri 2-mc. Atunci expresia pentru funcția DNF minimă va fi următoarea:

Când construiți zone închise, este permisă plierea hărții Carnaugh într-un cilindru atât pe orizontală, cât și pe verticală. r axele de căpuşă cu unirea feţelor opuse r tu, adică unități situate de-a lungul marginilor hărții de simetrie Carnot h dar poate fi și combinat.

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

									x 2 x 3

a b

Orez. 10. Diferite moduri de a descrie hărțile Carnaugh
pentru o funcție de 3 variabile

Dar cele mai convenabile opțiuni pentru hărțile Karnaugh pentru funcții de 2-4 variabile sunt cele prezentate în Fig. 11 tabele, pentru că arată pentru fiecare celulă O Avem toate variabilele în formă directă sau inversă.

a b

Orez. 11. Cea mai convenabilă imagine a hărților Carnaugh
pentru funcțiile 3 ( a) și 4 (b) variabile

Pentru funcțiile cu 5 și 6 variabile, metoda prezentată în Fig. 10, V .

Orez. 12. Imaginea unei hărți Karnaugh pentru o funcție de 5 variabile

Orez. 13. Imagine a unei hărți Karnaugh pentru o funcție de 6 variabile

Alte lucrări similare care vă pot interesa.vshm>
9020.		PRINCIPIUL DUALITĂȚII. EXTENSIREA FUNCȚILOR BOOLEANE ÎN VARIABILE. FORME NORMALE DISJUNCTIVE ȘI CONJUNCTIVE PERFECTE	96,34 KB
	Această teoremă este de natură constructivă, deoarece permite fiecărei funcție să construiască o formulă care o implementează sub forma unui d.n perfect. f. Pentru a face acest lucru, în tabelul de adevăr pentru fiecare funcție marchem toate rândurile în care
6490.		Descrierea și minimizarea funcțiilor logice	187,21 KB
	Relația dintre argumentele unei funcții și valorile acesteia este exprimată în formă verbală. Exemplu: O funcție cu trei argumente ia o valoare atunci când oricare două sau mai multe argumente ale 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, folosind tabelul de adevăr, obținem următoarea intrare sub formă de 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ționale Acesta este un set de relații interconectate în care sunt definite toate atributele, sunt specificate cheile primare ale relațiilor și sunt specificate unele proprietăți suplimentare ale relațiilor 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 implementare a funcțiilor de stat	197,3 KB
	Termenul „funcție” are departe de a fi același înțeles în literatura științifică națională ș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 ansamblu de acţiuni obişnuite sau specifice ale indivizilor sau organismelor
17873.		Formarea UUD logic pentru elevii clasei a III-a	846,71 KB
	Aspecte psihologice și pedagogice ale problemei formării acțiunilor logice universale în şcolari juniori Metode de evaluare a formării UUD-urilor logice. Dezvoltarea unui concept pentru dezvoltarea universalului activități educaționaleîn sistem educatie generala satisface noile nevoi sociale. Cea mai importantă sarcină sistem modern educația este formarea activităților educaționale universale ale UUD. Formarea de activități educaționale universale este cheia prevenirii dificultăților școlare.
2638.		Implementarea tehnică a conexiunilor logice în sistemele automate de blocare	1,04 MB
	Implementarea tehnică a conexiunilor logice în sistemele de blocare automată Implementarea tehnică a algoritmilor de control pentru bateriile cu trei și patru cifre poate fi realizată utilizând contact rele și elemente logice discrete și integrale fără contact...
10203.		APLICAREA CONCEPTULUI DE ABORDARE ORIENTATĂ LA RISC PENTRU CONSTRUIREA MODELELOR STRUCTURALE ȘI LOGICE DE Apariție ȘI DEZVOLTARE A URGENȚEI	70,8 KB
	Analiza generala risc Mediul de producție devine saturat de puternic sisteme tehnologiceși tehnologii care fac munca umană productivă și mai puțin dificilă din punct de vedere fizic, dar mai periculoasă. Riscul se caracterizează prin caracterul neașteptat și brusc al apariției 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ă impact negativ asupra unei persoane, precum și cauzarea de prejudicii sănătății și vieții acesteia.
11576.		Concept, tipuri și forme de tranzacții. Consecințele nerespectării formei cerute de tranzacții	49,82 KB
	Recunoașterea unei tranzacții ca fiind nevalide; Valoarea aplicației munca de curs este de a simplifica conceptul de tranzacție, adică de a o prezenta public într-o formă mai accesibilă.
6213.		Aproximarea funcției	3,08 MB
	Prima constă în înlocuirea unei anumite funcții specificate analitic sau tabelar cu o altă funcție apropiată de cea inițială 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 integrare numericăși diferențiere; Înlocuirea tabelului cu o funcție de aproximare vă permite să obțineți valori în punctele sale intermediare. Apare și a doua problemă: restabilirea unei funcții pe un anumit segment din valorile funcției date pe acest segment într-un set discret de puncte. Raspunsul la aceasta intrebare...
14058.		Evoluţia funcţiilor statului	29,99 KB
	stat rusesc ca fenomen juridic, în primul rând, trebuie să asigure punerea în aplicare a scopului statului, precum și principalele sale caracteristici constituționale ca societate juridică federală democratică. stat laic Cu formă republicană bord. Scopul principal al statului este determinat de art.

Disjunctiv și conjunctiv forme normale algebre propoziționale. Pentru fiecare funcție logică propozițională se poate construi un tabel de adevăr. Problema inversă este, de asemenea, întotdeauna rezolvabilă. Să introducem câteva definiții.

Conjuncții elementare (conjuncții) se numesc conjuncţii de variabile sau negaţii ale acestora în care fiecare variabilă apare cel mult

dată.

Forma normală disjunctivă(DNF) este o formulă care are forma unei disjuncții de conjuncții elementare.

Disjuncții elementare (disjuncții) se numesc disjuncţii de variabile cu sau fără negaţii.

Forma normală conjunctivă(CNF) este o formulă care are forma unei conjuncții de disjuncții elementare.

Pentru fiecare funcție de algebră propozițională se poate găsi un set de forme normale disjunctive și conjunctive.

Algoritm pentru construirea DNF:

1. Accesați operațiuni booleene folosind formule de transformare echivalente.

2. Mergeți la formule cu negații apropiate, adică la o formulă în care negațiile sunt situate nu mai sus decât deasupra variabilelor - aplicați legile lui De Morgan.

3. Deschideți parantezele - aplicați legile distributivității.

4. Luați termeni care se repetă pe rând - legea idempotității.

5. Aplicați legile absorbției și semiabsorbției.

Exemplul 6. Găsiți formule DNF: .

În algebra booleană este adevărat principiul dualității. Este după cum urmează.

Funcția este numită dual la funcţia dacă . Aceste. Pentru a găsi o funcție duală cu una dată, este necesar să construim negația funcției din negațiile argumentelor.

Exemplul 7. Găsiți funcția duală la .

Printre functii elementare algebra logicii 1 este duală cu 0 și invers, x este duală cu x, duală cu , duală și invers.

Dacă în formula F 1 reprezentând funcţia înlocuim toate conjuncţiile

pe disjuncție, disjuncție pe conjuncție, 1 pe 0, 0 pe 1, apoi obținem formula F * reprezentând funcția * duală la .

Forma normală conjunctivă (CNF) este un concept dual pentru DNF, deci poate fi construită cu ușurință conform următoarei scheme:

Exemplul 8. Găsiți formula CNF: .

Folosind rezultatul din Exemplul 6, avem

Formele normale disjunctive perfecte și conjunctive perfecte.În fiecare tip de forme normale (disjunctive și conjunctive), se poate distinge o clasă de forme perfecte SDNF și SCNF.

O conjuncție elementară perfectă este produsul logic al tuturor variabilelor cu sau fără negație, iar fiecare variabilă apare în produs o singură dată.

Orice DNF poate fi redus la SDNF prin divizarea conjuncțiilor care nu conțin toate variabilele, de exemplu. prin adunarea pentru variabila lipsă x i se înmulțește folosind legea distributivă

Exemplul 9. Găsiți SDNF pentru DNF din Exemplul 6

Disjuncția elementară perfectă este suma logică a tuturor variabilelor cu sau fără negații, iar fiecare variabilă este inclusă în sumă o singură dată.

Orice CNF poate fi redus la SCNF prin adăugarea unui termen de conjuncție care nu conține nicio variabilă X i prin conjuncție și aplicând legea distributivă

Exemplul 10. Aduceți KNF la SKNF:

Pentru a construi SCNF, puteți utiliza diagrama

Exemplul 11. Găsiți SCNF pentru formula din exemplul 6.

Fiecare funcție are un SDNF și, în plus, unul unic. Fiecare funcție are un SCNF și, în plus, unul unic.

Deoarece SDNF și SKNF sunt definite în mod unic prin formule, acestea pot fi construite folosind tabelul de adevăr al formulei.

Pentru a construi un SDNF, este necesar să selectați rândurile în care F ia valoarea 1 și să scrieți conjuncțiile elementare perfecte pentru ele. Dacă valoarea unei variabile din rândul dorit al tabelului de adevăr este egală cu unu, atunci într-o conjuncție perfectă se ia fără negație, dacă zero, atunci cu negație. Apoi conjuncțiile perfecte (numărul lor este egal cu numărul de unități din tabel) sunt legate prin semne de disjuncție.

Pentru a construi un SCNF folosind un tabel de adevăr, este necesar să selectați rândurile din acesta unde F = 0 și să scrieți disjuncțiile elementare perfecte și apoi să le conectați cu semne de conjuncție. Dacă în rândul necesar al tabelului de adevăr (F=0) valoarea variabilei corespunde cu zero, atunci în clauza perfectă se ia fără negație, dacă este una, atunci cu negație.

Exemplul 12. Găsiți SDNF și SCNF folosind tabelul de adevăr pentru formula exemplului 6.

Tabelul 14 arată doar valoarea finală F=10101101. Ar trebui să verificați singur validitatea acestei afirmații prin construirea unui tabel de adevăr detaliat.

Tabelul 14

x	y	z

Forma normală o formulă logică nu conține semne de implicare, echivalență și negație a formulelor neelementare.

Forma normală se prezintă sub două forme:

forma normala conjunctiva (CNF)-- conjuncția mai multor disjuncții, de exemplu, $\left(A\vee \overline(B)\vee C\right)\wedge \left(A\vee C\right)$;

forma normala disjuntiva (DNF)-- disjuncția mai multor conjuncții, de exemplu, $\left(A\wedge \overline(B)\wedge C\right)\vee \left(B\wedge C\right)$.