Formă canonică (algebră booleană)

Forma canonică sau forma normală a unei funcții booleene este un model de reprezentare a unei expresii booleene care poate fi obținută din analiza propriului tabel de adevăr .

Având o funcție booleană, există două tipuri de forme canonice:

prima formă canonică sau formă disjunctivă , numită și SOP ( suma produselor , suma produselor), construită ca sume de produse fundamentale, adică prin termeni care includ toate variabilele funcției, în formă adevărată sau negată, numite mintermini , corespunzătoare valori de ieșire ale funcției egale cu 1. Poate fi scris în general pentru n variabile:

f(x_{0},\dots ,x_{n-1})=\sum _{i=0}^{2^{n}-1}f(i)\cdot P_{i}

{\ displaystyle f (x_ {0}, \ dots, x_ {n-1}) = \ sum _ {i = 0} ^ {2 ^ {n} -1} f (i) \ cdot P_ {i}}

{\ displaystyle f (x_ {0}, \ dots, x_ {n-1}) = \ sum _ {i = 0} ^ {2 ^ {n} -1} f (i) \ cdot P_ {i}}

unde este $P_{i}$ ${\ displaystyle P_ {i}}$ $P_ {i}$ reprezintă minterms (de asemenea, notat cu $m_{i}$ ${\ displaystyle m_ {i}}$ $pe mine$ ), adică produsele fundamentale, e $f(i)$ ${\ displaystyle f (i)}$ ${\ displaystyle f (i)}$ reprezintă valoarea de ieșire a funcției la primul rând. De exemplu, cu trei variabile A, B, C:

f(A,B,C)=(A\cdot B\cdot C)+(A\cdot B\cdot {\overline {C}})+(A\cdot {\overline {B}}\cdot C)+(A\cdot {\overline {B}}\cdot {\overline {C}})+({\overline {A}}\cdot B\cdot C)+({\overline {A}}\cdot B\cdot {\overline {C}})+({\overline {A}}\cdot {\overline {B}}\cdot C)+({\overline {A}}\cdot {\overline {B}}\cdot {\overline {C}})

{\ displaystyle f (A, B, C) = (A \ cdot B \ cdot C) + (A \ cdot B \ cdot {\ overline {C}}) + (A \ cdot {\ overline {B}} \ cdot C) + (A \ cdot {\ overline {B}} \ cdot {\ overline {C}}) + ({\ overline {A}} \ cdot B \ cdot C) + ({\ overline {A}} \ cdot B \ cdot {\ overline {C}}) + ({\ overline {A}} \ cdot {\ overline {B}} \ cdot C) + ({\ overline {A}} \ cdot {\ overline { B}} \ cdot {\ overline {C}})}

{\ displaystyle f (A, B, C) = (A \ cdot B \ cdot C) + (A \ cdot B \ cdot {\ overline {C}}) + (A \ cdot {\ overline {B}} \ cdot C) + (A \ cdot {\ overline {B}} \ cdot {\ overline {C}}) + ({\ overline {A}} \ cdot B \ cdot C) + ({\ overline {A}} \ cdot B \ cdot {\ overline {C}}) + ({\ overline {A}} \ cdot {\ overline {B}} \ cdot C) + ({\ overline {A}} \ cdot {\ overline { B}} \ cdot {\ overline {C}})}

a doua formă canonică sau formă conjunctivă , numită și POS ( produsul sumelor , produsul sumelor), construit din produse din sume fundamentale, adică din termeni care includ toate variabilele funcției, în formă adevărată sau negată, numite maxtermini , corespunzând valorilor de ieșire ale funcției egale cu 0. De asemenea, poate fi generalizat la n variabile:

f(x_{0},\dots ,x_{n-1})=\prod _{i=0}^{2^{n}-1}\left(f(i)+S_{i}\right)

{\ displaystyle f (x_ {0}, \ dots, x_ {n-1}) = \ prod _ {i = 0} ^ {2 ^ {n} -1} \ left (f (i) + S_ {i } \ dreapta)}

