1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Truth Table Rules of Inference

  1. May 9, 2013 #1
    1. The problem statement, all variables and given/known data
    Use the rules of inference to prove the following:
    (¬p ^ q) ^ (r → p) ^ (¬r → s) ^ (s → t) ) ⇔ t.

    2. Relevant equations
    Rules of Inference I guess.

    3. The attempt at a solution
    Honestly I don't know where to start using the rules of inference. I drew a truth table and proved it was a tautology that way, but I can't see where to use the rules because it's such a long equation.
    If I could even get the first rule to use I could probably work my way from there.

    Thanks for any help.
  2. jcsd
  3. May 9, 2013 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You may have to post the rules of inference that your book is using. Not sure to what extent they are standardized.

    Sorry if this is a dumb question (I'm a bit of a noob at mathematical logic), but if you have proved that it's a tautology, doesn't that mean that there's nothing left to prove? Don't your rules of inference say that tautologies are to be considered true?
  4. May 9, 2013 #3
    1. p ⇒ p ∨ q addition
    2. p ∧ q ⇒ p simplification
    3. p ∧ (p → q) ⇒ q modus ponens
    4. ¬q ∧ (p → q) ⇒ ¬p modus tollens
    5. (p ∨ q) ∧ ¬p ⇒ q disjunctive syllogism
    6. (p → q) ∧ (q → r) ⇒ p → r hypothetical syllogism

    These are the rules that my lecture notes have written. I didn't write them because I thought they were the same for everyone XD
  5. May 9, 2013 #4
    That's correct, but I didn't use rules of inference, I drew up a truth table.
  6. May 9, 2013 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, but if you have used a truth table to show that the statement is a tautology, doesn't that mean that it can be considered an axiom? If that's the case, then you have no use for the rules of inference.

    I've been reading a little in "The foundations of mathematics" by Kenneth Kunen, which is a pretty difficult book for me, probably because I haven't taken a course like the one you seem to be taking now. He defines a proof theory with only one rule of inference, modus ponens. The simplest example of a proof from his book is to prove that ##p\land q\vdash p##, i.e. if that if we take ##p\land q## as an axiom, then ##p## is a theorem. The proof goes like this:

    0. ##p\land q\to p## (tautology)
    1. ##p\land q## (given)
    2. ##p## (modus ponens, using 0 and 1).

    Note that he doesn't have to use his one rule of inference to prove that ##p\land q\to p##, because tautologies are axioms in this theory.

    Not sure if this has any relevance to your problem. I'm asking you if it's possible that it does. If it does, then you're already done.
  7. May 9, 2013 #6
    I was under the inference that because it's a homework question they're looking for it to be done in a certain way. If I can hand it in as a truth table then that would be swell.
  8. May 9, 2013 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I don't know, something smells funny here. Your rules of inference are all(?) tautologies, so if you are allowed to use any tautology as an axiom (and use truth tables to determine which statements are tautologies), then you wouldn't need to list some of them as "rules of inference". I think you will have to dig deeper in your book to find out what's going on here.

    Maybe someone who knows this better than I do will show up and help you out, but if you want to make it easier for people to reply, it could help if you post a simple example of how these rules are supposed to be used.

    Here's a thought: Doesn't rule 2 tell us that the left-hand side of that equivalence implies ##\lnot p## and also ##q##? In fact, don't we get a whole bunch of results like that from rule 2?
    Last edited: May 9, 2013
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted