05 Exos Logique booléenne

Exercice 1 - Fonctions NAND, NOR, XOR et XNOR⚓︎

Écrire les tables de vérité de chacune des fonctions suivantes.

AND : ET ;
NAND : NON-ET \(~~~~~~\)(Not AND) ;
OR : OU ;
NOR : NON-OU \(~~~~~~\)(Not OR) ;
XOR : OU Exclusif \(~~~~~~\)(Exclusive OR) ;
XNOR : NON-OU Exclusif \(~~~~~~\)(Exclusive NOR).

Exercice 2⚓︎

Construire la table de vérité de l’expression non (non(x) ou non(y)).
On prendra une colonne pour \(x\), une pour \(y\), une pour non(x), une pour non(y), une pour (non(x) ou non(y)) et une dernière pour l’expression complète.
Quelle fonction reconnaît-on ?
En déduire que toutes les fonctions booléennes peuvent s’exprimer à l’aide de deux fonctions, que l’on précisera.

Exercice 3⚓︎

Montrer (à l’aide d’une table de vérité similaire à celle de l’exercice précédent) que x ou y = non (non(x) et non(y)).

En déduire que toutes les fonctions booléennes peuvent s’exprimer avec les fonctions non et et.

Exercice 4⚓︎

Montrer que non(x ou y) = non(x) et non(y) puis que non(x et y) = non(x) ou non(y).

Exercice 5⚓︎

Compléter la table de vérité de la porte logique suivante puis donner son expression booléenne.

\(A\)	\(B\)	\(\overline{A}\)	\(\overline{B}\)	Porte 1	Porte 2	Sortie
0	0
0	1
1	0
1	1

Exercice 6 - Multiplexeur⚓︎

On définit la fonction multiplexeur, notée mux, de \(B^3\) dans \(B\) par :
\(mux(A,y,z) = (non(A)\text{ } et \text{ } y)\text{ } ou\text{ } (A\text{ } et\text{ } z)\).
Il y a 3 entrées \(A\), \(y\) et \(z\), et une seule sortie.
Compléter la table suivante.

A	y	z
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

A quoi sert le multiplexeur ?

Exercice 7⚓︎

La fonction de Sheffer exprime l’incompatibilité de deux valeurs booléennes. Elle est définie par S(x, y) = non(x et y).
Montrer que S(x,x) = non(x) puis que S(S(x,x),S(y,y)) = x ou y.
En déduire que toutes les fonctions booléennes peuvent s’exprimer avec la fonction de Sheffer uniquement. Toute fonction booléenne peut donc être exprimée à l’aide de la seule fonction NAND (non-et). Donc, tout circuit logique pourrait être constitué de seules portes NAND.

Exercice 8⚓︎

Med est content si Bob et Jon sont tous les deux là, mais sans Rut, ou si Rut est là soit avec Bob, soit avec Jon. Construire une table avec en entrée la présence de Rut, Bob et Jon et en sortie le booléen qui vaut 1 si Med est content. Exprimer le choix de Med par une phrase plus simple.

Exercice 9 - Simplification d’expressions logiques⚓︎

Simplifier les équations logiques ci-dessous en utilisant l’algèbre de Boole.

\(A=a+a\cdot b\)
\(B=a\cdot(a+b)\)
\(C=a+\overline{a}\cdot b\)
\(D=(a+b)\cdot(a+\overline{b})\)
\(E=(a+b)\cdot(a+c)\)
\(F=(a+b)\cdot(\overline{a}+c)\)
\(G=(\overline{a}+\overline{b}) \cdot (\overline{a}+b) \cdot (a+\overline{b})\)
\(H=(a \cdot b)+(\overline{a} \cdot b)+(a \cdot \overline{b})\)

Pour les plus rapides :⚓︎

Exercice 10⚓︎

Sur la planète CSI vivent les Profs (qui disent toujours la vérité) et les Élèves (qui mentent toujours). Vous croisez deux personnes A et B sur cette planète. A affirme : « Au moins l’un de nous deux est un élève ». Dire ce que sont A et B.

Exercice 11 : pour s'amuser un peu⚓︎

Trois hommes sont l’un derrière l’autre.
Chacun porte un chapeau sur la tête tiré au hasard parmi 3 chapeaux noirs et 2 chapeaux blancs.
Ils ne savent pas eux-même quel chapeau ils ont sur la tête. L’homme C voit les deux autres, l’homme B ne voit que l’homme A, et l’homme A ne voit personne.

On demande à l’homme C s’il connait la couleur de son chapeau. Celui-ci répond que non.
On pose la même question à l’homme B qui lui non plus dit ne pas savoir la couleur de son chapeau.
Même question pour l’homme A qui lui sait quelle est la couleur de son chapeau.

Quelle est la couleur du chapeau de A ?