Logique¶

Warning

Ce cours a été automatiquement traduit des transparents de M.Noyer par Lorentzo et Elowan et mis en forme par Mehdi, nous ne nous accordons en aucun cas son travail, ce site à pour seul but d'être plus compréhensible pendant les périodes de révision que des diaporamas.

Crédits

Wikipedia,
Mansuy,
Becirspahic.

Introduction¶

Proposition¶

Notion affinée au cours des siècles.

Une proposition est une construction syntaxique pensée parler de vérité. La définition précise de ce concept est l'un des objectifs du calcul des propositions.

"Pourvu que je n'attrape pas le Coronavirus !" exprime un souhait et pas un fait. Il n'est pas modélisé par une proposition.

Il n'y a pas de quantification en calcul des propositions. Ainsi "M. Noyer marche sur les eaux" est exprimable comme une proposition mais pas "tous les marseillais marchent sur les eaux" ni "il existe un marseillais qui marche sur les eaux" (d'ailleurs c'est M. Noyer !)

Le calcul des propositions est la première étape dans la définition de la logique et du raisonnement. Etape suivante : calcul des prédicats.

Contenu des propositions¶

Une proposition donne une information évaluable sur quelque chose.

Exemple

$2 + 2 = 4$ ou "la maison de Pierre est rose" ou "si $a ≤ b$ et $f(a)f(b) < 0$ alors il existe $c\in \left ] a,b \right [$ tel que $f(c) = 0$".

L'idée est qu'on puisse attribuer une valeur de vérité à toute proposition.

Par exemple $2 + 2 = 4$ a pour valeur Vrai, la seconde phrase est vérifiable en se rendant chez Pierre, la dernière dépend du type et de la continuité de $f$ .

Contre-exemple

"À quelle heure finit le cours ?" ou "Travaille davantage !". Ces phrases n'apportent pas d'information. Il est difficile de leur attribuer une valeur.

Les valeurs attribuées aux propositions sont en général $0$ ou $1$, True ou False, Vrai ou Faux.

Logique classique¶

C'est celle du cours de maths en CPGE.

Quand le cardinal de l'ensemble des valeurs possibles que peuvent prendre les propositions est $2$, on parle de logique classique ou bouléenne.

Il existe d'autres logiques. Elles sont parfois tri-valuées. Par exemple Vrai, Faux, Je ne sais pas.

Pourquoi faudrait-il d'autres logiques ?
$\color{red} \text {En logique classique "je suis ici ou ailleurs" (= tiers exclu) est toujours vrai.}$ Cependant "si $x\in \mathbb{Q}$ alors machin sinon truc" n'est exploitable que si on possède un test d'appartenance à $\mathbb{Q}$ en temps fini, ce qui n'est pas le cas. Les logiciens intuitionnistes refusent le tiers exclu.

Tiers exclu¶

Le principe du tiers exclu a été introduit par Aristote comme conséquence du principe de non-contradiction. Le principe de non-contradiction stipule que pour toute proposition $P$ on ne peut pas avoir $P$ et $\neg P$ (non $P$) en même temps.

La proposition $\neg (P \wedge \neg P)$ (toujours vraie dans toute les logiques) équivaut sémantiquement (par utilisation de règle de De Morgan) à $\neg P \vee \neg \neg P$.
On retrouve le tiers exclu SI ON ACCEPTE que $\neg \neg P$ et $P$ sont sémantiquement équivalents.

D'autres mathématiques¶

La logique intuitionniste qui engendre les mathématiques constructives, admet le principe de non-contradiction mais réfute celui du tiers exclu.

Pour un constructiviste, le raisonnement "si $a \in A$ alors bla sinon bli" n'a de sens que s'il existe un test pour déterminer l'appartenance à $A$.

Les constructivistes réfutent aussi l'axiome du choix qui dit en substance que "dans un ensemble infini, je peux choisir un élément", au motif que "je ne peux pas choisir si je ne sais pas comment choisir".

