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
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 :
1) $P\Longleftrightarrow non\,(non\, P)$.
Les lois de Morgan
2) $non\,(P\, et\, Q) \Longleftrightarrow (non\, P\, ou\, non\, Q)$.
3) $non\,(P\, ou\, Q) \Longleftrightarrow (non\, P\, et\, non\, Q)$.
La négation d’une implication
4) $non(P\Rightarrow Q) \Longleftrightarrow (non\, P\, ou\, Q$.
Propriétés 2. Commutativité et associativité du « et » et du « ou »
Soient $P$, $Q$ et $R$ trois propositions logiques. Alors :
5) $(P\, et\, Q) \Longleftrightarrow (Q\, et\, P)$
6) $(P\, ou\, Q) \Longleftrightarrow (Q\, ou\, P)$
7) $P\, et\, (Q\, et\, R) \Longleftrightarrow (P\, et\, Q)\, et\, R$
8) $P\, ou\, (Q\, ou\, R) \Longleftrightarrow (P\, ou\, Q)\, ou\, R$
Propriétés 3. Formules de distributivité du « et » et « ou »
Soient $P$, $Q$ et $R$ trois propositions logiques. Alors :
9) $P\, et\, (Q\, ou\, R) \Longleftrightarrow (P\, et\, Q)\, ou\, (P\, et\, R$
10) $P\, ou\, (Q\, et\, R) \Longleftrightarrow (P\, ou\, Q)\, et\, (P\, ou\, R$
Propriétés 4. Implications et équivalences
Soient $P$, $Q$ et $R$ trois propositions logiques. Alors :
L’équivalence est une double implication
11) $(P\Leftrightarrow Q)\Longleftrightarrow (P \Rightarrow Q)\, et\, (Q \Rightarrow P)$
Transitivité de l’implication
12) $(P\Rightarrow Q)\, et (Q\Rightarrow R) \Longleftrightarrow (P \Rightarrow R)$
Transitivité de l’équivalence
12) $(P\Rightarrow Q)\, et (Q\Rightarrow R) \Longleftrightarrow (P \Rightarrow R)$
Propriétés 4. Formules de la contraposée
Soient $P$ et $Q$deux propositions logiques. Alors :
13) $(P\Rightarrow Q)\Longleftrightarrow (non\, Q \Rightarrow non\, P)$
12) $(P \Longleftrightarrow Q) \Longleftrightarrow (non\, Q \Longleftrightarrow non\, P)$
3. La démonstration
Une démonstration est un ensemble structuré d’étapes correctes et ordonnées d’un raisonnement.
Dans une démonstration, chaque étape est soit un axiome (un fait acquis), soit l’application d’une règle de déduction qui permet d’affirmer qu’une proposition, à savoir la conclusion, est une conséquence logique d’une ou plusieurs autres propositions appelées les prémisses de la règle. Les prémisses sont soit des axiomes, soit des propositions déjà obtenues comme conclusions de l’application d’autres règles. Une proposition qui est la conclusion de l’étape ultime d’une démonstration est un théorème.
Le terme « preuve » est parfois employé comme un synonyme de démonstration par attraction de l’anglais proof. (Wikipedia)
4. Méthodes de raisonnement pour construire une démonstration
- Méthode de démonstration d’une conjonction logique
- Méthode de démonstration d’une disjonction logique
- Méthode de démonstration d’une implication logique
- Méthode de raisonnement par disjonction des cas
- Méthode de démonstration d’une équivalence
- Méthode de démonstration par double implication logique
- Méthode de démonstration par un contre-exemple
- Méthode de démonstration par l’absurde
- Méthode de raisonnement par récurrence