{\ displaystyle f (x_ {0}, \ dots, x_ {n-1}) = \ prod _ {i = 0} ^ {2 ^ {n} -1} \ left (f (i) + S_ {i } \ dreapta)}

unde este $S_{i}$ ${\ displaystyle S_ {i}}$ $Da}$ reprezintă maxtermini (indicat și cu $M_{i}$ ${\ displaystyle M_ {i}}$ $Pe mine}$ ), adică sumele fundamentale, ed $f(i)$ ${\ displaystyle f (i)}$ ${\ displaystyle f (i)}$ reprezintă valoarea de ieșire a funcției la primul rând. De exemplu, cu trei variabile A, B, C:

f(A,B,C)=(A+B+C)\cdot (A+B+{\overline {C}})\cdot (A+{\overline {B}}+C)\cdot (A+{\overline {B}}+{\overline {C}})\cdot ({\overline {A}}+B+C)\cdot ({\overline {A}}+B+{\overline {C}})\cdot ({\overline {A}}+{\overline {B}}+C)\cdot ({\overline {A}}+{\overline {B}}+{\overline {C}})

{\ displaystyle f (A, B, C) = (A + B + C) \ cdot (A + B + {\ overline {C}}) \ cdot (A + {\ overline {B}} + C) \ cdot (A + {\ overline {B}} + {\ overline {C}}) \ cdot ({\ overline {A}} + B + C) \ cdot ({\ overline {A}} + B + {\ overline {C}}) \ cdot ({\ overline {A}} + {\ overline {B}} + C) \ cdot ({\ overline {A}} + {\ overline {B}} + {\ overline { C}})}

{\ displaystyle f (A, B, C) = (A + B + C) \ cdot (A + B + {\ overline {C}}) \ cdot (A + {\ overline {B}} + C) \ cdot (A + {\ overline {B}} + {\ overline {C}}) \ cdot ({\ overline {A}} + B + C) \ cdot ({\ overline {A}} + B + {\ overline {C}}) \ cdot ({\ overline {A}} + {\ overline {B}} + C) \ cdot ({\ overline {A}} + {\ overline {B}} + {\ overline { C}})}

Utilizarea tabelului adevărului:

număr	ABC	Intermini	Maxtermini
0	000	${\overline {A}}\cdot {\overline {B}}\cdot {\overline {C}}$ ${\ displaystyle {\ overline {A}} \ cdot {\ overline {B}} \ cdot {\ overline {C}}}$ ${\ displaystyle {\ overline {A}} \ cdot {\ overline {B}} \ cdot {\ overline {C}}}$	$A+B+C$ ${\ displaystyle A + B + C}$ ${\ displaystyle A + B + C}$
1	001	${\overline {A}}\cdot {\overline {B}}\cdot C$ ${\ displaystyle {\ overline {A}} \ cdot {\ overline {B}} \ cdot C}$ ${\ displaystyle {\ overline {A}} \ cdot {\ overline {B}} \ cdot C}$	$A+B+{\overline {C}}$ ${\ displaystyle A + B + {\ overline {C}}}$ ${\ displaystyle A + B + {\ overline {C}}}$
2	010	${\overline {A}}\cdot B\cdot {\overline {C}}$ ${\ displaystyle {\ overline {A}} \ cdot B \ cdot {\ overline {C}}}$ ${\ displaystyle {\ overline {A}} \ cdot B \ cdot {\ overline {C}}}$	$A+{\overline {B}}+C$ ${\ displaystyle A + {\ overline {B}} + C}$ ${\ displaystyle A + {\ overline {B}} + C}$
3	011	${\overline {A}}\cdot B\cdot C$ ${\ displaystyle {\ overline {A}} \ cdot B \ cdot C}$ ${\ displaystyle {\ overline {A}} \ cdot B \ cdot C}$	$A+{\overline {B}}+{\overline {C}}$ ${\ displaystyle A + {\ overline {B}} + {\ overline {C}}}$ ${\ displaystyle A + {\ overline {B}} + {\ overline {C}}}$
4	100	$A\cdot {\overline {B}}\cdot {\overline {C}}$ ${\ displaystyle A \ cdot {\ overline {B}} \ cdot {\ overline {C}}}$ ${\ displaystyle A \ cdot {\ overline {B}} \ cdot {\ overline {C}}}$	${\overline {A}}+B+C$ ${\ displaystyle {\ overline {A}} + B + C}$ ${\ displaystyle {\ overline {A}} + B + C}$
5	101	$A\cdot {\overline {B}}\cdot C$ ${\ displaystyle A \ cdot {\ overline {B}} \ cdot C}$ ${\ displaystyle A \ cdot {\ overline {B}} \ cdot C}$	${\overline {A}}+B+{\overline {C}}$ ${\ displaystyle {\ overline {A}} + B + {\ overline {C}}}$ ${\ displaystyle {\ overline {A}} + B + {\ overline {C}}}$
6	110	$A\cdot B\cdot {\overline {C}}$ ${\ displaystyle A \ cdot B \ cdot {\ overline {C}}}$ ${\ displaystyle A \ cdot B \ cdot {\ overline {C}}}$	${\overline {A}}+{\overline {B}}+C$ ${\ displaystyle {\ overline {A}} + {\ overline {B}} + C}$ ${\ displaystyle {\ overline {A}} + {\ overline {B}} + C}$
7	111	$A\cdot B\cdot C$ ${\ displaystyle A \ cdot B \ cdot C}$ ${\ displaystyle A \ cdot B \ cdot C}$	${\overline {A}}+{\overline {B}}+{\overline {C}}$ ${\ displaystyle {\ overline {A}} + {\ overline {B}} + {\ overline {C}}}$ ${\ displaystyle {\ overline {A}} + {\ overline {B}} + {\ overline {C}}}$

