Expressions et fonctions booléennes

Expression booléenne = terme construit à partir de variables booléennes et d'opérateur booléens.

Fonction booléenne = fonction binaire à variables binaires (de $\{0,1\}^n$ dans $\{0,1\}$).

Une fonction booléenne peut être décrite par :

• sa table de vérité (recensant toutes les combinaisons de valeur des variables)
• une expression booléenne (décrivant la sortie 1 de la fonction, par convention, désigne la valeur 0 pour a)

Exemple : fonction booléenne majorité s'exprime par

a	b	c	majorité
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

ou : majorité(a,b,c) = bc + a c + ab + abc

? Montrer qu'il y a 2²ⁿ fonctions booléennes à n arguments ?

! Les portes NAND et NOR sont dites complètes car on peut réaliser n'importe quelle fonction boléenne avec l'une ou l'autre.