Voir la source de Logique et raisonnement mathématique

La '''logique''' est le fondement du raisonnement mathématique. 

== Introduction ==
{{citation bloc | Depuis les Grecs qui dit mathématique dit démonstration.|[[Nicolas Bourbaki]]|[[Éléments de mathématique]], in Introduction de Théorie des ensembles}}
La '''logique''' explique comment un fait ou une affirmation peut découler d'autres faits déjà admis.  Un [[:wikt: enchaînement|enchaînement]] de faits qui sont énoncés pour découler les uns des autres s'appelle une ''[[Démonstration (logique et mathématique)|démonstration]]''. On constate que ''calculer'' et ''démontrer'' sont les deux principales activités des [[mathématiques]].  Ici, nous nous intéressons à l'activité de démontrer.  Pour démontrer quelque chose, il faut  soit utiliser un langage spécifique (présenté dans d'autres articles spécialisés de Wikipédia, par exemple dans l'article [[déduction naturelle]]), soit garder le français avec un certain nombre de conventions qui ont pour but d'éliminer les erreurs et les ambiguïtés.  La logique est donc, en mathématiques,  la pratique de la ''rigueur'' ou de l{{'}}''exactitude'' dans la pensée.

== Des conventions de langage dans la pratique des mathématiques ==
Dès qu'on fait des mathématiques, on se place dans une théorie où l'on accepte un certain nombre de faits de base.  Dans les exemples qui suivent, les faits de base sont ceux de la théorie des [[Nombre réel|nombres réels]], où l'on connaît les propriétés de l'addition, de la multiplication, de la [[relation d'ordre]] etc.  Nous allons nous intéresser à l'enchaînement des raisonnements corrects que l'on peut faire à partir de ces faits de base acquis.
=== L'implication ===
Commençons par examiner deux faits :
:''premier fait'' :  <math> x = 2 </math>
:''deuxième fait'' : <math> x^2 - 3 x + 2 = 0</math>.
Le deuxième fait découle du premier fait.  En effet, si <math>x=2</math>, nous pouvons remplacer <math>x</math> par <math>2</math> dans l'expression {{nobr|<math> x^2 - 3 x + 2 = 0</math>}} et nous constatons que {{nobr|<math> 2^2-(3 \times 2)+ 2 = 0</math>}}. <br>Nous dirions donc que
:* <math> x = 2 </math> '''implique''' <math> x^2 - 3 x + 2 = 0</math> 
ou que
:* <math> x^2 - 3 x + 2 = 0</math> '''découle de''' <math> x = 2 </math>
On écrit aussi
:'''si''' &nbsp;&nbsp; <math> x = 2 </math> &nbsp;&nbsp; '''alors''' &nbsp;&nbsp; <math> x^2 - 3 x + 2 = 0</math> 
ou encore
:<math> x = 2 </math>  '''est suffisante''' pour que <math> x^2 - 3 x + 2 = 0</math> 
ou encore
:<math> x^2 - 3 x + 2 = 0</math> '''est nécessaire''' quand <math> x = 2 </math>.
Toutes ces formulations sont des conventions que les mathématiciens ont choisies<ref group="note">Voyez l'article [[Des nains sur des épaules de géants]].</ref> pour mettre de la rigueur dans leurs raisonnements. Dans ce que l'on vient de dire, ce qui lie <math> x = 2 </math> à <math> x^2 - 3 x + 2 = 0</math> s'appelle une '''implication'''. Plus précisément l'affirmation que cette implication est vraie s'appelle une déduction, une déduction est une étape de base d'une démonstration.

En fait, quand on écrit <math> x = 2 </math> '''implique''' <math> x^2 - 3 x + 2 = 0</math>  on s'aperçoit que <math> x = 2 </math> dit quelque chose de plus fort que  <math> x^2 - 3 x + 2 = 0</math>. En faisant une implication on perd de l'information.

=== La disjonction ===
En revanche, pouvons-nous dire 
:* <math> x^2 - 3 x + 2 = 0</math> '''implique''' <math> x = 2 </math> ?
Non, parce qu'avec <math> x = 1 </math> on peut affirmer aussi que {{nobr|<math> x^2 - 3 x + 2 = 0</math>}}, en effet  {{nobr|<math> 1^2-</math> (3 x 1 ) <math>+ 2 = 0</math>}}. Pour pouvoir dire quelque chose avec les affirmations <math> x = 2 </math> et <math> x = 1 </math>, il faut les combiner pour former un seul fait.  Ce fait est une nouvelle affirmation :
:<math> x = 2 </math> '''ou''' <math> x = 1 </math>. 
L'opération logique qui combine deux affirmations par un '''ou''' s'appelle une '''disjonction'''.

La théorie des [[Équation du second degré|équations du second degré]] nous dit que nous pouvons écrire :
: <math> x^2 - 3 x + 2 = 0</math> '''implique''' <math> x = 2 </math> '''ou''' <math> x = 1 </math>
ou encore
: '''si''' <math> x^2 - 3 x + 2 = 0</math> '''alors''' <math> x = 2 </math> '''ou''' <math> x = 1 </math>.

=== L'équivalence  ===
Comment combiner deux faits en disant qu'il n'y a pas d'information perdue quand on passe de l'un à l'autre ou de l'autre à l'un, en disant qu'ils affirment exactement la même chose? Sur les faits ci-dessus cela s'écrit :
:<math> x^2 - 3 x + 2 = 0</math> '''est équivalent à''' <math> x = 2 </math> '''ou''' <math> x = 1 </math>
ou bien
:<math> x^2 - 3 x + 2 = 0</math> '''si et seulement si''' <math> x = 2 </math> '''ou''' <math> x = 1 </math>
ou bien
:<math> x^2 - 3 x + 2 = 0</math> '''est nécessaire et suffisant''' pour que <math> x = 2 </math> '''ou''' <math> x = 1 </math>
ou bien
:<math> x^2 - 3 x + 2 = 0</math> '''est une condition nécessaire et suffisante''' pour que <math> x = 2 </math> '''ou''' <math> x = 1 </math>.
Cette combinaison s'appelle une '''équivalence'''. 
Comme une équivalence va dans les deux sens on peut aussi écrire :
:<math> x = 2 </math> '''ou''' <math> x = 1 </math> '''est équivalent à''' {{nobr|<math> x^2 - 3 x + 2 = 0</math>}} 
ou bien
:<math> x = 2 </math> '''ou''' <math> x = 1 </math> '''si et seulement si''' {{nobr|<math> x^2 - 3 x + 2 = 0</math>}} 
ou bien encore
:<math> x = 2 </math> '''ou''' <math> x = 1 </math> '''ssi''' {{nobr|<math> x^2 - 3 x + 2 = 0</math>}} qui est une forme raccourcie du précédent, etc.

=== Propositions et connecteurs  ===
Jusqu’ici, nous avons parlé de ''faits'' ou d’''affirmations''. En logique, on emploie dans ce cas, le nom de '''proposition'''. Ainsi <math>x=2</math> est une proposition.   
On peut même donner aux propositions des noms qui sont des lettres, par exemple, on pourra écrire  <math>A</math> '''implique''' <math>B</math>.   
On peut voir donc que <math>A</math> '''implique''' <math>B</math> fonctionne un peu comme <math>x + y</math> en arithmétique.  On peut donc aussi « calculer » sur les propositions, on parle d'ailleurs de '''[[calcul des propositions]]''' quand on parle de cette façon de calculer.   Mais à la différence de l'arithmétique, où on dit que <math>+</math> est un opérateur, on dit que '''implique''' est un '''[[Connecteur logique|connecteur]]'''<ref group="note">Il s'agit d'un emprunt à la linguistique où ce terme existe et signifie « mot qui connecte des expressions ».</ref>.   C'est plus une question d'habitude, chez les logiciens, que vraiment un concept différent.  Nous avons vu trois connecteurs : 
:* '''implique''', 
:* '''ou''', 
:* '''équivalent'''.
En arithmétique, on n'écrit pas <math>x</math> '''plus''' <math>y</math>, mais bien <math>x + y</math>. En calcul des propositions, on utilise des notations comme <math>+</math> pour les connecteurs et on écrit
:* <math>A \Rightarrow B</math> pour <math>A</math> '''implique''' <math>B</math>,
:* <math>A \vee B</math> pour <math>A</math> '''ou''' <math>B</math>,
:* <math>A \Leftrightarrow B</math> pour <math>A</math> '''équivalent à''' <math>B</math>,
=== La négation ===
On ne peut pas dire que <math>x=1</math> '''implique''' <math>x=2</math>. Par contre on peut dire que si <math>x</math> vaut <math>1</math> alors <math>x</math> ne vaut pas <math>2</math>: pour cela il faut pouvoir dire que l'on n'a pas <math>x=2</math>. Pour cela, on introduit un connecteur qui ressemble au <math>-</math> unaire en arithmétique, celui qui remplace <math>1</math> par <math>-1</math>. Ce connecteur est appelé la '''négation''' et se note '''non'''. On peut donc écrire :
:<math>x=1</math> '''implique''' '''non''' <math>x=2</math>
ou encore 
:'''si''' <math>x=1</math> '''alors''' '''non''' <math>x=2</math>.
La notation formelle de '''non''' est <math>\neg</math>. On écrira <math>\neg (x =2)</math> au lieu de '''non''' <math>x=2</math>.  Mais 
très souvent, on utilisera une écriture encore plus condensée, à savoir <math>x\neq 2</math>.

=== La conjonction ===
Nous avons vu que l'on ne peut pas affirmer que 
:<math>x^2 -  3 x + 2 =0</math> '''implique''' <math>x = 2 </math>, 
par contre on peut renforcer la première proposition (celle qui est à gauche du '''implique''') en disant que l'on cherche des <math>x</math> qui sont plus grands que <math>1</math>.  
Autrement dit, on veut ajouter la condition <math>x >1</math> à <math>x^2 -  3 x + 2 =0</math>. Pour cela on crée la proposition : 
: <math>x^2 -  3 x + 2 =0</math>  '''et''' <math>x >1</math>.
On a introduit un nouveau connecteur '''et''' et grâce à lui on peut énoncer :
: <math>x^2 -  3 x + 2 =0</math>  '''et''' <math>x >1</math> '''implique''' <math>x = 2 </math>.  
Là nous commençons à entrevoir un petit problème.  Est-ce que dans la proposition précédente nous avons voulu dire que nous avions d'une part
:<math>x^2 -  3 x + 2 =0</math>
et d'autre part,
:<math>x >1</math> '''implique''' <math>x = 2 </math>
ou bien est-ce que nous avons voulu dire que
: <math>x^2 -  3 x + 2 =0</math>  '''et''' <math>x >1</math>
implique 
:<math>x = 2 </math> ?
C'est bien la deuxième intention que nous avions en tête.  Pour lever toute ambiguïté, on utilise des parenthèses et on écrit :
: (<math>x^2 -  3 x + 2 =0</math>  '''et''' <math>x >1</math>) '''implique''' <math>x = 2 </math>.
Le '''et''' se note formellement <math>\wedge</math>. Ainsi la proposition ci-dessus peut s'écrire<ref group="note">Ce n'est pas du bon style mathématique de mélanger dans la même phrase des notations formelles comme <math>\neg</math> ou <math>\Rightarrow</math> et du français !</ref> :
:<math>(x^2 -  3 x + 2 =0 ~\wedge~ x >1) ~~\Rightarrow~~ x = 2 </math>.

== Des propositions valables quelque part et des propositions valables partout ==
<!-- Ici on introduit les quantificateurs. -->

Supposons que l'on ne veuille pas dire la proposition A vue plus haut: 
:''pour <math>1</math> ou pour <math>2</math> l'expression <math>x^2 - 3x +2</math> s'annule'' 
mais une autre proposition: 
:'' il y a un entier naturel quelque part (c'est-à-dire un <math>x\in \mathbb{N}</math>) pour lequel cette expression s'annule''. 

Nous écrirons : 
:{{nobr| '''Il existe''' <math>x\in \mathbb{N}</math> '''tel que'''  <math>x^2 - 3x +2 = 0</math>}}.
« '''Il existe''' » s'appelle un '''quantificateur'''.  <br>Grâce à cette nouvelle construction logique, parce que nous savons que <math>2</math> annule {{nobr|<math>x^2 - 3x +2</math>}}, <br>nous pouvons écrire une proposition qui énonce qu'il y a un [[entier naturel]] qui annule <math>x^2 - 3x +2</math> :
:(<math>x=2</math> '''implique''' <math>x^2 - 3x +2 =0</math>) &nbsp;&nbsp; '''implique''' &nbsp;&nbsp; ('''Il existe''' <math>x\in \mathbb{N}</math> '''tel que'''  <math>x^2 - 3x +2 = 0</math>).

Si, maintenant, je considère l'expression {{nobr|<math>x^2 + 3x +2</math>}}, je ne peux pas affirmer qu'il existe un {{nobr|<math>x\in \mathbb{N}</math>}} qui l'annule. <br>Mais en revanche, je peux dire que pour tous les entiers naturels, elle ne s'annule pas.  J'écris alors
:'''Pour tout''' <math>x\in \mathbb{N}</math>, <math>x^2 + 3x +2\neq 0</math>.
« '''Pour tout''' » est aussi un '''quantificateur'''.  On peut aussi écrire: '''Quel que soit''' {{nobr|<math>x\in \mathbb{N}</math>, <math>x^2 + 3x +2\neq 0</math>}}. Et encore: {{nobr|'''∀''' <math>x\in \mathbb{N}</math>, <math>x^2 + 3x +2\neq 0</math>}} dans la formulation qui ne veut pas mélanger le français avec la langue mathématique.

== Des règles pour raisonner ==
Pour pouvoir raisonner il nous faut quelques règles.  Par exemple il y a des règles sur l'implication, auxquelles les logiciens ont donné des noms.

=== Modus ponens ===
Ainsi nous pouvons dire que si nous avons <math>A</math> et si nous avons <math>A</math> '''implique''' <math>B</math> alors nous avons <math>B</math>.   Cela veut dire que si nous avons pour but de démontrer <math>B</math>, alors nous pourrons nous donner deux sous-buts (deux buts intermédiaires)<ref group="note">Lors de la [[coupe du monde de football 2018#Tableau final|dernière coupe du monde de football en 2018 ]], pour que la France soit championne en vainquant la Croatie, il fallait comme sous-objectifs que la France vainque la Belgique et que la Croatie vainque l'Angleterre.</ref> : démontrer <math>A</math> et démontrer <math>A</math> '''implique''' <math>B</math>, alors seulement nous pourrons en utilisant la règle ci-dessus démontrer <math>B</math>.  Comme dans le deuxième sous-but, on avait une implication et que dans le but final, il n'y a plus d'implication. On appelle cette règle le ''[[modus ponens]]''.

Par exemple, supposons que nous ayons démontré<ref group="note">Par exemple, parce que <math>x = 1+1</math>.</ref>  que <math>x = 2</math> et puisque nous avons <math> x = 2 </math> '''implique''' <math> x^2 - 3 x + 2 = 0</math>, nous pouvons en déduire que <math> x^2 - 3 x + 2 = 0</math>.

=== L'introduction de l'implication ===
Comme on vient de le voir, il faut que nous ayons des moyens de démontrer des implications.  On utilise pour cela une règle qui « introduit » une implication.  Elle fonctionne comme suit. Mettons que nous voulions démontrer <math>A</math> '''implique''' <math>B</math>.  Nous ajoutons <math>A</math> à nos hypothèses admises et nous essayons de démontrer <math>B</math>.  Si nous réussissons, nous pouvons affirmer <math>A</math> '''implique''' <math>B</math> et nous pouvons l'utiliser par la suite.

Il y a des règles pour les autres connecteurs comme '''ou''' ou '''et''', mais aussi pour les quantificateurs.

== La construction des raisonnements mathématiques ==
L’existence de raisonnements mathématiques corrects est une chose, mais la construction de tels raisonnements corrects en est une autre. La question se pose donc de fournir aux mathématiciens ou aux élèves des méthodes pour fabriquer des démonstrations.  Voici donc quelques [[Heuristique (mathématiques)|heuristiques]] (outils d'aide à la construction de raisonnements) qu'ont les mathématiciens pour les aider à élaborer des démonstrations.   Quelques mathématiciens, comme [[Henri Poincaré]], [[George Pólya]], [[Martin Gardner]] ou [[Terence Tao]]  ont tenté de décrire dans des livres, leur démarche et celle de leurs collègues telle qu'ils la conçoivent. 

=== Induction ===
Dans l'induction, le mathématicien part de constats expérimentaux, puis les généralise en trouvant une {{cita|loi}} qui les unifie. 
Par exemple, on constate que si l'on trace un triangle dont l'un des côtés est le diamètre d'un cercle, et les 3 sommets de ce triangle coïncident avec la périphérie du cercle, alors ce triangle est rectangle<ref group="note">Le terme {{cita|induction}} est très surchargé en mathématique et en logique mathématique, car il peut recouvrir le concept présenté ici, mais aussi le concept de ''[[raisonnement par récurrence]]'', appelé aussi ''raisonnement par induction'' ou parfois simplement ''induction''. On veillera donc à savoir quel concept on considère.</ref>.  L{{'}}''induction''  est une [[Heuristique (mathématiques)|heuristique]], c'est-à-dire une méthode qui aide à construire ensuite un raisonnement mathématique rigoureux ; en aucun cas elle ne constitue une démonstration mathématique.

=== Déduction ===
{{Article détaillé|Raisonnement déductif|Déduction logique}}
Dans la déduction, on part d'hypothèses et on essaye de construire des enchaînements logiques pour aboutir à la démonstration du théorème.  Cette démarche peut conduire à un point où il n'y a plus de nouvelle déduction à faire sans qu'une démonstration ait été atteinte (voie sans issue). Cela nécessite un retour en arrière pour emprunter une autre voie (c'est-à-dire une autre déduction).  Cette approche purement déductive peut-être coûteuse, parce que le nombre de voies à explorer est extrêmement grand.  Il peut être intéressant alors d'avoir une idée même intuitive et incomplète de la {{cita | bonne}} direction et de {{cita  | mesurer}} de combien on se rapproche de la solution (voir [[Retour sur trace]]).  La déduction doit donc être combinée avec d’autres heuristiques.

=== Disjonction de cas ===
{{Article détaillé|Raisonnement par disjonction de cas}}
On cherche une démonstration en scindant le problème en cas.

'''''Exemple''''' : A-t-on, pour tout entier naturel <math>n</math>, <math>n^2+n</math> pair?

La proposition est : ''{{cita | <math>n^2+n</math> est pair pour tout entier naturel n}}''

L'heuristique est : ''{{cita|on raisonne par disjonction des cas}}''. 

Cas 1 : on considère <math>n</math> pair, soit <math>n=2k</math> avec <math>k</math> un entier naturel.

<math>n^2+n=(2k)^2+2k=4k^2+2k=2*(2k+k)</math>  qui est un nombre pair.

Cas 2 : on considère <math>n</math> impair, soit <math>n=2k+1</math> avec <math>k</math> un entier naturel.

<math>n^2+n=(2k+1)^2+2k+1=4k^2+4k+1+2k+1=2(2k^2+3k+1)</math> qui est un nombre pair.
Ainsi, pour tout entier naturel <math>n</math> (pair ou impair), on a <math>n^2+n</math> pair.

Si on a une démonstration pour chacun des  cas, on a une démonstration du problème général.

=== Par l'absurde ===
{{Article détaillé|Raisonnement par l'absurde}}
On suppose la négation de ce que l'on veut montrer, puis on montre que cela conduit à une absurdité.

=== Contraposition ===
{{Article détaillé|Proposition contraposée}}
Au lieu de montrer que ''A'' implique ''B'' on montre que la négation de ''B'' implique la négation de ''A''.

=== Récurrence ===
{{Article détaillé|Raisonnement par récurrence}}
Par un processus par étape, on démontre qu'une propriété est vraie pour tous les entiers ou pour toute structure mathématique qui ressemble aux entiers.

=== Analyse-synthèse ===
{{Article détaillé|Raisonnement par analyse-synthèse}}
On analyse des solutions candidates potentielles et l'on élimine, parmi celles-ci, celles qui ne sont pas d'authentiques solutions. On obtient ainsi une véritable démonstration parmi les candidates non éliminées.

===Par hypothèse auxiliaire===
{{loupe|Règle de coupure}}
Cette méthode de démonstration s'appuie sur le modus ponens {{supra|Modus ponens}}<ref>{{Ouvrage|titre=Algèbre et analyse|sous-titre=cours de mathématiques de première année avec exercices corrigés|auteur=S. Balac|auteur2=F. Sturm|éditeur=[[PPUR]]|date=2003|url={{Google Livres|-LbuKvfK9AkC|page=16}}|page=16}}.</ref> {{,}}<ref>{{Ouvrage|titre=Mathématiques pour les sciences de l'ingénieur|numéro d'édition=2|auteur=F. Bertrand|et al.=oui|éditeur=[[Dunod]]|date=2019|url={{Google Livres|Xy2oDwAAQBAJ|page=7}}|page=7}}.</ref>: pour démontrer ''Q'', il suffit de démontrer d'une part ''P'' (l'« hypothèse auxiliaire ») et d'autre part ''P'' ⇒ ''Q''.

Le [[théorème d'élimination des coupures]] démontre que cette "hypothèse auxiliaire" utilisée dans la démonstration peut toujours être contournée. L'idée étant que si par exemple avec le ''modus ponens'' qui est un cas particulier de la [[règle de coupure]], dans un contexte (soit une théorie mathématique), on a besoin de A et de A implique B pour démontrer B, alors on peut trouver dans ce contexte, une preuve directe de B sans faire intervenir A.

L'utilisation d'une hypothèse auxiliaire correspond à un raccourci dans la longueur d'une démonstration, au sens où transformer une [[démonstration formelle]] utilisant la règle de coupure en une démonstration ne l'utilisant pas amène bien souvent à une démonstration utilisant exponentiellement plus de fois les [[Règle d'inférence|règles d'inférence]] d'un système à la [[Gerhard Gentzen|Gentzen]] comme la [[déduction naturelle]].

== Démonstrations élégantes ==
{{article détaillé|Longueur d'une démonstration|Beauté mathématique|Complexité des preuves}}
{{...}}
Outre la correction formelle, les mathématiciens s'accordent à juger certaines démonstrations (du même résultat) plus élégantes que d'autres, souvent parce qu'elles sont plus courtes, mais aussi par l'ingéniosité des arguments utilisés, ou par l'apparition de relations cachées avec d'autres résultats déjà connus.  Les cinq auteurs cités dans la bibliographie (à savoir [[Martin Gardner]], [[Terence Tao]], [[George Pólya]], [[Martin Aigner]] et [[Günter M. Ziegler|Günter Ziegler]]) se sont intéressés aux démonstrations élégantes. Il faut y ajouter [[Paul Erdős]] qui est à l'origine de la notion de ''démonstrations divines'' (''démonstrations qui vient du Livre'' ou ''proofs from the Book'') décrites par [[Martin Aigner]] et [[Günter M. Ziegler|Günther Ziegler]].

== Notes et références ==
=== Notes ===
{{Notes}}
=== Références ===
{{Références}}

== Bibliographie ==
* {{Ouvrage|langue originale=en|auteur1=[[Martin Gardner]]|traducteur=Jeanne Peiffer|titre=Haha ou l'Éclair de la compréhension mathématique|titre original=Aha! Insight (1978)|éditeur=[[Éditions Belin|Belin]] - [[Pour la Science]]|année=1979|isbn=978-2-902918-06-5}}

* {{Ouvrage
| auteur1=[[Terence Tao]]
| titre=Solving Mathematical Problems
| sous-titre=A Personal Perspective
| éditeur=[[Oxford University Press]]
| année=2006
| pages totales=103
| isbn=978-0-19-920560-8
| lire en ligne=https://books.google.fr/books?id=SR4m7FxqsRsC&printsec=frontcover
}}

* [[George Polya]], ''Comment poser et résoudre un problème'', {{2e}} éd., 1965, nouveau tirage 2007 {{ISBN|978-2-87647-049-1}}, traduction de <cite lang=en>How to Solve It</cite>, 1957 (traduit en 17 langues)
*  [[Martin Aigner]] et [[Günter M. Ziegler]] [[Raisonnements divins]] (exemples de démonstrations élégantes).

== Voir aussi ==
* [[Calcul des propositions]]
* [[Calcul des prédicats]]
* [[Déduction naturelle]]
* [[Style de Fitch pour la déduction naturelle]]
* [[Calcul des séquents]]
* [[Système à la Hilbert]]

{{Palette|Logique|Mathématiques élémentaires}}
{{Portail|mathématiques|logique}}

[[Catégorie:Logique mathématique|*]]