Funcţie booleană

O funcție booleană (sau o funcție logică , sau o funcție a algebrei logicii ) [1] de n argumente - în matematică discretă - o mapare B n → B , unde B = {0,1} este o mulțime booleană . Elementele mulțimii booleene {1, 0} sunt de obicei interpretate ca valori logice „adevărat” și „fals”, deși în cazul general sunt considerate simboluri formale care nu poartă o semnificație specifică. Un întreg nenegativ n , care denotă numărul de argumente, se numește aritatea sau localitatea funcției, în cazul lui n = 0, funcția booleană se transformă într-o constantă booleană . Elementele produsului cartezian ( a n- a putere directă) B n se numesc vectori booleeni . Mulțimea tuturor funcțiilor booleene a oricărui număr de argumente este adesea notat cu P 2 , iar a n argumente cu P 2 ( n ). Variabilele care preiau valori dintr-un set boolean se numesc variabile booleene [2] . Funcțiile booleene sunt numite după matematicianul George Boole .

Când se lucrează cu funcții booleene, există o abstractizare completă din sensul semnificativ care este asumat în algebra propozițiilor [2] . Cu toate acestea, o corespondență unu-la-unu poate fi stabilită între funcțiile booleene și formulele de algebră propozițională dacă [3] :

stabiliți o corespondență unu-la-unu între variabilele booleene și propoziționale ;
stabiliți o conexiune între funcțiile booleene și conectivele logice;
lasă neschimbată prioritatea operațiunilor .

Informații de bază

Fiecare funcție booleană a arității n este complet definită prin stabilirea valorilor sale pe domeniul său de definire, adică pe toți vectorii booleeni de lungime n . Numărul de astfel de vectori este egal cu 2 n . Deoarece o funcție booleană poate lua fie 0, fie 1 pe fiecare vector, numărul tuturor funcțiilor booleene n -are este 2 (2 n ) . Prin urmare, în această secțiune sunt luate în considerare doar cele mai simple și mai importante funcții booleene.

Aproape toate funcțiile booleene ale ariităților inferioare (0, 1, 2 și 3) au primit nume istorice. Dacă valoarea funcției nu depinde de una dintre variabile (adică, de fapt, pentru oricare doi vectori booleeni care diferă doar prin valoarea acestei variabile, valoarea funcției pe ei este aceeași), atunci aceasta variabilă, fără a juca vreo „valoare”, se numește fictiv .

Tabele de adevăr

O funcție booleană este definită printr-un set finit de valori, care îi permite să fie reprezentată ca un tabel de adevăr , de exemplu [4] :

x 1	x2 _	…	xn - 1	x n	f ( x 1 , x 2 , …, x n )
0	0	…	0	0	0
0	0	…	0	unu	0
0	0	…	unu	0	unu
0	0	…	unu	unu	0
$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$	$\vdots$
unu	unu	…	0	0	unu
unu	unu	…	0	unu	0
unu	unu	…	unu	0	0
unu	unu	…	unu	unu	0

Funcții nulare

Pentru n = 0, numărul de funcții booleene se reduce la două 2 2 0 = 2 1 = 2, prima dintre ele este identic egală cu 0, iar a doua este 1. Se numesc constante booleene - identic zero și identic unul .
Tabel de valori și nume ale funcțiilor booleene nule:

	Sens	Desemnare	Nume
	0	F0,0 = 0	zero identic
	unu	F0,1 = 1	unitate identică, tautologie

Funcții unare

Pentru n = 1, numărul de funcții booleene este 2 2 1 = 2 2 = 4. Aceste funcții sunt definite în tabelul următor.

Tabel de valori și nume ale funcțiilor booleene dintr-o variabilă:

x0 = x	unu	0	Desemnare	Nume
0	0	0	F1.0 = 0	zero identic
unu	0	unu	F1,1 = x = ¬ x = x' = NU(x)	negație, logic „NU”, „NU”, „NOR”, invertor , SWAP (schimb)
2	unu	0	F1,2 = x	funcție de identitate, logic „DA”, repetor
3	unu	unu	F1.3=1	unitate identică, tautologie

Funcții binare

Pentru n = 2, numărul de funcții booleene este 2 2 2 = 2 4 = 16.

Tabel de valori și nume ale funcțiilor booleene din două variabile:

