I- Démontrer que la formule
raisonnement par l’absurde.
Réponse
𝑃 → (𝑄 → (𝑃 ∧ 𝑄))
est un théorème en utilisant un
● La formule
𝑓(𝑃, 𝑄): 𝑃 → (𝑄 → (𝑃 ∧ 𝑄))
est un théorème ( est une tautologie ) ssi sa
réfutation
closes.
𝑃 → (𝑄 → (𝑃 ∧ 𝑄))
est la racine d’un arbre dont toutes les branches sont
Publicité
● Dresser l’arbre :
𝑃 → (𝑄 → (𝑃 ∧ 𝑄))
𝑃
)
(𝐴 → 𝐵
𝐴
𝑄 → (𝑃 ∧ 𝑄)
𝐵
𝑄
𝑃 ∧ 𝑄
𝑃 𝑄
⊥ ⊥
Publicité
● Toutes les branches de l’arbre de Beth sont closes; la réfutation de f conduit à une
contradiction donc la formule f(P,Q) est une tautologie, c’est un théorème
(𝐴 → 𝐵) ∧ (𝐵 → 𝐶) → (𝐴 → 𝐶)
est une tautologie en utilisant un
II- Démontrer que la formule
raisonnement par l’absurde.
Réponse
● La formule
𝑓(𝐴, 𝐵, 𝐶) : ((𝐴 → 𝐵) ∧ (𝐵 → 𝐶)) → (𝐴 → 𝐶)
est une tautologie ssi sa
réfutation
toutes les branches sont closes.
Publicité
𝑓(𝐴, 𝐵, 𝐶) : ((𝐴 → 𝐵) ∧ (𝐵 → 𝐶)) → (𝐴 → 𝐶)
● Dresser l’arbre( ou encore la table de Beth)
est la racine d’un arbre dont
*
((𝐴 → 𝐵) ∧ (𝐵 → 𝐶)) → (𝐴 → 𝐶)
*
(𝐴 → 𝐵) ∧ (𝐵 → 𝐶)
*
𝐴 → 𝐶
*
𝐴 → 𝐵
𝐵 → 𝐶
Publicité
𝐴
𝐶
𝐴 𝐵
𝐵 𝐶 𝐵 𝐶
⊥ ⊥ ⊥ ⊥
● Toutes les branches de l’arbre de Beth sont closes c’est à dire la réfutation de
f(A,B,C) conduit à une contradiction donc f est une tautologie.