CODEWITHSUNDEEP
mathlogic
Adam Taylor
Adam Taylor

Reputation: 7793

Difficulty understand logic

Ok so I have to prove the following sequent:

(p -> r) ^ (q -> r) |- p ^ q -> r

I understand why that is clearly correct and I also understand the rules of natural deduction. What I don't understand is how I go about proving it. Here is the model answer provided:

1. (p -> r) ^ (q -> r) |- p ^ q -> r     premise
2. p ^ q                                 assumption
3. p                                     ^e 2
4. p -> r                                ^e 1
5. r                                     ->e 4,3
6. p ^ q -> r                            ->i 2,5

(e = elimination / i = introduction).

Could someone provide me with a link or a 'dumbed-down' explanation? I feel like I am missing a simple concept that is causing this to be hard to understand... ?

For example, on line 4, why does it require the p from line 3 to remove the ->, where as in line 3, you can remove the ^ q without using a q?

I am sure this is quite straight forward but it doesn't seem to make sense to me... ?

Upvotes: 4

Views: 312

Answers (2)

jbradaric
jbradaric

Reputation: 856

In line 2, you have p ^ q which means that both p and q are true. From that follows that p is true, because if both of them are true, then any single one is also true.

In line 4, r is true only if p is true. And in line 3 you have that p is true. Therefore, r is also true.

Upvotes: 4

Dave
Dave

Reputation: 10575

You can remove the ^ q without using q because p ^ q means p AND q -- p is true independent of q.

You can't remove the p -> without using p because p -> r means p IMPLIES r -- r is only guaranteed to be true if p is as well.

Upvotes: 0

Related Questions