x0 = x	unu	0	unu	0	Notarea funcției	Numele funcției
x 1 =y	unu	unu	0	0	Notarea funcției	Numele funcției
0	0	0	0	0	F2.0=0	zero identic
unu	0	0	0	unu	F2,1 = x ↓ y = x NOR y = NOR( x , y ) = x NOR y = NOR ( x , y ) = NOT(MAX(X,Y))	Săgeată străpunge - „↓” ( pumnalul lui Quine - „†”), funcție Webb - „°” [5] , NON-SAU, 2SAU-NU, antidisjuncție, inversare maximă
2	0	0	unu	0	F2,2 = x > y = x GT y = GT( x , y ) = x → y = x ↛ y	funcția de comparație „primul operand este mai mare decât al doilea operand”, inversul implicației directe , coiplicație [6]
3	0	0	unu	unu	F2,3 = y = y' = ¬ y = NOT2( x , y ) = NOT2( x , y )	negația (negația, inversarea) celui de-al doilea operand
patru	0	unu	0	0	F2,4 = x < y = x LT y = LT( x , y ) = x ← y = x ↚ y	funcția de comparație „primul operand este mai mic decât al doilea operand”, implicație inversă, coimplicație inversă [6]
5	0	unu	0	unu	F2,5 = x = x' = ¬ x = NOT1( x , y ) = NOT1( x , y )	negația (negația, inversarea) primului operand
6	0	unu	unu	0	F2,6 = x >< y = x <> y = x NE y = NE(x, y) = x ⊕ y = x XOR y = XOR( x , y )	funcția de comparație „operanzii nu sunt egali”, adăugarea modulo 2 excluzând „sau” , suma lui Zhegalkin [7]
7	0	unu	unu	unu	F2.7 = x \| y = x NAND y = NAND( x , y ) = x NAND y = NAND ( x , y ) = NOT(MIN(X,Y))	AVC lui Schaeffer , linia punctată a lui Chulkov [8] , NAND, 2I-NOT, anticonjuncție, inversare minimă
opt	unu	0	0	0	F2,8 = x ∧ y = x y = xy = x & y = x AND y = AND( x , y ) = x AND y = AND( x , y ) = min ( x , y )	conjuncție , 2I, minim
9	unu	0	0	unu	F2.9 = ( x ≡ y ) = x ~ y = x ↔ y = x EQV y = EQV( x , y )	funcția de comparație „operanzii sunt egali”, echivalență
zece	unu	0	unu	0	F2,10 = DA1( x , y ) = DA1( x , y ) = x	primul operand
unsprezece	unu	0	unu	unu	F2,11 = x ≥ y = x >= y = x GE y = GE( x , y ) = x ← y = x ⊂ y	funcție de comparație „primul operand nu este mai mic decât al doilea operand”, implicație inversă (de la al doilea argument la primul)
12	unu	unu	0	0	F2,12 = DA2( x , y ) = DA2( x , y ) = y	al doilea operand
13	unu	unu	0	unu	F2.13 = x ≤ y = x <= y = x LE y = LE( x , y ) = x → y = x ⊃ y	funcția de comparație „primul operand nu este mai mare decât al doilea operand”, implicație directă (materială) (de la primul argument la al doilea)
paisprezece	unu	unu	unu	0	F2,14 = x ∨ y = x + y = x SAU y = SAU( x , y ) = x SAU y = SAU( x , y ) = max( x , y )	disjuncție , 2OR, max
cincisprezece	unu	unu	unu	unu	F2.15=1	unitate identică, tautologie

Cu două argumente , notația prefix , infix și postfix sunt aproape aceleași din punct de vedere economic.

Unele funcții care au sens în tehnologia digitală , cum ar fi funcțiile de comparație, minime și maxime, nu au sens în logică, deoarece în logică , în general, valorile booleene TRUE și FALSE nu au o legătură solidă cu valorile numerice. (de exemplu, în TurboBasic , pentru a simplifica unele calcule, TRUE = -1 și FALSE = 0) și este imposibil să se determine ce este mai mare decât TRUE sau FALSE, în timp ce implicațiile și altele au sens atât în tehnologia digitală, cât și în logică.

Funcții ternare

