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 \]
Résultat
Les énoncés a) et c) sont des propositions. Les énoncés b) et d) ne sont pas des propositions.
Résolution
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} \]
Résultat
a) atomique ; b) composée ; c) composée ; d) composée.
Résolution
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} \]
Résultat
\[ p \land q \]
Résolution
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} \]
Résultat
\[ p \rightarrow q \]
Résolution
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} \]
Résultat
« Je n’étudie pas ou je réussis l’examen. »
Résolution
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 \]
Résultat
| \(p\) | \(q\) | \(p \land q\) |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | F |
Résolution
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 \]
Résultat
| \(p\) | \(q\) | \(p \lor q\) |
|---|---|---|
| V | V | V |
| V | F | V |
| F | V | V |
| F | F | F |
Résolution
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 \]
Résultat
| \(p\) | \(q\) | \(p \rightarrow q\) |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | V |
| F | F | V |
Résolution
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, de sorte que la condition exprimée par l’implication n’est pas respectée.
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 ★★★☆☆
Construisez la table de vérité de la formule :
\[ p \leftrightarrow q \]
Résultat
| \(p\) | \(q\) | \(p \leftrightarrow q\) |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | V |
Résolution
Le symbole :
\[ \leftrightarrow \]
représente le biconditionnel, aussi appelé double implication.
La formule :
\[ p\leftrightarrow q \]
se lit :
« \(p\) si et seulement si \(q\) ».
Le biconditionnel est vrai lorsque les deux propositions ont la même valeur de vérité : toutes deux vraies ou toutes deux fausses.
Comme deux variables propositionnelles apparaissent, nous devons considérer :
\[ 2^2=4 \]
interprétations.
À la première ligne :
\[ p=V \qquad q=V \]
les deux propositions ont la même valeur de vérité, donc :
\[ p\leftrightarrow q = V \]
À la deuxième ligne :
\[ p=V \qquad q=F \]
les valeurs de vérité sont différentes. Par conséquent :
\[ p\leftrightarrow q = F \]
À la troisième ligne :
\[ p=F \qquad q=V \]
les valeurs de vérité sont également différentes. Donc :
\[ p\leftrightarrow q = F \]
À la dernière ligne :
\[ p=F \qquad q=F \]
les deux propositions sont fausses ; elles ont donc la même valeur de vérité. Par conséquent :
\[ p\leftrightarrow q = V \]
Nous concluons que le biconditionnel est vrai exactement lorsque \(p\) et \(q\) ont la même valeur de vérité.
Exercice 10 — niveau ★★★☆☆
Vérifiez par table de vérité que :
\[ \neg(p\land q)\equiv \neg p \lor \neg q \]
Résultat
Les deux formules ont les mêmes valeurs de vérité dans toute interprétation, elles sont donc logiquement équivalentes.
Résolution
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 \]
Résultat
Les deux formules ont les mêmes valeurs de vérité dans toute interprétation, elles sont donc logiquement équivalentes.
Résolution
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.
Résultat
La formule est une tautologie.
Résolution
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.
Résultat
La formule est une contradiction.
Résolution
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.
Résultat
La formule est une tautologie.
Résolution
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.
Résultat
La formule est une tautologie.
Résolution
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 \]
Résultat
Oui, \(p\) est une conséquence logique de \(p\land q\).
Résolution
É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 \]
Résultat
Oui, \(p\lor q\) est une conséquence logique de \(p\).
Résolution
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 \]
Résultat
Oui, \(q\) est une conséquence logique des prémisses \(p\rightarrow q\) et \(p\).
Résolution
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) \]
Résultat
\[ \neg(p\rightarrow q)\equiv p\land\neg q \]
Résolution
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\).
Résultat
\[ p\rightarrow(q\lor r)\equiv \neg p\lor q\lor r \]
Résolution
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.