Résumé général - Logique mathématique

1 Propositions et Quantificateurs

Proposition

Énoncé mathématique qui a un sens, pouvant être vrai (V ou 1) ou faux (F ou 0).

Exemple : P = « 2 est un nombre pair » (Vraie)

Fonction propositionnelle

Énoncé contenant une ou plusieurs variables. Elle devient une proposition lorsqu'on remplace les variables par des valeurs.

Exemple : A(x) = « x² = 4 » → A(2) = Vraie, A(3) = Fausse

Quantificateurs

∀ = Quantificateur universel : « pour tout » ou « quel que soit »
∃ = Quantificateur existentiel : « il existe »
∃! = Quantificateur existentiel unique : « il existe un unique »

$\neg(\forall x \in E,\ P(x)) \iff \exists x \in E,\ \neg P(x)$
$\neg(\exists x \in E,\ P(x)) \iff \forall x \in E,\ \neg P(x)$

                    Important
                    L'ordre des quantificateurs identiques (∀∀ ou ∃∃) ne change pas le sens.
L'ordre des quantificateurs différents (∀∃ ou ∃∀) change le sens.

                

2 Opérations logiques

Négation ($\overline{P}$ ou ¬P)

Inverse la valeur de vérité de P.

$P$	$\overline{P}$
V	F
F	V

Conjonction ($P \land Q$) : « P et Q »

Vraie seulement si P et Q sont vraies.

$P$	$Q$	$P \land Q$
V	V	V
V	F	F
F	V	F
F	F	F

Disjonction ($P \lor Q$) : « P ou Q »

Fausse seulement si P et Q sont fausses.

$P$	$Q$	$P \lor Q$
V	V	V
V	F	V
F	V	V
F	F	F

Implication ($P \Rightarrow Q$) : « P implique Q »

Équivaut à $\overline{P} \lor Q$. Fausse seulement si P est vraie et Q est fausse.

$P$	$Q$	$P \Rightarrow Q$
V	V	V
V	F	F
F	V	V
F	F	V

Contraposée : $P \Rightarrow Q \iff \overline{Q} \Rightarrow \overline{P}$

Équivalence ($P \Leftrightarrow Q$) : « P équivaut à Q »

Équivaut à $(P \Rightarrow Q) \land (Q \Rightarrow P)$. Vraie si P et Q ont la même valeur de vérité.

$P$	$Q$	$P \Leftrightarrow Q$
V	V	V
V	F	F
F	V	F
F	F	V

3 Lois logiques

Lois de Morgan
                        $\overline{P \land Q} = \overline{P} \lor \overline{Q}$
                        
                        $\overline{P \lor Q} = \overline{P} \land \overline{Q}$

Distributivité
                        $P \land (Q \lor R) = (P \land Q) \lor (P \land R)$
                        
                        $P \lor (Q \land R) = (P \lor Q) \land (P \lor R)$

                    Autres lois
                    Double négation : $\overline{\overline{P}} = P$
Contraposée : $P \Rightarrow Q \iff \overline{Q} \Rightarrow \overline{P}$
Transitivité : $[(P \Rightarrow Q) \land (Q \Rightarrow R)] \Rightarrow (P \Rightarrow R)$
Commutativité : $P \land Q = Q \land P$ et $P \lor Q = Q \lor P$
Associativité : $(P \land Q) \land R = P \land (Q \land R)$ et $(P \lor Q) \lor R = P \lor (Q \lor R)$
Idempotence : $P \land P = P$ et $P \lor P = P$

                

4 Types de raisonnements

1. Contre-exemple

Pour montrer que $\forall x \in E,\ P(x)$ est fausse, on trouve un élément $x \in E$ qui ne vérifie pas P(x).

Exemple : $\sqrt{2}$ et $-\sqrt{2}$ sont irrationnels mais leur somme = 0 est rationnel.

2. Équivalences successives

Pour montrer que $P \Leftrightarrow Q$ est vraie, on enchaine :

$P \Leftrightarrow P_1 \Leftrightarrow P_2 \Leftrightarrow \cdots \Leftrightarrow Q$

Exemple : $a^2 + b^2 = 2ab \iff a = b$

3. Déductif

Si $P \Rightarrow Q$ est vraie et P est vraie, alors Q est vraie.

Exemple : $\sqrt{ab} \le \dfrac{a+b}{2}$ avec $a=1, b=x$ donne $2\sqrt{x} \le 1+x$

4. Contraposée

Pour montrer $P \Rightarrow Q$, on montre $\overline{Q} \Rightarrow \overline{P}$.

Exemple : $x^2 - 4x = y^2 - 4y \Rightarrow x = y$

5. Disjonction des cas

On divise le problème en plusieurs cas et on résout chacun séparément.

Exemple : $|x+1| + 2x = 0$ avec $x \le -1$ et $x \ge -1$

6. Raisonnement par l'absurde

On suppose le contraire de ce qu'on veut démontrer, on cherche une contradiction.

Exemples : $\sqrt{2} \notin \mathbb{Q}$ ; $r + i$ est irrationnel

7. Raisonnement par récurrence

Pour montrer que $P(n)$ est vraie pour tout $n \ge n_0$ :

Initialisation : Vérifier $P(n_0)$
Hérédité : $P(n) \Rightarrow P(n+1)$

Exemples : Somme des entiers, $n^3 + 2n$ divisible par 3

5 Tableau récapitulatif

Opération	Notation	Vraie si	Fausse si
Négation	$\overline{P}$	P est fausse	P est vraie
Conjonction	$P \land Q$	P et Q vraies	P ou Q fausse
Disjonction	$P \lor Q$	P ou Q vraie	P et Q fausses
Implication	$P \Rightarrow Q$	P fausse ou Q vraie	P vraie et Q fausse
Équivalence	$P \Leftrightarrow Q$	P et Q même valeur	P et Q valeurs différentes

6 Lettres grecques

Lettre	Nom	Lettre	Nom
α	alpha	ν	nu
β	bêta	ξ	xi
γ	gamma	ο	omicron
δ	delta	π	pi
ε	epsilon	ρ	rhô
ζ	zêta	σ	sigma
η	êta	τ	tau
θ	thêta	υ	upsilon
ι	iota	φ	phi
κ	kappa	χ	chi
λ	lambda	ψ	psi
μ	mu	ω	oméga

Résumé général : Logique mathématique

Table des matières