Pentru n = 3, numărul de funcții booleene este 2 (2 3 ) = 2 8 = 256. Unele dintre ele sunt definite în următorul tabel:
Tabel de valori și denumiri ale unor funcții booleene din trei variabile cu nume propriu :

x0 = x	unu	0	unu	0	unu	0	unu	0	Notaţie	Titluri
x 1 =y	unu	unu	0	0	unu	unu	0	0
x 2 \u003d z	unu	unu	unu	unu	0	0	0	0
unu	0	0	0	0	0	0	0	unu	F3,1 = x ↓ y ↓ z = ↓(x,y,z) = Webb 2 (x,y,z) = NOR(x,y,z)	3SAU-NU, funcție Webb, săgeata lui Pierce , pumnalul lui Quine - „†”
23	0	0	0	unu	0	unu	unu	unu	F3,23 = = ≥2(x,y,z) $\neg (>=2(x,y,z))$	Comutator majoritar cu inversare, 3PPB-NE, ventil majoritar cu inversare
71	0	unu	0	0	0	unu	unu	unu	F3.71= $[x,y,z]$	Disjuncția condiționată
126	0	unu	unu	unu	unu	unu	unu	0	F3.126 = (x≠y≠z) = [≠(x,y,z)] = NE(x,y,z)	Inegalitate
127	0	unu	unu	unu	unu	unu	unu	unu	F3,127 = x\|y\|z = \|(x,y,z) = NAND(x,y,z)	3I-NU, accident vascular cerebral Schaeffer
128	unu	0	0	0	0	0	0	0	F3,128 = x&y&z = &(x,y,z) = (x AND y AND z) = AND(x,y,z) = (x AND y AND z) = AND(x,y,z) = min (x,y,z)	3I, minim
129	unu	0	0	0	0	0	0	unu	F3.129 = (x=y=z) = [=(x,y,z)] = EQV(x,y,z)	Egalitatea
150	unu	0	0	unu	0	unu	unu	0	F3,150 = x⊕y⊕z = x⊕ 2 y⊕ 2 z = ⊕ 2 (x,y,z)	Adunarea ternară modulo 2
216	unu	unu	0	unu	unu	0	0	0	F3.216 = f 1	Împrumut cu scădere ternară
232	unu	unu	unu	0	unu	0	0	0	F3,232 = f 2 = [>=2(x,y,z)] = ≥2(x,y,z) = (x AND y) SAU (y AND z) SAU (z AND x)	Bit de transport pentru adăugare ternară, comutator majoritar, 3PPB, supapă majoritară
254	unu	unu	unu	unu	unu	unu	unu	0	F3,254 = (x+y+z) = +(x,y,z) = (x SAU y SAU z) = SAU(x,y,z) = (x SAU y SAU z) = SAU(x, y,z) = max(x,y,z)	SAU, maxim

Cu trei sau mai multe argumente, notația prefix (și postfix) este mai economică decât notația infix.
Modul obișnuit de a scrie funcții este prefixul (înainte de operanzi). Cu notația infixă (între operanzi) a funcțiilor, funcțiile sunt numite operatori, iar argumentele funcției sunt numite operanzi.

Sisteme complete de funcții booleene

Suprapunerea și clasele închise de funcții

Rezultatul evaluării unei funcții booleene poate fi folosit ca unul dintre argumentele unei alte funcții. Rezultatul unei astfel de operații de suprapunere poate fi privit ca o nouă funcție booleană cu propria sa tabelă de adevăr. De exemplu, o funcție (suprapunerea conjuncției, a disjuncției și a două negații) va corespunde următorului tabel: $f(x,y,z)=\overline {x(\overline {y}\lorz)}$

$x_{2}=x$	$x_{1}=y$	$x_{0}=z$	$f(x,y,z)$
0	0	0	unu
0	0	unu	unu
0	unu	0	unu
0	unu	unu	unu
unu	0	0	0
unu	0	unu	0
unu	unu	0	unu
unu	unu	unu	0

Se spune că un set de funcții este închis sub operația de suprapunere dacă orice suprapunere de funcții dintr-o mulțime dată este de asemenea inclusă în aceeași mulțime. Seturile închise de funcții sunt numite și clase închise .

