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 NAND Q=!(P&Q)P \text{ NAND } Q = !(P \& Q)
    • NOR : P NOR Q=!(P|Q)P \text{ NOR } Q = !(P | Q)
    • XOR : P XOR Q=(P&!Q)|(!P&Q)P \text{ XOR } Q = (P \& !Q) | (!P \& Q)
  2. Produire des tables de vérité pour :

    • P&!QP \& !Q

    • !P&!Q!P \& !Q

    • !P|!Q!P | !Q

    • P&Q&RP \& Q \& R

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

    • P&Q&R|P&!Q&RP \& 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 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 P | P \& Q = P

  • Montrer que:

    P|Q&R=(P|Q)&(P|R) 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) (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 XOR Q=(P&!Q)|(!P&Q)P \text{ XOR } Q = (P \& !Q)|(!P \&Q):

    Pour cela commencer par remarquer que:

    0XORQ=Q1XORQ=!Q \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 \& R) | (P \& Q \& S)

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

  • P&!Q&!R|P&!Q&R|P&Q&RP \& !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)