Prima formă canonică

Prima formă canonică , SOP, poate fi obținută direct din tabelul de adevăr al unei funcții. De exemplu, luați în considerare o funcție de trei variabile $f(A,B,C)$ ${\ displaystyle f (A, B, C)}$ ${\ displaystyle f (A, B, C)}$ a cărui tabel de adevăr este de exemplu:

LA	B.	C.	$f(A,B,C)$ ${\ displaystyle f (A, B, C)}$ ${\ displaystyle f (A, B, C)}$
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Trebuie să luăm în considerare valorile funcției egale cu 1, deci al treilea, al patrulea, al șaptelea și al optulea rând, care corespunde valorilor variabilelor luate în formă adevărată și negată:

f(A,B,C)=({\overline {A}}\cdot B\cdot {\overline {C}})+({\overline {A}}\cdot B\cdot C)+(A\cdot B\cdot {\overline {C}})+(A\cdot B\cdot C)

{\ displaystyle f (A, B, C) = ({\ overline {A}} \ cdot B \ cdot {\ overline {C}}) + ({\ overline {A}} \ cdot B \ cdot C) + (A \ cdot B \ cdot {\ overline {C}}) + (A \ cdot B \ cdot C)}

{\ displaystyle f (A, B, C) = ({\ overline {A}} \ cdot B \ cdot {\ overline {C}}) + ({\ overline {A}} \ cdot B \ cdot C) + (A \ cdot B \ cdot {\ overline {C}}) + (A \ cdot B \ cdot C)}

O altă modalitate este utilizarea teoremei lui Shannon .

