A red build does not tell you what you think#
A project has one rule about its automated checks:
“If the tests fail, the build turns red.”
This morning the build is red.
Did the tests fail? Decide before you read on.
Not necessarily. A red build is also what you get from a lint error, a timed-out runner, or a machine that filled its disk. The rule promised one direction only: failing tests produce a red build. It never said a red build has one cause.
Change one word and the answer flips. The build is green. Did the tests fail?
They did not, and you can be certain of it. If they had failed, the build would be red. It is not red. So they did not fail.
Two questions, same rule, same three sentences of reasoning — and one of them is airtight while the other is worth nothing. The difference is not the subject. It is the shape. This page is a list of the shapes that work, and the two that do not.
What a rule of inference actually is#
An argument is a list of statements you are granting, called the premises, followed by one statement you claim they force, called the conclusion. The conclusion is marked with ∴, which is read “therefore”.
An argument is valid when there is no possible situation in which every premise is true and the conclusion is false. Not “usually holds”. Not one where you cannot think of a counterexample. No such situation exists at all.
A rule of inference is one argument shape that has already been checked and found valid, so you may use it without re-checking. That is the entire point of naming them: a proof made only of named rules is valid because each of its steps already was.
Four connectives and one piece of punctuation carry every rule below:
| Symbol | Say it as | It means |
|---|---|---|
| ∧ | “and” | both are true |
| ∨ | “or” | at least one is true |
| ¬ | “not” | the opposite |
| → | “if … then” | a promise: whenever the left holds, the right does |
| ∴ | “therefore” | everything above this is a premise; this is the conclusion |
The eight rules, and what each one costs you#
These eight cover almost every step of a first proof course. Read the middle column as “what you already have” and the right column as “what you are allowed to write next”.
| Name | You have | You may write | The plain-English version |
|---|---|---|---|
| Modus ponens | p → q, and p | q | the promise fired |
| Modus tollens | p → q, and ¬q | ¬p | the promised result never came, so the trigger never happened |
| Hypothetical syllogism | p → q, and q → r | p → r | two promises chain into one |
| Disjunctive syllogism | p ∨ q, and ¬p | q | two options, one ruled out |
| Addition | p | p ∨ q | one true option makes the whole “or” true, whatever q is |
| Simplification | p ∧ q | p (or q) | take either half of an “and” |
| Conjunction | p, and q | p ∧ q | two separate truths become one |
| Resolution | p ∨ q, and ¬p ∨ r | q ∨ r | a letter and its negation cancel |
From r ∧ s a single use of simplification gives you r, or it gives you s. It does not hand you both at once, and it does not give you r ∨ s — that one needs addition afterward. Questions about this rule are usually testing whether you know it fires once.
Addition looks like cheating the first time. From “the file is open” you may conclude “the file is open or the server is on fire”. That is a weaker claim, not a stronger one — an “or” only needs one side, and you already have one. Weakening a true statement keeps it true.
Valid and true are different words#
Here is the sentence that costs the most points on this topic: a valid argument with a false premise proves nothing about its conclusion.
Validity is a promise about the shape: if every premise is true, the conclusion has to be. Feed a valid shape one false premise and the promise never comes due. The conclusion might be true. It might be false. The argument has stopped saying.
An argument that is valid and has all-true premises is called sound. Sound is the one that settles anything. Valid is only the shape.
Valid = the shape cannot fail. Sound = the shape cannot fail and the premises are actually true. An exam asking “what does this establish about the conclusion?” after telling you a premise is false wants exactly one answer: nothing.
The two fallacies, and why they feel right#
Both fallacies start from the same true conditional, p → q, and both reach for the direction it never promised.
| Affirming the consequent | Denying the antecedent | |
|---|---|---|
| The argument | p → q, and q ∴ p | p → q, and ¬p ∴ ¬q |
| It is really | the converse, assumed | the inverse, assumed |
| Build example | build is red ∴ tests failed | tests passed ∴ build is not red |
| Why it fails | q can have other causes | q can have other causes |
| Valid? | No | No |
Both are the same mistake wearing different clothes, and the mistake has a name you have already met: the converse and the inverse are not equivalent to the original. Only the contrapositive is — which is why modus tollens, the rule that is the contrapositive in action, is valid while these two are not.
A worked case. “If n is divisible by 6, then n is divisible by 3. The number n is divisible by 3. ∴ n is divisible by 6.” Both premises are true statements about arithmetic. The conclusion is false for n = 9. A true conditional plus a true second premise, and a false conclusion — which is exactly what invalid means.
And the mirror. “If Dana works every practice problem, Dana passes the quiz. Dana did not work every practice problem. ∴ Dana does not pass.” Dana may have already known the material. The conditional named one route to passing, not the only one.
Resolution — the one rule that cancels#
Resolution is the rule that looks least like the others, and it is the one behind most modern SAT solvers and automated theorem provers.
Take ¬p ∨ q and p ∨ r. One of them contains p, the other contains ¬p. Exactly one of p and ¬p is true, so whichever clause loses its p is left holding its other half — and the other halves are q and r.
¬p ∨ q, p ∨ r ∴ q ∨ r
Cancel the letter that appears both plain and negated, then or together everything that is left. The result is called the resolvent. Nothing else is removed, and nothing is turned into an “and”.
Disjunctive syllogism is the special case where one clause is a single letter: from p ∨ q and ¬p, cancelling p leaves q alone.
The four rules for “every” and “some”#
Two more symbols. ∀x is read “for every x”, and ∃x is read “there is some x”. A domain is the collection those x’s are drawn from — the students in a class, the files in a folder.
Four rules move statements between the general and the particular. Two are free. Two carry a condition, and both conditions are ways a tidy-looking proof goes wrong.
| Name | You have | You may write | Condition |
|---|---|---|---|
| Universal instantiation | ∀x P(x) | P(a), for any particular a | a is in the domain. That is all. |
| Universal generalization | P(c) for an arbitrary c | ∀x P(x) | you must not have chosen c, or used any fact about it |
| Existential instantiation | ∃x P(x) | P(c) | c must be a brand-new name |
| Existential generalization | P(a) for a particular a | ∃x P(x) | a is in the domain. That is all. |
Universal instantiation is the workhorse. From “every file that is corrupt fails validation” — ∀x (C(x) → V(x)) — you may write the line C(a) → V(a) about one specific file a. Nothing is assumed about a beyond its being a file.
“Some file is corrupt” tells you a corrupt file exists. It does not tell you which. So you name it something you have never used — and never a name already carrying facts, like the file a from a line above. Reusing a name silently asserts that the two are the same file, which is the most common way a quantified proof goes wrong while looking tidy.
Put them together. Given ∀x (C(x) → V(x)), plus C(a), plus ¬V(b), with a and b two different files: instantiate at a to get C(a) → V(a), then modus ponens gives V(a). Instantiate at b to get C(b) → V(b), then modus tollens on ¬V(b) gives ¬C(b). Both follow. What does not follow is anything about a third file, or that a and b are the only files.
A worked proof, line by line#
A real proof is a stack of these rules, each line naming the rule and the earlier lines it used. Premises:
| Line | Statement | Reason |
|---|---|---|
| 1 | p → q | premise |
| 2 | q → r | premise |
| 3 | ¬r | premise |
| 4 | s ∨ p | premise |
| 5 | p → r | hypothetical syllogism, 1 and 2 |
| 6 | ¬p | modus tollens, 5 and 3 |
| 7 | s | disjunctive syllogism, 4 and 6 |
Read it backward and the shape of the plan appears. To get s out of s ∨ p you need ¬p. To get ¬p by modus tollens you need a conditional ending in something you can deny — and you can deny r. So chain 1 and 2 into p → r first. Working backward from the conclusion is how these proofs are found; working forward is how they are written down.
Count the lines after the premises: three. Questions that ask for the length of the shortest proof are asking you to notice that no rule is wasted — every line here except the conclusion feeds a later one.
The argument that assumes its own conclusion#
One more failure, and it is not a bad rule — it is no rule at all.
“The sequence converges because it has a limit, and it has a limit because it converges.”
Every step is true. The two halves support each other and nothing else. This is circular reasoning, also called begging the question: the conclusion appears among the premises, dressed in different words.
It is harder to catch than the two fallacies because there is no rule being misapplied. The test is mechanical: strike out the conclusion and everything that restates it. If nothing is left, nothing was proved.
Where these go wrong#
- Reading a conditional both ways. p → q says nothing about what happens when q is true or when p is false. Both fallacies on this page are that one habit.
- Calling a valid argument true. Validity is about shape. A false premise ends the argument’s claim on you entirely.
- Applying simplification twice in one line. One use, one half. Take the other half on its own line.
- Reusing a name in existential instantiation. A fresh letter every time, or you have quietly assumed two things are the same thing.
- Generalizing from a chosen element. Universal generalization only works if you never used anything special about c. If you picked c because it was convenient, you cannot conclude ∀x.
- Naming no rule. A line without a justification is not a proof step, even when it is correct. Name the rule and the lines it used.
Test yourself in the free Kestrel Exams app
Discrete Math practice is free and works offline — 16 questions on argument forms, fallacies and quantifier rules alone.
Drill rules of inference →Frequently asked questions#
What is the difference between a valid argument and a true conclusion?
Validity is a property of the shape: there is no situation where all the premises are true and the conclusion is false. It says nothing about whether the premises are actually true. An argument that is valid and has all-true premises is called sound, and only a sound argument establishes its conclusion. A valid argument with one false premise establishes nothing at all.
Is modus tollens the same as the contrapositive?
They are the same fact used two ways. The contrapositive of p → q is ¬q → ¬p, and it is logically equivalent to the original. Modus tollens applies it: given p → q and ¬q, you may conclude ¬p. That equivalence is exactly why modus tollens is valid, while affirming the consequent — which uses the converse — is not.
Why does affirming the consequent feel correct?
Because in everyday life the effect usually does have the cause you have in mind. If the tests fail the build turns red, and most red builds really are failing tests. Logic asks a stricter question: is there any situation at all where the premises hold and the conclusion fails? One lint error is enough to make the answer yes, and one counterexample settles it.
When do I need a brand-new name in existential instantiation?
Every time. ∃x P(x) says something exists but not which thing, so the name you give it must carry no prior information. Reusing a letter already introduced — especially one from a universal instantiation — asserts that the two objects are the same, which the premise never said. Use a letter that appears nowhere else in the proof.
How many of these rules do I have to memorize?
The eight propositional rules and the four quantifier rules, by name, because exam questions ask you to name the rule a line used. Modus ponens, modus tollens, disjunctive syllogism and simplification cover most steps in practice; hypothetical syllogism and resolution appear in the multi-step proofs; addition and conjunction are easy to recognize but easy to forget the names of.
Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.