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

Table de vérité complète

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

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.