Logique propositionnelle

La logique propositionnelle (ou logique mathématique) est un outil d’expression des mathématiques, que l’on rencontre sous des terminologies variées et dans toutes sortes de théorèmes.

À quoi sert la logique

La logique est la science qui s’occupe du raisonnement, de la vérité, de la démontrabilité et de la réfutabilité. Dans tout cela, la logique ne s’intéresse qu’à la forme de ce que l’on énonce, pas à son contenu concret, pas plus qu’aux interprétations psychologiques et autres choses du même genre.

Si nous avons par exemple la phrase « le nombre 2 est pair et en même temps impair », nous pouvons en conclure que la phrase entière n’est pas vraie, car le nombre 2 n’est pas impair. Ce sont des questions que la logique traite en général.

Proposition

La base de la logique propositionnelle est bien sûr la proposition. Une proposition est toute phrase déclarative dont on peut déterminer la valeur de vérité. Exemples de propositions simples :

• Le Mont Blanc est la plus haute montagne des Alpes.
• L’entier naturel cinq est impair.
• HTML est un langage de programmation.
• Deux plus trois font six.

Ce sont toutes des propositions, qu’elles soient vraies (les deux premières) ou fausses (les deux dernières). Une phrase interrogative, ou une phrase dont on ne peut pas déterminer sans ambiguïté la valeur de vérité, n’est pas une proposition. Encore des exemples :

• Le Mont Blanc sera-t-il encore la plus haute montagne des Alpes l’année prochaine ?
• Le vert est la plus belle couleur.

La première phrase ne peut pas être une proposition, car c’est une phrase interrogative ; pour la deuxième, on ne peut pas dire si la proposition est vraie ou fausse. Une telle phrase s’appelle alors une hypothèse (ou conjecture).

La logique mathématique classique ne sait pas très bien traiter les phrases vagues comme « Lucas est grand » ou « Chloé chante bien ». Ces propositions se traitent mieux, par exemple, en logique floue, qui est conçue pour le vague.

Proposition atomique

Dans la première partie, nous avions l’exemple de la proposition « le nombre 2 est pair et en même temps impair ». Une telle proposition peut être appelée composée, car elle relie en réalité deux propositions plus courtes : « le nombre 2 est pair » et « le nombre 2 est impair ». Ces deux propositions sont reliées par le connecteur logique « et » ou encore « et en même temps ».

Une proposition atomique est donc une proposition que l’on ne peut plus diviser, c’est en un certain sens l’affirmation la plus simple. Les exemples de propositions précédents étaient en réalité des propositions atomiques :

• Le Mont Blanc est la plus haute montagne des Alpes.
• L’entier naturel cinq est impair.
• HTML est un langage de programmation.
• Deux plus trois font six.

Nous noterons les propositions atomiques par des lettres minuscules de l’alphabet, classiquement p, q, r, …, et nous les appellerons variables propositionnelles.

Connecteurs logiques

La logique mathématique utilise couramment un certain ensemble de connecteurs logiques. Parmi les connecteurs de base, il y a quatre connecteurs binaires :

• p ∧ q est la conjonction des propositions, on lit « la proposition p et (à la fois) la proposition q »
• p ∨ q est la disjonction des propositions, on lit « la proposition p ou la proposition q »
• p ⇒ q est l’implication, on lit « si la proposition p, alors la proposition q »
• p ⇔ q est l’équivalence, on lit « la proposition p si et seulement si la proposition q »

Exemples concrets de connecteurs logiques :

• Au centre de Lille, il pleut et le soleil brille en même temps. (conjonction)
• Au centre de Lille, il pleut ou le soleil brille. (disjonction)
• Léa est la meilleure joueuse de l’équipe et Hugo est le garçon le plus cool. (conjonction)
• Si tu manges trop de bonbons, alors tu auras bientôt mal au ventre. (implication)
• Si le nombre x est divisible par quatre, alors il est aussi divisible par deux. (implication)
• Manon est jolie et intelligente à la fois. (conjonction)
• Les chanteuses ont du succès si et seulement si elles sont jolies. (équivalence)
• S’il ne pleut pas, nous ne serons pas mouillés. (implication)
• Si Lucas sait chanter, alors je suis le père Noël. (implication)

Nous connaissons encore un connecteur courant : la négation. La négation se note soit par une barre $\bar{p}$, soit à l’aide du symbole ¬p.

Formules

À l’aide de variables propositionnelles (propositions atomiques) et de connecteurs, nous pouvons composer une proposition plus compliquée, que nous appellerons formule. Tous les exemples de la liste de phrases précédente étaient en réalité des formules, car nous avions deux formules atomiques, par exemple « Il pleut au centre de Lille » et « le soleil brille », et nous les avons reliées à l’aide de connecteurs. Dans le premier cas, nous les avons reliées par « et en même temps » et nous avons obtenu la formule « Il pleut au centre de Lille et le soleil brille en même temps » ; dans le second cas, nous avons utilisé « ou » et obtenu la formule « Il pleut au centre de Lille ou le soleil brille ».

Définissons formellement une formule ainsi :

• Toute variable propositionnelle (proposition atomique) est une formule (plus précisément, on dit que c’est une formule atomique).
• Si A et B sont des formules, alors ¬A, (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B) sont aussi des formules.

La définition a du sens : dans le premier point, nous disons que chaque proposition atomique est en même temps une formule. Ainsi, si nous avons deux propositions atomiques, par exemple « Il pleut au centre de Lille » et « le soleil brille », nous avons aussi deux formules. Nous pouvons alors appliquer le second point et construire une formule plus compliquée, par exemple ainsi :

• Il pleut au centre de Lille et le soleil brille en même temps.
• Il pleut au centre de Lille ou le soleil brille.
• Si le soleil brille au centre de Lille, alors il pleut.
• Le soleil brille au centre de Lille si et seulement s’il pleut.

Les formules ne sont évidemment pas forcément vraies. Nous avons obtenu un nouvel ensemble de formules, donc nous pouvons en composer d’encore plus compliquées. Notons A = « Au centre de Lille, le soleil brille ou il pleut. » (nous savons déjà que c’est une formule) et B = « on voit un arc-en-ciel » (supposons qu’il s’agisse encore du centre de Lille, pour ne pas avoir à le répéter sans cesse) ; nous pouvons alors créer d’autres formules. Les parenthèses dans les phrases indiquent seulement à quelles parties se rapporte le connecteur.

• A ∧ B : (Au centre de Lille, le soleil brille ou il pleut) et en même temps (on voit un arc-en-ciel).
• A ∨ B : (Au centre de Lille, le soleil brille ou il pleut) ou (on voit un arc-en-ciel).
• A ⇒ B : (Si, au centre de Lille, le soleil brille ou il pleut), alors (on voit un arc-en-ciel).
• A ⇔ B : (Au centre de Lille, le soleil brille ou il pleut) si et seulement si (on voit un arc-en-ciel).

Tout cela, ce sont des formules. Nous pouvons donc de nouveau prendre l’une de ces formules et y accrocher une autre formule. Nous pouvons ainsi fabriquer par exemple le monstre « Si, au centre de Lille, le soleil brille ou il pleut ou on voit un arc-en-ciel, alors le soleil brille ou il pleut si et seulement si on voit un arc-en-ciel. »

Dans la partie suivante, nous étudierons la vérité des formules.