Given ¬(p ∨ q), use the Fitch system to prove (¬p ∧ ¬q).

Question

So, I understood that in order to succeed I should prove ¬p and ¬q and then use And Introduction. However, I don't seem to figure out how to do this and was only able to prove (¬p ∨ ¬q) (I'm not sure if I'm even on the right path) I hope somebody can help me out

Answer 1

This is one of De Morgan's laws

$\lnot\left(p\lor q\right)$

$p\quad$ hyp.

$p\lor q$

$\left(p\lor q\right)\land\left(\lnot\left(p\lor q\right)\right)$

$\lnot p$

$q\quad$ hyp.

$p\lor q$

$\left(p\lor q\right)\land\left(\lnot\left(p\lor q\right)\right)$

$\lnot q$

$\lnot p\land\lnot q$

You just need to fill in the justification for each line.

Answer 2

proof

GOAL:     ~p  &  ~q                    conclusion 

so we need to derive ~p and we also need to derive ~q

we are given no atomic expressions in the premise set, therefore reductio ad absurdum is the only way forward.

Assume the negation of what you want to prove and show that this negation results in a contradiction

In this case we want to prove ~p so we start by assuming p and then showing that p entails a contradiction.

1.     ~(p|q)                    premise
2.         p                     assumption 
3.         ~(p|q)                reiteration                 1
4.     p => ~(p|q)               implication introduction    2-3
5.         p                     assumption                  
6.         p|q                   or introduction             6
7.     p =>  (p|q)               implication introduction    5-6

Thus we have a contradiction. How can p imply both ~(p|q) and (p|q)? We can thus conclude that ~p is the case.

8.     ~p                         negation introduction      4,7

We need to repeat this process to produce ~q

9.          q                     assumption 
10.         ~(p|q)                reiteration                 1
11.     q => ~(p|q)               implication introduction    10-11
12.         q                     assumption                  
13.         p|q                   or introduction             13
14.     q =>  (p|q)               implication introduction    13-14
15.     ~q                        negation introduction       12,15

Now it is easy to derive our conclusion

16.     ~p & ~q                   and introduction            8, 15 

Answer 3

Here is another way to prove with Fitch printscreen in fitch Note: lines without numbers mean a subproof

1. ¬(R v S)

   R

   R v S :V Intro 2

   ⊥ :⊥Intro 1,3

   5. ¬R :¬ Intro 2-5

      S

      R V S :v Intro 6

      ⊥ :⊥Intro 7,1

   6. ¬S :¬ Intro 6-7

   10.¬R∧¬S : ∧ Intro 5,9