Definiția 1.Monomiul conjunctiv (conjuncție elementară) din variabile se numește 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, - disjuncție elementară.
Definiția 3. O formulă echivalentă cu o formulă de algebră propozițională dată și fiind 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ă echivalentă cu o formulă de algebră propozițională dată și fiind conjuncția monomiilor disjunctive elementare se numește forma normală conjunctivă(CNF) din această formulă.
de exemplu, - CNF.
Pentru fiecare formulă a algebrei propoziționale, se poate găsi un set de forme normale disjunctive și conjunctive.
Algoritm pentru construirea formelor normale
Folosind echivalențe ale algebrei logicii, înlocuiți toate operațiile din formulă cu cele de bază: conjuncție, disjuncție, negație:
Scapa de semnele de dubla negatie.
Aplicați, dacă este necesar, la operațiile de conjuncție și disjuncție proprietățile distributivității și formula de absorbț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ă perfect DNF (SDNF) și perfect CNF (SKNF).
Definiția 1. Forma normală disjunctivă perfectă(SDNF) este un DNF în care în fiecare monom conjunctiv fiecare variabilă din mulțime apare exact o dată și apare fie ea însăși, fie negația sa.
În mod constructiv, SDNF pentru fiecare formulă a algebrei propoziționale redusă la 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ă(SKNF) este un CNF în care în fiecare monom disjunctiv fiecare variabilă din mulțime apare exact o dată și apare fie ea însăși, fie negația sa.
Din punct de vedere structural, SKNF pentru fiecare formulă a algebrei propoziționale redusă la CNF poate fi definit după cum urmează.
Definiția 4. Forma normală conjunctivă perfectă(SKNF) a unei formule de algebră propozițională dată se numește CNF ei 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, în plus, într-un mod unic.
Modalități de a găsi SDNF
1-a cale
a 2-a cale
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ă într-o conjuncție cu valoarea 1, atunci scriem această variabilă, dacă are 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 SKNF și, în plus, într-un mod unic.
Modalități de a găsi SKNF
1-a cale- folosind transformări echivalente:
a 2-a cale- 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ă într-o disjuncție cu valoarea 0, atunci scriem această variabilă, dacă cu valoarea 1, atunci negația ei. Primim SKNF.
Exemplul 1. Trasează funcțiile CNF.
Soluţie
Să excludem legătura „” folosind legile de transformare a variabilelor:
= / de Morgan și legile dublei negații / =
/ legi distributive / =
Exemplul 2. Aduceți formula la DNF.
Soluţie
Să exprimăm operațiile logice în termeni și:
= / vom referi negația la variabile și vom reduce dublele negative / =
= / legea distribuției /.
Exemplul 3. Scrieți formula în DNF și SDNF.
Soluţie
Folosind legile logicii, vom aduce 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, vom alcătui 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 formula care este adevărată pe setul de variabile, al rândului dat:
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ă (SDNF):
Exemplul 4. Aduceți formula la SKNF în două moduri:
a) folosind transformări echivalente;
b) folosind tabelul de adevăr.
Soluţie:
Transformăm a doua disjuncție elementară:
Formula este:
b) alcătuieș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 formula care este adevărată pe setul de variabile, al rândului dat:
randul 2:;
linia 6:.
Conjuncția acestor două formule va lua valoarea 0 numai pe seturile de variabile din liniile 2 și 6 și, prin urmare, va fi forma normală conjunctivă perfectă dorită (SCNF):
Întrebări și sarcini pentru soluții independente
1. Folosind transformări echivalente, aduceți formulele la DNF:
2. Folosind transformări echivalente, aduceți formulele la CNF:
3.Utilizați a doua lege distributivă pentru a converti DNF în CNF:
A) 
;
4. Convertiți DNF-urile date în SDNF-uri:
5. Convertiți CNF-ul dat în SKNF:
6. Pentru formulele logice date, construiți SDNF și SKNF în două moduri: folosind transformări echivalente și folosind tabelul de adevăr.
b) 
;
Forma normală conjunctivă este convenabilă pentru demonstrarea automată a teoremei. Orice formulă booleană poate fi convertită în CNF. Pentru a face acest lucru, puteți folosi: legea dublei negații, legea lui de Morgan, distributivitatea.
YouTube colegial
-
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).)Construirea CNF-ului
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, 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 semnele de negație, referitor la declarații de 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) Scăpați 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 (\ stil de afișare F) la o formulă care nu conține → (\ stil de afișare \ săgeată la dreapta):
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 dublele negative:
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).)Disjuncție simplă(disjuncție inclusivă) sau disjunct(English disjunct) este o disjuncție a uneia sau mai multor variabile sau a negațiilor acestora, iar 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 variabile negative.
Forma normală conjunctivă, CNF(ing. forma normală conjunctivă, CNF) formă normală, în care funcția booleană are forma conjuncției mai multor propoziții simple.
Exemplu CNF:$ f (x, y) = (x \ lor y) \ land (y \ lor \ neg (z)) $
SKNF
Forma 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 identitatea, există un SKNF care o definește.
Dovada: 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) $
Găsiți inversul părților stânga și dreaptă 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 de Morgan de două ori expresiei obținute în 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, se demonstrează teorema.
Algoritm pentru construirea SKNF conform tabelului de adevăr
- În tabelul de adevăr marchem acele seturi de variabile pe care valoarea funcției este egală cu $ 0 $.
- Pentru fiecare mulțime marcată, scriem disjuncția tuturor variabilelor după următoarea regulă: dacă valoarea unei variabile este $ 0 $, atunci variabila însăși este inclusă în disjuncție, în caz contrar negația ei.
- Conectăm toate disjuncțiile rezultate prin operații de conjuncție.
Un exemplu de construire a SKNF pentru mediană
unu). În tabelul de adevăr marchem 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 mulțime marcată, scriem conjuncția tuturor variabilelor după următoarea regulă: dacă valoarea unei variabile este $ 0 $, atunci includem variabila însăși în disjuncție, în caz contrar negația ei.
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) $
Exemplu. Găsiți formule CNF
~
~ 
O formă normală disjunctivă perfectă a SDNF poate fi construită folosind următorul algoritm:
1. = 1. a algoritmului DNF
2. = 2. a algoritmului DNF
3. = 3.Algoritmul DNF
4. = 4. a algoritmului DNF
5. Eliminați termenii identic falși, adică termenii formei
6. Completați termenii rămași cu variabilele lipsă
7. Repetați pasul 4.
Exemplu. Găsiți formule SDNF.
~ 
Pentru a construi SKNF, puteți utiliza următoarea schemă:
Exemplu. Găsiți formule SDNF.
~ 
Este cunoscut (Teoremele 2.11, 2.12) că SDNF și SKNF sunt determinate în mod unic de formulă și, prin urmare, pot fi construite din tabelul de adevăr al formulei.
Schema de construire a SDNF și SKNF 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 expresiile 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. Aflaț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 conform principiului generalizat și boolean (Tabelul 1). Comparați rezultatele.
№ f 1 f 2 f 3 
2.3. Întrebări de control.
2.3.1. Dați definiția enunțului.
2.3.2. Enumerați operațiunile de bază asupra enunțului.
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 efectuării 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. Aduceți următoarele formule la forma perfectă DNF (SDNF):
~ 2.3.9. Aduceți următoarele formule la forma perfectă CNF (SKNF):
~ 
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 se arată în, orice funcție booleană este reprezentabilă în formă normală perfectă (disjunctivă sau conjunctivă). Mai mult, o astfel de prezentare este primul pas în trecerea de la definiția tabelului unei funcții la exprimarea 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 reduce la minimizarea funcțiilor booleene, adică. să le reprezinte în formă normală disjunctivă, care conține cel mai mic număr de litere (variabile și negațiile acestora). Astfel de forme sunt numite minimale. În sinteza canonică, se presupune că atât semnalele, cât și inversiunile lor sunt alimentate la intrările circuitului.
Formula, prezentată sub forma normală disjunctivă, este simplificată prin multiple aplicații ale operației de lipire și ale 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ă a algebrei booleene. Ca rezultat, ajungem la o expresie analitică atunci când transformările ulterioare sunt deja imposibile, adică. obținem o formă fără fund.
Printre formele de fund se află forma disjunctivă minimă și poate să nu fie unică. Pentru a vă asigura că o anumită formă de fundătură este minimă, este necesar să găsiți toate formele fără fund și să le comparați după numărul de litere pe care le conțin.
De exemplu, să fie dată funcția în formă disjunctivă normală perfectă:
Gruparea membrilor si aplicarea operatiei 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 oricând, deoarece). În primul caz, un astfel de membru poate fi. Atunci . Prin adăugarea unui membru, obținem:. După ce parcurgeți 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 găsire a formelor minimale devine mai vizual și mai intenționat dacă utilizați unele reprezentări și simboluri grafice și analitice special concepute în acest scop.
Cub multidimensional
Fiecare vârf al cubului -dimensional poate fi asociat cu constituentul unității. Prin urmare, 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 Secțiunea 3.7.
Fig. 3.1 Afișarea pe un cub tridimensional a funcției prezentate în SDNF
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.
Miniterma de (-1) --lea rang poate fi considerată ca rezultat al lipirii a doi minitermi de --lea rang (constituent 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 printr-o muchie (se spune că muchia acoperă vârfurile incidente). Astfel, minitermenii de ordinul (-1) le corespund muchiilor cubului -dimensional. În mod similar, corespondența minitermenilor de ordinul (-2) se stabilește cu fețele cubului -dimensional, fiecare dintre ele acoperă patru vârfuri (și patru muchii).Elementele unui cub -dimensional, caracterizate prin dimensiuni, se numesc -cuburi. Deci, vârfurile sunt 0-cuburi, muchiile sunt 1-cuburi, fețele sunt 2-cuburi etc. Rezumând raționamentul de mai sus, putem presupune că minitermenul rangului () --lea în forma normală disjunctivă pentru funcția variabilelor este afișat printr-un -cub, iar fiecare -cub acoperă toate acele -cuburi de cea mai mică dimensiune care sunt asociate cu vârfurile sale. Ca exemplu, Fig. 3.2 este dată maparea funcției a trei variabile. Aici minitermii și corespund la 1-cuburi (), iar minitermii sunt afișați ca 2-cuburi ().
Figura 3.2 Acoperirea funcției
Deci, orice formă normală disjunctivă este afișată pe cubul -dimensional printr-o colecție de -cuburi care acoperă toate vârfurile corespunzătoare constituenților unității (0-cuburi). Reversul este de asemenea adevărat: dacă o colecție de -cuburi acoperă mulțimea tuturor vârfurilor corespunzătoare valorilor unitare ale funcției, atunci disjuncția minitermenilor corespunzătoare acestor -cuburi este expresia acestei funcții în formă normală disjunctivă. . Se spune că un astfel de set de -cuburi (sau minitermenii corespunzători) formează acoperirea unei funcții.
Efortul pentru forma minimală este înțeles intuitiv ca căutarea unei astfel de acoperiri, al căror 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 acoperirea funcției din Fig. 3.3 se potrivește cu 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ă pentru. Un cub cu patru dimensiuni poate fi desenat așa cum se arată în fig. 3.4, unde funcția a patru variabile și acoperirea minimă a acesteia corespunde expresiei 
... Utilizarea 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 dimensiuniHărți Karnaugh
O altă metodă de reprezentare grafică a funcțiilor booleene folosește Hărți Karnot, care sunt tabele de căutare 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, atât celulele adiacente orizontală, cât și verticală ale tabelului diferă în valoarea unei singure variabile. Celulele situate la marginile tabelului sunt, de asemenea, considerate adiacente și au această proprietate. În fig. 3.5 arată diagramele Karnaugh pentru două, trei, patru variabile.
Orez. 3.5 Hărți Karnot 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 unele (zerourile de obicei nu se potrivesc, ele corespund celulelor goale). De exemplu, în Fig. 3.6, A arată harta Karnot pentru funcție, a cărei mapare pe cubul cu patru dimensiuni este dată în Fig. 3.4. Pentru simplitate, rândurile și coloanele corespunzătoare valorilor lui 1 pentru o anumită variabilă sunt cuprinse între acolade cu denumirea acelei variabile.
Orez. 3.6 Afișarea unei funcții a patru variabile pe o diagramă Karnot
(a) și acoperirea minimă a acesteia (b)
Între mapările funcțiilor activate n-cub dimensional iar pe harta Karnot există o corespondență unu-la-unu. Pe harta din Karnot s-cubul corespunde unei colecții de 2 celule învecinate situate într-un rând, coloană, pătrat sau dreptunghi (ținând cont de apropierea marginilor opuse ale hărții). Prin urmare, toate prevederile expuse mai sus (vezi p. cub multidimensional) sunt valabile pentru hărțile Karnot. Deci, în fig. 3.6, b se arată acoperirea unităţilor de hartă corespunzătoare formei disjunctive minime
funcția luată în considerare.Citirea minitermenilor de pe cardul Karnot se realizează după o regulă simplă. Celulele care se formează s-cub, da miniter (n – s)- rangul, care le include pe acelea (n – s) variabile care stochează aceleași valori pe aceasta s-cub, unde valoarea 1 corespunde variabilelor în sine, iar valorile 0 corespund negațiilor acestora. Variabile care nu își stochează valorile pentru s-cub, în miniterm lipsesc. Diferite moduri de citire duc la diferite reprezentări ale funcției în formă normală disjunctivă (cea din dreapta este minimă) (Fig. 3.7).
Utilizarea hărților Karnaugh necesită construcții mai simple decât 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 Karnot pentru patru variabile, iar pentru o funcție de șase variabile sunt utilizate patru astfel de hărți. Odată cu o creștere suplimentară a numărului de variabile, hărțile Karnot devin practic inutilizabile.
Cunoscut în literatură Hărți Weich diferă doar într-o ordine diferită a seturilor de valori ale variabilelor și au aceleași proprietăți ca hărțile Karnot.
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. Una dintre astfel de reprezentări este complex de cuburi folosind terminologia spațiului logic multidimensional în combinație cu simbolistica special concepută.
). 0-cuburile corespunzătoare constituenților unuia sunt reprezentate prin seturi de valori ale variabilelor pe care funcția este egală cu unu. Evident, în înregistrare
Orez. 3.8 Complex de cuburi ale unei funcții de trei variabile ( A) și reprezentarea sa simbolică ( b)
Se formează un complex de cuburi acoperire maximă a funcției... Excluzând din el pe toți cei s-cuburi, care sunt acoperite de cuburi de cea mai mare dimensiune, obtinem invelisuri corespunzatoare formelor de fund. Deci, pentru exemplul luat în considerare (Fig. 3.8) avem un capac de fund
,care corespunde funcţiei
... În acest caz, această acoperire este, de asemenea, 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 de cuburi. Negația unei funcții corespunde complementului unui complex de cuburi, adică este determinată de toate vârfurile la care funcția ia valoarea 0. Astfel, există o corespondență unu-la-unu (izomorfism) între algebra lui Boolean. funcții și mulțimi booleene reprezentând complexe de cuburi.
Reprezentarea unei funcții sub formă de complexe de cuburi este mai puțin clară, dar cele mai importante avantaje ale acesteia sunt că elimină restricțiile privind numărul de variabile și facilitează codificarea informațiilor 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 în forma normală este exprimat prin prețul copertei
, unde este numărul de - cuburi care formează o acoperire a funcției date în 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ăutați o acoperire prescurtată care să includă toate -cuburile de dimensiune maximă, dar nu conține niciun cub acoperit de niciun cub din această acoperire. Forma normală disjunctivă corespunzătoare se numește prescurtată, iar minitermenii ei sunt numiți implicanți simpli. Pentru această funcție, acoperirea tăiată este singura, dar poate fi redundantă din cauza faptului că unele dintre cuburi sunt acoperite de colecții de alte cuburi.
În a doua etapă, se realizează trecerea de la formele normale disjunctive reduse la formele normale, din care sunt selectate formele minime. Formele de fund sunt formate prin excluderea din acoperirea abreviată a tuturor cuburilor redundante, fără de care setul de cuburi rămas încă formează o acoperire a funcției date, dar la excluderea ulterioară a oricăruia dintre cuburi, acesta nu mai acoperă seturile de toate vârfurile corespunzătoare valorilor unitare ale funcției, adică încetează să mai fie o acoperire ...
Un cub de acoperire redusă care acoperă vârfurile 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 corespunzător, se numește extremal (implicant esențial), iar vârfurile pe care le acoperă sunt numite vârfuri anulate. Setul de extremale formează nucleul acoperirii; este clar că atunci când se trece de la o acoperire redusă la cea minimă, în primul rând, toate extremele trebuie evidențiate. Dacă setul de extremale nu formează o acoperire, atunci acesta este suplimentat pentru a fi acoperit cu cuburi din capacul redus.
Aceste definiții sunt ilustrate în fig. 3.9, unde acoperirea redusă (vezi fig. 3.9a, ) iar acoperirea minimă (Fig. 3.9b) și (vezi Fig. 3.9, b) sunt exprimate după cum urmează.
Forme normale disjunctive și conjunctive ale algebrei propoziționale. Pentru fiecare funcție a logicii afirmațiilor, puteți crea un tabel de adevăr. Problema inversă este, de asemenea, întotdeauna rezolvabilă. Să introducem mai multe definiții.
Conjuncții elementare (conjuncții) sunt numite conjuncții de variabile sau negații ale acestora, în care fiecare variabilă apare cel mult
o singura data.
Forma normală disjunctivă(DNF) este o formulă care are forma unei disjuncții de conjuncții elementare.
Propoziții elementare (propoziț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 a algebrei propozițiilor, 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 - pentru a aplica legile lui de Morgan.
3. Extindeți paranteze - aplicați legile distribuției.
4. Luați termenii repeți o singură dată - legea idempotității.
5. Aplicați legile absorbției și semiabsorbției.
Exemplul 6. Găsiți formule DNF:.
Algebra booleană este valabilă principiul dualității... Este după cum urmează.
Funcția este numită dual la funcţia dacă. Acestea. pentru a găsi o funcție care este 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.
Dintre funcțiile elementare ale algebrei booleene, 1 este dual cu 0 și invers, x este dual cu x, dual, dual și invers.
Dacă în formula F 1 reprezentând funcţia se înlocuiesc toate conjuncţiile
pe disjuncție, disjuncție pe conjuncție, 1 la 0, 0 la 1, apoi obținem formula F * reprezentând funcția * duală.
Forma normală conjunctivă (CNF) este un concept dual pentru DNF, prin urmare este ușor să o construiți conform schemei:
Exemplul 8. Găsiți CNF-ul formulei:.
Folosind rezultatul din Exemplul 6, avem
Formele normale disjunctive perfecte și conjunctive perfecte.În fiecare dintre tipurile de forme normale (disjunctive și conjunctive), se poate distinge o clasă de forme perfecte SDNF și SKNF.
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. adunarea pentru variabila lipsă x i se înmulțește folosind legea distribuției
Exemplul 9. Găsiți SDNF pentru exemplul 6 DNF
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 SKNF prin adăugarea unui termen de conjuncție care nu conține nicio conjuncție variabilă X i și aplicând legea distributivă
Exemplul 10. Aduceți CNF la SKNF:
Pentru a construi SKNF, puteți utiliza schema
Exemplul 11. Găsiți SKNF pentru formula din exemplul 6.
Fiecare funcție are SDNF și, în plus, este unică. Fiecare funcție are un SKNF și, în plus, singura.
pentru că SDNF și SKNF sunt definite prin formule în mod unic, ele pot fi construite conform tabelului de adevăr al formulei.
Pentru a construi SDNF, este necesar să selectați liniile în care F ia valoarea 1 și să scrieți conjuncțiile elementare perfecte pentru ele. Dacă valoarea unei variabile din rândul necesar 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 conjunctele perfecte (numărul lor este egal cu numărul celor din tabel) sunt legate prin semne de disjuncție.
Pentru a construi SKNF conform tabelului de adevăr, este necesar să selectați liniile din acesta, unde F = 0, și să scrieți disjuncțiile elementare perfecte, 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 într-o clauză perfectă se ia fără negație, dacă este una - atunci cu negație.
Exemplul 12. Găsiți SDNF și SKNF folosind tabelul de adevăr pentru formula exemplului 6.
Tabelul 14 arată doar valoarea finală a lui F = 10101101. Ar trebui să vă convingeți singur de validitatea acestei afirmații prin construirea unui tabel de adevăr extins.
Tabelul 14
X y z