͏ Éléments de logique

Une assertion est un énoncé qui peut être soit vrai soit faux. Les connecteurs logiques permettent de construire des assertions à partir d'une ou deux assertions P et Q,

non logique: ¬P,
et logique: P ∧ Q,
ou logique: P ∨ Q,
implication: P ⇒ Q,
équivalence: P ⇔ Q.

Si les assertions P et Q ne contiennent pas de variables, elles ne peuvent prendre que deux valeurs, à savoir: Vrai ou Faux. Voici ces valeurs présentées dans les tables de vérité:

P	Q	P ∧ Q	P ∨ Q	P ⇒ Q	P ⇔ Q	¬P
Vrai	Vrai	Vrai	Vrai	Vrai	Vrai	Faux
Vrai	Faux	Faux	Vrai	Faux	Faux	Faux
Faux	Vrai	Faux	Vrai	Vrai	Faux	Vrai
Faux	Faux	Faux	Faux	Vrai	Vrai	Vrai

À noter que lorsque P est faux, P ⇒ Q est une assertion vraie. Ces tables de vérité s'établissent également pour n'importe quelle combinaison d'assertions liées par des connecteurs.

Propriété

Deux assertions sont équivalentes si leurs tables de vérité coïncident.

Il se dit aussi que ces deux assertions sont tautologiquement équivalentes. Les identités suivantes s'obtiennent facilement ; soient trois assertions A, B et C:

A ≡ A ∧ A (∧ est idempotent),
A ≡ A ∨ A (∨ est idempotent),
(A ∧ B) ∧ C ≡ A ∧ (B ∧ C) (∧ est associatif),
(A ∨ B) ∨ C ≡ A ∨ (B ∨ C) (∨ est associatif),
¬(A ⇒ B) ≡ A ∧ ¬B,
A ⇒ B ≡ ¬B ⇒ ¬A (utile dans un raisonnement par contraposition).

Il en va de même pour les lois de Morgan:

A ⇒ B ≡ ¬A ∨ B,
A ⇔ B ≡ (A ⇒ B) ∧ (B ⇒ A),
¬(A ∨ B) ≡ ¬A ∧ ¬B,
¬(A ∧ B) ≡ ¬A ∨ ¬B.

Il est donc possible de se limiter aux connecteurs ¬ et ∧. Lorsqu'une assertion composée prend la valeur Vrai en toute circonstance, elle est qualifiée de tautologie (ou expression valide). Voici trois exemples:

A ∨ ¬A (tiers exclu),
¬(A ∨ ¬A) (non-contradiction),
[(A ⇒ B) ∧ (B ⇒ C)] ⇒ (A ⇒ C) (transitivité de l'implication).

Un prédicat est un énoncé contenant des variables. En donnant une valeur à chaque variable du prédicat, celui-ci devient une assertion prenant la valeur Vrai ou Faux. Un prédicat à deux variables est une relation binaire et à trois variables il devient une relation ternaire. Si la valeur des variables est connue seulement en partie, il demeure un prédicat qui ne dépend que des variables inconnues restantes.