Question, please help

l3rian

1. Prove, using the laws of proposiional logic (truth tables not acceptable) that:

(i) from p -> q and p V r, we can logically deduce ¬r -> q
(ii) p->(q V r) equiv= (p -> q) V (p -> r)

Laws can be found here: http://www.cis.upenn.edu/~cse391/cse391_2003/laws.pdf

I would really apreicate any help.

pooka

How far have you gotten with this? You understand what all the symbols mean, right? Is the problem how you should lay out your proof, as opposed to whether or not they actually can be proved?

Cian

l3rian

Hi pooka,

I have gotten no-where with this. I understand all the symbols ok from doing truth tables, but I dont know where to start on these proofs.

I just dont have any notes or worked example of these types of questions

Exam on thursday and either the question above or the ones below is coming up.

1. Prove using the laws of propositional logic (no truth tables) that Г = {p -> q, q -> (r V s), ¬s} and φ = p -> r, then Г logically implies φ.

2. Prove using the laws of propositional logic (no truth tables), that from p-> (q V r), p and ¬q, we can logically deduce r.

If you could answer these questions for me I would pay you for any time spent, thanks

ecksor

I'm a bit rusty on applying the rules formally, but the main thing is to see for yourself why these things are clearly true. I'll try to talk through each case informally to get you started.

from p -> q and p V r, we can logically deduce ¬r -> q

p V r means that p or r or both are true at any one time. The crucial thing here being that ¬r (what we start with) implies that p must be true (otherwise). Can't have both false, so if r is false, then p must be true

p -> q, so any time we have p true, then q must be true. Since, we've shown that the starting condition leads to p being true, then it also implies that q must be true.

p->(q V r) equiv= (p -> q) V (p -> r)

This is a bit more at the statement level, since you're given two statements (p -> q) and (p -> r) and V giving that at least one of them is true. So, if p is true, then at least one of those statements is true. This can only happen if at least one of q or r is true. Which is basically a reformulation of what the first statement says. Working the other way (which you'll probably need to do unless you manage to use only iff/<-> type rules), the truth of p implies that at least one of q and r is true, which in turn means that either p implies q or p implies r, or both, which is a reformulation of the second statement says.

Prove using the laws of propositional logic (no truth tables) that Г = {p -> q, q -> (r V s), ¬s} and φ = p -> r, then Г logically implies φ.

Prove using the laws of propositional logic (no truth tables), that from p-> (q V r), p and ¬q, we can logically deduce r.

These are essentially the same as the first problem above, if you take the simplification of what the falsity of each symbol after the ¬ symbols, see what that means for the other one in the pair in the brackets with the V (i.e, if that one is false, but I know that one or the other or both is true, then ...)

If you can see your way through the logic (i.e, follow the informal argument I've made here) and practice working through from that to the formal expression, then you'll be fine. Reading a few formal examples is good, but if you don't write one or two from scratch you won't necessarily be able to do it on the day.

Let us know how you get on.

smiles

Since ecksor explained logically why they make sense, I'll just throw up how _I_ learned to prove them logically.

Firstly you should be able to use the Laws of Inferrence. Make sure you have all the notes, I'll put in the biggies you should have. (Also ~ is sometimes used instead of ¬)

Modus Ponens:
A -> B
A

---

B

Modus Tollens
A -> B
¬B

---

¬A

Disjunctive Syllogism
A V B
¬A

---

B

Similarily:
A V B
¬B

---

A

Transitivity of ->
p -> q
q -> r

---

p -> r

Or (V) Introduction
A

---

A V B

And (^) Elimination
A ^ B

---

A

Similarily:
A ^ B

---

B

(The way you read them is that if the statements above the line are present then you can assume the conclusions under the line and just quote the rules of inference and the lines the statements appeared on)

Originally posted by l3rian
1. Prove, using the laws of proposiional logic (truth tables not acceptable) that:
(i) from p -> q and p V r, we can logically deduce ¬r -> q

State the given statements:
1. p -> q (given)
2. p V r (given)

State the proposition to be proved:
3. ¬r (proposition)

State what you have deduced and beside it declare how you did it.
4. ¬r -> p (Disjunctive Syllogism on 2, 3)
5. ¬r -> q (Transitivity of -> on 4, 1)

That should do it.

Prove using the laws of propositional logic (no truth tables) that Г = {p -> q, q -> (r V s), ¬s} and φ = p -> r, then Г logically implies φ.

Deal with the Г components first.

1. p -> q (given)
2. q -> (r V s) (given)
3. ¬s (given)

4. p -> (r V s) (Transitivity of -> (1,2))
5. p -> r (Disjunctive Syllogism (4, 3))
6. Г -> φ (since you can prove φ given Г)

Prove using the laws of propositional logic (no truth tables), that from p-> (q V r), p and ¬q, we can logically deduce r.

1. p -> (q V r) (given)
2. p (given)
3. ~q (given)

4. q V r (Modus Ponens 2,1)
5. r (Disjunctive Syllogism 4, 3)

<< Fio >>