How to prove P^Q -||- ¬(¬Pv¬Q)?

Question

How do you prove P^Q -||- ¬(¬Pv¬Q)?

I would appreciate any help or tips so that I can be able to solve it!

What I'm sure of is the following:

P^Q                     Hyp
P                       ^I1
Q                       ^I2
¬Pv¬Q                   ass
.
.
.
¬Pv¬Q => ¬              (=>I)
¬Pv¬Q =>                (=>I)
¬(¬Pv¬Q)                (¬I)

Answer 1

For the first direction you have almost got it. You just Have to show a contradiction and that is it.

1. $P\land Q$ (premise)
2. $\lnot P \lor \lnot Q$ (assumption)
3. $P$ (from 1, &out)
4. $\lnot \lnot P$ (from 3, double $\lnot$in)
5. $\lnot Q$ (from 2,3, $\lor$out)
6. $Q$ (from 1, &out)
7. $Q\land \lnot Q$ (from 5, 6, &in)
8. $\bot$ (from7, contradiction in)

Therefore, $P\land Q \vdash ¬(¬Pv¬Q)$

This is for the other direction:

1. $\lnot(\lnot P \lor \lnot Q)$ (premise)
2. $\lnot (P\land Q)$ (Assumption)
3. $P\land Q$ (from 1, $\lnot \lor$out)
4. $\lnot P \lor \lnot Q$ (from 2, $\lnot$&out)
5. $P$ (from 3, &out)

Contnuing from 5 hopefully you can show a contradiction.

Answer 2

You have derived $P$ and $Q$ from $P\land Q$, so further assuming $\lnot P$ or $\lnot Q$ leads to contradiction in both cases. $\lnot P\to\bot$ and $\lnot Q\to\bot$.

Then you may derive a contradiction from $P\land Q$ and $\lnot P\lor\lnot Q$ by eliminating the disjunction.

Introduce the negation and you are done; $\lnot (\lnot P\lor\lnot Q)$ is derived from $P\land Q$.

---

Conversely, from a premise of $\lnot (\lnot P\lor\lnot Q)$, a contradiction may be derived assumption of $\lnot P$ or of $\lnot Q$. After either, just introduce a disjunction to derive $\lnot P\lor\lnot Q$, then eliminate the negation.

So make those assumptions, derive those contradictions, so as to introduce two negations, eliminated the double negations that result, and finally introduce a conjunction to thusly derive $P\land Q$ from $\lnot(\lnot P\lor\lnot Q)$

Answer 3

A different way of looking at it involves using a truth table :