Luăm doar funcția derivată din dezvoltarea teoremei lui Shannon și înlocuim valorile ca $f(0,0)$ ${\ displaystyle f (0,0)}$ ${\ displaystyle f (0,0)}$ cu valoarea reală pe care funcția o asumă în tabelul adevărului. În acest caz, am avea: $f(A,B)=A'B'*0+A'B*0+AB*0+AB*1$ ${\ displaystyle f (A, B) = A'B '* 0 + A'B * 0 + AB * 0 + AB * 1}$ ${\ displaystyle f (A, B) = A'B '* 0 + A'B * 0 + AB * 0 + AB * 1}$

$f(A,B)=AB$ ${\ displaystyle f (A, B) = AB}$ ${\ displaystyle f (A, B) = AB}$

Dacă cazurile în care funcția ia valoarea 1 de două ori, nu există nicio problemă, deoarece unul dintre cele trei zerouri ale funcției găsite devine unul și, prin urmare, rămâne termenul pentru care funcția rezultă 1.

În cazul în care nu dorim să folosim Teorema lui Shannon, luați rândurile tabelului în care funcția își asumă 1 ca valoare și mergeți pentru a vedea dacă variabilele sunt naturale sau completate (natural când de exemplu A = 1 sau B = 1 și completat când de exemplu A = 0 sau B = 0) și apoi scrieți $f$ ${\ displaystyle f}$ $f$ folosind formularea A dacă este naturală sau A 'dacă este completată.

Exemplu

LA	B.	$f(A,B)$ ${\ displaystyle f (A, B)}$ $f (A, B)$
0	1	1

A = 0, B = 1

$f(A,B)={\overline {A}}\cdot B$ ${\ displaystyle f (A, B) = {\ overline {A}} \ cdot B}$ ${\ displaystyle f (A, B) = {\ overline {A}} \ cdot B}$

În acest caz, dacă funcția își asumă valoarea 1 de mai multe ori, va fi suficient să adăugați celălalt minterm printr-o sumă, folosind întotdeauna procedura de mai sus pentru a o obține.

A doua formă canonică

A doua formă canonică se obține prin analiza tabelului adevărului, dar într-un mod dual în ceea ce privește metoda adoptată în prima formă canonică.

Din tabelul adevărului luăm apoi rândurile în care funcția ia valoarea 0, verificăm dacă variabilele sunt naturale sau completate , apoi scriem funcția $f$ ${\ displaystyle f}$ $f$ adunând împreună variabilele folosind formularea ${\overline {A}}$ ${\ displaystyle {\ overline {A}}}$ $\ overline A$ dacă natural e $LA$ ${\ displaystyle A}$ $LA$ dacă este completat (spre deosebire de cel folosit în prima formă canonică); dacă funcția ia valoarea 0 de mai multe ori, termenele minere trebuie împărțite la un produs. De exemplu:

LA	B.	$f(A,B)$ ${\ displaystyle f (A, B)}$ $f (A, B)$
0	0	0
0	1	1
1	0	0
1	1	0

$f(A,B)=(A+B)({\overline {A}}+B)({\overline {A}}+{\overline {B}})$ ${\ displaystyle f (A, B) = (A + B) ({\ overline {A}} + B) ({\ overline {A}} + {\ overline {B}})}$ ${\ displaystyle f (A, B) = (A + B) ({\ overline {A}} + B) ({\ overline {A}} + {\ overline {B}})}$

Unde $A+B$ ${\ displaystyle A + B}$ $A + B$ este determinat de primul rând, ${\overline {A}}+B$ ${\ displaystyle {\ overline {A}} + B}$ ${\ displaystyle {\ overline {A}} + B}$ este determinată de a treia linie e ${\overline {A}}+{\overline {B}}$ ${\ displaystyle {\ overline {A}} + {\ overline {B}}}$ ${\ displaystyle {\ overline {A}} + {\ overline {B}}}$ este determinată de ultima linie.

Alte caracteristici

În această formă, o clauză acționează ca o constrângere asupra valorilor posibile pe care le pot avea variabilele care o compun. De exemplu, clauza (A OR ~ B OR C) este satisfăcută de toate atribuțiile FALSE-TRUE posibile, cu excepția A = C = FALSE și B = TRUE. Mai mult, o formulă în CNF poate fi văzută ca un sistem de constrângeri în spațiul atribuirilor binare ale variabilelor sale. Pentru a extinde acest concept este util să remarcăm existența unui alt tip de "sistem de constrângeri", cum ar fi sistemele de inegalități liniare pe variabile reale sau întregi care identifică o regiune fezabilă (și, prin urmare, atribuiri admisibile) în programarea liniară și întreaga programare liniară. . Regiunea fezabilă a unei formule CNF conține exact acele valori care fac formula evaluabilă ca ADEVĂRATĂ.

Elemente conexe

Portal IT

Portalul de matematică