We define a new proof system N over the connectors: {∨,¬} For every α and β-

𝐴1: (𝛼 ∨ (𝛽 ∨ (¬𝛼))) (axiom)


𝑀𝑃1: if we have 𝛼, 𝛽 then we can deduce (¬(¬(α∨β)))

𝑀𝑃2: if we have ((¬α)∨(¬β)) then we can deduce (α∨β)

Prove/refute: For every α if ⊢α in the new system (defined above) then ⊢CPLα (classical propositional logic)

(I have asked the question before, but did not get any answer - and so far I know that it must be refuted)


Classical Propositional Logic calculus is sound and complete for classical semantics, i.e.

$\vdash_{ \text {CPL} } \alpha \text { iff } \alpha \text { is a tautology.}$

Thus, the problem amounts to prove that :

$\text { if } \vdash_{ \text N } \alpha, \text { then } \alpha \text { is a tautology.}$

To do this, we have to answer to the following questions :

1) is $\text A_1$ a tautology ? [Yes: check it with truth table.]

2) are $\text {MP}_1$ and $\text {MP}_2$ sound ? i.e. do they produce TRUE conclusions from TRUE premises ?

$\text {MP}_1$ is sound : when $𝛼$ and $𝛽$ are both TRUE, also $¬(¬(α∨β))$ is.

The issue is with $\text {MP}_2$ : what happens when both $𝛼$ and $𝛽$ are FALSE ?

  • $\begingroup$ That's why I said it should be refuted rather than proven. However, the problem is that I couldn't find a counterexample. $\endgroup$ – Kamal Khalaily May 12 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.