Bases de la logique
Progression
#title: "Bases de la logique" description: "Propositions, connecteurs et quantificateurs"
#Introduction à la logique
La logique mathématique fournit le cadre formel dans lequel s'expriment toutes les théories mathématiques. Elle permet de définir 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 mêmes connecteurs logiques que nous allons étudier.
#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é, appelée le principe du tiers exclu, est fondamentale : 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 la valeur 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.
#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 au langage 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 subtil et 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, donc je ne peux pas mentir.
Vocabulaire :
- est l'hypothèse (ou condition suffisante pour )
- est la conclusion (ou condition nécessaire si )
Propriété fondamentale : est logiquement équivalent à .
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 : .
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | V |
#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 permettent de préciser 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 que est vraie pour un élément arbitraire de . Pour montrer qu'elle est fausse, il suffit de trouver 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 ». Cette proposition affirme l'existence d'au moins un élément satisfaisant la propriété.
La notation (« il existe un unique ») signifie qu'il existe exactement un élément vérifiant la propriété.
#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.
#Types de raisonnement
La logique mathématique 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 logiques pour arriver à la conclusion . C'est la méthode la plus naturelle et la plus fréquente.
Exemple : Montrer que si est pair, alors est pair.
- Hypothèse : est pair, donc pour un entier .
- Alors , qui est bien pair.
#2. Contraposée
Pour montrer , on démontre l'implication contraposée , qui lui est logiquement équivalente. 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 a été démontrée ci-dessus.
#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.
Exemple célèbre : Preuve de l'irrationalité de .
- Supposons avec entiers premiers entre eux.
- Alors , donc est pair, donc est pair.
- Écrivons . Alors , donc , donc est pair.
- Contradiction : et sont tous deux pairs, donc non premiers entre eux.
#4. 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 que est vraie.
- Conclusion : Par le principe de récurrence, est vraie.
Exemple : Montrer que .
- Initialisation : Pour , . ✓
- Hérédité : Supposons la formule vraie au rang . Alors :
- La formule est vraie au rang .
#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 permettent de construire 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.