Extinderea funcțiilor booleene în variabile. Principiul dualității

Legătura dintre algebra mulțimilor și algebra logicii este că există 2 sisteme izomorfe.

BILETUL 25

Conceptul de dualitate. Principiul dualității.

Def. Pentru o funcție booleană dată dualul său se numește: ).

Note.

Să fie dată o funcție booleană.

Cometariu. În funcții f i, i=1,…,m unele variabile pot fi false.

= = = =

Consecinţă. Dacă o funcție booleană este dată de formula F în baza B 0 = (x&y,x˅y,-,0,1), atunci pentru a obține funcția duală este suficient să faceți substituția:

BILETUL 26

Extinderea funcțiilor booleene în variabile.

T. despre extinderea unei funcţii booleene în variabile.

Pentru orice funcție booleană f=f(x 1 ,…,x n) și V 1≤k≤n este valabilă reprezentarea f(x1,…,xn)=, unde x 1 =x, x 0 = ̚ x.

Să luăm o mulțime arbitrară Z=(α1,…,αn) și să o înlocuim în partea stângă și dreaptă a formulei:

L.H.=f(α1,…,αn)

P.Ch.= =

{ 1 0 ==0; 0 1 =0; 1 1 =1; 0 0 ==1; }

Partea dreaptă a coincis cu partea stângă.

Corolarul 1. Formula pentru descompunerea unei funcții booleene în variabile:

Să punem k=1. Să luăm expansiunea în termenii ultimei variabile.

Corolarul 2. Extinderea unei funcții într-o formulă normală disjunctivă perfectă (PDNF).

V corect = .

=1.

Să luăm cazul k=n în teoremă, i.e. extindere în toate variabilele.

Corolarul 3. Despre reprezentabilitatea oricărei funcții într-o bază clasică.

Orice funcție booleană poate fi reprezentată ca o formulă pe o bază.

B 0= (x&y,x˅y,)

Cometariu. Pentru orice funcție booleană există o reprezentare sub formă de SDNF și această reprezentare este singura.

BILETUL 27

Forme normale disjunctive perfecte (PDNF)[suma produselor ˅&].

Sistemul de operații al algebrei booleene este complet, iar trecerea de la o atribuire tabelară a oricărei funcții logice la o formulă de algebră booleană este întotdeauna posibilă. Să formulăm o metodă de tranziție de la o atribuire tabelară a unei funcții logice la o formulă booleană, care este foarte importantă pentru practică. El

include următoarele acțiuni:

·pentru fiecare set de valori ale variabilelor x 1, x 2,..., x n, pe care funcția f (x 1, x 2,..., x n) este egală cu 1, conjuncțiile tuturor variabilelor sunt scrise;

· peste acele variabile care sunt egale cu 0 în această mulţime se plasează negative;

Toate astfel de conjuncții sunt legate prin semne de disjuncție.

Formula obținută în acest fel se numește forma normală disjunctivă perfectă (PDNF) a unei funcții logice.

Pentru fiecare funcție, SDNF este unic.

Astfel, SDNF-ul funcției f (x 1, x 2,..., x n) este o disjuncție de conjuncții elementare: D = K 1 ˅ K 2 ˅ ... ˅ K m, unde toate conjuncțiile au același număr de factori egal cu numărul de variabile logice, iar numărul de conjuncții este egal cu numărul de seturi de valori ale variabilelor x 1, x 2,..., x n, pe care funcția f (x 1, x 2) ,..., x n) este egal cu 1. Orice alte intrări ale unei funcții logice, de forma D = K 1 ˅ K 2 ˅ ... ˅ K m care nu îndeplinesc aceste condiții se numesc

forme normale disjunctive (DNF) ale acestei funcţii.

BILETUL 28

Forme normale conjunctive perfecte (PCNF) [produs de sume &˅].

Afirmație. Pentru orice funcție booleană f=f(x1,…,xn),f ≠ 1 reprezentare corectă

Avem: f* ≠ 0. Acum să construim SDNF pentru f*.

Să luăm duala ambelor părți ale ecuației.

Facem înlocuiri: .

= .

Cometariu. Pentru fiecare funcție booleană ≠ 1 exista o reprezentare sub forma SCNF si aceasta reprezentare este singura.

BILETUL 29

polinoame Zhegalkin.

În algebra logicii, există de obicei 3 forme cononice de reprezentare a unei funcții sub forma unei formule:

    polinoame Zhegalkin

Monomial este o formulă de forma 0,1, .

Polinomul Zhegalkin:

P=M 1 ⊕M 2 ⊕…⊕M k , M i – monom.

Toate monomiile sunt distincte în perechi.

Teorema. Orice funcție booleană poate fi reprezentată ca un polinom Zhegalkin, iar această reprezentare este unică.

eu. Demonstrăm reprezentabilitatea funcției sub forma unui polinom Zhegalkin.

Să luăm în considerare 2 cazuri

  1. f ≠ 0, atunci

