02. Propositions et Connecteurs

Le langage de la logique propositionnelle

La logique propositionnelle (ou calcul propositionnel) est le système formel le plus simple. Elle étudie les propositions comme des unités atomiques, sans analyser leur structure interne.

Alphabet

Le langage propositionnel utilise:

1. Variables propositionnelles: $p, q, r, s, \dots$ (ou $p_1, p_2, p_3, \dots$)

   • Représentent des propositions atomiques
   • Peuvent prendre les valeurs VRAI ($\top$, 1, V) ou FAUX ($\bot$, 0, F)

2. Connecteurs logiques:

   • $\neg$ (négation, “non”)
   • $\land$ (conjonction, “et”)
   • $\lor$ (disjonction, “ou”)
   • $\rightarrow$ (implication, “si… alors”)
   • $\leftrightarrow$ (équivalence, “si et seulement si”)

3. Symboles auxiliaires: parenthèses $( )$

Formules bien formées (FBF)

Une formule bien formée est définie inductivement:

1. Base: Toute variable propositionnelle est une FBF.

2. Induction:

   • Si $\varphi$ est une FBF, alors $(\neg \varphi)$ est une FBF.
   • Si $\varphi$ et $\psi$ sont des FBF, alors $(\varphi \land \psi)$, $(\varphi \lor \psi)$, $(\varphi \rightarrow \psi)$, et $(\varphi \leftrightarrow \psi)$ sont des FBF.

3. Clôture: Rien d’autre n’est une FBF.

Exemples de FBF:

• $p$
• $(\neg p)$
• $(p \land q)$
• $((p \rightarrow q) \lor (\neg r))$
• $(((p \land q) \rightarrow r) \leftrightarrow (p \rightarrow (q \rightarrow r)))$

Non-exemples:

• $\land pq$
• $p\neg$
• $(p \land q$

Conventions de notation

1. Priorité des opérateurs:

$$ \neg ;>; \land ;>; \lor ;>; \rightarrow ;>; \leftrightarrow $$

1. Association à droite:

$$ p \rightarrow q \rightarrow r \equiv p \rightarrow (q \rightarrow r) $$

1. Exemple:

$$ \neg p \land q \rightarrow r \lor s $$

se lit:

$$ ((\neg p) \land q) \rightarrow (r \lor s) $$

Les connecteurs en détail

Négation ($\neg$)

$$ \begin{array}{c|c} p & \neg p \\ \hline V & F \\ F & V \end{array} $$

Conjonction ($\land$)

$$ \begin{array}{c|c|c} p & q & p \land q \\ \hline V & V & V \\ V & F & F \\ F & V & F \\ F & F & F \end{array} $$

Disjonction ($\lor$)

$$ \begin{array}{c|c|c} p & q & p \lor q \\ \hline V & V & V \\ V & F & V \\ F & V & V \\ F & F & F \end{array} $$

OU exclusif:

$$ p \oplus q \equiv (p \lor q) \land \neg (p \land q) $$

Implication ($\rightarrow$)

$$ \begin{array}{c|c|c} p & q & p \rightarrow q \\ \hline V & V & V \\ V & F & F \\ F & V & V \\ F & F & V \end{array} $$

Équivalence clé:

$$ p \rightarrow q \equiv \neg p \lor q $$

Équivalence ($\leftrightarrow$)

$$ \begin{array}{c|c|c} p & q & p \leftrightarrow q \\ \hline V & V & V \\ V & F & F \\ F & V & F \\ F & F & V \end{array} $$

$$ p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p) $$

Arbre syntaxique

Pour:

$$ (p \rightarrow q) \land (\neg p \rightarrow r) $$

    ∧
   / \
  →   →
 / \ / \
p  q ¬  r
     |
     p

Sous-formules

Pour:

$$ (p \rightarrow q) \land \neg r $$

Sous-formules:

$$ p,; q,; r,; \neg r,; p \rightarrow q,; (p \rightarrow q) \land \neg r $$

Connecteurs dérivés

$$ \begin{aligned} p \rightarrow q &\equiv \neg p \lor q \ p \leftrightarrow q &\equiv (p \rightarrow q) \land (q \rightarrow p) \ p \oplus q &\equiv (p \lor q) \land \neg(p \land q) \ p \uparrow q &\equiv \neg (p \land q) \ p \downarrow q &\equiv \neg (p \lor q) \end{aligned} $$

Formalisation d’énoncés

Exemple 1:

$$ (p \land \neg u) \rightarrow m $$

Exemple 2:

$$ (t \lor c) \rightarrow r $$

Attention:

$$ a \rightarrow v \quad \text{vs} \quad a \leftrightarrow v $$