Logic: proof that [p -> (q ^ r)] <=> [(p ^ -q) -> r]

[member 587159]

I'm preparing for college on my own. I need to proof that:

[p -> (q v r)] and [(p ^ -q) -> r] are logically equivalent.

with
1) v "or"
2) ^ "and"
3) -q "negation of q"

I did this using truth tables and this perfectly shows that those 2 statements are logically equivalent. Can someone confirm that this is the way of proving this? Is there an easier way? Keep in mind that I learned this matter myself so I will most likely not understand difficult answers :)

Thanks in advance.

 

[Mark44]

I'm preparing for college on my own. I need to proof that:

[p -> (q v r)] and [(p ^ -q) -> r] are logically equivalent.

with
1) v "or"
2) ^ "and"
3) -q "negation of q"

I did this using truth tables and this perfectly shows that those 2 statements are logically equivalent. Can someone confirm that this is the way of proving this? Is there an easier way?

Sounds good to me. Using truth tables is probably the easiest way to go.

Keep in mind that I learned this matter myself so I will most likely not understand difficult answers :)

Thanks in advance.

 

[stevendaryl]

I'm preparing for college on my own. I need to proof that:

[p -> (q v r)] and [(p ^ -q) -> r] are logically equivalent.

with
1) v "or"
2) ^ "and"
3) -q "negation of q"

I did this using truth tables and this perfectly shows that those 2 statements are logically equivalent. Can someone confirm that this is the way of proving this? Is there a simpler or easier way? Keep in mind that I learned this matter myself so I will most likely not understand difficult answers :)

Thanks in advance.

Well, truth tables are a perfectly good way to establish tautologies in classical propositional logic. An alternative that is useful for understanding proof theory is to establish it using axioms and rules of inference. There are lots of different ways to axiomatize propositional logic, but here's one way:

Axioms:

1. A \rightarrow (B \rightarrow A)
2. (A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C))
3. A \rightarrow (A \vee B)
4. B \rightarrow (A \vee B)
5. (A \rightarrow C) \rightarrow ((B \rightarrow C) \rightarrow ((A \vee B) \rightarrow C))
6. A \rightarrow (B \rightarrow (A \wedge B))
7. (A \rightarrow (B \rightarrow C)) \rightarrow ((A \wedge B) \rightarrow C)
8. A \rightarrow (\neg A \rightarrow B)
9. (\neg (\neg A)) \rightarrow A
10. (A \leftrightarrow B) \rightarrow (A \rightarrow B)
11. (A \leftrightarrow B) \rightarrow (B \rightarrow A)

Rule of inference: (Modus ponens is the name of this rule)

From A, and A \rightarrow B, conclude B.​

With this style of deduction, a proof consists of a sequence of statements such that every statement is either a substitution instance of an axiom (that is, replace each propositional variable by a full boolean expression), or follows from previous statements by modus ponens.

For example: To prove the trivial fact (A \wedge B) \rightarrow A:

1. A \rightarrow (B \rightarrow A) (Axiom 1)
2. (A \rightarrow (B \rightarrow A)) \rightarrow ((A \wedge B) \rightarrow A) (Axiom 7 with C replaced by A)
3. (A \wedge B) \rightarrow A (By Modus Ponens from 1 and 2)

 

[member 587159]

Well, truth tables are a perfectly good way to establish tautologies in classical propositional logic. An alternative that is useful for understanding proof theory is to establish it using axioms and rules of inference. There are lots of different ways to axiomatize propositional logic, but here's one way:

Axioms:

1. A \rightarrow (B \rightarrow A)
2. (A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C))
3. A \rightarrow (A \vee B)
4. B \rightarrow (A \vee B)
5. (A \rightarrow C) \rightarrow ((B \rightarrow C) \rightarrow ((A \vee B) \rightarrow C))
6. A \rightarrow (B \rightarrow (A \wedge B))
7. (A \rightarrow (B \rightarrow C)) \rightarrow ((A \wedge B) \rightarrow C)
8. A \rightarrow (\neg A \rightarrow B)
9. (\neg (\neg A)) \rightarrow A
10. (A \leftrightarrow B) \rightarrow (A \rightarrow B)
11. (A \leftrightarrow B) \rightarrow (B \rightarrow A)

Rule of inference: (Modus ponens is the name of this rule)

From A, and A \rightarrow B, conclude B.​

With this style of deduction, a proof consists of a sequence of statements such that every statement is either a substitution instance of an axiom (that is, replace each propositional variable by a full boolean expression), or follows from previous statements by modus ponens.

For example: To prove the trivial fact (A \wedge B) \rightarrow A:

1. A \rightarrow (B \rightarrow A) (Axiom 1)
2. (A \rightarrow (B \rightarrow A)) \rightarrow ((A \wedge B) \rightarrow A) (Axiom 7 with C replaced by A)
3. (A \wedge B) \rightarrow A (By Modus Ponens from 1 and 2)

Thanks for the answer. I think this might be more useful when you need to prove more difficult things, other than the expression I initially listed above. Truth tables can become very large when you have a large expression so I suppose that this is easier to use then (with some practise of course)