Putem înlocui ˅ cu ⊕, deoarece nu există doi termeni în SDNF≠1.

Deci există j()

Să facem câteva transformări

Deschidem parantezele și prezentăm altele asemănătoare conform regulii AA = 0.

Ca rezultat, obținem un polinom Zhegalkin pentru fiecare funcție care există un polinom Zhegalkin.

II. Demonstrăm unicitatea.

Să folosim principiul Dirichlet.

Să numărăm numărul de polinoame Zhegalkin.

. Adică 2 n diferit de zero.

Monom gol=1.

Să formăm un polinom:

Monomov = N=2 n

Polinoame = 2 N =

Dacă nimic nu este inclus, atunci 0.

BILET 30

Conceptul de completitudine funcțională a unui sistem de funcții booleene. Completitudinea sistemului (ȘI, SAU, NU).

Definiție. Un set de funcții ale algebrei logicii A se numește sistem complet (în P2) dacă orice funcție a algebrei logicii poate fi exprimată printr-o formulă peste A. Teorema. Sistemul A = (v, &, ─) este complet.

Dovada. Dacă o funcție algebrică logică f nu este identic zero, atunci f este exprimată sub forma unei forme normale disjunctive perfecte, care include doar disjuncția, conjuncția și negația. Dacă f≡ 0, atunci f = x*(─x). Teorema este demonstrată.

BILET 31

Cursuri închise și închise.

1°. Conceptul de clasă închisă.

Definiție 1. Fie A ⊆ P2. Atunci închiderea lui A este mulțimea tuturor funcțiilor algebrei logicii care pot fi exprimate prin formule peste A.

Denumire: [A].

Următoarele proprietăți au loc:

2) A ⊇ B ⇒ [A] ⊇ [B], iar dacă există o încorporare strictă pe partea stângă a implicației, atunci nu implică deloc o încorporare strictă pe partea dreaptă - doar A ⊃ B ⇒ [ A] ⊇ [B] este adevărată;

Definiție 2. Un sistem de funcții al unei algebre logice A se numește complet dacă [A] = P2.

Definiția 3. Fie A ⊆ P2. Atunci un sistem A se numește clasă închisă dacă închiderea lui A coincide cu A însuși: [A] = A.

2°. Exemple de clase închise.

Clasa T 0 = (f (x 1, ..., x n) | f (0, ..., 0) = 0).

Clasa T 0 include, de exemplu, funcțiile 0, x, xy, x ∨ y, x ⊕ y.

Clasa T 0 nu conține funcțiile 1, x, x → y, x | y, x ↓ y, x ~ y.

Clasa T 1 = (f (x 1, …, x n) | f (1, 1, …, 1) = 1).

Clasa T 1 conține funcțiile 1, x, xy, x ∨ y, x → y, x ~ y.

Clasa T 1 nu conține funcțiile 0, x, x ⊕ y, x | y, x ↓ y.

Clasa L de funcții liniare.

Definiția 4. O funcție algebrică logică f (x 1 , ..., x n) se numește liniară dacă

f (x 1 , …, x n) = a 0 ⊕ a 1 x 1 ⊕ … ⊕ a n x n , unde a i ∈ (0, 1).

Cu alte cuvinte, într-un polinom al unei funcții liniare nu există termeni care să conțină o conjuncție.

Clasa L conține funcțiile 0, 1, x = x⊕1, x ~ y, x ⊕ y.

Clasa L nu conține funcțiile xy, x ∨ y, x → y, x | y, x ↓ y.

Clasa S de funcții auto-duale.

Definiția 2. O funcție algebrică logică f (x 1 ,…, x n) se numește auto-duală dacă f (x 1 ,…, x n) = f* (x 1 ,…, x n).

Cu alte cuvinte, S = (f | f = f*).

Definiția 2. O funcție algebrică logică f (x 1 ,…,x n) se numește monotonă dacă pentru oricare două mulțimi comparabile ~α și ~β este valabilă implicația ~α≤ ~ β ⇒f(~α) ≤ f (~ β) .

Clasa M a tuturor funcțiilor monotone.

Clasa M conține funcțiile 0, 1, x, xy, x ∨ y, m (x, y, z) = xy ∨ yz ∨ zx.

Clasa M nu conține funcțiile x , x | y, x ↓ y, x ⊕ y, x ~ y, x → y

BILET 32

Postează cursuri.

Post criteriu este una dintre teoremele centrale în teoria funcțiilor booleene, stabilind o condiție necesară și suficientă pentru ca un set de funcții booleene să fie suficient de expresiv pentru a reprezenta orice funcție booleană. Formulat pentru prima dată de matematicianul american Emil Post.

