Help with Logic Problems: Show Answers Here

[_E_]

Hi Everyone.

I need some help with a few logic problems. For some reason I just get stuck and can't continue betond the first steps.

First one
1. P -> (Q -> R)
2 S -> (Q -> T)
3. (Q ^ ~R) ^ ~T
4. ~P ^ ~S
Show ~P ^ ~S

Second One
1. ~(P v Q) -> R
2. ~S -> ~Q
3. ~ <--> ~S
4. R v S
Show R v S

Third One
1. ([P ^ Q] v R) ^ (~R v Q) -> (P -> Q)
Show ([P ^ Q] v R) ^ (~R v Q) -> (P -> Q)

Thanks.

 

[honestrosewater]

Are those your assumptions (aka premises)? What are you trying to prove?

 

[_E_]

Are those your assumptions (aka premises)? What are you trying to prove?

Ok, sorry about not being clear enough.
I have gone back and made corrections, I have specified what I am trying to prove.

 

[honestrosewater]

First one
1. P -> (Q -> R)
2 S -> (Q -> T)
3. (Q ^ ~R) ^ ~T
Show ~P ^ ~S

Try the contrapositives of (1) and (2):
4) Q ^ ~R [from 3]
5) ~(Q -> R) -> ~P [1]
6) ~(~Q v R) -> ~P [5]
7) (~~Q ^ ~R) -> ~P [6]
8) (Q ^ ~R) -> ~P [7]
9) ~P [8, 4]

Try to get ~S the same way.

Second One
3. ~ <--> ~S

Typo?

Third One
Show ([P ^ Q] v R) ^ (~R v Q) -> (P -> Q)

Are you taking ([P ^ Q] v R) ^ (~R v Q) as a premise or trying to prove (([P ^ Q] v R) ^ (~R v Q)) -> (P -> Q) from no premises? I'm not sure which rules you have.

 

[AKG]

Looking at his first two examples, it looks as though he's just trying to prove

([P ^ Q] v R) ^ (~R v Q) -> (P -> Q)

from no premises, since in the first two examples he's also made it look like the desired conclusion is the last premise. There is a problem, however, in that this last question is ambiguous. You're missing brackets, so do you want it to be:

(([P ^ Q] v R) ^ (~R v Q)) -> (P -> Q)

or

([P ^ Q] v R) ^ ((~R v Q) -> (P -> Q))

?

 

[_E_]

Looking at his first two examples, it looks as though he's just trying to prove

([P ^ Q] v R) ^ (~R v Q) -> (P -> Q)

from no premises, since in the first two examples he's also made it look like the desired conclusion is the last premise. There is a problem, however, in that this last question is ambiguous. You're missing brackets, so do you want it to be:

(([P ^ Q] v R) ^ (~R v Q)) -> (P -> Q)

or

([P ^ Q] v R) ^ ((~R v Q) -> (P -> Q))

?

(([P ^ Q] v R) ^ (~R v Q)) -> (P -> Q)
This is the correct one.
Sorry about the confusion.

Second One
1. ~(P v Q) -> R
2. ~S -> ~Q
3. ~ <--> ~S
4. R v S
Show R v S

Also I left something out here, I forgot the P.
The corrected question is.
1. ~(P v Q) -> R
2. ~S -> ~Q
3. ~P <--> ~S

Show R v S

 

[honestrosewater]

Did you get the first one?
_______
1. ~(P v Q) -> R
2. ~S -> ~Q
3. ~P <--> ~S
Did you try reductio? Assume (~R ^ ~S) and try to derive a contradiction. If you do, you can infer ~(~R ^ ~S), which is equivalent to (R v S). Here's a start:
4)) ~R ^ ~S [assumption]
5)) ~R [4]
6)) ~R -> ~~(P v Q) [1]
7)) ~R -> (P v Q) [6]
8)) P v Q [7, 4 (now try to derive ~(P v Q), which is equivalent to (~P ^ ~Q)]
9)) ~S [4]
... can you see it from here? There may be a shorter way that I just can't see yet, but if the proof works...
_________
How far can you get by yourself on the last one?

 

[AKG]

Could you also specify what rules you have to work with. honestrosewater has recommended that you do things like show ~(P v Q) and use the fact that it is equivalent to (~P ^ ~Q). But are you allowed to use DeMorgan's Law (the one that allows you to infer (~P ^ ~Q) directly from ~(P v Q)) or would you have to derive one of those sentences from the other?

 

[_E_]

Could you also specify what rules you have to work with. honestrosewater has recommended that you do things like show ~(P v Q) and use the fact that it is equivalent to (~P ^ ~Q). But are you allowed to use DeMorgan's Law (the one that allows you to infer (~P ^ ~Q) directly from ~(P v Q)) or would you have to derive one of those sentences from the other?

Well DeMorgan's law is not allowed for these problems.
I am trying to use an indirect approach to solve them.

Also, (([P ^ Q] v R) ^ (~R v Q)) -> (P -> Q) is a Theorem.
So I have to solve it without premisis

 

[honestrosewater]

Well DeMorgan's law is not allowed for these problems.
I am trying to use an indirect approach to solve them.

Also, (([P ^ Q] v R) ^ (~R v Q)) -> (P -> Q) is a Theorem.
So I have to solve it without premisis

If your rules are complete, you can prove DeMorgan's laws with them - it's just more work for you. Anywho, what rules do you have? There are many different sets of rules possible.
These?
http://en.wikipedia.org/wiki/Propositional_calculus#Inference_rules
These?
http://www.mathpath.org/proof/proof.inference.htm
Different ones?

 

[AKG]

1  | (((P & Q) v R) & (~R v Q))      assumption
   |--------------------------
2  || P                           assumption
   ||-------------------------
3  || ((P & Q) v R)          from 1
4  || (~R v Q)               from 1
5  ||| ~Q                     assumption
   |||------------------------
6  |||| ~R                      assumption 
   ||||-----------------------
7  |||| ~R                        from 6
   |||
8  |||| Q                             assumption
   ||||-----------------------
9  ||||| R                           assumption
   |||||----------------------
10 ||||| Q                           from 8
11 ||||| ~Q                          from 5
12 |||| ~R                           from 9-11 (reductio)
13 ||| ~R                            from 4, 6-7, 8-12 (disjunction elimination)
14 |||| R                          assumption
   ||||-----------------------
15 |||| R                            from 14
   |||
16 |||| (P & Q)                      assumption
   ||||-----------------------
17 ||||| ~R                           assumption
   |||||----------------------
18 ||||| Q                              from 16
19 ||||| ~Q                            from 5
20 |||| R                           from 17-19
21 ||| R                            from 3, 14-15, 16-20 (disj. elim.)
22 || Q                           from 3, 13, 21 (reductio)
23 | (P -> Q)                   from 2, 22 (conditional introduction)
24 ((((P & Q) v R) & (~R v Q)) -> (P -> Q))      from 1, 23 (cond. intro.)