Exercices

Chapitre 5: Les booléens

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

    • P&!QP \& !Q
    • !P&!Q!P \& !Q
    • !P!Q!P \lVert !Q
    • P&Q&RP \& Q \& R
    • !P&!Q&!R!P \& !Q \& !R
    • P&Q&RP&!Q&RP \& Q \& R \lVert P \& !Q \& R

Expressions équivalentes

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

  • Montrer que:
P(!P&Q)=PQP \lVert ( !P \& Q)=P \lVert Q
  • Utiliser une table de vérité pour démontrer la propriété d’absorption de l’algèbre de Boole:
PP&Q=PP \lVert P \& Q = P
  • Montrer que:
PQ&R=(PQ)&(PR)P \lVert Q \& R = (P \lVert Q) \& (P \lVert R)

Simplifications d'expressions booléennes

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

  1. Simplifier l'expression:

    (PQ)&(P!Q)(P \lVert Q)\&(P \lVert !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: PXORQ=(P&!Q)(!P&Q)P XOR Q = (P \& !Q)\lVert(!P \&Q):

    Pour cela commencer par remarquer que:

    0 XOR Q = Q1 XOR Q = !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é.

Recherche d'expressions équivalentes (Plus dur)

Exprimer sous forme simplifiée les expressions suivantes:

  • P&Q&(RS)P \& Q \& (R \lVert S)
  • (PQ)&(RST)(P \lVert Q) \& (R \lVert S \lVert T)
  • (!PQ)&(PQS)&!S(!P \lVert Q) \& (P \lVert Q \lVert S) \& !S
  • P&!Q&!RP&!Q&RP&Q&RP \& !Q \& !R \lVert P \& !Q \& R \lVert P \& Q \& R
  • !P&R&!(!P&Q&S)!P&Q&!R&!SP&!Q&R!P \& R \& !( !P \& Q \& S) \lVert !P \& Q \& !R \& !S \lVert P \& !Q \& R

Vous pouvez vérifier vos résultats en Python en utilisant la bibiothè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)