Pré-requis : Introduction : Éléments de logique mathématique
1. La proposition logique
Intuitivement, une proposition logique est un assemblage de signes ayant un sens et formant un énoncé dont on peut affirmer sans ambiguïté qu’il est vrai ou faux.
Une proposition considérée comme évidente est appelée un « axiome ». Elle est admise sans démonstration. Par exemple les « axiomes d’Euclide » pour la Géométrie plane.
1.1. Formation des propositions
Il existe des propositions élémentaires qu’on appelle aussi des propositions ou formules atomiques. Par exemple : « $x = 2$ », « $t_1=t_2$ », « $2 < 3$ » sont des formules atomiques. $a=a$ est un axiome appelé l’axiome d’identité.
Les propositions composées peuvent être formées à l’aide de formules atomiques, en utilisant des connecteurs. Nous distinguons essentiellement deux connecteurs principaux : « non » et « et », ainsi que trois connecteurs : « ou », « implique » et « équivalent
à », qui se déduisent des deux premiers.
Dans un premier temps, nous construisons une logique des propositions ; c’est-à-dire comment construire de nouvelles propositions en tant que blocs, à partir de formules atomiques, des axiomes ou de propositions déjà établies (ou démontrées).
Nous verrons plus loin une deuxième logique, appelée logique des prédicats. Pour cela, on se place dans un ensemble $E$ dont les éléments sont appelés des « termes ». On distingue deux types de termes : les termes « constants » et les termes « variables ». On rentre alors à l’intérieur d’une proposition pour donner des attributs au sujet $x$ qui est un terme constant ou varie dans un sous-ensemble de termes de $E$.
1.2. La négation logique « $non$ » ou « $\neg$ »
Pour chaque proposition logique $P$, on sait former une proposition notée « $non\, P$ » ou en symboles « $\neg P$ » qui est appelée « la négation de $P$ » et vérifiant l’axiome suivant :
« ou bien $P$ est vraie, ou bien $non\, P$ est vraie, les deux propositions $P$ et $non\, P$ ne peuvent être vraies simultanément ».
Cet axiome fondamental en mathématiques s’appelle « Le principe du tiers exclu ».
La proposition « $P$ et $non\, P$ » s’appelle une contradiction ou encore une « antilogie ».
Par exemple, si $P$ est la proposition « $x<2$ » ; $non\, P$ est la proposition « $x\geq 2$ ».
Une proposition logique $P$ est dite « fausse » si, et seulement si, sa négation « $non\, P$ est vraie.
Ainsi, à toute proposition logique $P$, on attribue une « valeur de vérité », « $V$ » ou « $F$ » qu’on peut présenter dans un « tableau de vérité » de $P$. On peut également attribuer les valeurs $1$ pour «Vraie» et $0$ pour «Fausse»
$\begin{array}{|c|} \hline P \\ \hline \color{red}{V} \\ \hline \color{red}{F} \\ \hline \end{array}$
La table de vérité de la négation est donné par :
$\begin{array}{|c|c|} \hline P& non\, P \\ \hline \color{red}{V}& \color{red}{F} \\ \hline \color{red}{F} & \color{red}{V}\\ \hline \end{array}$
Remarque
Dans le bon sens populaire, les mathématiques ne peuvent pas être contradictoires. Or il existe plusieurs logiques, et d’après Kurt Gödel (1906-1978), un mathématicien autrichien naturalisé américain : « Une théorie suffisante pour y démontrer les théorèmes de base de l’arithmétique est nécessairement incomplète, au sens où il existe des énoncés [indécidables] qui n’y sont ni démontrables, ni réfutables ».
1.3. La conjonction logique
Soit $P$ et $Q$ deux propositions logiques. On appelle « conjonction logique » de $P$ et $Q$, la proposition logique « $P\, et\, Q$ » qui est vraie si, et seulement si, $P$ et $Q$ sont toutes les deux vraies (simultanément).
Par exemple : $P$ : « $x=-1$ et $x>0$ », est une proposition formée de deux propositions reliées par le connecteur de conjonction (de coordination) que nous appellerons « une conjonction logique ». Cette proposition $P$ est ici fausse, car si $x=-1$ est vraie, alors $x>0$ serait fausse. De même si $x>0$ est vraie, alors forcément $x=-1$ serait fausse. Donc l’une des deux propositions est fausse. Donc $P$ est fausse.
1.4. La disjonction logique
Soit $P$ et $Q$ deux propositions logiques. On appelle « disjonction logique » de $P$ et $Q$, la proposition logique « $P\, ou Q$ » qui est vraie si, et seulement si, l’une au moins des deux propositions $P$ et $Q$, est vraie. (L’une ou l’autre ou les deux).
Autrement dit « $P\, ou Q$ » est vraie si, et seulement si $P$ est vraie ou $Q$ est vraie ou bien encore les deux propositions $P$ et $Q$ sont vraies.
Contrairement à l’utilisation exclusive du « ou » dans le langage courant (dans « Fromage ou dessert ») ; en mathématiques, le « ou » est un connecteur est « inclusif ».
Par exemple : $P$ « $1+0=1$ ou $1\times 0=0$ », est une proposition formée de deux propositions reliées par le connecteur de disjonction que nous appellerons « une disjonction logique ». Cette proposition $P$ est ici vraie, car au moins une des deux propositions qui la composent, est vraie.
Ici les deux propositions qui composent $P$ sont vraies, donc a fortiori la proposition $P$ est vraie.
Remarque
Le « ou » peut s’exprimer en fonction du « non » et du $et$. En effet, la proposition ($P\, ou\, Q$) est équivalente [voir ci-dessous] à la proposition : $non(non\,P$ et $non\, Q)$.
1.5. L’équivalence logique
Soit $P$ et $Q$ deux propositions logiques. On appelle « équivalence logique » la proposition logique « $P \Leftrightarrow Q$ » qui est vraie si, et seulement si, les deux propositions $P$ et $Q$ sont toutes les deux vraies ou toutes les deux fausses.
La table de vérité de l’équivalence logique est donnée par :
$\begin{array}{|c|c|} \hline P& Q & P\Leftrightarrow Q\\ \hline
\color{red}{V} & \color{red}{V} & \color{red}{V}\\ \hline
V& F& F \\ \hline
F& V& F \\ \hline
\color{red}{F} & \color{red}{F} & \color{red}{V}\\ \hline
\end{array}$
Pour dire que deux propositions $P$ et $Q$ sont équivalentes, nous écrivons également : $$P\, \textrm{équivaut à}\, Q$$
ou encore : $$P\, \textrm{si, et seulement si}\, Q$$
ou encore symboliquement : $$P \Leftrightarrow Q$$
1.6. L’implication logique
Soit $P$ et $Q$ deux propositions logiques. On appelle « implication logique » la proposition logique « $P \Rightarrow Q$ » qui est $\color{red}{fausse}$ si, et seulement si, $P$ est vraie et $Q$ fausse.
Remarquez que, ici nous n’avons pas défini $P\Rightarrow Q$ lorsqu’elle est vraie, mais lorsqu’elle est fausse. Bien sûr, elle est vraie dans les autres cas. Pour construire la table de vérité de l’implication, nous devons donc distinguer les quatre combinaisons possibles de vérité des deux propositions et on commence par mettre un $\color{red}{F}$ dans la cellule où $P\Rightarrow Q$ est fausse et $V$ ailleurs.
$\begin{array}{|c|c|} \hline P& Q & P\Rightarrow Q\\ \hline
V& V& V \\ \hline
\color{red}{V} & \color{red}{F} & \color{red}{F}\\ \hline
F& V& V \\ \hline
F& V& V \\ \hline
\end{array}$
Nous avions l’habitude d’utiliser l’implication logique d’une manière régulière au Collège sous la forme équivalente : $$\color{red}{\textrm{[Si $P$, alors $Q$]}}$$ Autrement dit : $$\color{red}{\textrm{[Si $P$ est vraie, alors $Q$ est vraie].}}$$
Donnons-nous un exemple dans le langage courant : [Si « j’habite à Paris », alors « j’habite en France »]. Cette implication est bien sûr vraie. Peut-on affirmer que la conclusion est fausse, « si je n’habitais pas à Paris » ?
1.7. Négation d’une implication logique
Nous venons de dire que $P\Rightarrow Q$ est fausse lorsque $P$ est vraie et $Q$ fausse.
Autrement dit : $P\Rightarrow Q$ est fausse si, et seulement si, $\color{red}{ \textrm{($P$ et $non\, Q$)}}$ est vraie ; ou encore : $P\Rightarrow Q$ est $\color{red}{vraie}$ si, et seulement si, $\color{red}{\textrm{($non\, P$ ou $Q$)}}$ est vraie.
Par conséquent, l’implication logique peut s’écrire également uniquement en fonction des deux connecteurs « $non$ » et « $ou$ » et, par suite l’implication logique peut s’écrire uniquement en fonction des deux connecteurs « $non$ » et « $et$ ».
Conclusion : Les deux propositions logiques $\color{red}{P\Rightarrow Q}$ et $\color{red}{ \textrm{($non\, P$ ou $Q$)}}$ sont équivalentes.
1.8. Condition nécessaire. Condition suffisante
Dans une implication logique $ P\Rightarrow Q$, on dit que la proposition $Q$ est une $\color{red}{\textrm{condition nécessaire}}$ (CN) à la réalisation de $P$. D’une manière analogue, $P$ est une $\color{red}{\textrm{condition suffisante}}$ (CS) à la réalisation de $Q$.
Ainsi, dire que $P \Leftrightarrow Q$ équivaut à dire que $Q$ est une $\color{red}{\textrm{condition nécessaire et suffisante}}$ (CNS) à la réalisation de $P$ ou encore que $P$ est une $\color{red}{\textrm{condition nécessaire et suffisante}}$ (CNS) à la réalisation de $Q$.
2. Propriétés. Calcul propositionnel
Toutes les propriétés suivantes peuvent être démontrées en construisant dans un même tableau les tables de vérité de chacune des propositions logiques.
Propriétés 1.
Soient $P$, $Q$ et $R$ trois propositions logiques. Alors :
Négation :
$P\Longleftrightarrow non\,(non\, P)\quad(1)$
Les lois de Morgan :
$non\,(P\, \textbf{et}\, Q) \Longleftrightarrow (non\, P\, \textbf{ou}\, non\, Q)\quad(2)$
$non\,(P\, \textbf{ou}\, Q) \Longleftrightarrow (non\, P\, \textbf{et}\, non\, Q)\quad(3)$
La négation d’une implication :
$non(P\Rightarrow Q) \Longleftrightarrow (P\,\textbf{et}\,non\,Q)\quad(4)$
Propriétés 2. Commutativité et associativité du « et » et du « ou »
Soient $P$, $Q$ et $R$ trois propositions logiques. Alors :
$(P\,\textbf{et}\, Q) \Longleftrightarrow (Q\, \textbf{et}\, P)\quad(5)$
$(P\, \textbf{ou}\, Q) \Longleftrightarrow (Q\, \textbf{ou}\, P)\quad(6)$
$P\, \textbf{et}\, (Q\, \textbf{et}\, R) \Longleftrightarrow (P\, \textbf{et}\, Q)\, \textbf{et}\, R\quad(7)$
$P\,\textbf{ou}\, (Q\, \textbf{ou}\, R) \Longleftrightarrow (P\, \textbf{ou}\, Q)\, \textbf{ou}\, R\quad(8)$
Propriétés 3. Formules de distributivité du « et » et « ou »
Soient $P$, $Q$ et $R$ trois propositions logiques. Alors :
$P\,\textbf{et}\, (Q\,\textbf{ou}\, R) \Longleftrightarrow (P\,\textbf{et}\, Q)\,\textbf{ou}\, (P\, \textbf{et}\, R)\quad(9)$
$P\, \textbf{ou}\, (Q\,\textbf{et}\, R) \Longleftrightarrow (P\, \textbf{ou}\, Q)\,\textbf{et}\, (P\,\textbf{ou}\, R)\quad(10)$
Propriétés 4. Implications et équivalences :
Soient $P$, $Q$ et $R$ trois propositions logiques. Alors :
$\bullet$ L’équivalence est une double implication
$(P\Leftrightarrow Q)\Longleftrightarrow (P \Rightarrow Q)\, \textbf{et}\, (Q \Rightarrow P)\quad(11)$
$\bullet$ Transitivité de l’implication :
$(P\Rightarrow Q)\,\textbf{et} (Q\Rightarrow R) \Longleftrightarrow (P \Rightarrow R)\quad(12)$
$\bullet$ Transitivité de l’équivalence
$(P\Rightarrow Q)\, \textbf{et} (Q\Rightarrow R) \Longleftrightarrow (P \Rightarrow R)\quad(13)$
Propriétés 4. Formules de la contraposée
Soient $P$ et $Q$deux propositions logiques. Alors :
$(P\Rightarrow Q)\Longleftrightarrow (non\, Q \Rightarrow non\, P)\quad(14)$
$(P \Leftrightarrow Q) \Longleftrightarrow (non\, Q \Leftrightarrow non\, P)\quad(15)$
3. La démonstration (IA adaptée)
3.1 Qu’est-ce qu’une démonstration ?
Une démonstration est un raisonnement logique structuré d’étapes correctes et ordonnées d’un raisonnement. C’est un enchaînement ordonné de propositions logiques vraies, souvent formalisées en langage naturel mais sans ambiguïté, pour établir la véracité d’un énoncé ou d’un théorème.
Chaque étape est soit un axiome (vérité fondamentale admise), soit un théorème déjà démontré, déduits des axiomes par application de règles de déduction.
Les règles de déduction permettent d’affirmer qu’une assertion donnée, à savoir la conclusion, est nécessairement vraie comme conséquence logique d’une ou plusieurs autres propositions appelées les prémisses.
On emploie parfois le terme « preuve » comme un synonyme de démonstration par attraction de l’anglais proof. (Wikipedia).
3.2. Les principes d’une démonstration
- Axiomes et prémisses :
Toute démonstration commence par des propositions admises comme vraies, que ce soient des axiomes (vérités fondamentales évidentes) ou des théorèmes déjà démontrés. - Raisonnement déductif :
La démonstration progresse par déduction logique, en enchaînant des étapes rigoureuses qui utilisent les règles de la logique et les théorèmes et axiomes existants. - Conclusion :
Le but final est d’arriver à une conclusion indubitable, c’est-à-dire de prouver que l’assertion visée est effectivement vraie.
3.3. L’importance des démonstrations
- Établir la vérité
Une démonstration permet de dépasser les intuitions ou les conjectures pour établir des vérités universelles et incontestables construites sur des bases solides et reconnues par tous. - Construire le savoir mathématique
Chaque théorème démontré devient lui-même une nouvelle prémisse qui peut servir à en démontrer d’autres, créant ainsi un réseau de connaissances cohérent et fiable. - Rigueur et méthode
Une démonstration impose et exige une rigueur méthodologique, enseignée dès les premières années de scolarité, qui est essentielle à la pratique des mathématiques.