Ca cele mai simple exemple de clase închise de funcții booleene , se poate numi o mulțime formată dintr-o funcție identică, sau o mulțime , toate funcțiile din care sunt identic egale cu zero, indiferent de argumentele lor. Setul de funcții și setul tuturor funcțiilor unare sunt de asemenea închise. Dar unirea claselor închise poate să nu mai fie așa. De exemplu, combinând clasele și , putem folosi suprapunerea pentru a obține constanta 1, care a fost absentă în clasele originale. $\{X\}$ $\{0\}$ $\{x,\overline {x}\}$ $\{0\}$ $\{x,\overline {x}\}$ $\overline {0}$

Desigur, setul tuturor funcțiilor booleene posibile este de asemenea închis. $P_2$

Identitate și dualitate

Două funcții booleene sunt identice una cu cealaltă dacă iau valori egale pe orice seturi identice de argumente. Identitatea funcțiilor f și g poate fi scrisă, de exemplu, după cum urmează:
$f(x_{1},x_{2},\dots ,x_{n})=g(x_{1},x_{2},\dots ,x_{n})$

Privind tabelele de adevăr ale funcțiilor booleene, este ușor să obțineți următoarele identități:

$\overline {0}=1$	$\overline {1}=0$	$\overline {\overline {x}}=x$	$xy=yx$	$x\lor y=y\lor x$
$0x=0$	$1x=x$	$0\lor x=x$	$1\lorx=1$	$xx=x\lor x=x$

Și verificarea tabelelor construite pentru unele suprapuneri va da următoarele rezultate:

x\overline {x}=0

x\lor \overline {x}=1

\overline {x\cdot y}=\overline {x}\lor \overline {y}

\overline {x}\cdot \overline {y}=\overline {x\lor y}

( legile lui de Morgan )

$x(y\lor z)=xy\lor xz$
$x\lor yz=(x\lor y)(x\lor z)$ ( distributivitatea conjuncției și a disjuncției)

Funcția se numește funcție duală dacă . Este ușor de arătat că în această egalitate f și g pot fi interschimbate, adică funcțiile f și g sunt duale între ele. Dintre cele mai simple funcții, constantele 0 și 1 sunt duale între ele, iar dualitatea conjuncției și disjuncției rezultă din legile lui De Morgan. Funcția identică, ca și funcția de negație, este duală cu ea însăși. $g(x_{1},x_{2},\dots ,x_{n})$ $f(x_{1},x_{2},\dots ,x_{n})$ $f(\overline {x_{1}},\overline {x_{2}},\dots ,\overline {x_{n}})=\overline {g(x_{1},x_{2},\dots ,x_{n})}$

Dacă într-o identitate booleană înlocuim fiecare funcție cu duala ei, obținem din nou identitatea corectă. În formulele de mai sus, este ușor să găsiți perechi duble între ele.

Completitudinea sistemului, criteriul Postului

Un sistem de funcții booleene se numește complet dacă este posibil să se construiască suprapunerea lor, care este identică cu orice funcție predefinită. Ei mai spun că închiderea unui sistem dat coincide cu mulțimea . $P_2$

Matematicianul american Emil Post a introdus următoarele clase închise de funcții booleene:

Funcții care păstrează constanta și ; $P_0$ $P_1$
Funcții auto-duale ; $S$
Funcții monotone ; $M$
Funcții liniare . $L$

El a demonstrat că orice clasă închisă de funcții booleene care nu coincide cu este conținută în întregime în una dintre aceste cinci așa-numite clase precomplete , dar niciuna dintre cele cinci nu este conținută în întregime în uniunea celorlalte patru. Astfel, criteriul lui Post pentru completitudinea unui sistem se rezumă la a afla dacă întregul sistem este cuprins în întregime într-una dintre clasele precomplete. Dacă pentru fiecare clasă din sistem există o funcție care nu este inclusă în ea, atunci un astfel de sistem va fi complet și, cu ajutorul funcțiilor incluse în acesta, se va putea obține orice altă funcție booleană. Post a demonstrat că setul de clase închise de funcții booleene este o mulțime numărabilă . $P_2$

Rețineți că există funcții care nu sunt incluse în niciuna dintre clasele Post. Orice astfel de funcție formează în sine un sistem complet. Exemplele includ lovitura lui Schaeffer sau săgeata lui Pierce .

Reprezentarea funcțiilor booleene

