What are rules of inference?

A rule of inference is a step you can always take without risk of getting it wrong: if the formulas you start from are true, the one you get is true as well. That’s all. Chaining steps like these is how you build a proof.

An argument has two parts: the premises (or hypotheses), which we take as given, and the conclusion, which we want to justify. It is usually written with the symbol ⊢:

P → Q,  Q → R,  P  ⊢  R

An argument is valid when it is impossible for all the premises to be true and the conclusion false. Careful: valid does not mean “true”. An argument can be flawless and still start from false premises; what we check here is the reasoning, not the facts.

The rules of inference, one by one

These are the ones you use in practically every exercise. In each pattern, what is above the line are the premises, and what is below it (after ∴, “therefore”) is what you can deduce:

The equivalences you need along the way

Besides the rules above, there are rewrites that don’t deduce anything new: they say the same thing in a different way. The calculator applies them on its own when they’re needed, and flags them in the proof:

• Material implication: P → Q is equivalent to ¬P ∨ Q. Read the other way round, a disjunction P ∨ Q is the same as ¬P → Q, which lets you bring an “or” into a chain of syllogisms.
• Contraposition: P → Q is equivalent to ¬Q → ¬P.
• De Morgan’s laws: ¬(P ∧ Q) is equivalent to ¬P ∨ ¬Q, and ¬(P ∨ Q) is equivalent to ¬P ∧ ¬Q.
• Double negation: ¬¬P is the same as P.
• Idempotence: P ∨ P is equivalent to P, and so is P ∧ P. It shows up more than you’d think: if you reach P → ¬P, by material implication that is ¬P ∨ ¬P, that is, ¬P. If something leads to its own negation, it is false.
• Negated implication: ¬(P → Q) is equivalent to P ∧ ¬Q.
• Distribution of implication: there are four, and they’re worth keeping at hand because they unlock half the course.
  • (P ∨ Q) → R is equivalent to (P → R) ∧ (Q → R)
  • P → (Q ∧ R) is equivalent to (P → Q) ∧ (P → R)
  • P → (Q ∨ R) is equivalent to (P → Q) ∨ (P → R)
  • (P ∧ Q) → R is equivalent to (P → R) ∨ (Q → R)
  Notice the pattern: when you distribute, the connective of the consequent stays the same and the one of the antecedent flips. They work both ways: to split a long premise into manageable pieces, and to assemble the conclusion at the end.
• Definition of the biconditional: P ↔ Q is equivalent to (P → Q) ∧ (Q → P).
• Exclusive or: P ⊕ Q is equivalent to (P ∨ Q) ∧ ¬(P ∧ Q).

Two you’ll miss a lot if you forget them: De Morgan, because as soon as a modus tollens leaves you with something like ¬(P ∨ Q) you need to turn it into ¬P ∧ ¬Q to keep going; and material implication, which is what lets you use a loose disjunction as if it were an implication. For example, from P → ¬Q and Q ∨ R you get P → R: just read Q ∨ R as ¬Q → R and chain a hypothetical syllogism.

How to solve an exercise step by step

There’s no guesswork involved: almost every exercise works out with this order.

Step 1 · Identify the premises and the conclusion

Separate what you’re given from what you have to justify. If the exercise gives you a single formula A → B, the left side holds the premises and the right side is the conclusion.

Step 2 · Break the premises down

Before combining anything, make the premises as simple as possible: split conjunctions by simplification, expand biconditionals and apply De Morgan wherever a negation sits outside a parenthesis. The more loose formulas you have, the easier it is for a rule to fit.

Step 3 · Chain rules forward

Look for pairs that fit a rule and keep writing new lines, numbered and with the name of the rule next to them. The usual approach is to start with modus ponens (you have the antecedent of an implication), continue with modus tollens (you have the consequent negated) and finish with disjunctive syllogisms when you’re left with a disjunction and the negation of one of its sides.

Step 4 · Build the conclusion

Look at what you need to reach. If the conclusion is a conjunction such as S ∧ Q, don’t look for it whole: get S on one side and Q on the other and join them with the conjunction rule. And if it’s a disjunction such as Q ∨ Z, it’s enough to get one of the two sides and add the other by addition.

Step 5 · If it doesn’t work, question the argument

If you’ve run out of possible combinations, the argument may simply not be valid. To check, look for a counterexample: an assignment of true and false to each variable that makes every premise true and the conclusion false. If you find one, that’s it: there is no possible proof, however hard you try. The calculator always runs this check, and when the argument is not valid it shows you the counterexample with every premise substituted and evaluated, so you can see exactly where it breaks.

Worked example, step by step

What if the argument is valid but I can’t prove it?

It happens, and it isn’t always your fault. These rules work forward: they combine what you already have. Some valid arguments need a different kind of move, mainly two: assuming the antecedent (to prove A → B you assume A, reach B and discharge the assumption) and reasoning by cases (if you know P ∨ Q, look at what happens assuming P and what happens assuming Q). A simple example that doesn’t come out with the table alone: (P ∧ Q) → R ⊢ P → (Q → R). Be aware this is rarer than it seems: almost every conclusion of the form A → B comes out without assuming anything, using contraposition, material implication or the four distribution laws above, and the calculator does all of that on its own.

When the calculator runs into that situation it tells you plainly, instead of telling you the argument is false: it shows how far it got with the rules, checks validity on its own by evaluating every possible case, and lets you know that the argument is valid even though it didn’t find the proof.

Related calculators

Frequently asked questions