I need help with logic

[_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 ^ ~STry 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. ~ <--> ~STypo?
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 premisisIf 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.)