Teorema lui Post deschide calea pentru reprezentarea funcțiilor booleene într-un mod sintactic care în unele cazuri se dovedește a fi mult mai convenabil decât tabelele de adevăr. Punctul de plecare aici este găsirea unui sistem complet de funcții . Apoi, fiecare funcție booleană poate fi reprezentată printr-un anumit termen din semnătură , care în acest caz este numit și formulă . În ceea ce privește sistemul de funcții ales, este util să cunoaștem răspunsurile la următoarele întrebări: $\Sigma =\{f_{1},\ldots ,f_{n}\}$ $\Sigma$

Cum se construiește o formulă reprezentând această funcție?
Cum se verifică dacă două formule diferite sunt echivalente, adică definesc aceeași funcție?
- În special: există o modalitate de a reduce o formulă arbitrară la forma sa canonică echivalentă , astfel încât două formule să fie echivalente dacă și numai dacă formele lor canonice sunt aceleași?
Cum poate fi folosită o funcție dată pentru a construi o formulă care o reprezintă cu anumite proprietăți date (de exemplu, cea mai mică dimensiune) și este posibil acest lucru?

Răspunsurile pozitive la aceste și alte întrebări cresc semnificativ valoarea aplicată a sistemului de funcții ales.

Forma normală disjunctivă (DNF)

O conjuncție simplă sau conjuncție este o conjuncție a unui set finit de variabile sau a negațiilor acestora, fiecare variabilă aparând cel mult o dată. Forma normală disjunctivă sau DNF este disjuncția conjuncțiilor simple. Conjuncția elementară

corect , dacă fiecare variabilă este inclusă în ea nu mai mult de o dată (inclusiv negația);
complete , dacă fiecare variabilă (sau negația ei) o introduce exact 1 dată;
monoton dacă nu conține negații ale variabilelor.

De exemplu - este un DNF. $a{\overline {b}}c\lor b{\overline {c}}\lor {\overline {a}}$

O formă normală disjunctivă perfectă sau SDNF în raport cu un anumit set finit de variabile este un DNF astfel încât fiecare conjuncție conține toate variabilele mulțimii date și în aceeași ordine. De exemplu: . $a\overline {b}c\lor abc\lor \overline {a}b\overline {c}$

Este ușor de observat că fiecare funcție booleană corespunde unui DNF și unei alte funcții decât zeroul identic, chiar și unui SDNF. Pentru a face acest lucru, este suficient să găsiți în tabelul de adevăr al acestei funcții toți vectorii booleeni pe care valoarea sa este egală cu 1 și pentru fiecare astfel de vector să construiți o conjuncție , unde . Disjuncția acestor conjuncții este SDNF-ul funcției originale, deoarece pe toți vectorii booleeni valorile sale coincid cu valorile funcției originale. De exemplu, pentru o implicație , rezultatul este , care poate fi simplificat la . $b=(b_{1},b_{2},\ldots, b_{n})$ $x_{1}^{{b_{1}}}x_{2}^{{b_{2}}}\ldots x_{n}^{{b_{n}}}$ $x_{i}^{1}=x_{i}$ $x_{i}^{0}=\overline {x_{i}}$ $x\la y$ $\overline {x}y\lor \overline {x}\,\overline {y}\lor xy$ $\overline {x}\lor y$

Forma normală conjunctivă (CNF)

Forma normală conjunctivă (CNF) este definită dual la DNF. O disjuncție simplă sau disjuncție este o disjuncție a uneia sau mai multor variabile sau a negațiilor acestora și fiecare variabilă este inclusă în ea nu mai mult de o dată. CNF este o conjuncție de disjuncții simple.

O formă normală conjunctivă perfectă (PCNF), în raport cu un anumit set finit de variabile, este un astfel de CNF, în care fiecare disjuncție include toate variabilele acestei mulțimi și în aceeași ordine. Deoarece (C)CNF și (C)DNF sunt reciproc duale, proprietățile (C)CNF repetă toate proprietățile (C)DNF, aproximativ vorbind, „exact opusul”.

CNF poate fi convertit în DNF echivalent prin deschiderea parantezelor conform regulii:

a(b\lor c)\to ab\lor ac

care exprimă distributivitatea conjuncţiei faţă de disjuncţie. După aceea, este necesar să se elimine variabilele repetate sau negațiile lor în fiecare conjuncție și, de asemenea, să se elimine din disjuncție toate conjuncțiile în care variabila apare împreună cu negația ei. În acest caz, rezultatul nu va fi neapărat SDNF, chiar dacă CNF inițial a fost SKNF. În mod similar, se poate trece întotdeauna de la DNF la CNF. Pentru a face acest lucru, utilizați regula

