Fiche de révision : Logique propositionnelle et preuves

📋 Plan du Cours

1. Évaluation des formules propositionnelles
2. Transitivité de l’implication
3. Transformations et table de vérité

📖 1. Évaluation des formules propositionnelles

★ À maîtriser

• 🔄 La vérification suit plusieurs étapes:

  1. Réécrire les implications avec des disjonctions
  2. Appliquer les transformations logiques
  3. Constater que les deux composantes sont vraies

• La formule $(R\Rightarrow S)\Rightarrow[(S\Rightarrow T)\Rightarrow(R\Rightarrow T)]$ est vraie.

Compléments

• La formule $(\neg R\lor T\lor S\lor R)\land(\neg R\lor T\lor S\lor\neg S)$ est vraie.

💡 Astuce mémo

Remplacer les implications, distribuer, puis constater les valeurs vraies.

📖 2. Transitivité de l’implication

★ À maîtriser

• Pour démontrer la transitivité, on suppose que R ⇒ S et S ⇒ T sont vraies, que R est vraie et que T est fausse ; comme S ⇒ T est vraie alors que T est fausse, S est fausse, puis comme R ⇒ S est vraie alors que S est fausse, R est fausse, ce qui contredit R vraie.

📌 Dans la démonstration par contradiction, R vraie et R fausse sont simultanément obtenues, ce qui rend l’hypothèse contradictoire.

Compléments

• La formule $(R\Rightarrow S)\Rightarrow[(\neg R\lor T)\lor(S\land\neg T)]$ se transforme en $(R\Rightarrow S)\Rightarrow(\neg R\lor T\lor S)$ parce que la composante $\neg R\lor T\lor\neg T$ est vraie.

💡 Astuce mémo

R ⇒ S et S ⇒ T entraînent R ⇒ T.

📖 3. Transformations et table de vérité

★ À maîtriser

• La négation de l’implication S ⇒ T se transforme ainsi : $\neg(S\Rightarrow T)\Leftrightarrow\neg(\neg S\lor T)\Leftrightarrow S\land\neg T$.

• La formule $(R\oplus S)\Rightarrow[(S\Rightarrow T)\Rightarrow(R\Rightarrow T)]$ se réécrit $(R\oplus S)\Rightarrow[(S\land\neg T)\lor(\neg R\lor T)]$.

• Les huit valuations possibles sont:

  • VVV
  • VVF
  • VFV
  • VFF
  • FVV
  • FVF
  • FFV
  • FFF

• Dans la table fournie, la colonne A→D vaut V pour chacune des huit valuations de R, S et T.

Compléments

• La formule $\neg(\neg R\lor S)\lor(\neg R\lor T\lor S)$ se transforme en $(R\land\neg S)\lor(\neg R\lor T\lor S)$, puis en une forme où les deux termes sont réunis par distributivité.

💡 Astuce mémo

Une contradiction oppose R vraie et R fausse ; une table vérifie chaque valuation.