1
$\begingroup$

I am trying to show (~P v Q) is in contradiction with (P^~Q) as part of a larger proof.

I am having a hard time wrapping my head around it because it is really obvious informally. I am given (~P v Q) and I have established (P^~Q)--initially, I thought this would be sufficient to prove that the two are a contradiction, but I can only show this using AnaCon or TautCon, both of which are not allowed by my professor.

I searched my book for a proof of DeMorgan's Equivalence (so I could turn P^~Q to have the form ~[~PvQ]) but could not find it.

The system that I am required to use is Fitch.

$\endgroup$

1 Answer 1

0
$\begingroup$

Hint

We can derive $\lnot (\lnot P \lor Q)$ from $P \land \lnot Q$:

1) $P \land \lnot Q$ --- premise

2) $\lnot P \lor Q$ --- assumed

3) $P$ --- from 1) by $\land$-elim

4) $\lnot Q$ --- from 1) by $\land$-elim

5) $\lnot P$ --- assumed [a] from 2) for $\lor$-elim

6) $\bot$ --- contradiciton: from 3) and 5)

7) $Q$ --- assumed [b] from 2) for $\lor$-elim

8) $\bot$ --- contradiciton: from 4) and 7)

9) $\bot$ --- from 2), 5)-6) and 7)-8) by $\lor$-elim, discharging [a] and [b]

10) $\lnot (\lnot P \lor Q)$ --- from 2) and 9) by $\lnot$-intro, discharging assumption 2).

In conclusion:

$P \land \lnot Q \vdash \lnot (\lnot P \lor Q)$.

The same for the other "direction".

$\endgroup$
4
  • $\begingroup$ Thank you, the hint was just what I needed! But what if I have ~P v Q as a previous assumption, should I still assume the same statement after I have established P^~Q? Essentially repeating it? Would that be necessary if the latter statement, P^~Q came after ~P v Q? $\endgroup$
    – Matt
    Apr 28, 2017 at 8:02
  • $\begingroup$ @Matt - not clear... You are saying: to swap 1) and 2) to prove : $\lnot (P \land \lnot Q)$ from $\lnot P \lor Q$ ? $\endgroup$ Apr 28, 2017 at 8:09
  • $\begingroup$ My bad. Imagine that I already have ~P v Q as step #5, then I manage to establish P^~Q as step #8, do I then have to assume ~P v Q again as step #9 (in order to obtain ~(~PvQ) or could I have used the ~PvQ from step #5? $\endgroup$
    – Matt
    Apr 28, 2017 at 8:38
  • $\begingroup$ You can re-use it. $\endgroup$ Apr 28, 2017 at 8:43

You must log in to answer this question.

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