O funcție booleană este o funcție de tip , unde , a este aritatea. Numărul de funcții diferite de aritate este egal cu , dar numărul total de funcții booleene diferite este infinit. Cu toate acestea, este evident că multe funcții pot fi exprimate în termenii altora folosind operatorul de suprapunere. De exemplu, se știe de mult că din disjuncție și negație se poate obține o conjuncție, folosind legile lui De Morgan. În plus, orice funcție booleană (cu excepția zeroului identic) poate fi reprezentată sub formă DNF, adică în termeni de conjuncție, disjuncție și negație. Apare o întrebare firească: cum putem determina dacă un anumit set de funcții este suficient pentru a reprezenta orice funcție booleană? Astfel de seturi sunt numite complet funcțional. Teorema lui Post răspunde la această întrebare. Deoarece condițiile teoremei sunt necesare și suficiente, se mai numește criteriu.

Ideea teoremei este de a considera mulțimea tuturor funcțiilor booleene ca o algebră sub operația de suprapunere. Acum poartă numele Postalgebră. Această algebră conține ca subalgebre seturi de funcții care sunt închise sub suprapunere. Se mai numesc si ei clase închise. Să fie un subset de . Prin inchidere a unei multimi se numeste subalgebra minima care contine . Cu alte cuvinte, o închidere constă din toate funcțiile care sunt suprapoziții. Evident, va fi complet funcțional dacă și numai dacă . Astfel, întrebarea dacă o anumită clasă este completă din punct de vedere funcțional se rezumă la verificarea dacă închiderea sa se potrivește cu .

BILET 33

Criteriul de completitudine.

Teorema 12 (teorema lui Post). Un sistem de funcții de algebră logică A = (f1, f2, ...) este complet în P2 dacă și numai dacă nu este cuprins în întregime în oricare dintre următoarele clase: T0, T1, S, L, M.

Dovada. Necesitate. Fie A - sistem complet, N - oricare dintre clasele T 0 , T 1 , S, L, M și fie A ⊆ N. Atunci [A] ⊆ [N] = N ≠ P2 și [A] ≠ P2. Contradicția rezultată completează justificarea nevoii.

Adecvarea. Fie A ⊄ T 0, A ⊄ T 1, A ⊄ M, A ⊄ L, A ⊄ S. Atunci în A există funcții f 0 ∉ T 0, f 1 ∉ T 1, f m ∉ M,

f l ∉ L, f s ∉ S. Este suficient să arătăm că [A] ⊇ = P2. Să împărțim demonstrația în trei părți: obținerea negației, a constantelor și a conjuncției.

a) Obținerea ─x . Se consideră funcția f 0 (x 1 , …, x n) ∉ T0 și se introduce funcția φ 0 (x) = f 0 (x, x, …, x). Deoarece funcția f 0 nu păstrează zero, φ 0 (0) = f (0, 0, …, 0) = 1. Sunt posibile două cazuri: fie ϕ 0 (x) = ─x, fie φ0 (x) ≡ 1. Se consideră funcția f 1 (x 1 , …, x n) ∉ T 1 și se introduce în mod similar funcția φ 1 (x) = f 1 (x, x, …, x). Deoarece funcția f 1 nu păstrează unitatea, φ 1 (1) = f (1, 1, …, 1) = 0. Sunt posibile și două cazuri: fie ϕ 1 (x) = ─x, fie φ1 (x) ≡ 0 Dacă în cel puțin un caz se obține negația cerută, punctul este completat. Dacă în ambele cazuri obținem constante,

apoi, conform lemei privind funcțiile nemonotone, prin substituirea constantelor și funcțiilor identice în funcția f m ∉ M în locul tuturor variabilelor, se poate obține o negație.

Negare primită.

b) Obținerea constantelor 0 și 1. Avem f s ∉ S. Conform lemei pe o funcție non-duală, înlocuind negația (care s-a obținut la punctul a) și funcția identică în locul tuturor variabilelor funcției f s, putem obține constantele: ∋ . S-au obţinut constantele.

c) Obţinerea conjuncţiei x · y. Avem o funcție f l ∉ L. Conform lemei funcției neliniare, substituind constante și negații în funcția fl în locul tuturor variabilelor (care au fost obținute în etapele anterioare ale demonstrației), se poate obține fie o conjuncție, fie negația a unei conjuncţii. Cu toate acestea, în prima etapă negația a fost deja obținută, prin urmare, este întotdeauna posibil să se obțină o conjuncție:

∋ Se obține conjuncția.

Ca rezultat, s-a constatat că ⊇ [ ─x,xy] = P 2 . Ultima egalitate decurge din paragraful 2 al teoremei 4. Prin lema 2 se dovedește suficiența.

BILET 34

Implementarea funcţiilor booleene prin circuite de elemente funcţionale.

*manual*

Una dintre principalele aplicații ale funcțiilor booleene constă în domeniul creării de diagrame de elemente funcționale sau diagrame funcționale, care pot fi implementate ca dispozitive electronice cu un număr finit de intrări și ieșiri și doar două valori pot apărea la fiecare intrare și ieșire. Astfel de dispozitive sunt asamblate din elemente functionale, generarea de operații booleene de bază.

Prin conectarea elementelor funcționale împreună obținem diagrama functionala. Cu ajutorul acestuia puteți implementa orice funcție booleană.

