Tables de vérité

Pour étudier l'équivalence entre deux expressions logiques on utilise souvent les tables de vérité. Une table de vérité permet d'établir la valeur de vérité qui prend une expression logique, et ceci pour toutes les valeurs possibles des symboles qui en font partie.

Pour construire une table de vérité on dessine une colonne pour chaque variable qui apparaît dans l'expression, et une ligne pour chaque valeur possible qu'on peut donner aux variables. La dernière colonne correspond à à l'expression qui nous intresse et à la valeur de vérité. Nous notons true par t, et false par f.

Table de vérité du and:

p	q	p and q
t	t	t
t	f	f
f	t	f
f	f	f

Table de vérité du or:

p	q	p or q
t	t	t
t	f	t
f	t	t
f	f	f

Pour établir l'équivalence entre deux expressions e₁ et e₂ on construit une table de vérité où figurent toutes les variables présentes dans les deux expressions, plus une colonne pour chacune des expressions e₁,e₂. Si pour toutes les lignes de la table les valeurs données à e₁ et e₂ sont à chaque fois les mêmes, alors, les deux expression sont équivalentes. En effet, cela veut dire que e₁, e₂ prennent la valeur vrai ou faux, exactement dans les mêmes cas.

Exemple: établissons l'équivalence suivante:

not(p or q) $\quad \equiv \quad$ not(p) and not(q)

p	q	not(p or q)	not(p) and not(q)
t	t	f	f
t	f	f	f
f	t	f	f
f	f	t	t

Chaque ligne dans cette table donne la même valeur aux deux expressions. En conclusion: elles sont équivalentes.

Quelques équivalences utiles:

1.

Anihilation

• p or true $\quad \equiv \quad$ true

• p and false $\quad \equiv \quad$ false
  

2.

Elément neutre

• p and true $\quad \equiv \quad$ p

• p or false $\quad \equiv \quad$ p
  

3.

Idempotence

• p or p $\quad \equiv \quad$ p
• p and p $\quad \equiv \quad$ p
• not( not(p)) $\quad \equiv \quad$ p
  

4.

Lois DeMorgan

• not(p or q) $\quad \equiv \quad$ not(p) and not(q)
• not(p and q) $\quad \equiv \quad$ not(p) or not(q)
  

5.

Simplification

• p or (p and q) $\quad \equiv \quad$ p
• p and (p or q) $\quad \equiv \quad$ p
  

6.

Elimination de négations

• p and ( not(p) or q) $\quad \equiv \quad$ p and q
• p or ( not(p) and q) $\quad \equiv \quad$ p or q
  

7.

Distribution

• p or (q and r) $\quad \equiv \quad$ (p or q) and (p or r)
• p and (q or r) $\quad \equiv \quad$ (p and q) or (p and r)
  

Exercices:

Utilisez les lois d'équivalence logique et/ou de factorisation, pour simplifier les conditionnelles et/ou les conditions suivantes. Indiquez à chaque fois la loi utilisée. Signalez des problèmes éventuels (p.e: des intructions jamais exécutées).

1.

if a or not(a) then B;
else C; 
end if;

2.

if a = true then p:=true; 
else p:= false;
end if;

3.

if a = false then p:=true; 
else p:= false;
end if;

4.

if x >= a or x < a then B;
else C; 
end if;

5.

if a and not(a) then B;
else C;
end if;

6.

if x >= a and x < a then B;
else C; 
end if;

7.

if a and not(a) then B; end if;

8.

if a or not(a) then B; end if;

9.

(a < b) or ((a < b) and ( c = d))

10.

(a < b) and ((a < b) and ( c = d))

11.

(a < b) or ((a $\geq$ b) and ( c = d))

12.

(a < b) and ((a $\geq$ b) or ( c = d))