Show that the proof rule is not sound and proof question

637 Views Asked by At

I'm asked to show that the proof rule

\begin{equation} \dfrac{\varphi \to \psi}{\lnot \varphi \to \lnot \psi} \end{equation}

is not sound.

To show this would I just make the truth tables for the statement above the line and below the line and show that they are not equivalent?

I'm also asked to show $\vdash p \lor \lnot p$. I can have $\lnot (p \lor \lnot p) \to p \land \lnot p$ as an assumption. When I try to move from the conclusion upward I get

\begin{equation} \dfrac{\dfrac{p \land ¬p}{p}}{p \lor \lnot p} \end{equation} as I try to move toward the assumption, but I don't think that's right because $p \lor \lnot p$ should conclude $\bot$, not $p$. If I try to move from the assumption downward toward the conclusion I'm not sure what to do because for an implication elimination wouldn't I need to have

\begin{equation} \lnot(p \lor ¬p) \to p \land \lnot p \qquad\qquad \lnot (p \lor \lnot p) \end{equation}

as an assumption rather than just

\begin{equation} \lnot (p \lor \lnot p) \to p \land \lnot p \end{equation}

1

There are 1 best solutions below

0
On

The first question is:

To show this would I just make the truth tables for the statement above the line and below the line and show that they are not equivalent?

One would check that the premise implies the conclusion noting any line in the truth table where that is not true. From that line one can build a counter-example.

enter image description here

For the second question, the OP wants to show $⊢p∨¬p$. One is permitted to use this portion of the De Morgan rules: $¬(p∨¬p)→p∧¬p $.

Proceeding the way the OP starts to show this we could derive a proof using a Fitch-style proof checker as follows:

enter image description here