Une collection progressive de 20 exercices résolus sur la logique propositionnelle, conçue pour apprendre à reconnaître les propositions, à formaliser les énoncés, à construire des tables de vérité et à utiliser correctement les principaux connecteurs logiques.
Chaque exercice est corrigé étape par étape, en prêtant attention à la signification des formules et pas seulement au résultat final. L’objectif est d’apprendre à raisonner de manière rigoureuse sur la valeur de vérité des énoncés et sur les relations logiques entre propositions.
Rappelons qu’une proposition est un énoncé déclaratif auquel il est possible d’attribuer, de façon non ambiguë, une et une seule valeur de vérité :
\[ V \quad \text{ou} \quad F \]
Les principaux connecteurs de la logique propositionnelle sont :
\[ \neg,\quad \land,\quad \lor,\quad \rightarrow,\quad \leftrightarrow \]
Ils permettent de construire des propositions composées à partir de propositions plus simples.
Exercice 1 — niveau ★☆☆☆☆
Déterminez lesquels des énoncés suivants sont des propositions :
\[ \text{a) } 7>3 \]
\[ \text{b) } \text{Ferme la porte.} \]
\[ \text{c) } 5+2=10 \]
\[ \text{d) } x+1=4 \]
Solution
Les énoncés a) et c) sont des propositions. Les énoncés b) et d) ne sont pas des propositions.
Développement
Pour déterminer si un énoncé est une proposition, nous devons nous demander s’il possède une valeur de vérité bien déterminée, c’est-à-dire s’il est vrai ou faux.
Considérons le premier énoncé :
\[ 7>3 \]
Cet énoncé est déclaratif et nous pouvons établir clairement qu’il est vrai. Il s’agit donc d’une proposition.
Considérons maintenant :
\[ \text{Ferme la porte.} \]
Ce n’est pas un énoncé déclaratif, mais un ordre. Il n’a pas de sens de dire qu’il est vrai ou faux. Ce n’est donc pas une proposition.
Le troisième énoncé est :
\[ 5+2=10 \]
Il s’agit d’un énoncé déclaratif. Nous pouvons établir qu’il est faux, car :
\[ 5+2=7 \]
Un énoncé faux peut tout à fait être une proposition : ce qui compte, c’est qu’il ait une valeur de vérité déterminée.
Enfin, considérons :
\[ x+1=4 \]
Cet énoncé contient une variable libre, \(x\). Sans préciser la valeur de \(x\), nous ne pouvons pas établir s’il est vrai ou faux.
Par exemple, si \(x=3\), l’énoncé est vrai ; si \(x=0\), l’énoncé est faux.
Donc, tel qu’il est écrit, ce n’est pas une proposition.
En résumé :
\[ \text{a) proposition vraie} \]
\[ \text{b) non-proposition} \]
\[ \text{c) proposition fausse} \]
\[ \text{d) non-proposition} \]
Exercice 2 — niveau ★☆☆☆☆
Déterminez si les propositions suivantes sont atomiques ou composées :
\[ \text{a) } 4 \text{ est pair} \]
\[ \text{b) } 4 \text{ est pair et } 5 \text{ est impair} \]
\[ \text{c) } \text{Il ne pleut pas} \]
\[ \text{d) } \text{Si j’étudie, alors je réussis l’examen} \]
Solution
a) atomique ; b) composée ; c) composée ; d) composée.
Développement
Une proposition est atomique lorsqu’elle ne contient pas de connecteurs logiques et n’est pas obtenue en combinant des propositions plus simples.
Une proposition est composée lorsqu’elle contient au moins un connecteur logique, explicite ou implicite.
Considérons :
\[ 4 \text{ est pair} \]
Cette proposition n’est pas construite en combinant d’autres propositions. Elle est donc atomique.
Considérons maintenant :
\[ 4 \text{ est pair et } 5 \text{ est impair} \]
Ici apparaissent deux propositions :
\[ 4 \text{ est pair} \]
et :
\[ 5 \text{ est impair} \]
reliées par le mot « et », qui correspond au connecteur logique de conjonction :
\[ \land \]
La proposition est donc composée.
La proposition :
\[ \text{Il ne pleut pas} \]
contient une négation. Si nous notons \(p\) la proposition « il pleut », alors « il ne pleut pas » s’écrit :
\[ \neg p \]
Elle est donc composée.
Enfin :
\[ \text{Si j’étudie, alors je réussis l’examen} \]
contient une implication logique. Si nous posons :
\[ p = \text{j’étudie} \]
et :
\[ q = \text{je réussis l’examen} \]
alors la proposition se représente par :
\[ p \rightarrow q \]
Elle est donc composée.
Exercice 3 — niveau ★☆☆☆☆
Traduisez en symboles logiques la proposition suivante :
« Marco étudie et Laura lit. »
Avec :
\[ p = \text{Marco étudie} \]
\[ q = \text{Laura lit} \]
Solution
\[ p \land q \]
Développement
La proposition contient deux énoncés simples.
Le premier est :
\[ \text{Marco étudie} \]
noté par :
\[ p \]
Le second est :
\[ \text{Laura lit} \]
noté par :
\[ q \]
Le mot « et » indique que les deux propositions doivent être vraies simultanément.
En logique propositionnelle, cela correspond à la conjonction :
\[ \land \]
La proposition :
« Marco étudie et Laura lit »
se traduit donc par :
\[ p \land q \]
Exercice 4 — niveau ★☆☆☆☆
Traduisez en symboles logiques la proposition suivante :
« S’il pleut, alors je reste à la maison. »
Avec :
\[ p = \text{il pleut} \]
\[ q = \text{je reste à la maison} \]
Solution
\[ p \rightarrow q \]
Développement
La phrase contient une structure conditionnelle :
« Si ..., alors ... »
En logique propositionnelle, cette structure est représentée par l’implication :
\[ \rightarrow \]
L’antécédent est la proposition qui suit le mot « si » :
\[ p = \text{il pleut} \]
Le conséquent est la proposition qui suit « alors » :
\[ q = \text{je reste à la maison} \]
La proposition :
« S’il pleut, alors je reste à la maison »
se traduit donc par :
\[ p \rightarrow q \]
Il est important de noter que \(p\rightarrow q\) ne signifie pas que \(p\) et \(q\) sont tous deux vrais, mais que la vérité de \(p\) entraîne la vérité de \(q\).
Exercice 5 — niveau ★★☆☆☆
Traduisez en langage naturel la formule :
\[ \neg p \lor q \]
sachant que :
\[ p = \text{j’étudie} \]
\[ q = \text{je réussis l’examen} \]
Solution
« Je n’étudie pas ou je réussis l’examen. »
Développement
La formule est :
\[ \neg p \lor q \]
Analysons les symboles un par un.
La proposition \(p\) signifie :
\[ \text{j’étudie} \]
Donc :
\[ \neg p \]
signifie :
\[ \text{je n’étudie pas} \]
La proposition \(q\) signifie :
\[ \text{je réussis l’examen} \]
Le connecteur :
\[ \lor \]
représente la disjonction inclusive, c’est-à-dire « ou ».
Par conséquent :
\[ \neg p \lor q \]
se lit :
« Je n’étudie pas ou je réussis l’examen. »
En logique, cette disjonction est vraie même si les deux propositions sont vraies, c’est-à-dire même si je n’étudie pas et que je réussis l’examen.
Exercice 6 — niveau ★★☆☆☆
Construisez la table de vérité de la formule :
\[ p \land q \]
Solution
| \(p\) | \(q\) | \(p \land q\) |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | F |
Développement
La formule contient deux variables propositionnelles :
\[ p \qquad \text{et} \qquad q \]
Une table de vérité à deux variables doit contenir :
\[ 2^2=4 \]
interprétations possibles.
Le connecteur :
\[ \land \]
représente la conjonction logique.
La conjonction n’est vraie que lorsque les deux propositions sont vraies simultanément.
Analysons les quatre lignes.
À la première ligne :
\[ p=V \qquad q=V \]
les deux propositions sont vraies, donc :
\[ p\land q = V \]
À la deuxième ligne :
\[ p=V \qquad q=F \]
l’une des deux propositions est fausse. Par conséquent la conjonction est fausse :
\[ p\land q = F \]
Il en va de même à la troisième ligne :
\[ p=F \qquad q=V \]
car les deux propositions ne sont pas toutes deux vraies.
Enfin, à la dernière ligne :
\[ p=F \qquad q=F \]
les deux sont fausses, donc la conjonction est également fausse.
Nous concluons donc que :
\[ p\land q \]
n’est vraie que dans le cas :
\[ p=V \qquad q=V \]
Exercice 7 — niveau ★★☆☆☆
Construisez la table de vérité de la formule :
\[ p \lor q \]
Solution
| \(p\) | \(q\) | \(p \lor q\) |
|---|---|---|
| V | V | V |
| V | F | V |
| F | V | V |
| F | F | F |
Développement
Le symbole :
\[ \lor \]
représente la disjonction logique inclusive.
La disjonction est vraie lorsqu’au moins une des deux propositions est vraie.
Ici aussi, avec deux variables, nous devons considérer :
\[ 2^2=4 \]
interprétations possibles.
À la première ligne :
\[ p=V \qquad q=V \]
les deux propositions sont vraies. Donc :
\[ p\lor q = V \]
À la deuxième ligne :
\[ p=V \qquad q=F \]
au moins une des deux propositions est vraie, donc :
\[ p\lor q = V \]
À la troisième ligne :
\[ p=F \qquad q=V \]
ici aussi au moins une proposition est vraie. Par conséquent :
\[ p\lor q = V \]
Seule la dernière ligne :
\[ p=F \qquad q=F \]
donne les deux propositions fausses.
Par conséquent :
\[ p\lor q = F \]
Nous concluons donc que la disjonction inclusive n’est fausse que lorsque les deux propositions sont fausses.
Exercice 8 — niveau ★★☆☆☆
Construisez la table de vérité de la formule :
\[ p \rightarrow q \]
Solution
| \(p\) | \(q\) | \(p \rightarrow q\) |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | V |
| F | F | V |
Développement
L’implication :
\[ p\rightarrow q \]
se lit :
« si \(p\), alors \(q\) ».
Ce connecteur est souvent le plus délicat à interpréter correctement.
L’implication n’est fausse que dans le cas où :
\[ p=V \]
et simultanément :
\[ q=F \]
En effet, dans ce cas l’antécédent est vrai mais le conséquent est faux, ce qui viole la promesse logique contenue dans l’implication.
Analysons les quatre possibilités.
Première ligne :
\[ p=V \qquad q=V \]
L’implication est vraie.
Deuxième ligne :
\[ p=V \qquad q=F \]
C’est le seul cas où l’implication est fausse :
\[ p\rightarrow q = F \]
Troisième ligne :
\[ p=F \qquad q=V \]
L’implication est considérée vraie.
En effet, quand l’antécédent est faux, l’implication n’est pas violée.
Quatrième ligne :
\[ p=F \qquad q=F \]
Ici aussi l’implication est vraie, toujours parce que l’antécédent est faux.
Nous concluons donc que :
\[ p\rightarrow q \]
n’est fausse que lorsque :
\[ p=V \qquad \text{et} \qquad q=F \]
Exercice 9 — niveau ★★★☆☆
Déterminez la valeur de vérité de la formule :
\[ (p\land q)\rightarrow r \]
dans l’interprétation :
\[ p=V,\qquad q=F,\qquad r=F \]
Solution
La formule est vraie.
Développement
Considérons la formule :
\[ (p\land q)\rightarrow r \]
Pour évaluer correctement la formule, nous devons procéder de l’intérieur vers l’extérieur.
La sous-formule la plus interne est :
\[ p\land q \]
Substituons les valeurs assignées :
\[ p=V,\qquad q=F \]
Nous obtenons :
\[ V\land F \]
Une conjonction n’est vraie que si les deux propositions sont vraies.
Puisqu’une des deux est fausse, il suit que :
\[ p\land q = F \]
La formule initiale devient donc :
\[ F\rightarrow F \]
Rappelons qu’une implication n’est fausse que lorsque l’antécédent est vrai et le conséquent est faux.
Ici l’antécédent est faux.
Par conséquent :
\[ F\rightarrow F = V \]
Nous concluons donc que la formule est vraie.
Exercice 10 — niveau ★★★☆☆
Vérifiez par table de vérité que :
\[ \neg(p\land q)\equiv \neg p \lor \neg q \]
Solution
Les deux formules ont les mêmes valeurs de vérité dans toute interprétation, elles sont donc logiquement équivalentes.
Développement
Pour démontrer que deux formules sont logiquement équivalentes, nous devons vérifier qu’elles prennent toujours la même valeur de vérité.
Construisons donc une table de vérité complète.
| \(p\) | \(q\) | \(p\land q\) | \(\neg(p\land q)\) | \(\neg p\) | \(\neg q\) | \(\neg p\lor \neg q\) |
|---|---|---|---|---|---|---|
| V | V | V | F | F | F | F |
| V | F | F | V | F | V | V |
| F | V | F | V | V | F | V |
| F | F | F | V | V | V | V |
Observons maintenant les deux dernières colonnes :
\[ \neg(p\land q) \]
et :
\[ \neg p\lor\neg q \]
Elles coïncident sur toutes les lignes de la table.
Par conséquent :
\[ \neg(p\land q)\equiv \neg p\lor\neg q \]
Cette équivalence porte le nom de première loi de De Morgan.
Exercice 11 — niveau ★★★☆☆
Vérifiez par table de vérité que :
\[ p\rightarrow q \equiv \neg p \lor q \]
Solution
Les deux formules ont les mêmes valeurs de vérité dans toute interprétation, elles sont donc logiquement équivalentes.
Développement
Nous voulons comparer les deux formules :
\[ p\rightarrow q \]
et :
\[ \neg p \lor q \]
Deux formules sont logiquement équivalentes si elles prennent la même valeur de vérité dans toutes les interprétations possibles.
Puisqu’il y a deux variables propositionnelles, \(p\) et \(q\), nous devons considérer :
\[ 2^2=4 \]
interprétations.
| \(p\) | \(q\) | \(p\rightarrow q\) | \(\neg p\) | \(\neg p\lor q\) |
|---|---|---|---|---|
| V | V | V | F | V |
| V | F | F | F | F |
| F | V | V | V | V |
| F | F | V | V | V |
Comparons maintenant la colonne de \(p\rightarrow q\) avec celle de \(\neg p\lor q\).
Les valeurs sont identiques sur chaque ligne :
\[ V,\ F,\ V,\ V \]
Les deux formules sont donc logiquement équivalentes :
\[ p\rightarrow q \equiv \neg p \lor q \]
Cette équivalence est très importante car elle permet d’éliminer l’implication et de la réécrire en n’utilisant que la négation et la disjonction.
Exercice 12 — niveau ★★★☆☆
Déterminez si la formule :
\[ p\lor\neg p \]
est une tautologie, une contradiction ou une formule contingente.
Solution
La formule est une tautologie.
Développement
Une formule est une tautologie si elle est vraie dans toute interprétation.
Une formule est une contradiction si elle est fausse dans toute interprétation.
Une formule est contingente si elle est vraie dans certaines interprétations et fausse dans d’autres.
Considérons :
\[ p\lor\neg p \]
La formule ne contient qu’une seule variable propositionnelle, nous devons donc considérer :
\[ 2^1=2 \]
interprétations.
| \(p\) | \(\neg p\) | \(p\lor\neg p\) |
|---|---|---|
| V | F | V |
| F | V | V |
À la première ligne \(p\) est vraie et la disjonction est vraie.
À la deuxième ligne \(p\) est fausse, mais \(\neg p\) est vraie ; la disjonction est donc vraie également dans ce cas.
La formule est vraie dans toutes les interprétations.
Par conséquent :
\[ p\lor\neg p \]
est une tautologie.
Cette tautologie est connue sous le nom de principe du tiers exclu.
Exercice 13 — niveau ★★★☆☆
Déterminez si la formule :
\[ p\land\neg p \]
est une tautologie, une contradiction ou une formule contingente.
Solution
La formule est une contradiction.
Développement
Considérons la formule :
\[ p\land\neg p \]
Elle affirme simultanément \(p\) et sa négation.
Construisons la table de vérité.
| \(p\) | \(\neg p\) | \(p\land\neg p\) |
|---|---|---|
| V | F | F |
| F | V | F |
À la première ligne \(p\) est vraie, mais \(\neg p\) est fausse. La conjonction est donc fausse.
À la deuxième ligne \(p\) est fausse, tandis que \(\neg p\) est vraie. La conjonction est également fausse.
La formule est fausse dans toute interprétation.
Par conséquent :
\[ p\land\neg p \]
est une contradiction.
Cette loi porte le nom de principe de non-contradiction.
Exercice 14 — niveau ★★★★☆
Déterminez si la formule :
\[ p\rightarrow(p\lor q) \]
est une tautologie, une contradiction ou une formule contingente.
Solution
La formule est une tautologie.
Développement
Pour classer la formule nous devons construire sa table de vérité complète.
La formule est :
\[ p\rightarrow(p\lor q) \]
La sous-formule interne à calculer est :
\[ p\lor q \]
Construisons la table :
| \(p\) | \(q\) | \(p\lor q\) | \(p\rightarrow(p\lor q)\) |
|---|---|---|---|
| V | V | V | V |
| V | F | V | V |
| F | V | V | V |
| F | F | F | V |
Analysons la colonne finale.
Elle ne contient que des valeurs vraies :
\[ V,\ V,\ V,\ V \]
La formule est donc vraie dans toute interprétation.
Par conséquent :
\[ p\rightarrow(p\lor q) \]
est une tautologie.
D’un point de vue intuitif, si \(p\) est vraie, alors la disjonction \(p\lor q\) est certainement vraie, car une disjonction inclusive est vraie dès qu’au moins une de ses composantes est vraie.
Exercice 15 — niveau ★★★★☆
Déterminez si la formule :
\[ (p\land q)\rightarrow p \]
est une tautologie, une contradiction ou une formule contingente.
Solution
La formule est une tautologie.
Développement
La formule à analyser est :
\[ (p\land q)\rightarrow p \]
Elle contient une conjonction dans le premier membre de l’implication. Avant d’évaluer l’implication, nous devons donc calculer :
\[ p\land q \]
Construisons la table de vérité complète :
| \(p\) | \(q\) | \(p\land q\) | \((p\land q)\rightarrow p\) |
|---|---|---|---|
| V | V | V | V |
| V | F | F | V |
| F | V | F | V |
| F | F | F | V |
Observons la colonne finale :
\[ V,\ V,\ V,\ V \]
La formule est vraie dans toutes les interprétations.
Donc :
\[ (p\land q)\rightarrow p \]
est une tautologie.
La signification logique est simple : si \(p\) et \(q\) sont vraies simultanément, alors en particulier \(p\) est vraie.
Exercice 16 — niveau ★★★★☆
Vérifiez si :
\[ p\land q \models p \]
Solution
Oui, \(p\) est une conséquence logique de \(p\land q\).
Développement
Écrire :
\[ p\land q \models p \]
signifie qu’il n’existe aucune interprétation qui rende vraie la prémisse \(p\land q\) tout en rendant fausse la conclusion \(p\).
Nous devons donc considérer les interprétations dans lesquelles :
\[ p\land q \]
est vraie.
Une conjonction n’est vraie que lorsque ses deux membres sont vrais. Donc :
\[ p\land q = V \quad \Longleftrightarrow \quad p=V \ \text{et}\ q=V \]
Dans toute interprétation où \(p\land q\) est vraie, on a nécessairement :
\[ p=V \]
Il n’existe donc aucune interprétation où la prémisse est vraie et la conclusion fausse.
Par conséquent :
\[ p\land q \models p \]
Exercice 17 — niveau ★★★★☆
Vérifiez si :
\[ p \models p\lor q \]
Solution
Oui, \(p\lor q\) est une conséquence logique de \(p\).
Développement
L’écriture :
\[ p \models p\lor q \]
signifie que toute interprétation qui rend vraie la prémisse \(p\) rend également vraie la conclusion \(p\lor q\).
Supposons donc que la prémisse soit vraie :
\[ p=V \]
La conclusion est :
\[ p\lor q \]
Une disjonction inclusive est vraie dès qu’au moins une des deux propositions est vraie.
Puisque \(p\) est déjà vraie, la disjonction :
\[ p\lor q \]
est nécessairement vraie, quelle que soit la valeur de \(q\).
En effet :
\[ V\lor V=V \]
et :
\[ V\lor F=V \]
Donc tout modèle de \(p\) est aussi un modèle de \(p\lor q\).
Par conséquent :
\[ p \models p\lor q \]
Exercice 18 — niveau ★★★★★
Vérifiez si :
\[ p\rightarrow q,\ p \models q \]
Solution
Oui, \(q\) est une conséquence logique des prémisses \(p\rightarrow q\) et \(p\).
Développement
L’écriture :
\[ p\rightarrow q,\ p \models q \]
signifie que toute interprétation qui rend vraies les deux prémisses rend également vraie la conclusion.
Les prémisses sont :
\[ p\rightarrow q \]
et :
\[ p \]
Supposons donc que les deux soient vraies.
De la deuxième prémisse nous savons que :
\[ p=V \]
De plus, la première prémisse affirme que :
\[ p\rightarrow q=V \]
Rappelons qu’une implication dont l’antécédent est vrai n’est vraie que si le conséquent est également vrai.
Puisque l’antécédent \(p\) est vrai, pour que l’implication reste vraie il faut nécessairement que :
\[ q=V \]
Donc toute interprétation qui rend vraies les prémisses rend vraie la conclusion.
Par conséquent :
\[ p\rightarrow q,\ p \models q \]
C’est la forme sémantique du modus ponens.
Exercice 19 — niveau ★★★★★
Réduisez la formule suivante en utilisant les équivalences logiques :
\[ \neg(p\rightarrow q) \]
Solution
\[ \neg(p\rightarrow q)\equiv p\land\neg q \]
Développement
Partons de la formule :
\[ \neg(p\rightarrow q) \]
Pour la simplifier, éliminons d’abord l’implication.
Rappelons l’équivalence fondamentale :
\[ p\rightarrow q \equiv \neg p\lor q \]
En substituant nous obtenons :
\[ \neg(p\rightarrow q)\equiv \neg(\neg p\lor q) \]
Appliquons maintenant la loi de De Morgan :
\[ \neg(A\lor B)\equiv \neg A\land\neg B \]
Dans notre cas :
\[ A=\neg p \qquad \text{et} \qquad B=q \]
Donc :
\[ \neg(\neg p\lor q)\equiv \neg\neg p\land\neg q \]
Enfin, utilisons la double négation :
\[ \neg\neg p\equiv p \]
Nous obtenons :
\[ \neg(p\rightarrow q)\equiv p\land\neg q \]
Le résultat est cohérent avec la signification de l’implication : \(p\rightarrow q\) n’est fausse que lorsque \(p\) est vraie et \(q\) est fausse.
Exercice 20 — niveau ★★★★★
Transformez la formule :
\[ p\rightarrow(q\lor r) \]
en une formule équivalente sans le connecteur \(\rightarrow\).
Solution
\[ p\rightarrow(q\lor r)\equiv \neg p\lor q\lor r \]
Développement
La formule de départ est :
\[ p\rightarrow(q\lor r) \]
Nous voulons éliminer le connecteur d’implication.
Utilisons l’équivalence :
\[ A\rightarrow B\equiv \neg A\lor B \]
Dans notre cas :
\[ A=p \]
et :
\[ B=q\lor r \]
En appliquant l’équivalence nous obtenons :
\[ p\rightarrow(q\lor r)\equiv \neg p\lor(q\lor r) \]
Par associativité de la disjonction, nous pouvons omettre les parenthèses :
\[ \neg p\lor(q\lor r)\equiv \neg p\lor q\lor r \]
La formule équivalente sans implication est donc :
\[ \neg p\lor q\lor r \]
Cette formule est une clause disjonctive, c’est-à-dire une disjonction de littéraux, et peut aussi être vue comme une forme normale conjonctive composée d’une seule clause.