• Support PF! Buy your school textbooks, materials and every day products Here!

I need help with logic

  • Thread starter _E_
  • Start date
  • #1
_E_
4
0
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:

Answers and Replies

  • #2
honestrosewater
Gold Member
2,105
5
Are those your assumptions (aka premises)? What are you trying to prove?
 
  • #3
_E_
4
0
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.
 
  • #4
honestrosewater
Gold Member
2,105
5
_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:
  • #5
AKG
Science Advisor
Homework Helper
2,565
3
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))

?
 
  • #6
_E_
4
0
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.
Sorry about the confusion.
_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
 
  • #7
honestrosewater
Gold Member
2,105
5
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?
 
  • #8
AKG
Science Advisor
Homework Helper
2,565
3
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?
 
  • #9
_E_
4
0
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
 
  • #10
honestrosewater
Gold Member
2,105
5
_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:
  • #11
AKG
Science Advisor
Homework Helper
2,565
3
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.)
 

Related Threads for: I need help with logic

  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
0
Views
900
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
18
Views
7K
  • Last Post
Replies
10
Views
4K
Replies
2
Views
13K
Replies
3
Views
851
  • Last Post
Replies
9
Views
5K
Top