În tabel, Ai, j - constantele 0 sau 1, care definesc valorile argumentelor; Fj - constantele 0 sau 1, definind valorile funcției pentru o combinație dată de argumente; M = 2 N - numărul tuturor combinațiilor posibile.
Definirea funcțiilor unui argument:
Apoi funcția inițială poate fi reprezentată ca:
După cum puteți vedea, este exprimată doar prin funcții,
și . Fiecare linie din regula noastră (*) corespunde rândului din tabel.
Rămâne să se demonstreze că partea stângă a lui (*) este într-adevăr egală cu funcția inițială. Luați un rând n-le arbitrar al mesei. Să se asigure că valoarea funcției Fn este într-adevăr egală cu valoarea părții stângi (*) atunci când valorile argumentelor sunt egale cu valorile indicate în această linie: xi = Ai, n pentru i = 1, 2, 3. N.
Aceasta este, pentru n ales și pentru orice i este adevărat:
Luăm linia n în (*), înlocuim (1) în ea și aplicăm legea absorbției x 1 = x.
Acum luați în (*) orice altă linie, cu excepția n-ta. Să presupunem că are numărul m. Deoarece toate rândurile tabelului conțin diferite seturi de Ai, j. atunci cel puțin o coloană va avea o diferență. Diferența trebuie inclusă în coloana k:
Asta este, pentru k și m selectate este adevărat:
Luăm rândul m în (*), înlocuim (2) în el și aplicăm legile de absorbție x 0 = 0 și 0 x = 0.
Astfel, valoarea tuturor rândurilor SDNF, cu excepția celui de-al n-lea, este zero datorită zero, ceea ce dă cel puțin o diferență în seturile de argumente. Și numai linia n este Fn.
Ca rezultat, obținem:
Și conform legilor de absorbție x 0 = x și 0 x = x primim:
Am considerat un rând n-a arbitrar al tabelului și ne-am asigurat că pentru setul de argumente scrise în această linie, valoarea funcției coincide cu valoarea părții din stânga (*). Exact același raționament poate fi repetat pentru toate celelalte linii, indiferent de cât de multe dintre ele. Astfel, valoarea funcției coincide cu partea stângă (*) pentru toate seturile posibile de argumente. După cum este necesar pentru a dovedi.
În formula (*) liniile în care Fj = 0 pot fi omise, datorită legilor de absorbție: x 0 = 0, x 0 = x și 0 x = x. Și în rândurile în care Fj = 1 putem omite Fj. datorită legii absorbției: x 1 = x.
După aceste abrevieri, se obține o înregistrare, care se numește forma normală disjunctivă normală (SDNF).
Exemplu de compilare a CDNF.
Vom compune CDNF pentru funcția, care a fost dată mai devreme ca exemplu.
Noi compunem CDNF în acest fel: pentru fiecare rând cu o unitate în coloana din dreapta, formează paranteze și le combinăm cu o operație. În fiecare bracket introducem o succesiune de elemente simple, unite de o operație : pentru celula tabelului unde este pus 1, scriem argumentul variabil, iar pentru fiecare celula unde se pune 0, scriem argumentul variabil cu semnul
CDNF poate fi simplificată în continuare, pentru care există diferite metode, inclusiv o metodă numită "hărți Carnot", construită pe imagini vizuale vizuale. Toate aceste metode se bazează pe regulile de simplificare:
b c) = a c
(un b) (a
Adică dacă se găsesc două paranteze în SDNF, care diferă doar în semn
înaintea unuia dintre elementele, ele pot fi înlocuite de o singură bandă, în care acest element nu există. De exemplu, formula obținută mai sus poate fi simplificată prin această regulă, combinând cele două ultimele paranteze cu unul:
Trimiteți-le prietenilor: