Aller au contenu

1NSI : Architectures Matérielles - Fonctions Booléennes & Tables de Vérité⚓︎

Fonctions Booléennes & Tables de Vérité⚓︎

Définition : Les fonctions booléennes sont des fonctions qui prennent en entrée un ou plusieurs bits, et qui produisent un unique bit en résultat. Elles peuvent donc se représenter par une Table de vérité.

Une table de vérité d'une fonction booléenne avec \(n\) bits en entrée, aura besoin de \(2^n\) lignes (correspondant aux \(2^n\) combinaisons possibles sur les \(n\) bits en entrée).

Exemple: une fonction booléenne \(f\) avec 3 entrées \(x\), \(y\) et \(z\), sera entièrement définie par une table de vérité de \(2^3=8\) lignes. Chaque valeur \(f(x,y,z)\) étant ou bien un \(0\), ou bien un \(1\).

\(x\) \(y\) \(z\) \(f(x,y,z)\)
\(0\) \(0\) \(0\) \(f(0,0,0)\)
\(0\) \(0\) \(1\) \(f(0,0,1)\)
\(0\) \(1\) \(0\) \(f(0,1,0)\)
\(0\) \(1\) \(1\) \(f(0,1,1)\)
\(1\) \(0\) \(0\) \(f(1,0,0)\)
\(1\) \(0\) \(1\) \(f(1,0,1)\)
\(1\) \(1\) \(0\) \(f(1,1,0)\)
\(1\) \(1\) \(1\) \(f(1,1,1)\)

Par exemple, les portes logiques vues précédemment, peuvent être vues comme des fonctions booléennes élémentaires:

  • \(\neg (x)\) représente la fonction booléenne associée à la porte NOT
  • \(\land (x,y)\) la fonction booléenne associée à la porte AND
  • \(\lor (x,y)\) la fonction booléenne associée à la porte OR

Propriété : Les 3 fonctions booléennes \(\neg (x)\), \(\land (x,y)\) et \(\lor (x,y)\) forment une base complète pour la construction des autres fonctions booléennes, ce qui veut dire que toute fonction booléenne peut être définie à l'aide d'une combinaison de ces 3 fonctions booléennes.

Opérateurs Booléens⚓︎

Pour simplifier les notations, au lieu de parler de fonctions booléennes, on préfère plutôt utiliser des opérateurs booléens (unaires ou binaires) :

  • \(\overline {x}\) ou \(\neg x\) est la négation de \(x\)
  • \(x.y\) ou \(x\land y\) est la conjonction de \(x\) et \(y\): comprendre "\(x\) ET \(y\)"
  • \(x+y\) ou \(x\lor y\) est la disjonction de \(x\) et \(y\): comprendre "\(x\) OU \(y\)"

Expressions Booléennes⚓︎

Définition : La composition de plusieurs opérateurs booléens est appelée une Expression Booléenne

Exemple: \(\overline{(x+y)}.z\) est une expression booléenne.

Propriété : Toute fonction booléenne peut être définie par une Expression Booléenne, ou Formule Booléenne, de ses entrées.

Exemple: L'expression booléenne \(f(x,y,z)=(x. \overline{y}) \oplus (\overline{x} + z)\) définit une fonction booléenne \(f\) des entrées \(x,y,z\).

Utilité: En électronique,

  • les Tables de vérité permettent de représenter des Expressions Booléennes (et réciproquement), i.e. qu'une table de vérité peut être convertie en expression booléenne (et réciproquement)
  • les Expressions Booléennes permettent de réprésenter des circuits.

Mais il faut d'abord apprendre à simplifier les expressions booléennes, grâce aux:

Lois de composition⚓︎

Propriétés :

Les lois de composition sont des règles logiques qui permettent de simplifier des expressions algébriques:

and, ., \(\wedge\) or, +, \(\vee\)
Involutif \(\overline {\overline{A}} = A\)
\(not\) \(not A = A\)
Neutre \(1.A=A\)
\(1\) \(and\) \(A=A\)		 \(0+A=A\)
\(0\) \(or\) \(A\) \(=A\)
Absorbant \(0.A=0\)
\(0\) \(and\) \(A\) \(=0\)		 \(1+A=1\)
\(1\) \(or\) \(A\) \(=1\)
Idempotence \(A.A=A\)
\(A\) \(and\) \(A\) \(=A\)		 \(A+A=A\)
\(A\) \(or\) \(A\) \(=A\)
Complément \(A.\overline{A}=0\)
\(A\) \(and\) \(\overline{A}\) \(=0\)		 \(A+\overline{A}=1\)
\(A\) \(or\) \(\overline{A}\) \(=1\)
Commutativité \(A.B=B.A\)
\(A\) \(and\) \(B\) \(=B\) \(and\) \(A\)		 \(A+B=B+A\)
\(A\) \(or\) \(B\) \(=B\) \(or\) \(A\)
Associativité \(A.(B.C)=(A.B).C\)
\(A\) \(and\) \((B\) \(and\) \(C)\) \(=(A\) \(and\) \(B)\) \(and\) \(C\)		 \(A+(B+C)=(A+B)+C\)
\(A\) \(or\) \((B\) \(or\) \(C)\) \(=(A\) \(or\) \(B)\) \(or\) \(C\)
Distributivité \(A.(B+C)=A.B+A.C\)
\(A\) \(and\) \((B\) \(or\) \(C)\) \(=(A\) \(and\) \(B)\) \(or\) \((A\) \(and\) \(C)\)		 \(A+(B.C)=(A+B).(A+C)\)
\(A\) \(or\) \((B\) \(and\) \(C)\) \(=(A\) \(or\) \(B)\) \(and\) \((A\) \(or\) \(C)\)
Lois de Morgan \(\overline{A.B}=\overline{A}+\overline{B}\)
\(not (A\) \(and\) \(B)\) \(=not\) \(A\) \(or\) \(not\) \(B\)
\(=(not\) \(A)\) \(or\) \((not\) \(B)\)		 \(\overline{A+B}=\overline{A}.\overline{B}\)
\(not (A\) \(or\) \(B)\) \(=not\) \(A\) \(and\) \(not\) \(B\)
\(=(not\) \(A)\) \(and\) \((not\) \(B)\)

Priorités des Opérateurs Booléens:

  • le \(not\) est prioritaire sur le \(and\) et sur le \(or\) (cf dernière ligne du tableau précédent)
  • le \(and\) est prioritaire sur le \(or\)
  • Résumé: \(not\) \(>>\) \(and\) \(>>\) \(or\)
  • Précaution : En cas de doute -> surparenthéser !

Conversions: Tables de Vérité \(\Leftrightarrow\) Expressions Booléennes \(\Leftrightarrow\) Circuits⚓︎

  • Expression Booléenne \(\Rightarrow\) Table de Vérité: Soit \(f(x,y,z)=(x.\overline{y})+z\) une fonction booléenne. Construire la Table de vérité de cette Expression Booléenne :
\(x\) \(y\) \(z\) \(\overline{y}\) \(x. \overline{y}\) \(f(x,y,z)=(x.\overline{y})+z\)
\(0\) \(0\) \(0\) \(1\) \(0\) \(0\)
\(0\) \(0\) \(1\) \(1\) \(0\) \(1\)
\(0\) \(1\) \(0\) \(0\) \(0\) \(0\)
\(0\) \(1\) \(1\) \(0\) \(0\) \(1\)
\(1\) \(0\) \(0\) \(1\) \(1\) \(1\)
\(1\) \(0\) \(1\) \(1\) \(1\) \(1\)
\(1\) \(1\) \(0\) \(0\) \(0\) \(0\)
\(1\) \(1\) \(1\) \(0\) \(0\) \(1\)
  • Table de Vérité: \(\Rightarrow\) Expression Booléenne:
  • A chaque combinaison de valeurs qui rend la fonction égale à 1, on associe le produit des variables en ajoutant la barre de la négation sur les variables dont la valeur est 0.
  • Ensuite, on fait la somme des produits déterminés précédemment.
  • Enfin, on simplifie la formule
\(x\) \(y\) \(z\) \(f(x,y,z)\)
\(0\) \(0\) \(0\) \(0\)
\(0\) \(0\) \(1\) \(0\)
\(0\) \(1\) \(0\) \(0\)
\(0\) \(1\) \(1\) \(1\) \(\overline x.y.z\)
\(1\) \(0\) \(0\) \(0\)
\(1\) \(0\) \(1\) \(1\) \(x.\overline y.z\)
\(1\) \(1\) \(0\) \(1\) \(x.y.\overline z\)
\(1\) \(1\) \(1\) \(1\) \(x.y.z\)

On trouve \(f(x,y,z)=\overline x.y.z + x.\overline y.z + x.y.\overline z + x.y.z\)