Logique (mathématiques)
Image manquante
Fairytale_info.png
lettre i
| Sommaire |
Les opérations logiques élémentaires
Les propositions et les objets mathématiques, sont des assemblages de symboles et de lettres formés en suivant certaines règles de logique. Les deux signes les plus simples qui servent à former des propositions sont ∨ et ¬ souvent notés ou et non en mathématiques. On peut montrer que seulement deux opérateurs sont nécessaires pour former toutes les propositions, par exemple ou et non.
La disjonction
La disjonction de deux proposition P et Q est la proposition notée P ∨ Q ou « P ou Q » qui est vraie si l’une au moins des deux propositions est vraie, et fausse si les deux propositions sont fausses.
La négation
La négation d’une proposition P, est la proposition notée ¬P, ou « non P » qui est vraie lorsque P est fausse et fausse lorsque P est vraie.
À partir de ces deux signes, nous pouvons construire d’autres symboles ou abréviations utiles :
La conjonction
Le conjonction de deux propositions P et Q est la proposition suivante :
- ¬((¬P) ∨ (¬Q)) c'est-à-dire non ( (non P) ou (non Q) )
Celle-ci est notée P ∧ Q ou « P et Q » et n’est vraie que lorsque P et Q sont vraies et fausse si l’une des deux propositions est fausse.
L'implication
L'implication de Q par P, est la proposition (¬P) ∨ Q, notée « P ⇒ Q » ou « P implique Q », et qui est fausse seulement si P est une proposition vraie et Q fausse.
Exemple : je vote, cela implique que je suis majeur. En effet, je peux être majeur sans voter, mais je ne peux pas voter sans être majeur. Notons que cette implication serait fausse si je pouvais voter sans être majeur.
L'équivalence
L'équivalence logique de P et Q est la proposition ( (P ⇒ Q) ∧ ( Q ⇒ P) ) ( ((P implique Q) et (Q implique P) )), notée « P ⇔ Q » ou (P est équivalent à Q).
Axiomes et théorèmes
Par assemblage, des symboles ou lettres introduites précédemment nous pouvons construire des propositions plus complexes, des assertions vraies ou des théorèmes ; et ainsi développer des théories. Mais nous devons au départ énoncer des propositions qui seront considérées, une fois pour toute, comme vraies et fixer des règles de transformation, permettant d’obtenir des propositions à partir d’autres. Ces propositions et règles de logique sont les axiomes. Toute proposition obtenue à partir d’un axiome ou d’une proposition vraie au moyen d’une implication sera considérée comme vraie.
Le calcul des prédicats
Substitution
Il est également possible de construire à partir d’une proposition P, d’autres propositions en remplaçant un objet mathématique indéterminé x dans la proposition partout où il intervient, par un autre objet mathématique a.
Par exemple, la proposition P : « 8 est un nombre pair », peut être représentée sous la forme P{8}, où P est le prédicat « est un nombre pair », et 8 est son argument.
Ou par exemple, la proposition « Les droites D et D’ sont parallèles » peut être représentée sous la forme P{D, D’} où P est le prédicat « sont parallèles » et les droites D et D’ sont les arguments.
Si P est une proposition, x un objet indéterminé, et a un objet mathématique, l’assemblage obtenu en remplaçant x par a dans P est encore une proposition notée
- (a|x)P
et s’appelle proposition obtenue par substitution de x par a dans P.
Pour mettre en évidence un objet indéterminé x dans une proposition P, on écrit la proposition sous la forme P{x} ; et on note P{a} la proposition (a|x)P.
Soit P une proposition, x un objet indéterminé, et a un objet mathématique donné. Si P est vraie, alors P{a} est vraie.
Et tout cela se généralise au cas de plusieurs objets indéterminés.
Les quantificateurs
Il existe encore un autre procédé logique, permettant de construire d’autres propositions à partir d’une proposition.
Soit une proposition P et x un objet indéterminé. Nous pouvons considérer la proposition :
- il existe un objet a, tel que (a|x)P soit vraie
c'est-à-dire
- il existe un objet a, tel que P{a} soit vraie
« il existe un objet » signifie intuitivement « nous pouvons trouver au moins un objet ».
Symboliquement, nous écrivons :
- ∃ a P
ou
- ∃ a P{a}
ce qui se lit :
- « il existe a tel que P »
Ce signe ∃ s’appelle le quantificateur existentiel.
Nous définissons, à partir de ∃ le symbole ∀ :
Soit P une proposition et x un objet indéterminé, la proposition notée ∀ x P est la proposition
- ¬( ∃x ¬P )
et se lit « pour tout x, P »
ou « quel que soit x, on a P vraie »
∀ s’appelle le quantificateur universel.
Évidemment, la proposition (∀ x P) est fausse si et seulement si (∃ x ¬ P) est vraie.
Utilisation des quantificateurs
Propriétés élémentaires
Soient P et Q deux propositions et x un objet indéterminé.
- ¬(∃ x P) ⇔ (∀ x ¬ P)
- (∀ x) (P∧Q) ⇔ ( (∀ x) P ∧ (∀ x) Q )
- (∀ x) P ∨ (∀ x) Q ⇒ (∀ x) (P ∨ Q )
(Implication réciproque fausse en général) - (∃ x) (P∨Q) ⇔ ( (∃ x) P ∨ (∃ x) Q )
- (∃ x) (P∧Q) ⇒ ( (∃ x) P ∧ (∃ x) Q )
(Implication réciproque fausse en général)
Propriétés utiles
Soient P une proposition et x un objet indéterminé.
- (∀ x) (∀ y) P⇔(∀ y) (∀ x) P
- (∃ x) (∃ y) P ⇔ (∃ y) (∃ x) P
- (∃ x) (∀ y) P⇒(∀ y) (∃ x) P
(Implication réciproque fausse)
La dernière implication dit que s’il existe un x, tel que pour tout y, on ait P vraie, alors pour tout y, il existe bien un x (celui obtenu avant) tel que P soit vraie.
Intuitivement, l’implication réciproque est fausse en général, parce que si pour chaque y, il existe un x tel que P soit vraie, ce x pourrait dépendre de y et varier suivant y. Ce x pourrait donc ne pas être le même pour tout y tel que P soit vraie.
Vers la théorie des ensembles
La théorie des ensembles est à la base de nombreuses théories mathématiques. Outre les symboles de logique énumérés précédemment, cette théorie utilise des autres symboles = et ∈ permettant de mettre des objets mathématiques en relation. Les objets mathématiques sont appelés des ensembles.
L’égalité
Le signe de l’égalité se note
- =
et représente la relation d’égalité entre objets mathématiques.
Nous nous contenterons de la définition intuitive :
Soient a et b deux objets. a=b signifie que a et b représentent des objets identiques, et se lit « a est égal à b »
≠ est définie par a ≠ b si ¬(a=b)
Propriétés :
- (∀ x) x=x vraie (réflexivité de =)
- (∀ x) (∀ y) (x=y ) ⇔ (y=x ) vraie (symétrie de =)
- (∀ x) (∀ y) (∀ z) ((x=y) ∧ (y=z))⇒x=z (transitivité de =)
La relation = étant réflexive, symétrique et transitive, on dit que la relation = est une relation d'équivalence
- Soit P{x} une proposition contenant un objet indéterminé x. Soient a et b des objets tels que a=b. Alors les propositions P{a} et P{b} (obtenues en remplaçant respectivement x par a et x par b dans P{x}) sont équivalentes.
L’appartenance
Le signe de l’appartenance se note :
- ∈
et représente la relation d’appartenance d’un objet à un autre.
Si a et b sont deux objets a ∈ b se lit :
- « a appartient à b »
ou encore
- « a est élément de b »
∉ se définit par a ∉ b si ¬(a ∈ b) vraie.
a ∉ b se lit « a n’appartient pas à b »
Théorème :
Soient a et b deux objets mathématiques.
- a=b ⇔ ( (∀x) (x ∈ a ⇔ x ∈ b) )
Pour les régles d'utilisation de ces symboles reportez vous à l'article langage formel mathématique.
Historique
Le nom fut donné par Giuseppe Peano. Pour l'essentiel c'est encore la logique d'Aristote mais écrit comme une branche de l'algèbre abstraite.
Ce fut George Boole et Auguste De Morgan, vers le milieu du XIXe siècle, pour laquelle une mathématique -- bien que non-quantitatif -- façon de regarder la logique devait être fait. Par cela, non seulement la doctrine traditionelle ou aristotélicienne de la logique fut réformée et complétée, mais de cela ils ont développés un instrument qui traite d'une manière certaine avec la tâche d'enqueter les concepts fondamentaux des mathématiques -- une tâche que les philosophes ont constamment examinés, et pour laquelle ils ont aussi souvent échoués -- bien que ce soit trompeur de dire que les controverses qui avaient lieu dans la période 1900-1925 avaient toutes été résolues. (voir aussi mathématiques)
Bien que le développement traditionnel de la logique (voir liste des sujets en logique place une forte emphase sur la forme des arguments, l'attitude de la logique mathématique courante peut être résumée comme l'étude combinatoire du contenu. Ceci couvre à la fois le syntactique (par exemple, envoyer une chaîne de caractères d'une langue naturelle à un compilateur pour écrire comme une séquence d'instructions d'ordinateur) et la sémantique (construction des modèles spécifiques ou de leurs ensembles complets, dans la théorie du modèle.
La plus grande partie de la matière dépend de l'existence d'algorithmes efficaces pour vérifier les preuves. Cela n'est pas souligné dans les traitements traditionels: cela pourrait changer comme les programmes progressent et l'exposition commence à rattraper.
Les résultats d'instauration
Quelques résultats importants, tous découvert pendant les années 1930, sont:
- des preuves putatives de la validité universelle des formules du premier ordre peuvent être vérifiées rapidement pour la validité, par algorithme. En langage technique, l'ensemble des preuves est une primitive récursive. Essentiellement, c'est le théorème d'incomplétude de Gödel, bien que ce théorème soit habituellement présenté d'une manière qui ne rend pas évident qu'il ait quelque chose à voir avec les algorithmes.
- l'ensemble des formules du premier ordre n'est pas calculable, càd, qu'il n'y a pas d'algorithmes pour vérifier une validité universelle. Il y a, cependant, un algorithme qui se comporte de cette façon: donnant une formule du premier ordre en entrée, l'algorithme éventuellent s'interrompt si la formule est universellement valide, et continue pour toujours autrement. Si l'algorithme est utilisé depuis des milliards d'années la réponse reste inconnue. En d'autres mots, cet ensemble est « récursivement énumérable » ou comme c'est quequefois dit plus suggestivement « semi-décidable ».
- L'ensemble de toutes les formules universellement valides de second ordre n'est pas énumérable même récursivement. Ceci est une conséquence du théorème de l'incomplétude.