Prove the two logic expressions are equal

Question

Prove $\neg(a \lor b)$ is the same as $(\neg a \land \neg b)$

It makes sense when I think about it, but how does one prove it?

Also is there a relationship with the above and saying: $(a \implies b)$ is the same as its contrapositive $(\neg b \implies \neg a)$ ?

Answer 1

To prove it, write out a logic table with the four cases for $a$ and $b$.

You can write a similar truth table proof out to show the equivalence of $a \Rightarrow b$ and its contrapositive. See this question and answer. The formal proof (see my answer to the linked question) uses a slightly different construction that the ones you are asking about.

Answer 2

We are required to show that $$¬(a∨b) \vdash (¬a∧¬b)$$

I assume the natural deduction method:

1. $\neg(¬a∧¬b)$, H

2. $a$, H
3. $a \vee b$, 2, ∨I
4. $\neg(a \vee b)$, P

5. $\neg a$, 3,4,¬I

6. $b$, H
7. $a \vee b$, 6, ∨I

8. $\neg b$, 4,7 ¬I
9. $\neg a \wedge \neg b$, 2,8 ∧I

10. $\neg\neg(\neg a \wedge \neg b)$, 1,9 ¬I
11. $(\neg a \wedge \neg b)$, 10, DNE

Observe the way we conduct the reasoning by contradiction. Now, can you repeat the proof?

Answer 3

Truth Table is my favorite option

As you can see. LHS=RHS