Vous êtes sur une version archivée de lyceum.fr de l'année 2023/2024. Revenir au présent.

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 & ! Q P \& !Q

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

    • ! P | ! Q !P | !Q

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

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

    • 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 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:

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

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 & R 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)