Théorèmes et propriétés

Guy Bégin

3 Théorèmes et propriétés

1.1. Objectifs

Bien saisir les relations de dualité entre les opérations
Connaître les principaux théorèmes de l’algèbre de Boole et les appliquer correctement
Appliquer les théorèmes de DeMorgan
Passer d’une version d’un théorème à sa version duale
Connaître les autres fonctions logiques importantes
Construire un tableau de vérité

1.2. Dualité

Les postulats ont été formulés en paires, identifiés par ♠ et ♥. En interchangeant les opérateurs et les éléments identité, on transforme un postulat de forme ♠ en un postulat de forme ♥. C’est le principe de dualité. Ainsi, n’importe quelle expression algébrique demeurera valide si les opérateurs et les valeurs d’éléments identité sont interchangés.

Puisque notre algèbre ne comporte que deux éléments, les deux éléments identité sont en fait les deux seuls éléments, 0 et 1. On obtient donc le dual d’une expression en changeant les 0 pour des 1, les 1 pour des 0 et les ET pour des OU, les OU pour des ET.

1.3. Théorèmes de base

Le tableau 1 résume les postulats et théorèmes de base de notre algèbre. On présente en parallèle chaque version et sa version duale.

Tableau 1 : Théorèmes de l’algèbre de Boole
	Version ♠	Version ♥
Postulat 2	$x+0=x$	$x \cdot 1 = x$
Postulat 5	$x+x^{\prime} = 1$	$x \cdot x^{\prime} = 0$
Théorème 1	$x + x = x$	$x \cdot x = x$
Théorème 2	$x + 1 = 1$	$x \cdot 0 = 0$
Théorème 3	$(x^{\prime})^{\prime} = x$
Postulat 3	$x + y = y + x$	$xy = yx$
Théorème 4	$x + (y + z) = (x + y ) + z$	$x(yz) = (xy)z$
Postulat 4	$x(y+z) = xy + xz$	$x + yz = (x+y)(x+z)$
Théorème 5	$(x + y)^{\prime} = x^{\prime} y^{\prime}$	$(xy)^{\prime} = x^{\prime} + y^{\prime}$
Théorème 6	$x + xy = x$	$x(x+y) = x$

1.3.1. Autres fonctions logiques

Nous avons vu que les opérateurs logiques ET, OU et NON, qu’on peut aussi appeler fonctions logiques, sont à la base même de la définition de notre algèbre de Boole. Il est possible de concevoir d’autres fonctions logiques qui vont s’avérer utiles pour la formulation, la conception et la réalisation de systèmes logiques. Voici quelques-unes des plus souvent utilisées.

Fonction NON-ET (NAND)

La fonction NON-ET, souvent désignée NAND, est obtenue en complémentant la sortie d’une fonction ET : $(x \cdot y)^\prime$ .

Tableau 2 : Tableau de vérité de la fonction NON-ET

$x$ $y$ $(x \cdot y)^\prime$

0 0 1

0 1 1

1 0 1

1 1 0
Fonction NON-OU (NOR)

La fonction NON-OU, souvent désignée NOR, est obtenue en complémentant la sortie d’une fonction OU : $(x + y)^\prime$ .

Tableau 3 : Tableau de vérité de la fonction NON-OU

$x$ $y$ $(x + y)^\prime$

0 0 1

0 1 0

1 0 0

1 1 0
Fonction OU-exclusif (XOR)

La fonction OU-exclusif, souvent désignée XOR, est obtenue en évaluant $x \cdot y^\prime + x^\prime \cdot y$ . La sortie est 1 seulement si une seule des entrées est 1. On verra plus loin que cette fonction joue un rôle important dans la formulation d’un additionneur.

Tableau 4 : Tableau de vérité de la fonction OU-exclusif

$x$ $y$ $(x \cdot y^\prime + x^\prime \cdot y)$

0 0 0

0 1 1

1 0 1

1 1 0

1.3.2. Fonctions de plusieurs entrées

La plupart des fonctions logiques simples peuvent naturellement se formuler en fonction de plus de deux entrées. Par exemple, $a \cdot b \cdot c$ nous donne une fonction ET à trois entrées, et on peut facilement imaginer des fonctions ET ou des fonctions OU avec encore plus d’entrées.

1.3.3. Expressions et fonctions binaires

Une fonction binaire peut être décrite par une expression algébrique booléenne. Selon les valeurs des variables, la valeur de l’expression booléenne détermine la valeur de la fonction. Par exemple, $F_1$ est une fonction de trois entrées $a$ $b$ et $c$ définie par l’expression

$F_1 = a + b \cdot c^\prime$

La priorité des opération dans les expressions algébriques est (1) parenthèses, (2) NON, (3) ET, et (4) OU.

Il est possible de construire le tableau de vérité pour $F_1$ en évaluant la fonction pour les $2^3 = 8$ combinaisons d’entrées possibles, comme dans le tableau 5.

Tableau 5 : Fonction de trois variables
$a$	$b$	$c$	$F_1$
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

En général, pour une fonction à $n$ entrées, le tableau de vérité comportera $2^n$ lignes.

1.4. Théorèmes de DeMorgan

Le complément d’une fonction $F$ , $F^\prime$ , s’obtient en remplaçant tous les 0 par des 1 et tous les 1 par des 0 dans les valeurs de la fonction. Par exemple, en complémentant ainsi les valeurs dans le tableau de vérité, on effectue ce changement.

On peut aussi effectuer ce changement en appliquant les théorèmes de DeMorgan (Théorème 5 ♠ et ♥ du tableau 1) qui peuvent se généraliser à plus de deux variables.

Quiz de fin de chapitre

Licence

Symbole de License Creative Commons Attribution - Partage dans les mêmes conditions 4.0 International

Circuits logiques combinatoires et séquentiels Droit d'auteur © 2023 par Guy Bégin est sous licence License Creative Commons Attribution - Partage dans les mêmes conditions 4.0 International, sauf indication contraire.

Tableau 2 : Tableau de vérité de la fonction NON-ET
$x$	$y$	$(x \cdot y)^\prime$
0	0	1
0	1	1
1	0	1
1	1	0

Tableau 3 : Tableau de vérité de la fonction NON-OU
$x$	$y$	$(x + y)^\prime$
0	0	1
0	1	0
1	0	0
1	1	0

Tableau 4 : Tableau de vérité de la fonction OU-exclusif
$x$	$y$	$(x \cdot y^\prime + x^\prime \cdot y)$
0	0	0
0	1	1
1	0	1
1	1	0