01. Fondements et Histoire
Origines de la logique formelle, d'Aristote à Frege, et motivations pour l'étude rigoureuse du raisonnement.
Qu’est-ce que la logique?
La logique est l’étude des principes du raisonnement valide. Elle cherche à répondre à une question fondamentale: qu’est-ce qui fait qu’un argument est correct?
Un argument est une séquence d’énoncés où certains (les prémisses) sont supposés justifier un autre (la conclusion). La logique ne s’intéresse pas à la vérité des prémisses elles-mêmes, mais à la validité de l’inférence: si les prémisses sont vraies, la conclusion doit-elle nécessairement l’être?
Exemple d’argument valide:
- Tous les hommes sont mortels. (prémisse)
- Socrate est un homme. (prémisse)
- Donc, Socrate est mortel. (conclusion)
Cet argument est valide car il est impossible que les prémisses soient vraies et la conclusion fausse. La validité est une propriété structurelle — elle ne dépend pas du contenu spécifique mais de la forme de l’argument.
Brève histoire de la logique
La logique aristotélicienne (IVe siècle av. J.-C.)
Aristote est considéré comme le fondateur de la logique en tant que discipline. Dans l’Organon, il développe la théorie du syllogisme — un type d’argument à deux prémisses et une conclusion.
La forme canonique du syllogisme:
- Majeure: Tous les $M$ sont $P$
- Mineure: Tous les S sont M
- Conclusion: Tous les S sont P
Aristote identifie les figures et modes valides du syllogisme, créant le premier système formel de l’histoire. Cette logique dominera pendant plus de deux millénaires.
Les limites de la logique aristotélicienne
Malgré sa puissance, le syllogisme ne peut exprimer certains raisonnements courants:
- Les relations: “Si Jean est plus grand que Pierre, et Pierre plus grand que Marc, alors Jean est plus grand que Marc.”
- Les propositions avec quantification multiple: “Chaque nombre a un successeur.”
- Les inférences mathématiques complexes.
La révolution du XIXe siècle
George Boole (1815-1864) transforme la logique en introduisant l’algèbre booléenne. Il montre que les opérations logiques (ET, OU, NON) obéissent à des lois algébriques, permettant de calculer avec des propositions comme on calcule avec des nombres.
Gottlob Frege (1848-1925) crée la Begriffsschrift (1879), le premier système complet de logique des prédicats. Ses innovations:
- La distinction fonction/argument appliquée aux propositions
- Les quantificateurs $\forall$ (pour tout) et $\exists$ (il existe)
- Un système de preuve formel avec des règles d’inférence explicites
Le travail de Frege permet d’exprimer toute la logique mathématique dans un langage formel précis.
Le XXe siècle et l’informatique
Les théorèmes d’incomplétude de Kurt Gödel (1931) révèlent les limites intrinsèques des systèmes formels: tout système assez puissant pour exprimer l’arithmétique contient des énoncés vrais mais indémontrables.
Alan Turing (1936) utilise la logique pour définir rigoureusement la notion de calcul, posant les fondations de l’informatique théorique. La machine de Turing est essentiellement un système formel qui manipule des symboles selon des règles logiques.
Aujourd’hui, la logique est indispensable en:
- Vérification formelle: prouver qu’un programme est correct
- Intelligence artificielle: systèmes de raisonnement automatique
- Bases de données: SQL repose sur la logique des prédicats
- Circuits numériques: les portes logiques implémentent l’algèbre booléenne
Logique formelle vs. logique informelle
La logique informelle étudie les arguments en langage naturel, avec attention aux sophismes, à la rhétorique, et au contexte.
La logique formelle (notre sujet) utilise un langage artificiel avec:
- Un alphabet de symboles
- Une grammaire définissant les formules bien formées
- Une sémantique assignant des significations aux formules
- Des règles d’inférence permettant de dériver des conclusions
L’avantage du formalisme: l’élimination de l’ambiguïté. Chaque étape d’un raisonnement peut être vérifiée mécaniquement.
Types de logiques
La logique n’est pas monolithique. Différents systèmes capturent différents aspects du raisonnement:
| Logique | Objets étudiés | Exemple |
|---|---|---|
| Propositionnelle | Propositions atomiques, connecteurs | $p \land q \rightarrow r$ |
| Prédicats (1er ordre) | Objets, prédicats, quantificateurs | $\forall x(H(x) \rightarrow M(x))$ |
| Modale | Nécessité, possibilité | $\Box p \rightarrow \Diamond p$ |
| Temporelle | Temps, séquences d’états | $Gp$ (p est toujours vrai) |
| Intuitionniste | Preuves constructives | Rejette le tiers exclu |
Ce cours se concentre sur la logique propositionnelle et la logique des prédicats du premier ordre — les fondations sur lesquelles reposent les autres.
Vocabulaire essentiel
- Proposition: énoncé déclaratif qui est soit vrai, soit faux
- Connecteur (ou opérateur): symbole combinant des propositions ($\land$, $\lor$, $\neg$, $\rightarrow$, $\leftrightarrow$)
- Formule: expression construite selon les règles grammaticales
- Interprétation: assignation de valeurs de vérité aux propositions atomiques
- Tautologie: formule vraie sous toute interprétation
- Contradiction: formule fausse sous toute interprétation
- Contingence: formule ni tautologique ni contradictoire
- Validité: propriété d’un argument où la conclusion suit nécessairement des prémisses
- Satisfiabilité: existence d’une interprétation rendant la formule vraie
Exercices de reflection
L’argument suivant est-il valide? “Tous les chats sont des mammiferes. Certains animaux domestiques sont des chats. Donc, certains animaux domestiques sont des mammiferes.”
mc:valide|invalide,correct:validePourquoi la phrase “Cette phrase est fausse” pose-t-elle probleme en logique classique?
mc:paradoxe|tautologie|contradiction,correct:paradoxeLa distinction entre validite et verite est:
mc:la meme chose|la validite concerne la forme|le contenu nest pas important,correct:la validite concerne la formeLes theoremes d’incompletude de Godel demonstrent que:
mc:tout systeme formel est complet|tout systeme assez puissant a des enonces indemontrables|tout systeme est incoherent,correct:tout systeme assez puissant a des enonces indemontrablesLa logique intuitionniste rejette:
mc:le tiers exclu|les quantificateurs|les connecteurs,correct:le tiers excluLa Begriffsschrift de Frege a introduce:
mc:les tables de verite|les quantificateurs|algebre booleenne,correct:les quantificateursUn argument valide peut avoir des premises fausses et une conclusion:
mc:vraie|fausse|autre,correct:vraieLa machine de Turing formalise le concept de:
mc:algorithme|hardware|programmation,correct:algorithmeLa logique modale etudie les notions de:
mc:necessite et possibilite|verite et faussete|quantification,correct:necessite et possibiliteEn logique aristotelicienne, un syllogisme valide dont les premises sont vraies:
mc:a toujours une conclusion fausse|peut avoir une conclusion vraie|autre,correct:a toujours une conclusion vraie