Truth Table Rules of Inference

[Siann122]

Homework Statement

Use the rules of inference to prove the following:
(¬p ^ q) ^ (r → p) ^ (¬r → s) ^ (s → t) ) ⇔ t.

Homework Equations

Rules of Inference I guess.

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.

 

[Fredrik]

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?

 

[Siann122]

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

 

[Siann122]

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?

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

 

[Fredrik]

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

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.

 

[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.

 

[Fredrik]

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?