Logique propositionnelle et booléenne

Propositions et connecteurs

Une proposition est un énoncé pouvant être vrai ($V$ ou $1$) ou faux ($F$ ou $0$).

Connecteurs logiques

| Nom | Symbole | Python | Table de vérité | |-----|---------|--------|----------------| | Négation | $\neg p$ | `not p` | $\neg V = F$, $\neg F = V$ | | Conjonction | $p \wedge q$ | `p and q` | $V$ ssi $p$ et $q$ sont vrais | | Disjonction | $p \vee q$ | `p or q` | $V$ ssi au moins un est vrai | | Implication | $p \Rightarrow q$ | — | $F$ ssi $p$ vrai et $q$ faux | | Équivalence | $p \Leftrightarrow q$ | `p == q` | $V$ ssi $p$ et $q$ ont même valeur |

Table de vérité complète

| $p$ | $q$ | $\neg p$ | $p \wedge q$ | $p \vee q$ | $p \Rightarrow q$ | $p \Leftrightarrow q$ | |-----|-----|---------|-------------|-----------|-------------------|---------------------| | $V$ | $V$ | $F$ | $V$ | $V$ | $V$ | $V$ | | $V$ | $F$ | $F$ | $F$ | $V$ | $F$ | $F$ | | $F$ | $V$ | $V$ | $F$ | $V$ | $V$ | $F$ | | $F$ | $F$ | $V$ | $F$ | $F$ | $V$ | $V$ |

Tautologies et équivalences

Définition. Une tautologie est une formule toujours vraie, quelle que soit la valuation.

Lois fondamentales

• De Morgan : $\neg(p \wedge q) \equiv \neg p \vee \neg q$ et $\neg(p \vee q) \equiv \neg p \wedge \neg q$
• Contraposée : $(p \Rightarrow q) \equiv (\neg q \Rightarrow \neg p)$
• Double négation : $\neg(\neg p) \equiv p$
• Distributivité : $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$

Représentation en Python

```python def table_verite_implication(): """Génère la table de vérité de l'implication.""" print("p | q | p => q") print("-" * 16) for p in [True, False]: for q in [True, False]: impl = (not p) or q # p => q equiv. (non p) ou q print(f"{int(p)} | {int(q)} | {int(impl)}") ```

Formules en forme normale

Forme normale conjonctive (FNC)

Conjonction de clauses, où chaque clause est une disjonction de littéraux :

Forme normale disjonctive (FND)

Disjonction de monômes, où chaque monôme est une conjonction de littéraux :

Théorème. Toute formule propositionnelle admet une FNC et une FND équivalentes.

Problème SAT

Le problème de satisfaisabilité (SAT) consiste à déterminer si une formule propositionnelle admet une valuation qui la rend vraie.

Théorème (Cook-Levin). SAT est NP-complet : c'est l'un des problèmes les plus difficiles de la classe NP.