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.

~

Este cunoscut (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. Exercițiu.

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 control.

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.6. Folosind transformări echivalente, dovediți adevărul identic al formulelor:

2.3.7. 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):

~

Lucrare de laborator nr 3

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 trecerea de la o specificație tabelară a unei funcții la expresia ei analitică. În cele ce urmează, vom proceda de la forma disjunctivă, iar rezultatele corespunzătoare pentru forma conjunctivă se obțin pe baza principiului dualității.

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 urmare, 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. În consecință, submulțimea vârfurilor marcate este o mapare pe cubul -dimensional al unei funcții booleene de variabile î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 minitermen de rang (constituent al unității), i.e. , 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 aceasta). 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 ()-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ârfurile sale. . 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 minitermilor 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 – ; pe dreapta –

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ă construcții atât de complexe încât toate avantajele sale se pierd.

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. . Din acest motiv, 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, A 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 o hartă Karnaugh urmează o regulă simplă. 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. Diferite moduri de citire 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

Inconsecvența metodelor grafice cu un număr mare de variabile este compensată de diverse metode analitice de reprezentare a 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 ( A) ș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

Formularea 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 forma 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ă de cea mai mică valoare a prețului său.

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 cuburi. 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, la fel ca 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 este 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 date a algebrei propoziționale se numește un astfel de CNF al acesteia 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 transformării 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:

randul 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:

A) ;

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) ;

Forma normală conjunctivă este convenabilă pentru demonstrarea automată a teoremelor. Orice formulă booleană poate fi redusă la CNF. Pentru aceasta puteți folosi: legea dublei negații, legea lui de Morgan, distributivitatea.

YouTube enciclopedic