Complexitatea unui circuit de elemente funcționale este numărul de elemente funcționale din circuit.

Disjunctor, vector.

SFE – circuite de elemente funcţionale.

F=(f 1 , f 2 , …, f m)

L(S) – complexitate – numărul de elemente funcționale din circuit.

L(S) = minL(S) – cel mai mic număr de elemente cu care puteți construi un circuit.

L A (f) = L(S A (f)) – complexitatea circuitului.

L A (n) = maxL A (f), f ϵ . Max este preluat peste toate variabilele.

Funcția Shannon pentru A.

Lăsați în SDNF l (el) termeni.

f = k 1 ˅k 2 ˅…˅k l

Să notăm schema rezultată S, atunci

L(S) = L(Dn)+L(V l)

L(Dn) = 2*2 n + n – 4

l≤ 2 n

L(V l)=l- 1≤ 2 n – 1

L(S) ≤ (2*2 n + n - 4) + (2 n - 1) = 3*2 n + n – 5.

BILET 35

Implementarea unui decodor într-o clasă de circuite formată din elemente funcționale (circuit de selectare a elementelor).

*manual*

Un decodor Qn de ordinul n este un circuit de elemente funcționale cu n intrări x 1, x 2, ..., x n și 2 n ieșiri z0, z 1,..., astfel încât dacă |x1x2...xn| = i, atunci zi = 1 și zj = 0 pentru i ≠ j.

Rețineți că dacă i = (i 1, i 2, …, i n) 2, atunci z i (x 1,…, x n) = .

Lema. Există un decodor Qn cu numărul de elemente care nu depășește n2 n+1 .

Dovada. Pentru a implementa fiecare z i, este suficient să luăm exact n–1 conjuncții și nu mai mult de n negații, adică mai puțin de 2n elemente funcționale în total. Există exact 2 n conjuncții diferite în total, iar complexitatea decodorului nu depășește n 2n+1.

Metodele banale se bazează pe implementarea autonomă a conjuncțiilor elementare.

BILET 36

Metode universale de sintetizare a circuitelor din elemente funcționale.

Teorema. Există o metodă de sinteză a circuitelor din elemente funcționale astfel încât pentru orice funcție booleană f(x1,...,xn) circuitul său de implementare S este construit astfel încât

L(S) ≤ 3*2 n + n – 5, prin urmare:

Consecinţă. L(n) ≤ 3*2 n + n – 5

Cometariu.

BILET 37

Implementarea unui sumator binar într-o clasă de circuite din elemente funcționale.

*manual*

Definiție. Adder S n de ordinul n este un circuit cu 2n intrări X 1 , X 2 , …, X n, y 1 , y 2 , …, y nși n + 1 ieșire z 0 , z 1 , z 2 , …, z n astfel încât | z| = |S n (X,y)| = |X|+|y|.

Teorema. Există un sumator de circuit de ordinul n în bază (˅, &, ̚ ) cu numărul de elemente 9n – 5. Dovada. Să construim sumatorul de circuit necesar. Pentru a face acest lucru, luați o celulă cu jumătate de adunare care conține patru elemente și n-1 celule de adunare, fiecare dintre acestea conținând nouă elemente. Să construim un sumator din aceste părți.

Să fie două numere scrise în formă binară.

Dificultate: L(Bi)=9.

Teorema. Există o metodă pentru sintetizarea unui sumator binar de n biți astfel încât L()=9n-5.

BILET 38

Logica afirmațiilor.

Logica propozițională este un anumit set de formule, adică. enunţuri complexe înregistrate într-un limbaj artificial special construit. Limbajul logicii propoziționale include:

1. un set nelimitat de variabile: A, B, C, ..., A1, B1, C1, ..., reprezentând enunţuri;

2. simboluri speciale pentru conexiunile logice: & - „și”, v - „sau”, V - „ori, sau”, ? - "daca atunci", ? - „dacă și numai dacă”, ~ - „nu este adevărat că””

3. paranteze care acționează ca semne de punctuație pentru limbajul obișnuit. Pentru a folosi mai puține paranteze, să fim de acord că mai întâi se realizează operația de negație, apoi conjuncția și disjuncția și abia apoi implicarea și echivalența.

Formule logice propoziționale formate din variabile și conjunctive corespund propozițiilor în limbaj natural. De exemplu, dacă A este afirmația „Este ziua”, B este afirmația „Acum este lumină” și C este afirmația „Acum este frig”, atunci formula este:

A? În v C, sau cu toate parantezele: (A? (B v C)),

reprezintă afirmația „Dacă este zi, atunci este lumină sau frig”. Formulă:

B&C? A sau ((B & C) ? A),

reprezintă afirmația „Dacă este lumină și frig, atunci este zi”. Formulă:

~V? ~ A sau ((~ B) ? (~ A)),

