Eléments de logique propositionnelle

Considérons la conditionnelle suivante:

if a = b  then     A;               (1)
elsif a /= b then  B;
else               C;
end if;

nous aurions pu l'écrire plus simplement par:

if a = b  then  A;                  (2)
else            B;
end if;

Les instructions (1) et (2) sont équivalentes. En effet,

• si a = b est vrai, alors aussi bien (1) que (2) exécutent A.

• si a = b est faux, alors a /= b est forcément vrai, et (1) et (2) exécutent B.

• C est exécuté dans (1), seulement s'il arrive qu'aucune des deux conditions précédentes ne soit vrai. Or, soit a =b est vrai, soit a /=b est vrai. Donc, C n'est jamais executée. Par ailleurs, (2) n'exécute jamais C non plus.

• En conclusion, indépendamment des valeurs de a,b, (1) et (2) se comportent de la même manière: A,B,C sont exécutées ou pas exactement dans les mêmes cas. Nous pouvons conlure à l'équivalence de (1) et (2).

Considérons maintenant l'instruction suivante, avec une condition un peu plus complexe:

if a < b or (a >= b and c = d) then ...    (1)
end if;

nous aurions pu l'écrire plus simplement par:

if a < b or  c = d then ...                (2)
end if;

comment arrivons-nous à cette conclusion?

• Supposons a < b. Alors, les conditions dans (1) et (2) sont toutes les deux vraies, et pour ces deux instructions on exécute la branche then.

• Supposons a < b faux. Alors, on prend la branche then pour les deux instructions seulement si la deuxime partie du or est vrai. Dans (1) cela revient à demander que
  

  a >= b and c = d
  

  soit vrai. Comme nous avons supposé a < b faux, alors a >= b est forcément vrai. Il s'en suit que dans (1) on exécute la branche then exactement quand c=d. Pour l'instruction (2), il est clair que l'on exécute aussi la branche then exactement dans ce cas (puisque nous venos de montrer que a >= b est aussi vrai).

  Ainsi, indépendamment des valeurs de a,b,c,d, (1) et (2) exécutent la branche then ou ne l'exécutent pas exactement dans les mêmes conditions. Nous pouvons conclure que (1) et (2) sont des instructions équivalentes: elles se comportent exactement de la même manière.

Raissonnement logique

La logique propositionnelle est une modélisation mathématique du raisonnement. Le raisonnement dans notre premier exemple ne dépend pas du sens que l'on peut donner à a = b ou à a /= b. Tout ce qu'importe est que ces deux expressions sont complémentaires, c.a.d., l'une est vraie lorsque l'autre est fausse et vice-versa. Nous pouvons donc remplacer a = b par p et a /= b par not(p) et obtenir pour (1):

if p  then         A;               (1')
elsif not(p) then  B;
else               C;
end if;

qui du coup semble plus facilement simplifiable. Les symboles p et q sont appelées variables propositionnelles ou logiques, dans ce sens où elles auront l'une des deux valeurs true ou false.

Expressions logiques

Une expression logique (ou booléenne) est formée de variables logiques, des valeurs de vérité et des connecteurs usuels and , or , not auxquels nous ajoutons le connecteur $\equiv$ d'équivalence logique.

Si dans notre deuxieme exemple nous remplaçons a < b par p, a >= b par not(p) et c = d par q, la condition dans (1) devient:

p or ( not(p) and q)

Nous avons déjà montre dans cet exemple, qu'indépendamment des valeurs de p,q, l'équivalence suivante est toujours vraie:

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

Dans la partie suivante, nous donnons une liste d'équivalences logiques qui pourront servir à mieux comprendre et formuler les conditions dans nos programmes.