logical equivalence

[ Follow Ups ] [ Post Followup ] [ Main Message Board ] [ FAQ ]

Posted by Joel on September 25, 2002 at 19:06:03:

[(p -> q) ^ (q -> r)] -> (p -> r)

This statement is a tautology. It can easily be proven to be a tautology using a truth table, but I have to prove it without using a truth table. Here's what I have (using ~ for negation, ^ for conjunction, v for disjunction, -> for implication, and <==> for equivalence):

[(p -> q) ^ (q -> r)] -> (p -> r) (SAME AS ABOVE)
~[(p -> q) ^ (q -> r)] v (p -> r)
[~(p -> q) v ~(q -> r)] v (p -> r)
[~(~p v q) v ~(~q v r)] v (~p v r)
[(p ^ ~q) v (q ^ ~r)] v (~p v r)

Here I'm stuck, as far as formal proof is concerned. It's easy to see, just looking at the expression within the brackets, that if q is true, the truth value of that expression is equal to the truth value of ~r, and if q is false, the truth value of the expression is equal to the truth value of p, so somehow that expression has to boil down to (p v ~r) which is the exact contradiction of the expression on the right, thus proving the tautology. But that is not a formal proof and I can't find the steps to show that
[(p ^ ~q) v (q ^ ~r)] <==> (p v ~r).

Help!

Follow Ups:

did you do a www.google.com search :) Denis Borris 20:53:16 09/25/02 (2)
- Got it! Believe me, you don't want to try to figure this out. n/t Joel 02:06:46 09/26/02 (1)
  - we'll take your word for it! Denis Borris 15:55:24 09/26/02 (0)

Post a Followup

Name:
E-Mail:

Subject:

Comments:
: [(p -> q) ^ (q -> r)] -> (p -> r) : This statement is a tautology. It can easily be proven to be a tautology using a truth table, but I have to prove it without using a truth table. Here's what I have (using ~ for negation, ^ for conjunction, v for disjunction, -> for implication, and <==> for equivalence): : [(p -> q) ^ (q -> r)] -> (p -> r) (SAME AS ABOVE) : ~[(p -> q) ^ (q -> r)] v (p -> r) : [~(p -> q) v ~(q -> r)] v (p -> r) : [~(~p v q) v ~(~q v r)] v (~p v r) : [(p ^ ~q) v (q ^ ~r)] v (~p v r) : Here I'm stuck, as far as formal proof is concerned. It's easy to see, just looking at the expression within the brackets, that if q is true, the truth value of that expression is equal to the truth value of ~r, and if q is false, the truth value of the expression is equal to the truth value of p, so somehow that expression has to boil down to (p v ~r) which is the exact contradiction of the expression on the right, thus proving the tautology. But that is not a formal proof and I can't find the steps to show that : [(p ^ ~q) v (q ^ ~r)] <==> (p v ~r). : Help!

Optional Link URL:
Link Title:
Optional Image URL:

[ Follow Ups ] [ Post Followup ] [ Main Message Board ] [ FAQ ]