reprezintă afirmația „Dacă este fals că acum este lumină, atunci este fals că este zi” etc. Înlocuind alte afirmații specifice (adevărate sau false) în loc de variabile, obținem alte traduceri ale acestor formule în limbajul obișnuit.

O formulă care nu corespunde unei propoziții cu sens este construită incorect.

Acestea sunt, în special, formulele:

(A?), (& B), (A v BC), (~ &), etc.

Fiecare formulă a logicii propoziționale corespunde unui tabel de adevăr, care arată sub ce substituții de enunțuri specifice într-o formulă dată dă o afirmație complexă adevărată și sub care una falsă. De exemplu, formula (~ B? ~ A) va da o afirmație falsă numai dacă o afirmație falsă este înlocuită cu B și o afirmație adevărată este înlocuită cu A.

O formulă întotdeauna adevărată a logicii propoziționale, sau tautologie, este o formulă care oferă o afirmație adevărată sub orice substituție de enunțuri specifice (adică adevărate sau false) în ea.

Cu alte cuvinte, structura internă a unei tautologii garantează că aceasta se va transforma întotdeauna într-un enunț adevărat, indiferent de enunțurile specifice pe care le înlocuim variabilele incluse în ea.

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


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


Aranov Viktor Pavlovici. Matematică discretă.

Secțiunea 4. Sisteme funcționale cu operatii. Algebra logicii.

Cursul 21. Principiul dualității. Extinderea funcțiilor în variabile. DNF și CNF perfecte

Cursul 21. PRINCIPIUL DUALITĂȚII. DESCOMPUNERE BOOLEANĂ

FUNCȚII PE VARIABILE. DISJUNCTIV PERFECT ȘI

FORME NORMALE CONJUNCTIVE

Schema cursului:

  1. Principiul dualității.
  2. Extinderea funcțiilor booleene în variabile. Formele normale disjunctive și conjunctive perfecte.
  1. Principiul dualității

Se apelează o funcție egală cu dual functie la functie.

Evident, tabelul de adevăr pentru funcția duală se obține din tabelul de adevăr pentru funcție prin inversarea (adică înlocuirea 0 cu 1 și 1 cu 0) a valorilor variabilelor și funcției. De exemplu, .

Este ușor de setat pentru funcțiile 0, 1 care

  1. funcția 0 este duală cu 1;
  2. funcția 1 este duală la 0;
  3. functia este duala;
  4. functia este duala;
  5. functia este duala;
  6. functia este duala.

Din definiţia dualităţii rezultă că

adică funcția este duală cu (proprietatea de reciprocitate).

Principiul dualității.Dacă o formulă implementează o funcție, atunci formula, adică formula obținută din înlocuirea funcțiilor cu respectiv, implementează funcția.

Vom numi formula formula duală la.

Pentru a demonstra această afirmație, este necesar să se verifice validitatea ei pentru etapele elementare de suprapunere și.

Să fie, de exemplu, o funcție obținută dintr-o funcție ca urmare a următoarei înlocuiri de variabile:

Apoi

adică funcția este obținută din ca urmare a aceleiași substituții de variabile.

Vom demonstra validitatea principiului dualității pentru o etapă folosind un exemplu. Lăsa

Apoi

adică se obține o funcție din și în același mod în care se obține o funcție din și.

Principiul dualității ne permite să simplificăm derivarea tautologiilor de bază și are o serie de aplicații utile, care vor fi discutate mai jos.

Exemplul 1. De la identitate urmează identitatea.

Într-adevăr,

;; .

Exemplul 2. Construirea unei formule pentru negarea unei funcții.

Din definiția funcției duale rezultă

Obținem următoarea regulă: lăsa formula implementează funcția. Pentru a obține o formulă pentru o funcție, trebuie să înlocuiți toate variabilele din formulă cu negațiile lor.

Să găsim negația funcției.

De atunci.

  1. Extinderea funcțiilor booleene în variabile. Perfect

Forme normale disjunctive și conjunctive

Să introducem notația

unde este un parametru egal fie cu 0, fie cu 1. Evident,

Este ușor de observat că 1 dacă și numai dacă.

Teorema de extindere a functiilor in variabile. Fiecare funcție a algebrei logice pentru orice () poate fi reprezentată în următoarea formă:

, (1)

unde disjuncția este preluată peste toate seturile posibile de valori variabile.

Această vedere se numeșteextinderea unei funcții în variabile.

Dovada. Să luăm în considerare un set arbitrar de valori variabile și să arătăm că părțile din stânga și din dreapta relației (1) iau aceeași valoare. Partea stângă dă. Dreapta

Ca corolare ale teoremei, luăm în considerare două cazuri speciale de expansiune.

  1. Extindere variabilă:

Funcțiile sunt numitecomponente ale descompunerii.Această descompunere este utilă atunci când unele proprietăți sunt stabilite prin inducție.

  1. Extindere pentru toate variabilele:

Dacă nu este identic egal cu 0, acesta poate fi transformat:

Drept urmare, în sfârșit obținem

. (2)