• 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 în 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).)

  Construcția CNF

  Algoritm pentru construirea CNF

  1) Scăpați de toate operațiile logice cuprinse în formulă, înlocuindu-le cu cele de bază: conjuncție, disjuncție, negație. 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 negație referitor la întreaga expresie cu semne de negație referitoare la declarațiile variabile individuale bazate pe formulele:

  ¬ (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) Scapa de dublele negative.

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

  Exemplu de construcție CNF

  Să aducem formula la CNF

  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 negative duble:

  F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\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).)

  Simplu conjuncţie numit conjuncţie unu sau mai multe variabile, la acest fiecare variabil se intalneste Nu Mai mult unu ori (sau se, sau a ei negare).

  De exemplu, este o conjuncție simplă,

  Disjunctiv normal formă(DNF) numit disjuncție simplu conjuncţii.

  De exemplu, expresia este DNF.

  Perfect disjunctiv normal formă(SDNF) numit ca aceasta disjunctiv normal formă, la care V fiecare conjuncţie inclus Toate variabile dat listă (sau înșiși, sau al lor negare), și V unu Și volum sauBine.

  De exemplu, expresia este DNF, dar nu SDNF. Expresie este SDNF.

  Definiții similare (cu înlocuirea conjuncției cu disjuncție și invers) sunt valabile pentru CNF și SKNF. Să dăm formularea exactă.

  Simplu disjuncție numit disjuncție unu sau mai multe variabile, la acest fiecare variabil inclus Nu Mai mult unu ori (sau se, sau a ei negare).De exemplu, expresia este o disjuncție simplă,

  Conjunctiv normal formă(KNF) numit conjuncţie simplu disjuncţii(de exemplu, expresia este CNF).

  O formă normală conjunctivă perfectă (PCNF) este o CNF în care fiecare disjuncție simplă include toate variabilele unei liste date (fie ele însele sau negațiile lor) și în aceeași ordine.

  De exemplu, expresia este SKNF.

  Să prezentăm algoritmi pentru tranzițiile de la o formă la alta. Desigur, în cazuri specifice (cu o anumită abordare creativă) utilizarea algoritmilor poate fi mai laborioasă decât transformările simple folosind un anumit tip de formă dată:

  a) trecerea de la DNF la CNF

  Algoritmul pentru această tranziție este următorul: punem două negații deasupra DNF și, folosind regulile lui De Morgan (fără a atinge negația superioară), reducem negația DNF înapoi la DNF. În acest caz, trebuie să deschideți paranteze folosind regula de absorbție (sau regula lui Blake). Negația (superioară) a DNF rezultat (din nou conform regulii lui de Morgan) ne oferă imediat CNF:

  Rețineți că CNF poate fi obținut și din expresia originală dacă scoatem la dincolo de paranteze;

  b) trecerea de la CNF la DNF

  Această tranziție se realizează prin simpla deschidere a parantezelor (se folosește din nou regula de absorbție)

  Astfel, am primit DNF.

  Tranziția inversă (de la SDNF la DNF) este asociată cu problema minimizării DNF. Acest lucru va fi discutat mai detaliat în secțiune. 5, aici vom arăta cum să simplificăm DNF (sau SDNF) conform regulii lui Blake. Acest tip de DNF se numește abreviat DNF;

  c) abrevierea DNF (sau SDNF) prin regulă Blake

  Aplicarea acestei reguli constă din două părți:

  Dacă printre termenii disjunși din DNF există termeni , apoi la întreaga disjuncție adăugăm termenul LA 1 LA 2. Efectuăm această operație de mai multe ori (eventual secvențial, sau simultan) pentru toate perechile posibile de termeni și apoi aplicăm absorbția normală;

  Dacă termenul adăugat a fost deja conținut în DNF, atunci poate fi eliminat complet, de exemplu,

  sau

  Desigur, DNF abreviat nu este definit în mod unic, dar toate conțin același număr de litere (de exemplu, există DNF , după aplicarea regulii lui Blake, se poate ajunge la un DNF echivalent cu acesta):

  c) trecerea de la DNF la SDNF

  Dacă unei conjuncții simple lipsește o variabilă, de exemplu, z, introduceți expresia în ea și apoi deschideți parantezele (nu scriem termeni disjunși care se repetă). De exemplu:

  d) trecerea de la KNF la SKNF

  Această tranziție se realizează într-o manieră similară cu cea anterioară: dacă unei disjuncții simple lipsește o variabilă (de exemplu, z, apoi îi adăugăm o expresie (aceasta nu schimbă disjuncția în sine), după care deschidem paranteze folosind legea distribuției):

  Astfel, SKNF a fost obținut de la CNF.

  Rețineți că CNF-ul minim sau redus este de obicei obținut din DNF-ul corespunzător.

  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ă o modalitate 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ține exact una dintre toate variabilele logice ale funcției, luate cu sau fără negații, atunci un astfel de CNF se numeșteforma 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 realizată î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ă destul de 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 hărții este scrisă o valoare A 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 = xy.

  În harta Carnot pentru funcția SAU există deja trei 1-uri și puteți face două perechi lipite, cu 1 corespunzător termenului X y , 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 ( A ) ș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 de 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 mic decât numărul total de 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 tipuri diferite de 2-cuburi. Atunci expresia pentru funcția DNF minimă va fi următoarea:

  Când construiți zone închise, este permisă plierea hărții Carnot într-un cilindru atât pe orizontală, cât și pe verticală. R axele tikal 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 reprezenta 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ă A Avem toate variabilele în formă directă sau inversă.

  a b

  Orez. unsprezece. 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, un proiect de bază de date stă la baza unui viitor pachet software care va fi folosit destul de 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 la elevii din ciclul primar Metode de evaluare a formării UUD-urilor logice. Elaborarea 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 modern de învățământ 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 generală a riscurilor Mediul de producție devine saturat de sisteme tehnologice și tehnologii puternice care fac ca munca umană să fie 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ă a impactului negativ asupra unei persoane, precum și a prejudiciului asupra sănătății și vieții sale.
  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 aplicată a cursului constă în simplificarea conceptului de tranzacție, adică prezentarea publică a acesteia î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 de 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 ș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
  	Statul rus ca fenomen juridic trebuie să asigure în primul rând punerea în aplicare a scopului statului, precum și a principalelor sale caracteristici constituționale ca stat laic social, federal, democratic, cu o formă republicană de guvernare. Scopul principal al statului este determinat de art.