1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Mar 21, 2016 #1

    Math_QED

    User Avatar
    Homework Helper

    • 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 :)

    Thanks in advance.
     
  2. jcsd
  3. Mar 21, 2016 #2

    Mark44

    Staff: Mentor

    Sounds good to me. Using truth tables is probably the easiest way to go.
     
  4. Mar 21, 2016 #3

    stevendaryl

    User Avatar
    Staff Emeritus
    Science Advisor

    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. [itex]A \rightarrow (B \rightarrow A)[/itex]
    2. [itex](A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C))[/itex]
    3. [itex]A \rightarrow (A \vee B)[/itex]
    4. [itex]B \rightarrow (A \vee B)[/itex]
    5. [itex](A \rightarrow C) \rightarrow ((B \rightarrow C) \rightarrow ((A \vee B) \rightarrow C))[/itex]
    6. [itex]A \rightarrow (B \rightarrow (A \wedge B))[/itex]
    7. [itex](A \rightarrow (B \rightarrow C)) \rightarrow ((A \wedge B) \rightarrow C)[/itex]
    8. [itex]A \rightarrow (\neg A \rightarrow B)[/itex]
    9. [itex](\neg (\neg A)) \rightarrow A[/itex]
    10. [itex](A \leftrightarrow B) \rightarrow (A \rightarrow B)[/itex]
    11. [itex](A \leftrightarrow B) \rightarrow (B \rightarrow A)[/itex]
    Rule of inference: (Modus ponens is the name of this rule)

    From [itex]A[/itex], and [itex]A \rightarrow B[/itex], conclude [itex]B[/itex].​

    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 [itex](A \wedge B) \rightarrow A[/itex]:
    1. [itex]A \rightarrow (B \rightarrow A)[/itex] (Axiom 1)
    2. [itex](A \rightarrow (B \rightarrow A)) \rightarrow ((A \wedge B) \rightarrow A)[/itex] (Axiom 7 with [itex]C[/itex] replaced by [itex]A[/itex])
    3. [itex](A \wedge B) \rightarrow A[/itex] (By Modus Ponens from 1 and 2)
     
  5. Mar 21, 2016 #4

    Math_QED

    User Avatar
    Homework Helper

    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)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



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