Logique & Arithmétique · L1 · Section 1/2
Bases de la logique
Progression
#Introduction à la logique
La logique mathématique fournit le cadre formel dans lequel s'expriment toutes les théories mathématiques. Elle définit rigoureusement ce qu'est une proposition vraie et ce qu'est une démonstration valide. Bien au-delà des mathématiques, la logique est le fondement de l'informatique : chaque circuit électronique, chaque algorithme, chaque programme repose sur les connecteurs logiques étudiés ici.
#Prérequis et objectifs
Prérequis. Aucun prérequis mathématique spécifique ; les manipulations algébriques du lycée suffisent.
Objectifs. Distinguer proposition et prédicat, construire et lire les tables de vérité des connecteurs, nier correctement une proposition quantifiée, et choisir le type de raisonnement adapté à un énoncé (direct, contraposée, absurde, disjonction, récurrence).
#Logique propositionnelle
#Proposition
Une proposition (ou assertion) est un énoncé mathématique qui peut être soit vrai, soit faux, mais jamais les deux à la fois. Cette propriété, le principe du tiers exclu, affirme qu'il n'existe pas de troisième état entre vrai et faux.
Exemples de propositions :
- « » est une proposition vraie.
- « » est une proposition fausse.
- « Paris est la capitale de la France » est une proposition vraie.
Attention : « » n'est pas une proposition, car sa valeur de vérité dépend de . C'est un prédicat, noté . Le prédicat devient une proposition une fois que est fixé à une valeur particulière ou quantifié sur un ensemble.
De même, « cette phrase est fausse » n'est pas une proposition : lui attribuer « vrai » ou « faux » conduit à une contradiction. La logique classique exclut les énoncés autoréférents.
#Connecteurs logiques
On construit des propositions complexes à partir de propositions élémentaires et à l'aide de connecteurs logiques. Leur sens est défini par des tables de vérité qui spécifient la valeur de la proposition composée pour chaque combinaison possible des valeurs de et .
1. Négation (NON)
La négation de , notée ou , est vraie si et seulement si est fausse. C'est le connecteur le plus simple : il inverse la valeur de vérité.
| V | F |
| F | V |
2. Conjonction (ET)
La conjonction (lue « P et Q ») est vraie uniquement lorsque et sont toutes deux vraies. C'est l'opérateur le plus restrictif : une seule condition fausse suffit à rendre le résultat faux.
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | F |
3. Disjonction (OU)
La disjonction (lue « P ou Q ») est vraie dès que l'une des deux propositions est vraie. C'est un ou inclusif : la proposition est vraie aussi lorsque les deux sont vraies. En mathématiques, « ou » signifie toujours « au moins l'un des deux », contrairement à l'usage courant.
| V | V | V |
| V | F | V |
| F | V | V |
| F | F | F |
4. Implication
L'implication (lue « P implique Q » ou « si P alors Q ») est le connecteur le plus important en mathématiques. Elle est fausse uniquement lorsque est vraie et est fausse. Dans tous les autres cas, elle est vraie.
| V | V | V |
| V | F | F |
| F | V | V |
| F | F | V |
Cette définition peut surprendre : pourquoi l'implication est-elle vraie quand est fausse ? Considérons la promesse « S'il pleut, je prends mon parapluie ». Cette promesse n'est violée que s'il pleut et que je ne prends pas mon parapluie. S'il ne pleut pas, je n'ai rien promis : je ne peux pas mentir, quelle que soit ma conduite.
Vocabulaire :
- est l'hypothèse ; c'est une condition suffisante pour ;
- est la conclusion ; c'est une condition nécessaire à .
Propriété fondamentale : est logiquement équivalent à (vérification immédiate sur les tables : les deux formules sont fausses dans le seul cas vrai, faux).
5. Équivalence
L'équivalence (lue « P si et seulement si Q ») est vraie lorsque et ont la même valeur de vérité. Elle correspond à une double implication :
Démontrer une équivalence demande donc en général deux implications, traitées séparément.
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | V |
#Lois de De Morgan et équivalences utiles
Deux identités reviennent constamment, dans les preuves comme dans la simplification de circuits :
Vérification sur un cas : si est fausse et vraie, alors est fausse donc vraie ; à droite, = vrai ou faux = vrai. Cohérent. Le lecteur vérifiera les trois autres cas.
Autres équivalences essentielles :
À retenir : la négation d'une implication n'est jamais une implication, c'est une conjonction.
#Constructeur de tables de vérité
Utilisez l'outil interactif ci-dessous pour explorer les tables de vérité de n'importe quelle formule logique. Entrez une expression utilisant les variables (p, q, r...) et les opérateurs (! pour la négation, & pour ET, | pour OU, -> pour l'implication, <-> pour l'équivalence).
Essayez ces expressions classiques :
!p | q: équivalent à(p -> q) <-> (!p | q): toujours vraie (tautologie)p & !p: toujours fausse (contradiction)!(p & q) <-> (!p | !q): loi de De Morgan
#Quantificateurs
Les quantificateurs précisent l'étendue de validité d'un prédicat où appartient à un ensemble . Ils transforment un prédicat (dont la valeur dépend de ) en une proposition (dont la valeur est fixée).
#Quantificateur universel ()
L'énoncé « » se lit « Pour tout appartenant à , est vraie ». Cette proposition affirme que la propriété est vérifiée pour tous les éléments de l'ensemble, sans exception.
Pour montrer qu'une proposition universelle est vraie, il faut démontrer pour un élément arbitraire de (« Soit ... »). Pour montrer qu'elle est fausse, il suffit d'exhiber un seul contre-exemple : un élément tel que soit fausse.
#Quantificateur existentiel ()
L'énoncé « » se lit « Il existe (au moins) un appartenant à tel que soit vraie ». On la prouve en exhibant un témoin explicite ; on la réfute en montrant que tous les éléments la violent.
La notation (« il existe un unique ») signifie qu'il existe exactement un élément vérifiant la propriété. La preuve d'unicité se fait en supposant deux témoins et et en montrant .
#Négation des quantificateurs
La négation d'une proposition quantifiée inverse le quantificateur et nie le prédicat :
Exemple concret : la négation de « Tous les cygnes sont blancs » n'est pas « Aucun cygne n'est blanc », mais « Il existe au moins un cygne qui n'est pas blanc ». Une seule exception suffit à réfuter une affirmation universelle.
Exemple mathématique : la négation de « » est « ». Ce schéma est exactement celui utilisé pour définir les limites.
#Ordre des quantificateurs
L'ordre des quantificateurs différents ne s'échange jamais gratuitement :
Règle de lecture : dans , le peut dépendre de ; dans , un même doit convenir pour tous les . Cette distinction est omniprésente dans les définitions de limite, de continuité uniforme et d'injectivité/surjectivité.
#Types de raisonnement
La logique fournit plusieurs techniques de démonstration. Le choix de la méthode dépend de la structure de l'énoncé à prouver.
#1. Raisonnement direct
On part de l'hypothèse et on enchaîne les implications pour arriver à la conclusion . C'est la méthode la plus fréquente.
Exemple : montrer que si est pair, alors est pair.
- Hypothèse : pour un entier .
- Alors , qui est pair. ∎
#2. Contraposée
Pour montrer , on démontre l'implication contraposée , qui lui est logiquement équivalente (même table de vérité). Cette technique est utile quand la négation de la conclusion offre un point de départ plus exploitable.
Exemple : montrer que si est impair, alors est impair.
- Contraposée : si est pair, alors est pair.
- Cette implication vient d'être démontrée ci-dessus. ∎
Autre exemple : si est impair, montrer directement « impair » exigerait d'examiner la parité de sans information exploitable ; la contraposée contourne l'obstacle.
#3. Raisonnement par l'absurde
On suppose que la proposition à démontrer est fausse, et on montre que cette hypothèse conduit à une contradiction logique. La proposition doit donc être vraie (son faux est impossible). Formellement : .
Exemple célèbre : irrationalité de .
- Supposons avec entiers premiers entre eux, .
- Alors , donc est pair, donc est pair (contraposée du résultat sur les carrés).
- Écrivons . Alors , donc , donc est pair.
- Contradiction : et sont tous deux pairs, donc non premiers entre eux alors que la fraction était supposée irréductible. ∎
#4. Disjonction de cas
On partitionne l'ensemble des cas possibles et on traite chaque cas séparément. La preuve n'est complète que si tous les cas sont couverts.
Exemple : montrer que pour tout entier , est pair.
- Si est pair, et , pair.
- Si est impair, est pair, et , pair.
- Tout entier est soit pair soit impair : les deux cas couvrent tout. ∎
#5. Récurrence
Pour montrer qu'une propriété est vraie pour tout entier naturel :
- Initialisation : vérifier que est vraie.
- Hérédité : supposer vraie pour un fixé (hypothèse de récurrence), et montrer .
- Conclusion : par le principe de récurrence, .
Exemple : montrer que .
- Initialisation : pour , .
- Hérédité : supposons la formule vraie au rang . Alors :
qui est la formule au rang . ∎
- Vérification numérique : : ; : la formule donne 55, et l'addition directe confirme.
Piège classique : l'hérédité sans initialisation ne prouve rien. La propriété « après avoir ajouté 1 des deux côtés » est héréditaire mais jamais initialisée : l'échec de l'initialisation bloque la conclusion.
#Application en informatique : circuits logiques
Les connecteurs logiques sont directement implémentés dans les circuits électroniques sous forme de portes logiques. Chaque porte réalise physiquement une opération logique sur des signaux électriques représentant 0 (faux) et 1 (vrai).
Les circuits logiques construisent tout système numérique, du plus simple compteur au microprocesseur le plus complexe. L'algèbre de Boole fournit les outils mathématiques pour optimiser ces circuits : les lois de De Morgan, par exemple, permettent de remplacer un ensemble de portes ET par des portes OU, choix décisif pour la vitesse et la consommation des puces.
#Exercices type d'examen
Exercice 1 (négations). Écrire la négation des propositions suivantes :
- « Tout entier naturel est pair ou impair. »
- « »
- « Il existe un entier tel que est pair. »
Correction.
- « Il existe un entier naturel ni pair ni impair » (fausse, heureusement) : la négation d'un « ou » est un « et » de négations.
- « » : la négation d'une implication est la conjonction de l'hypothèse et de la négation de la conclusion. Cette négation est vraie (prendre ), ce qui confirme que la proposition initiale est fausse.
- « Pour tout entier , est impair » : on peut vérifier directement que est toujours pair, donc toujours impair ; la proposition initiale est donc fausse, et sa négation est vraie.
Exercice 2 (tautologies). Montrer que est une tautologie (toujours vraie).
Correction. Raisonnons par cas sur . Si est vraie, alors est vraie (conclusion vraie). Si est fausse, alors est vraie (hypothèse fausse). Dans les deux cas, la disjonction est vraie. ∎
Vérification avec le constructeur : saisir (p -> q) | (q -> p) dans l'outil interactif ; la colonne résultat ne contient que des V.