a\lor bc\to (a\lor b)(a\lor c)

exprimând distributivitatea disjuncției față de conjuncție. Rezultatul trebuie transformat în modul descris mai sus, înlocuind cuvântul „conjuncție” cu „disjuncție” și invers.

Forma normală algebrică (ANF sau polinomul Zhegalkin)

Forma normală algebrică (nume comun în literatura străină) sau polinomul Zhegalkin (nume folosit în literatura internă) este o formă de reprezentare a unei funcții logice ca polinom cu coeficienți de forma 0 și 1, în care operația de conjuncție („ȘI” , AND), și ca adunare - adiție modulo 2 (exclusiv "OR", XOR). Pentru a obține polinomul Zhegalkin, procedați după cum urmează:

Obțineți funcții sdnf
Înlocuiți toate SAU cu SAU exclusiv
În toți termenii, înlocuiți elementele cu negație cu construcția: ("element" "SAU exclusiv" 1)
Deschideți parantezele conform regulilor algebrei Zhegalkin și dați termeni identici în perechi

Clasificarea funcțiilor booleene

După numărul n de operanzi de intrare, de care depinde valoarea la ieșirea funcției, există nuli ( n = 0), unari ( n = 1), binari ( n = 2), ternari ( n = 3) boolean funcţii şi funcţii dintr-un număr mai mare de operanzi .

După numărul de unu și zerouri din tabelul de adevăr, o clasă restrânsă de funcții booleene echilibrate (numite și echilibrate sau equiprobabile, deoarece cu valori aleatoare echiprobabile la intrare sau la iterarea tuturor combinațiilor din tabelul de adevăr, probabilitatea de a obține valoarea 1 la ieșire este 1/2) se distinge de clasa mai largă de funcții booleene dezechilibrate (numite și dezechilibrate, deoarece probabilitatea de a obține valoarea 1 la ieșire este diferită de 1/2). Funcțiile booleene echilibrate sunt utilizate în principal în criptografie .

În funcție de dependența valorii funcției de permutarea biților săi de intrare, funcțiile booleene simetrice (a căror valoare depinde numai de numărul de unități la intrare) și funcțiile booleene asimetrice (a căror valoare depinde și de permutarea biții săi de intrare) se disting.

Funcțiile auto-duale (a căror valoare este inversată atunci când valorile tuturor intrărilor sunt inversate) se disting de alte funcții booleene care nu au această proprietate prin valoarea funcției pe seturi opuse de valori ale argumentelor . Partea inferioară a tabelului de adevăr pentru funcțiile auto-duale este o imagine în oglindă a părții superioare inversate (dacă aranjați combinațiile de intrare în tabelul de adevăr într-o ordine naturală).

În funcție de gradul algebric de neliniaritate, se disting funcțiile booleene liniare ( al căror ANF se reduce la o sumă liniară modulo 2 a valorilor de intrare) și funcțiile booleene neliniare ( al căror ANF conține cel puțin o operație neliniară de conjuncție a valorile de intrare). Exemple de funcții liniare sunt: adunarea modulo 2 (exclusiv OR, XOR), echivalența , precum și toate funcțiile booleene ale căror ANF conține numai operații de adunare liniare modulo 2 fără conjuncții. Exemple de funcții neliniare sunt: conjuncția ("ȘI", ȘI), cursa Schaeffer ("NU-ȘI", NAND), săgeata lui Pierce ("NU-SAU", NOR), precum și toate funcțiile booleene al căror ANF conține cel puțin o operație de conjuncție neliniară.

Variabile esențiale și fictive

O variabilă a unei funcții booleene este numită esențială dacă pentru o funcție booleană există două seturi de valori ale argumentelor sale care diferă doar prin valoarea acestei variabile și valorile funcției booleene pe acestea diferă. Dacă valorile acestei funcții coincid cu ele, atunci variabila se numește dummy. O variabilă este esențială dacă și numai dacă intră într-un DNF perfect al unei funcții booleene sau într-un polinom Zhegalkin al unei funcții booleene.

