INSA de Rouen  Département STPI  Section SIB  M2 2013-2014

Vocabulaire du raisonnement logique

1 Assertions et tables de vérité
1.1 Structure du cours de mathématiques

On dispose en mathématiques d' axiomes : ce sont les règles de base du maniement des objets ma-
thématiques. A partir des axiomes, on propose des assertions (ou propositions ) : ce terme désigne
toute formulation mathématique. La valeur de vérité d'une assertion est  vrai  ou  faux  − mais pas
les deux. Une assertion est dite vraie si elle est conforme aux axiomes. Deux assertions sont équivalentes
ou identiques si elles ont les mêmes valeurs de vérité.
Exemple :
 π > 3 est une assertion vraie.
 7 + 4 = 12 est une assertion fausse.

Le but du cours de mathématiques est de proposer des assertions vraies, qui sont appelées, par ordre
d'importance : théorèmes , propositions , propriétés . La vérité de ces assertions est le résultat des
axiomes et règles ou assertions déjà déduits des axiomes. La vérité de toute nouvelle assertion doit être
démontrée !

Remarque :
 Dans le cours de mathématiques, les nouveaux objets ou qualicatifs sont introduits par des déni-
tions .
 Parfois, on formule aussi des lemmes : ce sont de petits résultats ou assertions intermédiaires, sur
lesquels on s'appuie pour prouver des résultats plus importants (théorèmes ou propositions).

1.2 Connecteurs logiques

On appelle connecteur logique tout procédé permettant de dénir une nouvelle assertion à partir
d'une ou plusieurs assertions : par exemple et, ou, si... alors. Les valeurs de vérité vraie (V) ou faux
(F) dénissant ces nouvelles assertions peuvent être représentées par un tableau appelé table de vérité .
Dans la suite, on considère trois assertions P, Q et R.

1.2.1 Négation
Dénition 1 L'assertion  non P est vraie seulement si P est fausse :

P non P
V F
F V

Proposition 2 L'assertion non(non P ) est équivalente à P.

1.2.2 Conjonction et disjonction

Dénition 3  L'assertion  P et Q est vraie lorque P et Q sont vraies toutes les deux, et fausse
sinon.
 L'assertion  P ou Q est vraie si l'une au moins des assertions P ou Q est vraie, et fausse dans le
seul cas où P et Q sont toutes les deux fausses.

P Q P et Q P ou Q
V V V V
V F F V
F V F V
F F F F

1
INSA de Rouen  Département STPI  Section SIB  M2 2013-2014

Attention ! En mathématiques, le ou est dit inclusif : il a la signication l'un ou l'autre ou les
deux. Par opposition, dans le langage courant, le ou est souvent exclusif (l'un ou l'autre, mais pas les
deux).

Proposition 4
 L'assertion non(P ou Q) est équivalente à l'assertion (non P ) et (non Q).
 L'assertion non(P et Q) est équivalente à l'assertion (non P ) ou (non Q).
Exemple :  x > 3 et y < 2 a pour négation  x ≤3 ou y ≥ 2.

Proposition 5
 L'assertion  P et (Q ou R) est équivalente à l'assertion (P et Q) ou (P et R).
 L'assertion  P ou (Q et R) est équivalente à l'assertion (P ou Q) et (P ou R).

1.2.3 Implication et équivalence

Dénition 6  L'assertion  P ⇒ Q se lit  P implique Q ou  Si P alors Q. Elle est fausse dans
le seul cas où P est vraie et Q est fausse. Elle est vraie dans tous les autres cas.
 L'assertion  P ⇔ Q se lit  P si et seulement si Q ou  P et Q sont équivalentes. Elle est
vraie si P et Q ont les mêmes valeurs de vérité, fausse sinon.

P Q P ⇒ Q P ⇔ Q
V V V V
V F F F
F V V F
F F V V

Attention ! Armer que  P ⇒ Q est vraie ne signie ni que P est vraie, ni que Q est vraie. Par
exemple, il est vrai que  3 > 4 ⇒ 2 < −1 et pourtant, ni  3 > 4 ni  2 < −1 ne sont des assertions
vraies. Précisément,  P ⇒ Q est toujours vraie si P est fausse.

Remarque :
 On dit que Q est une condition nécessaire pour que P soit vraie si, lorsque P est vraie, Q l'est
aussi forcément (nécessairement) − autrement dit si l'implication P ⇒ Q est vraie.
 On dit que Q est une condition susante pour que P soit vraie s'il sut que Q soit vraie pour
