Logique propositionnelle et preuves : exercices corrigés pas à pas
Aussi appelé : logique propositionnelle · table de vérité
Exercices gratuits sur Logique propositionnelle et preuves avec schémas, indices et corrigés complets. De nouvelles valeurs à chaque fois, à trois niveaux : tables de vérité, équivalences et méthodes de preuve, quantificateurs et raisonnements.
Exercice gratuitFacile
Complétez la table de vérité (1 = vrai, 0 = faux). Dans combien de lignes N est-elle vraie pour (p → r) ↔ (r ∨ q) ?
Comment résoudre les exercices de Logique propositionnelle et preuves
Comptez les variables distinctes : la table de vérité a 2ⁿ lignes, la première avec toutes les variables à 1.
Donnez à chaque sous-formule sa propre colonne et remplissez les colonnes de l’intérieur vers l’extérieur.
Appliquez la règle de chaque connecteur : → n’est 0 que pour 1 → 0, ↔ vaut 1 quand les deux côtés sont égaux.
Pour des équivalences, comparez les colonnes finales ligne par ligne ; pour un raisonnement, regardez seulement les lignes où toutes les prémisses valent 1.
Pour nier un énoncé quantifié, faites passer ¬ vers l’intérieur, échangez ∀ et ∃, et niez la formule intérieure.
Erreurs fréquentes
Considérer p → q comme fausse quand p est fausse.
Compter deux fois une variable répétée en cherchant le nombre de lignes.
Confondre la contraposée ¬q → ¬p avec la réciproque q → p.
Apprendre Logique propositionnelle et preuves depuis zéro
1Énoncés et connecteurs
Une proposition est un énoncé qui est soit vrai, soit faux, comme « 7 est premier ». On la note avec une lettre, p ou q, et sa valeur de vérité par 1 (vrai) ou 0 (faux).
Les connecteurs construisent des formules plus grandes à partir de plus petites :
¬p (non p) inverse la valeur.
p ∧ q (et) vaut 1 seulement quand les deux valent 1.
p ∨ q (ou) vaut 0 seulement quand les deux valent 0. C’est le ou inclusif : les deux peuvent être vrais.
p → q (si p alors q) vaut 0 seulement quand p = 1 et q = 0.
p ↔ q (si et seulement si) vaut 1 quand p et q ont la même valeur.
L’implication surprend beaucoup d’étudiants : quand p est faux, p → q est vrai quelle que soit la valeur de q. Une promesse « s’il pleut, je prends un parapluie » n’est rompue que par un jour de pluie sans parapluie.
Auto-évaluation p = 0 et q = 1. Quelle est la valeur de p → q ?
0
1
Cela dépend du contexte
Indéfinie
Réponse: 1. Une implication n’est fausse que lorsque la condition est vérifiée et la conclusion non (p = 1, q = 0). Avec p = 0 elle est vraie, quel que soit q.
2Tables de vérité
Une table de vérité énumère toutes les combinaisons de valeurs de vérité des variables. Avec n variables distinctes il y a 2ⁿ lignes : 4 pour deux variables, 8 pour trois, 16 pour quatre. Une variable qui apparaît deux fois ne compte qu’une fois.
Travaillez de l’intérieur vers l’extérieur. Donnez à chaque sous-formule sa propre colonne, de sorte que chaque nouvelle colonne n’exige qu’un connecteur appliqué à des colonnes déjà remplies.
Listez les variables et écrivez les 2ⁿ combinaisons, en commençant par tous les 1.
Ajoutez une colonne pour chaque sous-formule, en commençant par la plus interne.
Remplissez chaque colonne avec la règle de son connecteur principal.
Lisez la réponse dans la dernière colonne : comptez les 1, ou trouvez la ligne demandée.
Auto-évaluation Combien de lignes a la table de vérité de (p ∧ q) → (r ∨ p) ?
16
4
6
8
Réponse: 8. La formule a trois variables distinctes, p, q et r, donc 2³ = 8 lignes. p apparaît deux fois mais c’est une seule variable ; 16 serait 2⁴ pour quatre occurrences.
3Un exemple détaillé
Suivez chaque étape. Essayez de deviner la suivante avant de l’ouvrir.
Exemple détaillé
Dans combien de lignes de sa table de vérité (p → q) ∧ ¬q est-elle vraie ?
1
Variables et lignes
Deux variables, p et q, donc 4 lignes : (1, 1), (1, 0), (0, 1), (0, 0).
2
Colonne p → q
Elle vaut 0 seulement dans la ligne p = 1, q = 0 :
p → q: 1, 0, 1, 1
3
Colonne ¬q
¬q: 0, 1, 0, 1
4
La conjonction
Les deux colonnes doivent valoir 1. Cela n’arrive que dans la dernière ligne, p = 0 et q = 0.
(p → q) ∧ ¬q: 0, 0, 0, 1
Réponse
La formule est vraie dans 1 ligne, la ligne p = 0, q = 0. C’est pourquoi p → q et ¬q ensemble donnent ¬p (modus tollens).
4Équivalences et méthodes de preuve
Deux formules sont équivalentes (≡) quand leurs colonnes de table de vérité sont identiques. Une tautologie vaut 1 dans toutes les lignes, une contradiction 0 dans toutes les lignes, et une contingence n’est ni l’une ni l’autre.
Les lois que vous utilisez le plus :
¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p ¬(p → q) ≡ p ∧ ¬q
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Ces lois fondent les méthodes de preuve. Une preuve par contraposée de p → q prouve à la place ¬q → ¬p, qui lui est équivalente. Une preuve par l’absurde suppose p ∧ ¬q, la seule façon dont l’implication peut échouer, et en déduit quelque chose d’impossible.
Attention : la réciproque q → p et l’inverse ¬p → ¬q ne sont pas équivalentes à p → q.
Auto-évaluation Quelle formule est équivalente à ¬(p ∧ q) ?
p ∨ q
¬p ∧ q
¬p ∧ ¬q
¬p ∨ ¬q
Réponse: ¬p ∨ ¬q. Par De Morgan, le ∧ devient ∨ et les deux parties sont niées. ¬p ∧ ¬q est la négation de p ∨ q, un énoncé différent : il est faux quand exactement un de p et q est vrai, alors que ¬(p ∧ q) est vrai.
5Quantificateurs et raisonnements valides
Avec des variables sur un domaine, ∀x P(x) dit « P est vrai pour tout x » et ∃x P(x) dit « P est vrai pour au moins un x ». Une négation échange le quantificateur :
¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)
Faites passer la négation vers l’intérieur une étape à la fois ; à l’intérieur, utilisez les lois propositionnelles. Par exemple ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x)) : « tout P n’est pas un Q » signifie « un certain P n’est pas un Q ».
Un raisonnement est valide quand la conclusion vaut 1 dans toutes les lignes où toutes les prémisses valent 1. Les formes valides classiques sont le modus ponens (p → q, p, donc q), le modus tollens (p → q, ¬q, donc ¬p) et le syllogisme hypothétique (p → q, q → r, donc p → r).
Une ligne où toutes les prémisses valent 1 et la conclusion 0 est un contre-exemple. Affirmer le conséquent (p → q, q, donc p) est invalide : la ligne p = 0, q = 1 est un contre-exemple.
Auto-évaluation Quelle est la négation de « tous les étudiants ont réussi », ∀x P(x) ?
¬P(x) pour un étudiant x fixé
∀x ¬P(x) : aucun étudiant n’a réussi
∃x P(x) : un étudiant a réussi
∃x ¬P(x) : un étudiant n’a pas réussi
Réponse: ∃x ¬P(x) : un étudiant n’a pas réussi. Un seul étudiant qui a échoué suffit à rendre « tous les étudiants ont réussi » faux. « Aucun étudiant n’a réussi » est bien plus fort que la négation.
6Erreurs fréquentes
Considérer p → q comme fausse quand p est fausse. Elle n’est fausse que si p = 1 et q = 0.
Compter deux fois une variable répétée en cherchant le nombre de lignes.
Confondre la contraposée ¬q → ¬p avec la réciproque q → p ou l’inverse ¬p → ¬q.
Nier ∀x P(x) par ∀x ¬P(x) : le quantificateur doit devenir ∃.
Écrire ¬(p ∧ q) comme ¬p ∧ ¬q : De Morgan échange aussi le connecteur.
Auto-évaluation Quel énoncé est la contraposée de « si n² est pair, alors n est pair » ?
Si n est impair, alors n² est impair
Si n est pair, alors n² est pair
Si n² est impair, alors n est impair
n² est pair et n est impair
Réponse: Si n est impair, alors n² est impair. Échangez les deux parties et niez-les : non (n pair) → non (n² pair). « Si n est pair, alors n² est pair » est la réciproque ; la dernière option est ce que suppose une preuve par l’absurde.
7À quoi ressemblent les questions d’examen
Facile : tables de vérité. Vous trouvez le nombre de lignes, comptez les lignes où une formule est vraie, ou cliquez sur la seule ligne qui rend une formule vraie ou fausse.
Moyen : équivalences et méthodes de preuve. Vous décidez si une formule est une tautologie, une contradiction ou une contingence, choisissez la formule équivalente, ou l’énoncé à prouver dans une preuve par contraposée ou par l’absurde.
Difficile : quantificateurs et raisonnements. Vous niez des énoncés quantifiés, choisissez la conclusion qui découle des prémisses, cliquez sur la ligne contre-exemple d’un raisonnement invalide, ou comptez les lignes vraies d’une table à quatre variables.
Une seule ligne de la table de vérité rend ¬(p ∨ q) → q fausse. Cliquez sur cette ligne.
¬(p ∨ q) → q
1p = 1, q = 1
2p = 1, q = 0
3p = 0, q = 1
4p = 0, q = 0
Afficher les indices
a → b vaut 0 seulement quand a = 1 et b = 0. ¬a inverse la valeur. a ∨ b vaut 0 seulement quand les deux valent 0.
Déterminez d’abord le connecteur principal : que doivent valoir ses deux côtés pour que la formule entière soit 0 ?
Donnez à chaque partie sa propre colonne : p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Afficher la réponse et l’explication
Tables de vérité : une formule à n variables distinctes a 2ⁿ lignes, une pour chaque combinaison de valeurs de vérité (1 = vrai, 0 = faux). Travaillez de l’intérieur vers l’extérieur et donnez à chaque sous-formule sa propre colonne. ¬a inverse la valeur ; a ∧ b vaut 1 seulement quand les deux valent 1 ; a ∨ b vaut 0 seulement quand les deux valent 0 ; a → b vaut 0 seulement quand a = 1 et b = 0 ; a ↔ b vaut 1 quand les deux côtés sont égaux.
Quelle formule est logiquement équivalente à (b ∧ c) → a ? Cliquez dessus.
(b ∧ c) → a
1(b → a) ∧ (c → a)
2b → (c → a)
3b ∧ (c → a)
4(b → c) → a
Afficher les indices
Des formules équivalentes s’accordent dans chaque ligne de la table de vérité. Une seule ligne où elles diffèrent élimine une option.
Essayez une ligne qui donne 0 à (b ∧ c) → a et vérifiez quelles options valent aussi 0 sur cette ligne.
Exportation : (a ∧ b) → c ≡ a → (b → c). Les deux valent 0 seulement quand a = 1, b = 1 et c = 0.
Afficher la réponse et l’explication
Équivalence logique : deux formules sont équivalentes (≡) quand elles ont la même valeur dans chaque ligne de la table de vérité. Une tautologie vaut 1 dans toutes les lignes, une contradiction 0 dans toutes les lignes, et une contingence n’est ni l’une ni l’autre. Lois utiles : De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b et ¬(a ∨ b) ≡ ¬a ∧ ¬b ; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contraposée) ; ¬(a → b) ≡ a ∧ ¬b ; et les lois de distributivité, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
La loi
Exportation : (a ∧ b) → c ≡ a → (b → c). Les deux valent 0 seulement quand a = 1, b = 1 et c = 0.
(b ∧ c) → a ≡ b → (c → a)
Vérifier avec la table de vérité
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 0 1
a = 1, b = 0, c = 0: 1 | 1 1 0 1
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0
Réponse
b → (c → a)
Les colonnes après la barre sont les options dans l’ordre affiché.
Exemple 3Difficile
Les prémisses (q ∧ p) → r; q; ¬r sont données. Quelle conclusion en découle ? Cliquez dessus.
(q ∧ p) → rq¬r
1p
2p ∧ ¬r
3¬p
4r
Afficher les indices
Une conclusion découle des prémisses quand elle vaut 1 dans toutes les lignes où toutes les prémisses valent 1.
Trouvez les lignes où toutes les prémisses valent 1, puis testez chaque option dans ces lignes.
C’est une règle standard : modus tollens avec une conjonction.
Afficher la réponse et l’explication
Quantificateurs et raisonnements : ¬∀x P(x) ≡ ∃x ¬P(x) et ¬∃x P(x) ≡ ∀x ¬P(x). Faites passer une négation vers l’intérieur, échangez chaque quantificateur qu’elle traverse, et niez la formule intérieure avec les lois propositionnelles, comme ¬(a → b) ≡ a ∧ ¬b. Un raisonnement est valide quand la conclusion vaut 1 dans toutes les lignes où toutes les prémisses valent 1. Une seule ligne avec des prémisses vraies et une conclusion fausse est un contre-exemple et montre que le raisonnement est invalide.
Lignes où toutes les prémisses sont vraies
p = 0, q = 1, r = 0: p = 0, p ∧ ¬r = 0, ¬p = 1, r = 0
Conclusion
¬p (modus tollens avec une conjonction)
Réponse
¬p
Questions et réponses
Logique propositionnelle et preuves : de quoi s’agit-il ?
Une proposition est un énoncé qui est soit vrai, soit faux, comme « 7 est premier ». On la note avec une lettre, p ou q, et sa valeur de vérité par 1 (vrai) ou 0 (faux).
Les connecteurs construisent des formules plus grandes à partir de plus petites :
Logique propositionnelle et preuves : comment résoudre les exercices étape par étape ?
Comptez les variables distinctes : la table de vérité a 2ⁿ lignes, la première avec toutes les variables à 1.
Donnez à chaque sous-formule sa propre colonne et remplissez les colonnes de l’intérieur vers l’extérieur.
Appliquez la règle de chaque connecteur : → n’est 0 que pour 1 → 0, ↔ vaut 1 quand les deux côtés sont égaux.
Pour des équivalences, comparez les colonnes finales ligne par ligne ; pour un raisonnement, regardez seulement les lignes où toutes les prémisses valent 1.
Pour nier un énoncé quantifié, faites passer ¬ vers l’intérieur, échangez ∀ et ∃, et niez la formule intérieure.
Logique propositionnelle et preuves : quelles sont les erreurs fréquentes ?
Considérer p → q comme fausse quand p est fausse.
Compter deux fois une variable répétée en cherchant le nombre de lignes.
Confondre la contraposée ¬q → ¬p avec la réciproque q → p.
Nier ∀x P(x) par ∀x ¬P(x) au lieu de ∃x ¬P(x).
Appliquer De Morgan sans échanger ∧ et ∨.
Logique propositionnelle et preuves : que couvrent les exercices ?
Facile: tables de vérité
Moyen: équivalences et méthodes de preuve
Difficile: quantificateurs et raisonnements
Chaque exercice a de nouvelles valeurs : vous apprenez la méthode, pas une réponse. Bloqué ? Ouvrez d’abord un petit indice, et l’explication complète seulement si vous en avez besoin.
Comment fonctionne l’entraînement
Chaque exercice a de nouvelles valeurs : vous apprenez la méthode, pas une réponse.
Bloqué ? Ouvrez d’abord un petit indice, et l’explication complète seulement si vous en avez besoin.
Votre progression, vos erreurs et vos exercices enregistrés sont conservés pour que vous puissiez réviser avant l’examen.