Două funcții booleene se numesc egale dacă seturile variabilelor lor esențiale sunt egale, iar valorile funcțiilor coincid cu oricare două seturi egale de valori ale variabilelor esențiale. [9]

Vezi și

Literatură

Alekseev V.B. (conferentiar), Pospelov A.D. (compilator). Matematică discretă (curs de prelegeri, semestrul II) . - M .: Ed. otd. fals. Calculati. Matematică și Cibernetică, Universitatea de Stat din Moscova. M. V. Lomonosov, 2002. - 44 p.
Bykova S. V., Burkatovskaya Yu. B. Funcții booleene: un manual pentru studenții instituțiilor de învățământ superior care studiază în specialitatea HPE 010501 „Matematică aplicată și informatică” . - Tomsk: Statul Tomsk. un-t, 2010. - 190 p.
Gavrilov G. P., Sapozhenko A. A. Probleme și exerciții de matematică discretă . - M. : FIZMATLIT, 2009.
Igoshin VI Logica matematică și teoria algoritmilor . - Ed. a II-a, stereotip .. - M . : Centrul editorial „Academia”, 2008. - 448 p.
Kuznetsov OP Matematică discretă pentru un inginer . - Sankt Petersburg. : Lan, 2007. - 394 p.
Manuale ale Departamentului de Cibernetică Matematică a MSU VMiK (pe site-ul web al Departamentului de Cibernetică Matematică a MSU VMK).
Lozhkin S.A. Prelegeri despre fundamentele ciberneticii: manual. manual pentru cursurile „Fundamentele ciberneticii” și „Structură. implementare discretă. funcții” . - M .: Ed. otd. fals. Calculati. Matematică și Cibernetică, Universitatea de Stat din Moscova. M. V. Lomonosov, 2004. - 254 p.
Marchenkov SS Clase închise de funcții booleene . - M. : Fizmatlit, 2001. - 126 p.
Samofalov K. G., Romankevich A. M., Valuysky V. N., Kanevsky Yu. S., Pinevich M. M. Teoria aplicată a automatelor digitale . - Kiev: Vishcha Shkola, 1987. - S. 183-189. — 375 p.
Yablonsky SV Introducere în matematica discretă . - M .: Mai sus. şcoală, 2006. - 384 p.

Link -uri

↑ Igoshin, 2008 , Capitolul 2. Funcții booleene.
↑ 1 2 Igoshin, 2008 , p. 94.
↑ Igoshin, 2008 , p. 104-105.
↑ Samofalov, 1987 .
↑ Funcții booleene elementare . Consultat la 9 noiembrie 2016. Arhivat din original pe 10 noiembrie 2016. (nedefinit)
↑ 1 2 Întrebări alese ale teoriei funcțiilor booleene. // A. S. Balyuk şi colab. Ed. S. F. Vinokurov și N. A. Peryazev. — M.: FIZMATLIT, 2001. — 192 p. - S. 13.
↑ Igoshin, 2008 , p. 96.
↑ I.A. Nasyrov. ajutor didactic . Preluat la 20 noiembrie 2020. Arhivat din original la 22 decembrie 2019. (nedefinit)
↑ Gavrilov G.P., Sapozhenko A.A. Culegere de probleme de matematică discretă. - M., Nauka, 1977. - p. 44, 46, 47

Dicționare și enciclopedii	Rusă mare
În cataloagele bibliografice	LNB : 000324702

$x_{2}=x$	$x_{1}=y$	$x_{0}=z$	$f(x,y,z)$
0	0	0	unu
0	0	unu	unu
0	unu	0	unu
0	unu	unu	unu
unu	0	0	0
unu	0	unu	0
unu	unu	0	unu
unu	unu	unu	0

$x_{2}=x$	$x_{1}=y$	$x_{0}=z$	$f(x,y,z)$
0	0	0	unu
0	0	unu	unu
0	unu	0	unu
0	unu	unu	unu
unu	0	0	0
unu	0	unu	0
unu	unu	0	unu
unu	unu	unu	0

$x_{2}=x$	$x_{1}=y$	$x_{0}=z$	$f(x,y,z)$
0	0	0	unu
0	0	unu	unu
0	unu	0	unu
0	unu	unu	unu
unu	0	0	0
unu	0	unu	0
unu	unu	0	unu
unu	unu	unu	0