Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I P ^ (p -> q) => q proof

Tags:
  1. Sep 8, 2016 #1

    Math_QED

    User Avatar
    Homework Helper

    Hello everyone!

    I want to proof that:

    ##p \land (p \to q) \Rightarrow q##

    I know this is a quite trivial problem using truth tables, however, I want to do it without it. As I'm learning this myself, is this the correct approach?

    ##p \land (p \to q)##
    ##\iff p\land (\neg p \lor q)##
    ##\iff (p \land \neg p) \lor (p \land q)## (distributive law)
    Now, ##p \land \neg p## is a contradiction (see the questions below)
    ##\iff (p \land q)##

    Now, it is clear, that ##p \land q \Rightarrow q##

    Also, I have some additional questions.

    1) Suppose there is a contradiction (or tautology) r. Can we always say then, that:
    ##r \lor p \iff p##
    2) Suppose there is a contradiction r. Can we always say then, that:
    ##r \land p## is a contradiction?
    3) Suppose there is a tautology r. Can we always say then, that:
    ##r \land p \iff p##

    Thanks in advance.
     
  2. jcsd
  3. Sep 8, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Hello. How one proves that depends on what system of logical axioms and rules of inference one is using.

    If one is not using truth tables, one uses axioms and rules of inference. Two well known systems are (a) the Hilbert System and (b) Natural Deduction. Each has a set of axioms and rules of inference that are used to deduce tautologies and, given a set of non-logical axioms A, to deduce theorems of the theory T that is generated by A.

    For instance your first challenge ##(p\wedge (p\to q)\to q)## is pretty close to the rule of inference known as Modus Ponens, which is in both (a) and (b).

    Here is a list of rules that can be used in (b)
    The rules of (a) are set out in this article.
     
  4. Sep 11, 2016 #3

    Math_QED

    User Avatar
    Homework Helper

    I suppose I'm using natural deduction. Could you maybe look at the additional questions?
     
  5. Sep 11, 2016 #4

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Those three items you've quoted in your additional questions are all valid theorems of classical logic. How they are proven depends on what axioms one starts with.
     
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: P ^ (p -> q) => q proof
  1. P value? (Replies: 1)

Loading...