Exercices Table de Beth
Les formules suivantes sont-elles des théorèmes ? Justiier en appliquant un raisonnement par l’absurde (
càd on utilisera la méthode de la table de Beth);
1-
⊢𝑃 → 𝑄 → 𝑃 ∧ 𝑄
(
?
)
La formule
une contradiction ( antilogie) càd toutes les branches de l’arbre de Beth sont closes.
est un théorème ( une tautologie) ssi la réfutation de
(
𝑓(𝑃, 𝑄): 𝑃 → 𝑄 → (𝑃 ∧ 𝑄)
)
𝑓 𝑓
( ) est
)
𝑃 → 𝑄 → (𝑃 ∧ 𝑄)
(
*
𝑃
𝑄 → (𝑃 ∧ 𝑄)
*
𝑄
𝑃 ∧ 𝑄
*
𝑃
⊥
𝑄
⊥
Règle de contradiction : ⊥
une branche est close ssi elle porte une contradiction sur au moins un des atomes qui constituent la
formule;
est exprimée en fonction de
Publicité
𝑃 𝑒𝑡 𝑄
𝑓
:
● si ,
𝑃
puis on trouve : c’est une contradiction
𝑃
● si ,
𝑃
puis on trouve : c’est une contradiction
𝑃
● si ,
𝑄
puis on trouve : c’est une contradiction
𝑄
● si ,
𝑄
puis on trouve : c’est une contradiction
𝑄
Conclusion: toutes les branches de l’arbre de Beth sont closes donc
théorème.
)
𝑓(𝑃, 𝑄): 𝑃 → 𝑄 → (𝑃 ∧ 𝑄)
(
est un
(
2 − ⊢ 𝐴 → 𝐵
La formule
)?
(
) → 𝐴 → 𝐶
) ∧ 𝐵 → 𝐶
(
) → 𝐴 → 𝐶
Publicité
)
) ∧ 𝐵 → 𝐶
𝑓(𝐴, 𝐵, 𝐶): 𝐴 → 𝐵
(
(
(
(
)
est un théorème ssi
𝑓(𝐴, 𝐵, 𝐶): 𝐴 → 𝐵
(
(
)
) → 𝐴 → 𝐶
(
)
) ∧ 𝐵 → 𝐶
(
conduit à une contradiction.
)
) → 𝐴 → 𝐶
(
)
(
(
) ∧ 𝐵 → 𝐶
(
𝐴 → 𝐵
*
)
(
) ∧ 𝐵 → 𝐶
(
𝐴 → 𝐵
Publicité
*
𝐴 → 𝐶
*
*
𝐴 → 𝐵
𝐵 → 𝐶 *
𝐴
𝐶
𝐴
𝐵
⊥
𝐶
𝐵
⊥ ⊥
𝐵
𝐶
⊥
) → 𝐴 → 𝐶
) ∧ 𝐵 → 𝐶
𝐴 → 𝐵
)
(
)
(
(
(
*
)
(
) ∧ 𝐵 → 𝐶
(
𝐴 → 𝐵
*
𝐴 → 𝐶
Publicité
*
𝐴 → 𝐵
𝐵 → 𝐶 *
𝐵
𝐶
𝐴
𝐴
𝐶
𝐵
𝐴
𝐶
𝐴
𝐴
𝐶
𝐵
𝐴
𝐶
la première branche porte une contradiction sur A
la deuxième branche porte une contradiction sur A et C
la troisième branche porte une contradiction sur B
la quatrième branche porte une contradiction sur C
Conclusion toutes les branches de l’arbre de Beth sont closes donc
𝑓(𝐴, 𝐵, 𝐶): 𝐴 → 𝐵
)
) → 𝐴 → 𝐶
(
)
) ∧ 𝐵 → 𝐶
est un théorème.
(
(
(