2
$\begingroup$

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}

$\endgroup$
1
  • 3
    $\begingroup$ For your first question, find a pair of values for $\phi$ and $\psi$ such that the formula above the line is true but the formula below is false. For your second question, see Mauro's answer. $\endgroup$
    – user524154
    Jan 6, 2019 at 19:37

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .