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
● 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 (𝐴 → 𝐵) ∧ (𝐵 → 𝐶) → (𝐴 → 𝐶)
Publicité
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.
𝑓(𝐴, 𝐵, 𝐶) : ((𝐴 → 𝐵) ∧ (𝐵 → 𝐶)) → (𝐴 → 𝐶)
● 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.