Această descompunere se numeșteformă normală disjunctivă perfectă(d.n.f. perfect).

Direct la conceptul de perfect d.n. f. următoarea teoremă este adiacentă.

Teorema. Fiecare funcție a algebrei logicii poate fi reprezentată printr-o formulă în bază.

Dovada.1) Fie. Apoi, evident

  1. Să nu fie identic egal cu 0. Atunci poate fi reprezentat prin formula (2).

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. Pentru fiecare astfel de linie formăm un produs logic și apoi conectăm toate conjuncțiile rezultate cu un semn de disjuncție.

Exemplul 3. Găsiți un d.n perfect. f. pentru functie.

Doctor perfect în științe f. este o expresie de tip P. Să arătăm că atunci când nu este identic egal cu 1, poate fi reprezentat sub forma. Să scriem expansiunea pentru funcția duală (evident nu identic egală cu 0) sub forma unui d.n perfect. f.:

Din principiul dualității rezultă

Astfel, obținem o descompunere numităforma normală conjunctivă perfectă(doctorat perfect):

. (3)

Exemplul 4. Construiește un doctorat perfect. f. pentru functie.

Avem.

Alte lucrări similare care vă pot interesa.vshm>
200. Forme normale de funcții logice 63,53 KB
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.
9015. METODE DE MINIMIZAREA FUNCȚILOR BOOLEANE 81,74 KB
Circuite DNF și FE. Minimizarea funcțiilor booleene pe baza construcției de DNF-uri dead-end. Minimizarea funcțiilor booleene bazate pe construcția de dead-end DNF Punctul mort redus și DNF minim sunt în următoarea relație. Un DNF fără margini se obține dintr-unul redus prin eliminarea unor termeni.
9017. PROBLEMA MINIMIZĂRII FUNCȚIILOR BOOLEANE. INTERPRETAREA GEOMETRICA 109,86 KB
Circuite DNF și FE. INTERPRETARE GEOMETRICĂ Schema cursului: Conceptul de formă normală disjunctivă a DNF. Conceptul de DNF. Expresia pentru unde este o conjuncție elementară de rang se numește forma normală disjunctivă a DNF.
14731. Descompunerea semnalelor într-o serie Fourier generalizată în sisteme de funcții ortogonale. Funcțiile Walsh 38,95 KB
Descompunerea semnalelor într-o serie Fourier generalizată în sisteme de funcții ortogonale. Familiarizați-vă cu caracteristicile de bază ale semnalelor și interferențelor. Studiați reprezentarea semnalelor sub forma unei serii Fourier generalizate în sisteme de funcții ortogonale. Descompunerea semnalelor într-o serie Fourier generalizată în sisteme de funcții ortogonale.
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 bază relațională date 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
1790. Descompunere 180,15 KB
Cuvântul algoritm în sine seamănă cu algorithmi – forma latină de a scrie numele marelui matematician al secolului al IX-lea. al-Khwarizm, care a formulat regulile operațiilor aritmetice. Inițial, în baza algoritmilor, au fost înțelese doar regulile pentru calcularea mai multor operații aritmetice asupra numerelor digitale bogate.
2690. Studierea performanței burghiilor cu pas variabil de helix 18,85 KB
Modelele procesului de tăiere pot fi reprezentate printr-un sistem de ecuații matematice care determină în fiecare caz concret funcția de evaluare sau criteriile de performanță a sculelor de tăiere, precum și limitările tehnice ale cinematicii mașinii, rigiditatea sculelor de tăiere și a sistemului tehnologic în ansamblu
17088. RĂSPUNDERE PENALĂ PENTRU INFRACȚIUNI SAVĂRITE CA MEMBRI AI UNUI GRUP PENAL ORGANIZAT 50,97 KB
Lomtev CARACTERISTICI GENERALE ALE LUCRĂRII Relevanța temei de cercetare este determinată de necesitatea dezvoltării și îmbunătățirii în continuare a teoriei și practicii implementării răspunderii penale pentru infracțiunile comise ca parte a unui grup infracțional organizat. Cercetările în domeniul combaterii crimei organizate arată că tocmai în cadrul grupurilor infracționale organizate se comit infracțiunile cele mai periculoase și greu de rezolvat. Ca parte a soluționării problemei creșterii eficacității legii penale în ceea ce privește combaterea...
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ă.

Mulțimea B pe care sunt definite două operații binare (conjuncție și disjuncție) și o operație unară (negație) și sunt selectate două elemente 0 și 1 se numește algebră booleană.

În plus, pentru aceste operații este necesar să se îndeplinească următoarele proprietăți:

Asociativitatea

Comutativitate

Distributivitatea conjuncției în raport cu disjuncția

Distributivitatea unei disjuncții în raport cu o conjuncție

Idempotenta

De două ori nu

Proprietățile constantelor

regulile lui De Morgan

Legea contradicției

Legea mijlocului exclus

În algebra logicii, aceste legi se numesc echivalențe.

Forme normale perfecte

