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.
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.
| 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$$ |
| Theorè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$$ |
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.
La fonction NON-ET, souvent désignée NAND est obtenue en complémentant la sortie d’une fonction ET: \((x \cdot y)^\prime\).
| $$x$$ | $$y$$ | $$(x \cdot y)^\prime$$ | |
|---|---|---|---|
| 0 | 0 | 1 | |
| 0 | 1 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 0 |
La fonction NON-OU, souvent désignée NOR est obtenue en complémentant la sortie d’une fonction OU: \((x + y)^\prime\).
| $$x$$ | $$y$$ | $$(x + y)^\prime$$ | |
|---|---|---|---|
| 0 | 0 | 1 | |
| 0 | 1 | 0 | |
| 1 | 0 | 0 | |
| 1 | 1 | 0 |
La fonction OU-exclusif, souvent désignée XOR, est obtenue par \(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.
| $$x$$ | $$y$$ | $$(x \cdot y^\prime + x^\prime \cdot y)$$ | |
|---|---|---|---|
| 0 | 0 | 0 | |
| 0 | 1 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 0 |
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.
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, (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.
| $$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.
Le complément d’une fonction \(F\) est \(F^\prime\) et 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 dans Théorèmes de base qui peuvent se généraliser à plus de deux variables.