Exercices

Chapitre 5: Les booléens

1 Construire des tables de vérité

1. Produisez les tables de vérité pour les opérations suivantes:

   • NAND : $P \text{ NAND } Q = !(P \& Q)$
   • NOR : $P \text{ NOR } Q = !(P | Q)$
   • XOR : $P \text{ XOR } Q = (P \& !Q) | (!P \& Q)$

2. Produire des tables de vérité pour :

   • $P \& !Q$

   • $!P \& !Q$

   • $!P | !Q$

   • $P \& Q \& R$

   • $!P \& !Q \& !R$

   • $P \& Q \& R | P \& !Q \& R$

2 Expressions équivalentes

Savoir-faire: Utiliser une table de vérité pour montrer que deux expressions logiques sont équivalentes

• Montrer que:

  $$P | ( !P \& Q)=P | Q$$

• Utiliser une table de vérité pour démontrer la propriété d’absorption de l’algèbre de Boole:

  $$P | P \& Q = P$$

• Montrer que:

  $$P | Q \& R = (P | Q) \& (P | R)$$

3 Simplifications d’expressions booléennes

Utilisez les lois de l’algèbre de Boole (ne les apprenez pas!) pour simplifier ces expressions.

Astuce

Utiliser le $\times$ pour le «ET» et le $+$ pour le «OU» pour pouvoir utiliser les règles habituelles de développement et de factorisant de l’algèbre non booléen.

1. Simplifier l’expression:

   $$(P | Q)\&(P | !Q)$$

   Vérifier votre résultat avec une table de vérité.

2. Démontrer l’expression de XOR utilisée dans l’exercice 1: $P \text{ XOR } Q = (P \& !Q)|(!P \&Q)$:

   Pour cela commencer par remarquer que:

   $$\begin{aligned} 0\ \text{XOR}\ Q\ &=\ Q \\ 1\ \text{XOR}\ Q\ &=\ !Q \end{aligned}$$

   Vérifier votre résultat avec une table de vérité.

4 Recherche d’expressions équivalentes (Plus dur)

Exprimer sous forme simplifiée les expressions suivantes:

• $(P \& Q \& R) | (P \& Q \& S)$

• $(!P | Q) \& (P | Q | S) \& !S$

• $P \& !Q \& !R | P \& !Q \& R | P \& Q \& R$

Vous pouvez vérifier vos résultats en Python en utilisant la bibliothèque sympy qui propose la fonction simplify_logic(Attention la syntaxe utilisée est: ET: &, OU: | et NON:~`).

from sympy import symbols
from sympy.logic import simplify_logic

P, Q, R, S, T = symbols('P Q R S T')

simplify_logic((~P|Q)&(P|Q|S)&~S) # renvoie Q & !S

La fonction propose deux modes de simplifications:

• Produit(ET) de sommes(OU): simplify_logic(expr, 'cnf')
• Somme(OU) de produit(ET): simplify_logic(expr, 'dnf')

expr = "P&!Q&!R|P&!Q&R|P&Q&R"
simplify_logic(expr, 'cnf')   # renvoie P & (R | !Q)
simplify_logic(expr, 'dnf')   # renvoie (P & R) | (P & !Q)