Forma normală disjunctivă perfectă

Să introducem următoarea notație:

; A A =1; X A =1 dacă X=A, X A =0 dacă XA.

Formula X A 1…… X A n, unde A = este orice mulțime binară, iar între variabilele Xi pot exista unele care coincid, se numește conjuncție elementară.

Orice disjuncție a conjuncțiilor elementare se numește formă normală disjunctivă (DNF).

O conjuncție elementară se numește corectă dacă fiecare variabilă apare în ea nu mai mult de o dată (inclusiv apariția ei sub semnul negației).

De exemplu: 1) (pictograma conjuncție este omisă în acest caz).

1),4) - conjuncţii elementare corecte;

2) - variabila x apare o data de la sine si a doua oara sub semnul negatiei;

Variabila y apare de trei ori: o dată singură și de două ori sub semnul negativ.

O conjuncție elementară corectă se numește completă față de variabilele x 1 .....x n dacă include fiecare dintre aceste variabile o singură dată (genul poate fi și un semn de negație).

De exemplu: dintre conjuncțiile enumerate în exemplul anterior, doar 4) este completă în ceea ce privește variabilele x,y,z,t; și referitor la variabile x,y,z plin este doar 1).

O formă normală disjunctivă perfectă (PDNF) în raport cu variabilele x 1 .....x n este o formă normală disjunctivă în care nu există conjuncții elementare identice și toate conjuncțiile elementare sunt corecte și complete în raport cu variabilele x 1 . ....x n

Descompunere variabilă

Teorema 1. Orice funcție logică poate fi reprezentată în SDNF:

unde m, iar disjuncția este preluată peste toate cele 2 m seturi de valori ale variabilelor x 1,...x m. Funcția f este extinsă în primele n-variabile. Această egalitate se numește expansiune în variabile. x 1,...x m. De exemplu, cu n=4, m=2, expansiunea are forma:

teorema se dovedește prin substituirea în ambele părți ale egalității (1) a unei mulțimi arbitrare (b 1 ,…,b m , b m+1 ,…,b n) a tuturor n-variabilelor.

Pentru m = 1, din (1) obținem extinderea funcției într-o variabilă:

Evident, o expansiune similară este valabilă pentru oricare dintre n-variabile.

Un alt caz important este când n=m. În acest caz, toate variabilele din partea dreaptă a (1) primesc valori fixe, iar funcțiile din conjuncția părții drepte devin egale cu 0 sau 1, ceea ce dă:

unde disjuncția este preluată peste toate mulțimile (b 1 ...b n), pe care f=1. Pentru f=0, mulțimea de conjuncții din partea dreaptă este goală. Această descompunere se numește formă normală disjunctivă perfectă. SDNF al unei funcții f conține exact atâtea conjuncții câte unități există în tabelul de adevăr al lui f. Fiecare mulțime de unități (b 1,..., b n) corespunde unei conjuncții a tuturor variabilelor, în care x i este luat cu negație dacă b i =0 b și fără negație dacă b i =1. Astfel, există o corespondență unu-la-unu între tabelul de adevăr al funcției f și SDNF-ul acesteia și, în consecință, SDNF pentru orice funcție logică este unic. Singura funcție care nu are un SDNF este constanta 0.

Teorema 2. Orice funcție logică poate fi reprezentată ca o formulă booleană.

Într-adevăr, pentru orice altă funcție decât constanta 0, SDNF-ul său poate servi ca o astfel de reprezentare. Constanta 0 poate fi reprezentată printr-o formulă booleană.

Să selectăm variabila x 1 și să considerăm funcția f relativ la aceasta.

Toate multe seturi Tabelul de adevăr este împărțit în două subseturi, fiecare având patru seturi<0, a 2 , a 3 >Și<1, a 2 , a 3 >.

Atunci funcția f(x 1 ,x 2 ,x 3) poate fi reprezentată ca o disjuncție a două funcții a două variabile și această formulă va arăta astfel:

Luați în considerare următoarele formule:

Partea stângă a primei formule este echivalentă cu cea dreaptă, deoarece pentru x 1 =0 și în conformitate cu operația de conjuncție. În mod similar, putem arăta validitatea celei de-a doua formule. Astfel, punând aceste formule în disjuncția anterioară, obținem:

Această expresie se numește extinderea funcției f(x 1, x 2, x 3) în variabila x 1.

Acum, în mod similar, putem extinde funcțiile f(0,x 2,x 3) și f(1,x 2,x 3) în variabila x 2. Primim

Înlocuind aceste formule în cele anterioare obținem

În conformitate cu distributivitatea operației &, introducem variabila x 1 și inversarea acesteia între paranteze, obținem

ÎN vedere generala pentru o funcție f(x 1 ,x 2 ,..,x n) a n variabile, expansiunea în m variabile (m£n) are forma

unde disjuncția este preluată pe toate cele 2 m seturi de variabile x 1 ,x 2 ,..,x m .

