Introduction aux mathématiques/Rudiments de logique

Assertions

Exemples :

• « $i^2=-1$ » est une assertion vraie ;
• « $2+2=5$ » est une assertion fausse ;
• « $x\ge 1$ » n’est pas une assertion.

Le but est de montrer que certaines assertions, des plus simples aux plus ardues, sont vraies ou fausses. Pour élaborer de nouvelles assertions à partir d'un petit jeu de base, qu'on appelle axiomes, on utilise [quasiment exclusivement non ?] les connecteurs logiques et les quantificateurs.

Connecteurs logiques

Ici $P$ et $Q$ désignent des assertions. On en construit de nouvelles grâce aux connecteurs logiques suivants. On présente le résultat de la nouvelle assertion, en fonction des valeurs de vérité de $P$ et $Q$ dans une table de vérité :

Négation

On note non P ou ¬P, la négation de $P$ :

P	non P (¬P)
Vrai	Faux
Faux	Vrai

Conjonction

L'assertion « P et Q » (aussi notée « P ∧ Q ») est vraie si et seulement si P et Q sont toutes deux vraies :

P	Q	P ∧ Q
Faux	Faux	Faux
Faux	Vrai	Faux
Vrai	Faux	Faux
Vrai	Vrai	Vrai

On appelle cette assertion la conjonction de P et de Q.

Disjonction

On appelle disjonction de P et Q l'assertion « P ou Q » (aussi notée « P ∨ Q ». Elle est vraie si et seulement si au moins l'une des deux assertions P et Q est vraie. Il s'agit d'un « ou » inclusif :

P	Q	P ∨ Q
Faux	Faux	Faux
Faux	Vrai	Vrai
Vrai	Faux	Vrai
Vrai	Vrai	Vrai

Implication

On appelle implication de Q par P l'assertion « $P\Rightarrow Q$ » qui n'est autre que « non P ou Q » :

P	Q	non P	$P\Rightarrow Q$
Vrai	Vrai	Faux	Vrai
Vrai	Faux	Faux	Faux
Faux	Vrai	Vrai	Vrai
Faux	Faux	Vrai	Vrai

Remarques :

• Si P et « $P\Rightarrow Q$ » sont vraies, alors Q est vrai. Par contre, en écrivant que « $P\Rightarrow Q$ » est vraie, on ne se prononce pas sur la valeur de vérité de P ni de Q.
• Si « $P\Rightarrow Q$ » est vraie, on dit que P est une condition suffisante de Q et que Q est une condition nécessaire de P.

Équivalence

On appelle équivalence de P et Q l'assertion, notée « $P\iff Q$ » — qui n'est autre que « ($P\Rightarrow Q)\text{et}(Q\Rightarrow P)$ ».

$P\iff Q$ est vraie si et seulement si P et Q ont même valeur de vérité. Dans ce cas on dit que P (resp : Q) est une condition nécessaire et suffisante de Q (resp : P) :

P	Q	$P\Rightarrow Q$	$Q\Rightarrow P$	$P\iff Q$
Vrai	Vrai	Vrai	Vrai	Vrai
Vrai	Faux	Faux	Vrai	Faux
Faux	Vrai	Vrai	Faux	Faux
Faux	Faux	Vrai	Vrai	Vrai

Quelques résultats usuels

Ici P, Q et R désignent des assertions quelconques. Les résultats suivants sont valables :

• $\text{non}(P\text{et}Q)\iff (\text{non}P\text{ou non}Q)$
• $\text{non}(P\text{ou}Q)\iff (\text{non}P\text{et non}Q)$
• $\text{non}(P\Rightarrow Q)\iff (P\text{et non}Q)$
• $(P\Rightarrow Q)\iff (\text{non}Q\Rightarrow \text{non}P)$ (c'est la contraposition ou modus tollens.)