# I need help with logic

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.

Last edited:

Related Introductory Physics Homework Help News on Phys.org
honestrosewater
Gold Member
Are those your assumptions (aka premises)? What are you trying to prove?

honestrosewater said:
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
Gold Member
_E_ said:
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.

Last edited:
AKG
Homework Helper
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))

?

AKG said:
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.
_E_ said:
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
Gold Member
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
Homework Helper
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?

AKG said:
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
Gold Member
_E_ said:
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?

Last edited:
AKG
Homework Helper
Code:
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.)