Să considerăm expansiunea (*4) în cazul extrem când m=n. (vezi exemplul (*3)).

Apoi, în toate conjuncțiile, valorile funcției f pe fiecare mulțime fixă ​​au valori egale cu zero sau unu. După ce am eliminat toate conjuncțiile zero, obținem o nouă expansiune și în această nouă expansiune eliminăm factorii funcțiilor din conjuncții, deoarece sunt egale cu 1. Expresia rămasă se numește SDNF (forma normală disjunctivă perfectă).

Să facem toate acestea pentru un exemplu (*3).

După eliminarea din (*3) conjuncții cu valori zero ale funcției f pe mulțimi date, obținem:

Din moment ce, conform tabelului de adevăr

f(0,0,0) = f(0,1,0) = f(1,1,0) = f(1,1,1)=1

apoi eliminăm factorii funcțiilor din conjuncții, după care obținem:

Aceasta este forma normală disjunctivă perfectă a funcției booleene f.

Lema. Orice funcție booleană (cu excepția constantei „0”) are un SDNF și doar unul.

În mod similar, puteți introduce forma conjunctivă,

Construcția SDNF pentru o funcție dată de un tabel

Această consecință este de natură constructivă, deoarece folosind tabelul de funcții, vă permite să construiți o formulă care este un SDNF (dacă).
Funcții SDNF f conține exact atâtea conjuncții câte unități există în tabel f; fiecare set „unitate”. (d 1 ,…,d n), acestea. multimea la care valoarea functiei este egala cu 1 corespunde conjunctiei tuturor variabilelor in care x i luat cu negaţie dacă d i=0, și fără negație, dacă d i =1.

Stabilirea funcțiilor booleene ale variabilelor folosind un tabel de adevăr, definirea unei formule, a tipurilor celor mai importante echivalențe (legi) ale algebrei logicii. Formule echivalente, legi de echivalență, ecuații logice. Extinderea funcțiilor booleene în variabile.

Făcând clic pe butonul „Descărcați arhiva”, veți descărca gratuit fișierul de care aveți nevoie.
Înainte de a descărca acest fișier amintiți-vă acele eseuri bune, teste, referate, teze, articole și alte documente care se află nerevendicate pe computerul dvs. Aceasta este munca ta, ar trebui să participe la dezvoltarea societății și să beneficieze oamenii. Găsiți aceste lucrări și trimiteți-le la baza de cunoștințe.
Noi și toți studenții, studenții absolvenți, tinerii oameni de știință care folosesc baza de cunoștințe în studiile și munca lor vă vom fi foarte recunoscători.

Pentru a descărca o arhivă cu un document, introduceți un număr de cinci cifre în câmpul de mai jos și faceți clic pe butonul „Descărcați arhiva”

Documente similare

    Axiomele și identitățile de bază ale algebrei logicii. Forma analitică de reprezentare a funcţiilor booleene. Funcții elementare ale algebrei logice. Funcțiile algebrei logice cu un singur argument și formele implementării acesteia. Proprietăți, caracteristici și tipuri de operații logice.

    rezumat, adăugat 12.06.2010

    Conceptul de algebră a logicii, esența și trăsăturile sale, conceptele și definițiile de bază, subiectul și metodologia de studiu. Legile algebrei logicii și consecințele lor, metode de construire a formulelor folosind un tabel de adevăr dat. Forme de reprezentare a funcţiilor booleene.

    tutorial, adăugat 29.04.2009

    Algebre booleene - rețele tip special, utilizat în studiul logicii (atât logica gândirii umane, cât și logica computerului digital), precum și circuitele de comutare. Forme minime ale polinoamelor booleene. Teoreme ale algebrei booleene abstracte.

    lucrare de curs, adăugată 05.12.2009

    Operații pe instrucțiuni logice: funcții booleene și exprimarea unor astfel de dependențe prin altele. Formule propoziționale și unele legi ale logicii propoziționale. Traducerea expresiilor din limbajul natural în vorbirea simbolică a algebrei logicii.

    test, adaugat 26.04.2011

    Logica este știința legilor și a formelor de gândire, iar conceptul principal al algebrei logicii este o afirmație. Concepte de bază și identități ale algebrei booleene. Studiul metodelor de minimizare a funcţiilor booleene. Metoda lui Quine, bazată pe aplicarea a două relații de bază.

    test, adaugat 20.01.2011

    Concepte de bază ale algebrei logicii. Forme normale disjunctive și conjunctive. Esența teoremei lui Shannon. Funcții booleene a două variabile. Conexiune în serie și paralelă a două întrerupătoare. Proprietăți functii elementare algebre de logică.

    test, adaugat 29.11.2010

    Variabila logica in algebra logicii. Operații logice: negație, conjuncție, disjuncție, implicație, echivalență. Legile de bază ale algebrei logicii. Reguli de minimizare a unei funcții logice (scăparea de operațiile de implicare și echivalență).

    lucrare de curs, adăugată 16.01.2012



Se încarcă...
Top