TD 1 : Logique propositionnelle




Ce document est disponible à l'URL http://www.liafa.jussieu.fr/~sighirea/logver/td_lprop.html

Dans la traduction en HTML des symboles mathématiques, les correspondances suivantes ont été utilisées :

Symbol Sémantique
Î appartient à
Ï n'appartient pas à
 .  et logique
 +  ou logique
 xor  ou exclusif logique

1   Propriétés

Exercice 1 :
On appelle fonction caractéristique d'une partie A d'un ensemble E la fonction cA : E -> { 0, 1} définie par :
cA (e) = ì
í
î
1 si e Î A
0 si e ÏA
  1. Exprimer en termes de fonction caractéristique les opérations d'union, intersection, différence, différence symétrique, complémentation.
  2. Si E est un ensemble fini de taille n montrer que la fonction caractéristique d'une partie A de E peut être écrite comme un n-uplet de nombres 0 ou 1 ; en déduire un isomorphisme entre les algèbres de Boole P(E) et {0,1}n.

Exercice 2 :
Trouver un polynôme booléen pour la fonction f définie par :
x1 x2 x3 f(x1,x2,x3)
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0
Quelle est la table de vérité de la fonction duale ? Trouver un polynôme booléen pour la fonction duale.

Exercice 3 :
On définit x  nand  y = ¬ (xy). Montrer que toutes les opérations booléennes sont exprimables en fonction de nand.

2   Formes normale

Rappels :
Exercice 4 :
Mettre en forme normale disjonctive, conjonctive et Reed-Muller les expressions suivantes :
  (1) ¬ (p  .  ¬ (q  +  s))
  (2) ¬ (p  .  (q  +  s)
  (3) ¬ (p  +  (q  .  ¬ s))  .  s

3   Décomposition de Shannon

Soient x1, x2,...., xn un ensemble de variables booléennes et f une expression booléenne de ces variables (f : IBn -> IB).

Définition : La décomposition de Shannon d'une fonction f selon la variable xk est le couple (unique) de formules :
f
 
¬ xk
= f [faux /xk]    ,    f
 
xk
= f [vrai/xk]
On a f = (¬ xk  .  f¬ xk)  +  (xk  .  fxk).

Définition : L'arbre de Shannon pour un ordre fixé des variables x1, x2,...., xn est obtenu par la décomposition itérative de f selon les variables x1, x2,...., xn. L'arbre réduit de Shannon est obtenu par élimination des sommets dont les deux sous-arbres sont égaux.

Exercice 5 :
Ecrire l'arbre de Shannon pour la formule
f (x1, x2, x3, x4) = (x1  .  (x3  xor  x4))  +  (x2  .  (x3 <=> x4))
pour les ordres suivants des variables :

4   Graphes binaires de décision (BDD)

Définition : Un BDD est un graphe obtenu à partir de arbre réduit de Shannon par partage des sous-arbres identiques.

Exemple : Le BDD de la formule (x1  .  (x3  xor  x4))  +  (x2  .  (x3 <=> x4)) pour l'ordre x1 < x2 < x3 < x4 est :



Exercice 6 :
Ecrire le BDD de la formule ci-dessus pour l'ordre x3 < x4 < x1 < x2
Ce document a été traduit de LATEX par HEVEA.