# Truth Table Rules of Inference

1. May 9, 2013

### Siann122

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. May 9, 2013

### Fredrik

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

3. May 9, 2013

### Siann122

1. p ⇒ p ∨ q addition
2. p ∧ q ⇒ p simpliﬁcation
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

4. May 9, 2013

### Siann122

That's correct, but I didn't use rules of inference, I drew up a truth table.

5. May 9, 2013

### Fredrik

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

6. May 9, 2013

### Siann122

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.

7. May 9, 2013

### Fredrik

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