Funcția booleană

În matematică și informatică , o funcție booleană cu n variabile este o funcție :

f(x_{0},x_{1},\dots ,x_{n})\colon B^{n}\rightarrow B

{\ displaystyle f (x_ {0}, x_ {1}, \ dots, x_ {n}) \ colon B ^ {n} \ rightarrow B}

{\ displaystyle f (x_ {0}, x_ {1}, \ dots, x_ {n}) \ colon B ^ {n} \ rightarrow B}

a variabilelor booleene $x_{i}$ ${\ displaystyle x_ {i}}$ $x_i$ care iau valori în spațiul boolean $B=\{0,1\}$ ${\ displaystyle B = \ {0,1 \}}$ ${\ displaystyle B = \ {0,1 \}}$ , precum și $f$ ${\ displaystyle f}$ $f$ în sine. Cu un set de $n$ ${\ displaystyle n}$ $n$ variabilele există $2^{2^{n}}$ ${\ displaystyle 2 ^ {2 ^ {n}}}$ ${\ displaystyle 2 ^ {2 ^ {n}}}$ funcții posibile. Funcțiile booleene sunt, de asemenea, importante, deoarece sunt izomorfe pentru circuite digitale, adică un circuit digital poate fi exprimat printr-o expresie booleană și invers; prin urmare, joacă un rol cheie în proiectarea circuitelor digitale, dar găsesc și aplicații în criptografie și telecomunicații . Deoarece variabilele pot lua doar valorile 0 sau 1, o funcție booleană cu $n$ ${\ displaystyle n}$ $n$ variabilele de intrare au numai $2^{n}$ ${\ displaystyle 2 ^ {n}}$ $2 ^ {n}$ combinații posibile și pot fi descrise printr-un tabel, numit tabel adevăr , cu $2^{n}$ ${\ displaystyle 2 ^ {n}}$ $2 ^ {n}$ dungi.

Expresii booleene: definiții

O variabilă generică booleană care apare în interiorul unei funcții booleene este indicată cu o literă și din acest motiv este denumită și literală . Produsul logic al două sau mai multor literali, negat sau nu, constituie o clauză numită și termen elementar . Suma logică a doi sau mai mulți literali, negată sau nu, este un factor elementar .

Să luăm câteva exemple:

a\cdot {\overline {b}}\cdot x.

{\ displaystyle a \ cdot {\ overline {b}} \ cdot x.}

{\ displaystyle a \ cdot {\ overline {b}} \ cdot x.}

Aceasta este o clauză sau un termen elementar alcătuit din trei literali. Sau putem avea factori elementari care în exemplul următor sunt introduși ȘI:

(a+{\overline {x}})\cdot (b+c).

{\ displaystyle (a + {\ overline {x}}) \ cdot (b + c).}

{\ displaystyle (a + {\ overline {x}}) \ cdot (b + c).}

O funcție de trei variabile $la,$ ${\ displaystyle a,}$ ${\ displaystyle a,}$ $b$ ${\ displaystyle b}$ $b$ Și $c$ ${\ displaystyle c}$ $c$ poate fi exprimat în două forme canonice numite forma P care este o sumă de produse și forma S care este un produs al sumelor: în cadrul acestor două forme apar respectiv clauze cu toate cele trei variabile sau factori elementari cu toate cele trei variabile negate sau refuzate: acestea sunt numite mintermin și maxtermin .

f(a,b,c)=\ldots +a{\overline {b}}{\overline {c}}+\ldots

{\ displaystyle f (a, b, c) = \ ldots + a {\ overline {b}} {\ overline {c}} + \ ldots}

{\ displaystyle f (a, b, c) = \ ldots + a {\ overline {b}} {\ overline {c}} + \ ldots}

f(a,b,c)=\ldots \cdot (a+b+{\overline {c}})\cdot \ldots

{\ displaystyle f (a, b, c) = \ ldots \ cdot (a + b + {\ overline {c}}) \ cdot \ ldots}

{\ displaystyle f (a, b, c) = \ ldots \ cdot (a + b + {\ overline {c}}) \ cdot \ ldots}

prima formulă reprezintă forma P, a doua reprezintă forma S.

Funcțiile elementare booleene

Toate așa-numitele funcții booleene generalizate sunt obținute prin compunerea a trei funcții specifice numite elementare sau fundamentale. Funcțiile booleene fundamentale sunt ȘI (de obicei indicat cu semnul produsului: x, $\cdot$ ${\ displaystyle \ cdot}$ $\ cdot$ ), OR (de obicei indicat cu semnul plus: +) și NOT (de obicei indicat cu semnul ¬ sau! sau cu o liniuță deasupra variabilei de negat). Deoarece descrierea algebrică sau mai bună, logică a unui circuit dat este o funcție booleană; funcțiile sale elementare descriu propriile circuite, care în acest caz poartă numele de porți elementare . Mai mult, funcțiile / porțile AND și OR pot fi tratate și ca funcții generalizate a $n$ ${\ displaystyle n}$ $n$ variabile în timp ce NOT are proprietatea de a fi unar, adică poate avea o singură variabilă binară ca intrare.

Funcțiile booleene și procesul de minimizare

În domeniul circuitelor digitale, în special în domeniul proiectării logice a circuitelor, procesul de Minimizare a unei funcții booleene și a circuitului pe care îl descrie, în termeni de porți AND, SAU și NU, are o importanță considerabilă. Practic, se poate spune că dată o funcție booleană

y=f(x_{0},x_{1},\dots ,x_{n})

{\ displaystyle y = f (x_ {0}, x_ {1}, \ dots, x_ {n})}

{\ displaystyle y = f (x_ {0}, x_ {1}, \ dots, x_ {n})}

există multiple reprezentări ale acesteia, în sensul că, în conformitate cu teoremele dualității, De Morgan și axiomele algebrei booleene, funcția poate lua diferite forme, fără a-și schimba numărul caracteristic , adică setul de valori care își asumă a lui $y .$ ${\ displaystyle y.}$ ${\ displaystyle y.}$ Minimizarea unei funcții, prin urmare, înseamnă găsirea, printre toate reprezentările sau formele sale, a celei care are numărul minim de porți elementare.

linkuri externe

Software MIN pentru minimizarea funcțiilor booleene (de Dario Mazzeo)

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică