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

Tags:
1. Mar 21, 2016

Math_QED

• Thread moved from the technical forums, so no HH Template is shown.
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 :)

2. Mar 21, 2016

Staff: Mentor

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

3. Mar 21, 2016

stevendaryl

Staff Emeritus
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)

4. Mar 21, 2016

Math_QED

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)