que P le soit aussi − autrement dit si l'implication Q ⇒ P est vraie.

Exemple : Soit f :R→R une fonction. On note P :  f est dérivable et Q :  f est continue. Alors, P
est une condition susante (mais non nécessaire) pour que Q soit vraie. Et Q est une condition nécessaire
mais non susante pour que P soit vraie.

Proposition 7
 L'assertion  P ⇔ Q est équivalente à l'assertion (P ⇒ Q) et (Q ⇒ P ).
 L'assertion  P ⇒ Q est équivalente à l'assertion (non Q) ⇒ (non P ).
 L'assertion non(P ⇒ Q) est équivalente à l'assertion  P et (non Q).

L'assertion (non Q) ⇒ (non P ) est appelée la contraposée de l'assertion  P ⇒ Q. Elle est parfois
plus facile à démontrer.

Exemple : Soit n un entier naturel. Pour montrer que

n2 pair ⇒ n pair,

il est plus facile de montrer la contraposée

n impair ⇒ n2 impair.

Supposons en eet que n est un entier naturel impair. Par dénition, il existe k tel que n = 2k + 1. Alors,
n2 = (2k + 1)2 = 2(2k 2 + 2k) + 1. Ainsi, n2 = 2k 0 + 1 avec k 0 = 2k 2 + 2k . Cela montre que n2 est impair.

2
INSA de Rouen  Département STPI  Section SIB  M2 2013-2014

2 Quanticateurs
Le cours de mathématiques fait aussi appel à des quanticateurs . Nous ne dénirons pas ici cette
notion de manière rigoureuse, mais nous considérerons qu'un quanticateur est un symbole. Les deux
principaux sont :
 Quanticateur universel ∀ : pour tout, quel que soit.
 Quanticateur existentiel ∃ : il existe (au moins un...).
Ils permettent d'écrire de façon condensée certaines assertions (voir le cours de M1).

Exemple :
 L'assertion ∀n ∈ N, n ≥ 3 signie que tous les entiers naturels vérient la propriété être supérieur
à 3. Elle est bien évidemment fausse.
 L'assertion ∃n ∈ N, n ≥ 3 signie qu'il existe (au moins) un entier naturel n supérieur à 3. Elle est
donc vraie.

Proposition 8 On considère un ensemble E et P une propriété. On note P(x) le fait que l'élément x
de E vérie la propriété P.
 L'assertion  ∀x ∈ E , P(x) a pour négation  ∃x ∈ E, (non P(x)).
 L'assertion  ∃x ∈ E , P(x) a pour négation  ∀x ∈ E, (non P(x)).

Pour obtenir la négation d'une assertion comportant des quanticateurs, on remplace tous les ∀ par
des ∃, tous les ∃ par des ∀, et la dernière assertion par sa négation.

Attention ! La position (ou ordre) des quanticateurs est cruciale pour le sens d'une assertion.
 on ne peut pas généralement, permuter un quanticateur existentiel ∃ et un quanticateur uni-
versel ∀. On obtient généralement deux assertions qui n'ont pas la même signication. Par exemple,
considérons

∃n ∈ N, ∀m ∈ N, m ≤ n, (1)

∀m ∈ N, ∃n ∈ N, m ≤ n, (2)

La proposition ∀m ∈ N, m ≤ n signie que n est plus grand que tous les entiers. L'assertion (1) veut
donc dire qu'il existe un entier plus grand que tous les autres. Ce qui est évidemment faux.
La proposition ∃n ∈ N, m ≤ n veut dire qu'étant donné un entier p, on peut trouver un entier n
supérieur à m. L'assertion (2) signie donc que pour chaque entier on peut trouver un entier plus
grand, ce qui est vrai.
 On peut toujours permuter les quanticateurs universels ∀ ENTRE EUX et les quanticateurs
existentiels ∃ ENTRE EUX. Par exemple, les deux assertions suivantes sont équivalentes :

∀x, ∀y, P(x, y) et ∀y, ∀x, P(x, y).

Ces deux assertions ont aussi le même sens que :

∀(x, y), P(x, y).

De la même façon, on a équivalence entre

∃x, ∃y, P(x, y) et ∃y, ∃x, P(x, y).

Ces deux assertions ont aussi le même sens que :

∃(x, y), P(x, y).

Enn, un dernier symbole peut-être utilisé, c'est le pseudo-quanticateur ∃! signiant il existe un
unique.

√
Exemple : L'assertion ∃!x ∈ R+ , x2 = 2 est vraie (le réel x en question est x= 2).