La plupart des théorèmes de CPGE sont adaptables en mathématiques constructives (parfois, les énoncés sont les mêmes, d'autre fois, il faut adapter). En revanche l'affirmation "tout $𝕂$-espace vectoriel admet une base " n'est pas constructive (oui pour la dimension finie mais pas en dimension quelconque)

Une preuve de mathématiques constructives est bien adaptée à l'informatique en ce sens qu'elle est pratiquement donnée sous forme d'algorithme.

Structure (d'après Wikipedia)¶

Dans les théories de la logique mathématique, on considère deux points de vue dits syntaxique et sémantique, c'est le cas en calcul des propositions.

La forme : Aspect syntaxique. Il s'agit de définir le langage du calcul des propositions par les règles d'écriture des propositions. On décrit donc ce qu'EST une proposition.
Le fond : Aspect sémantique. Il s'agit de donner un sens aux symboles représentant les connecteurs logiques. Il y a deux façons de donner un tel sens :
- Soit par sémantique : en munissant d' une interprétation (un sens) les connecteurs logique. On peut alors définir inductivement une interprétation pour toute proposition complexe. Ex: table de vérité.
- Soit par déduction : On se donne des règles purement syntaxiques qui permettent de déduire une proposition d'un ensemble d'autres : les règles d'inférence (Par exemple : calcul des séquents ou déduction naturelle). On ne se préoccupe donc pas du sens, juste de la déductibilité.

Sémantique VS déduction¶

Définition: Une interprétation

La fonction "qui donne du sens" est appelé une interprétation.

On construit un arbre d'inférence et on dit qu'une formule est prouvable si toutes les feuilles de l'arbre sont des axiomes. On appelle théorème une proposition prouvable.

En calcul des propositions, tout ce qui est vrai est prouvable et réciproquement.

Si on reste en logique du 1er ordre (en ajoutant quantificateurs, termes et prédicats au cours de 1ere année) alors ce qui est vrai est prouvable et réciproquement.

Pour avoir mal à la tête¶

La logique du 1er ordre (telle qu'enseignée en MP2I/MPI) est $\color{red}\text{cohérente : on ne peut pas démontrer à la fois une formule et son contraire}$; ce qui revient à dire qu'on ne peut pas démontrer le faux.

Le calcul des prédicats est $\color{red}\text{complet : ce qui est vrai est prouvable et réciproquement}$.

Aucun système logique cohérent (comme la déduction naturelle ou le calcul des séquents) ne peut démontrer tous les résultats de l'arithmétique. $\color{red}\text{Quel que soit le système, s'il est assez riche pour exprimer l'arithmétique, on peut}$ $\color{red}\text{trouver un énoncé valide qui ne sera pas démontrable dans ce système}$.

$\color{red}\text{Aucun système logique cohérent assez riche pour exprimer l'arithmétique ne peut}$ $\color{red}\text{démontrer sa propre cohérence}$. Par exemple, les mathématiques enséeignées en CPGE ne peuvent pas établir la preuve qu'elles sont sans contradiction.

Syntaxe¶

L'alphabet¶

Définition

On considère un alphabet $\Sigma$ constitué :

de symboles Vrai et Faux notés V et F,
de variables propositionnelles en nombre dénombrable notées dans ce cours en lettres romaines $a, b$, $\dotsb$ , $a_1$, $\dotsb$ , $z_{32}$, $\dotsb$
de deux symboles de parenthèses "($,$)" (ouvrante et fermante).
d'un connecteur unaire $\neg$ dit de négation
de trois connecteurs binaires notés $\vee , \wedge , \rightarrow$ et appelés connecteurs logiques de disjonction, conjonction et d'implication.

Remarque

On dit aussi opérateur pour "connecteur"
Dans certains cours, on ajoute aussi l'opérateur $\Leftrightarrow$ et le XOR. Dans certains autres, seulement $\neg , \vee , \wedge$ , voire même $\neg , \wedge$ .
Le NAND ($A$ NAND $B$ vaut $\neg (A \wedge B)$) est universel.

Ensemble des propositions¶

Définition

On appelle langage des propositions le langage défini inductivement par :

les constantes et les variables propositionnelles sont dans le langage,
si $A$ est dans le langage, alors $(A)$ aussi,
si $A$ est dans le langage $(\neg A)$ aussi,
si $A, B$ sont dans le langage alors $(A \vee B)$, $(A \wedge B)$ et $(A \rightarrow B)$ aussi.

Représentation arborescente¶

$(((\neg a) \vee b) \wedge (\neg c))$ se représente sous la forme d'un arbre binaire (dit arbre syntaxique) :

Remarque

Puisque les propositions sont construites comme des arbres binaires, il est naturel de parler de leur taille et de leur hauteur.

Simplification de l'écriture¶

On ne note pas les parenthèses autour de la racine.

On convient (souvent, mais je ne trouve pas ça si commode) que l'opérateur de négation $\neg a$ priorité sur les autres, que la conjonction et la disjonction ont priorité sur l'implication, et enfin que la conjonction a priorité sur la disjonction. C'est très classique !

Remarque

C'est à dire : $\neg \gg \wedge \gg \vee \gg \text{ } \rightarrow$

Pour passer des écritures sans parenthèses aux écritures avec parenthèses, une règle simple : plus l'opérateur est prioritaire, plus il a de parenthèses autour de lui.

Priorités en Python¶

Figure – Règles de priorité de la plus haute (en haut) à la plus basse (en bas). Les opérateurs de même niveau sont évalués de gauche à droite

Exercice

Remettre des parenthèses

$\neg a \vee b \wedge c$
$((\neg a) \vee (b \wedge c))$
$\neg a \wedge b \vee c$
$(((\neg a) \wedge b) \vee c)$
$a \vee \neg b \wedge c \rightarrow a \wedge c$
$[(a \vee ((\neg b) \wedge c)) \rightarrow (a \wedge c)]$

Sémantique¶

Contexte¶

Définition: Un contexte

Un contexte (ou une distribution de vérité) sur un ensemble de variables propositionnelles ${\displaystyle {\mathcal {V}}}$ est une application de ${\displaystyle {\mathcal {V}}}$ dans l'ensemble des bouléens ${\displaystyle {\mathcal {B}}}$.

Remarque

Si $|{\displaystyle {\mathcal {V}}}| = n$ alors il y a $2^n$ distributions de vérité.
L'ensemble des bouléens peut être représenté de différentes façons.
Dans ce cours, on pose ${\displaystyle {\mathcal {B}}} = {0, 1}$, et on identifie ${\displaystyle {\mathcal {B}}}$ avec l'anneau $\mathbb{Z}/2\mathbb{Z}$ (donc $1 + 1 = 0$ en particulier.)
La multiplication est l'interprétation de la conjonction, $0$ celle de F, $1$ celle de V, l'addition celle du XOR.

Interprétation¶

Définition: Une évaluation / interprétation

Soit $\mu$ un contexte sur un ensemble de variables ${\displaystyle {\mathcal {V}}}$ à valeur dans ${\displaystyle {\mathcal {B}}} = ℤ/2ℤ$. On appelle évaluation (ou encore interprétation) associée à $\mu$ l'application notée $\varepsilon_\mu$ définie sur l'ensemble des propositions par :

$\varepsilon_\mu(V ) = 1, \varepsilon_\mu(F ) = 0$
pour toute variable $v \in {\displaystyle {\mathcal {V}}}, \varepsilon_\mu(v ) = \mu(v )$
pour toute expression $p, \varepsilon_\mu(\neg p) = 1 − \varepsilon_\mu(p)$
pour toutes expressions $p_1$ et $p_2$ :

\[\begin{matrix} \varepsilon_\mu(p_1 \wedge p_2) &=& \varepsilon_\mu(p_1)\varepsilon_\mu(p_2)\\ \varepsilon_\mu(p_1 \vee p_2) &=& \varepsilon_\mu(p_1) + \varepsilon_\mu(p_2) − \varepsilon_\mu(p_1)\varepsilon_\mu(p_2)\\ \varepsilon_\mu(p_1 \rightarrow p_2) &=& 1 − \varepsilon_\mu(p_1) + \varepsilon_\mu(p_2)\varepsilon_\mu(p_1). \end{matrix}\]

Remarque

Observer l'analogie avec les fonctions caractéristiques.

Implication¶

Comme on va le voir $a \rightarrow b$ est sémantiquement équivalent à $\neg a \vee b$, c'est à dire que les deux propositions ont la même valeur de vérité pour toute interprétation.
L'interprétation de l'implication donnée au transparent précédent s'obtient par calcul :

\[ \begin{matrix} \varepsilon_\mu((\neg p_1) \vee p_2) &=& \varepsilon_\mu(\neg p_1) + \varepsilon_\mu(p_2) − \varepsilon_\mu(\neg p_1)\varepsilon_\mu(p_2) \\ &=& (1 − \varepsilon_\mu(p_1)) + \varepsilon_\mu(p_2) − (1 − \varepsilon_\mu(p_1))\varepsilon_\mu(p_2) \\ &=& 1 − \varepsilon_\mu(p_1) + \varepsilon_\mu(p_2) − \varepsilon_\mu(p_2) + \varepsilon_\mu(p_1)\varepsilon_\mu(p_2) \\ &=& 1 − \varepsilon_\mu(p_1) + \varepsilon_\mu(p_2)\varepsilon_\mu(p_1) \\ &=&\varepsilon_\mu(p_1 \rightarrow p_2) \end{matrix} \]

Tables de vérité¶

Equivalence sémantique¶

Définition: Sémantiquement équivalent

Deux propositions $p, q$ sont dites sémantiquement équivalentes si elles ont même table de vérité. Ceci revient à dire que pour tout contexte $\mu$, si $\varepsilon_\mu$ de l'une vaut $1$, alors pour l'autre aussi.On note $p$ $\equiv$ $q$.

Définition: Tautologie

On dit qu'une proposition $p$ est une tautologie lorsque $p$ $\equiv$ $V$ (c'est à dire que la dernière colonne de sa table de vérité ne contient que des $1$).

Remarque

Par exemple $a \wedge V$ est sémantiquement équivalente à $a$.
Montrer que le tiers exclu $a \vee \neg a$ est une tautologie.
Certains auteurs parlent d'équivalence logique.

XOR¶

Exercice

Définir l'opérateur XOR au moyen des opérateurs usuels

La table du XOR (=OU du cantinier)

\[\begin{array}{c|c|c} a & b & a \oplus b\\ \hline 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{array}\]

Correction

$(¬ A ∨ ¬ B) ∧ (A ∨ B)$

Priorités¶

Les opérateurs $\wedge$ et $\vee$ sont associatifs : en conséquence on peut écrire (($a \vee b$) $\vee$ ($c$ $\vee$ $d$)) comme $a \vee b \vee c \vee d$
$\rightarrow$ n'est pas associatif : $a$ $\rightarrow$ ($b$ $\rightarrow$ $c$) n'est pas sémantiquement équivalent à ($a$ $\rightarrow$ $b$) $\rightarrow$ c
Exercice : montrer ces assertions par des tables de vérité.
L'implication n'est pas associative mais par convention $A$ $\rightarrow$ $B$ $\rightarrow$ $C$ $\rightarrow$ $D$ se lit $A$ $\rightarrow$ ($B$ $\rightarrow$ ($C$ $\rightarrow$ $D$)).

Observer l'analogie avec une fonction f de type a->b->c->d en OCaml : f x est de type b->c->d.

D'autres opérateurs¶

Exercice

Montrer qu'on peut se passer de l'opérateur d'implication.
L'opérateur binaire $\Leftrightarrow$ est défini ainsi : $a \Leftrightarrow b$ a la table de $(a \rightarrow b) \wedge (b \rightarrow a)$. Montrer que $a$ XOR $b$ est sémantquement équivalent à $\neg (a \Leftrightarrow b)$.

Calcul à partir de l'arbre syntaxique

$(a \vee n) \rightarrow ((\neg c)\vee (b \wedge V)), \mu(a) = 1; \mu(b) = \mu(c) = 0$. Commencer par les feuilles et remonter aux pères.

Satisfiabilité¶

Tautologies¶

Tautologie, proposition satisfiable¶

Définition: Tautologie, modèle et antilogie

On appelle tautologie toute expression évaluée à $1$ dans tout contexte.
Une proposition $p$ est dite satisfiable ou satisfaisable si il existe un contexte $\mu$ tel que $\varepsilon_\mu(p) = 1$. On dit que $\mu$ est un modèle de $p$ et on note $\mu \models p$.
Une proposition qui n'est pas satisfiable est apellée une antilogie. On dit aussi que l'expression est insatisfiable.

Exemples

Le tiers exclu $a \vee \neg a$ est une tautologie, $(a \wedge b) \rightarrow b$ aussi.
$a \rightarrow b$ est satisfiable mais n'est pas une tautologie.
$a \wedge \neg a$ est insatisfiable.
Montrer que $(\neg A \rightarrow A) \rightarrow A$ est une tautologie

Notation¶

Pour indiquer qu'une proposition $a$ est sémantiquement équivalente à une proposition $b$, il n'est pas suffisant d'écrire $a \Leftrightarrow b$.
En effet $a \Leftrightarrow b$ est juste une proposition. Celle-ci peut être satisfiable ou non (peut-être même pas, comme $V \Leftrightarrow F$ ).
La bonne façon d'indiquer cette équivalence est de déclarer "$a \Leftrightarrow b$ est une tautologie".
Les mathématiciens sont parfois paresseux : il leur arrive d'écrire "$a \Leftrightarrow b$" au lieu de "$a \Leftrightarrow b$ est vraie (ce qui signifie vraie pour tout contexte)".
On écrit $a \equiv b$ pour indiquer que $a \Leftrightarrow b$ est une tautologie.
Attention, "$\equiv$" n'est pas un opérateur (il n'appartient pas au langage) mais un méta-opérateur.

A ce propos, un principe empirique est que, pour exprimer des idées sur un langage, il faut souvent "sortir" du langage.

Notion de conséquence¶

Définition: Conséquence

On considère une expression logique $p$ et $\chi$ un ensemble d'expressions logiques. On dit que $p$ est une conséquence de $\chi$ si toute interprétation qui satisfait toutes les formules de l'ensemble $\chi$ satisfait $p$. Si c'est le cas, on note : $\chi \models p$.

Notation

Si $\chi = \left \{ h_1, \dotsb , h_n \right \}$, on écrit aussi $h_1, \dotsb , h_n \models p$. Si $\chi = \left \{h \right \}$, on écrit $h \models p$ Par convention, $\models p$ indique que $p$ est une tautologie.