Fiche Mémo Complète : Lois & Équivalences de la Logique Propositionnelle

Formulaire Rigoureux Équivalence : $\equiv$ | Non-équivalence / Différence : $\not\equiv$ ou $\neq$

Théorèmes & Équivalences du Calcul Propositionnel

Distinction Clé : Négation de l'Implication & Non-Équivalence ($\not\equiv$ ou $\neq$)

Erreur Fréquente Évitée

Une formule $P \to Q$ et la formule $P \land \neg Q$ affirment deux réalités incompatibles : elles sont strictement opposées et ne sont en aucun cas équivalentes.

≠ Non-Équivalence Stricte (Différence)

$$(P \to Q) \not\equiv (P \land \neg Q) \quad \text{ou} \quad (P \to Q) \neq (P \land \neg Q)$$

Explication :

• $P \to Q$ dit : « Si $P$ est vrai, $Q$ est obligatoirement vrai. »
• $P \land \neg Q$ dit : « $P$ est vrai et $Q$ est faux. » (c'est l'infraction à la règle).

Quand l'une est vraie ($1$), l'autre est obligatoirement fausse ($0$).

≡ Équivalences Exactes Authentiques

$$\neg(P \to Q) \equiv P \land \neg Q \quad \text{et} \quad P \to Q \equiv \neg(P \land \neg Q)$$

Démonstration formelle :

$\neg(P \to Q) \equiv \neg(\neg P \lor Q) \equiv \neg(\neg P) \land \neg Q \equiv P \land \neg Q$

La négation d'une promesse équivaut à observer son antécédent avec le conséquent falsifié.

Lois Fondamentales Booléennes

Élément Neutre Neutre

$$P \land 1 \equiv P \quad \text{et} \quad P \lor 0 \equiv P$$

$1$ est neutre pour le $ET$ ; $0$ est neutre pour le $OU$.

Élément Absorbant Domination

$$P \land 0 \equiv 0 \quad \text{et} \quad P \lor 1 \equiv 1$$

$0$ annule tout $ET$ ; $1$ valide tout $OU$.

Idempotence Répétition

$$P \land P \equiv P \quad \text{et} \quad P \lor P \equiv P$$

Répéter une même prémisse ne change rien.

Complémentarité Fondamental

$$P \lor \neg P \equiv 1 \quad \text{et} \quad P \land \neg P \equiv 0$$

Tiers-exclu (toujours vrai) et non-contradiction (impossible).

Involution (Double Négation) Annulation

$$\neg(\neg P) \equiv P \quad \text{avec} \quad \neg 1 \equiv 0, \;\; \neg 0 \equiv 1$$

Deux négations successives se détruisent.

Absorption Élémentaire Réduction

$$P \lor (P \land Q) \equiv P \quad \text{et} \quad P \land (P \lor Q) \equiv P$$

La variable isolée prédomine et absorbe le bloc composé.

Lois de Structure

Commutativité Non commutative : $\to$

$$P \land Q \equiv Q \land P \qquad P \lor Q \equiv Q \lor P \qquad P \leftrightarrow Q \equiv Q \leftrightarrow P$$

Attention : $(P \to Q) \not\equiv (Q \to P)$ [(P → Q) ≠ (Q → P)].

Associativité

$$(P \land Q) \land R \equiv P \land (Q \land R) \qquad (P \lor Q) \lor R \equiv P \lor (Q \lor R)$$

Permet d'enlever les parenthèses entre connecteurs identiques.

Double Distributivité

$$P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$$ $$P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$$

En logique booléenne, le $\lor$ se distribue aussi sur le $\land$.

Lois de De Morgan & Absorption Étendue

Négation d'un $ET$ (De Morgan 1)

$$\neg(P \land Q) \equiv \neg P \lor \neg Q$$

Nier deux vérités simultanées signifie qu'au moins l'une des deux est fausse.

Négation d'un $OU$ (De Morgan 2)

$$\neg(P \lor Q) \equiv \neg P \land \neg Q$$

Nier une alternative impose que les deux termes soient faux à la fois.

Absorption Étendue (Règle d'élimination)

$$P \lor (\neg P \land Q) \equiv P \lor Q \qquad P \land (\neg P \lor Q) \equiv P \land Q$$

Le terme externe élimine son opposé dans le produit interne.

Lois de l'Implication & Biconditionnel

Définition Matérielle Pivot

$$P \to Q \equiv \neg P \lor Q$$

Permet de transformer toute implication en disjonction.

Loi de Contraposition Stricte

$$P \to Q \equiv \neg Q \to \neg P$$

Pour inverser les membres de la flèche, il faut obligatoirement les nier.

Loi d'Exportation Calcul

$$P \to (Q \to R) \equiv (P \land Q) \to R$$

Deux conditions successives s'agrègent en une condition jointe ($ET$).

Formes du Biconditionnel (Équivalence $P \leftrightarrow Q$) et Ou Exclusif ($P \oplus Q$)

Double implication $$(P \to Q) \land (Q \to P)$$

Forme Disjonctive (FND) $$(P \land Q) \lor (\neg P \land \neg Q)$$

Forme Conjonctive (FNC) $$(\neg P \lor Q) \land (\neg Q \lor P)$$

Négation (XOR / $\oplus$) $$\neg(P \leftrightarrow Q) \equiv P \oplus Q$$

Arbres de Quine : Table de Réduction par les Pivots 0 et 1

Connecteur	Branche Pivot P = 0	Branche Pivot P = 1	Règle de Réduction Directe
$P \land Q$	$0 \land Q \equiv 0$	$1 \land Q \equiv Q$	$0$ annule tout ; $1$ est transparent.
$P \lor Q$	$0 \lor Q \equiv Q$	$1 \lor Q \equiv 1$	$0$ est transparent ; $1$ valide directement.
$P \to Q$	$0 \to Q \equiv 1$	$1 \to Q \equiv Q$	Antécédent faux = toujours vrai ; antécédent vrai = donne le conséquent.
$Q \to P$	$Q \to 0 \equiv \neg Q$	$Q \to 1 \equiv 1$	Conséquent nul = exige $\neg Q$ ; conséquent vrai = toujours vrai.
$P \leftrightarrow Q$	$0 \leftrightarrow Q \equiv \neg Q$	$1 \leftrightarrow Q \equiv Q$	Inverse pour $0$ ; recopie la valeur pour $1$.

Règles d'Inférence Classiques

Modus Ponens (Affirmation) Valide

$$((P \to Q) \land P) \vdash Q \quad \iff \quad ((P \to Q) \land P) \to Q \equiv 1$$

Si l'implication est posée et que la condition $P$ se réalise, $Q$ s'ensuit nécessairement.

Modus Tollens (Réfutation) Contraposée

$$((P \to Q) \land \neg Q) \vdash \neg P \quad \iff \quad ((P \to Q) \land \neg Q) \to \neg P \equiv 1$$

Si la conséquence promise n'a pas lieu ($\neg Q$), alors la cause ne s'est pas produite ($\neg P$).

Démonstration Pas-à-Pas Type

Preuve de l'exportation : $S \to (B \to C) \equiv (S \land B) \to C$

1. Formule initiale : $S \to (B \to C)$
2. Définition sur $B \to C$ : $S \to (\neg B \lor C)$
3. Définition sur la flèche externe : $\neg S \lor (\neg B \lor C)$
4. Associativité de la disjonction : $(\neg S \lor \neg B) \lor C$
5. Règle inverse de De Morgan : $\neg(S \land B) \lor C$
6. Reconstitution de l'implication : $(S \land B) \to C$ ∎