Logic and reasoning

Propositions

A proposition is a declarative sentence that is either true or false. Questions and commands are not propositions.

Logic is the study of correct reasoning. It gives us a way to check whether a conclusion really follows from what we know, which matters in mathematics, in law, in programming and in any argument we hear.

We name simple propositions with small letters such as p, q and r. Joining them with connectives builds compound propositions.

1. Connectives

• Negation ¬p: the opposite truth value.
• Conjunction p ∧ q: true only when both are true.
• Disjunction p ∨ q: false only when both are false.
• Conditional p → q: false only when p is true and q is false.
• Biconditional p ↔ q: true when both have the same truth value.

In p → q, p is the hypothesis (or antecedent) and q is the conclusion (or consequent). Think of a promise: "If you pass the exam, I will buy you lunch." The promise is broken only if you pass and get no lunch. If you fail, the promise is not broken whatever happens, so the conditional counts as true.

Building a truth table

A truth table lists every possible combination of truth values. With 2 simple propositions there are 2 × 2 = 4 rows; in general, n propositions need 2ⁿ rows, so 3 propositions need 8 rows and 4 need 16.

To evaluate a longer statement, work from the inside out, as in arithmetic. Negation is done first, then ∧ and ∨, then → and ↔, unless parentheses say otherwise. If p is true and q is false, then ¬p ∨ q is F ∨ F, which is false, while p ∧ ¬q is T ∧ T, which is true.

Tautologies and contradictions

A tautology is true in every row, such as p ∨ ¬p: "It is raining or it is not raining." A contradiction is false in every row, such as p ∧ ¬p. Two statements are logically equivalent, written ≡, when they have the same truth value in every row. For example, p → q ≡ ¬p ∨ q, which you can check against the table above.

Reading conditionals in English

English has many ways to say p → q.

• "If p, then q", "q if p" and "p implies q".
• "p only if q": you get p only when q holds. "You may vote only if you are registered" is "If you vote, then you are registered."
• "p is sufficient for q" and "q is necessary for p".
• "q unless p" means ¬p → q: "You will be late unless you leave now" is "If you do not leave now, you will be late."

2. Related conditionals

For "If it rains, the ground is wet":

• Converse q → p: If the ground is wet, it rains.
• Inverse ¬p → ¬q: If it does not rain, the ground is not wet.
• Contrapositive ¬q → ¬p: If the ground is not wet, it does not rain. This one is logically equivalent to the original.

The converse and the inverse are equivalent to each other, but not to the original. The ground can be wet because someone watered the garden, so the converse may be false while the original is true.

3. Negating

• Not (p and q) is (not p) or (not q).
• The negation of "All teachers are strict" is "Some teachers are not strict".

These are De Morgan’s laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q. The negation of "I will study and sleep early" is "I will not study or I will not sleep early."

A conditional is negated by keeping the hypothesis and denying the conclusion: ¬(p → q) ≡ p ∧ ¬q. The negation of "If you pass, you get lunch" is "You pass and you do not get lunch."

Quantified statements are negated by switching the quantifier and negating what follows.

"All teachers are not strict" is a common wrong answer. It claims no teacher is strict, which is much stronger than the true negation.

4. Arguments

Modus ponens: p → q and p, so q. Modus tollens: p → q and ¬q, so ¬p. Reasoning from q back to p is the fallacy of affirming the consequent.

An argument is a list of premises followed by a conclusion. It is valid when the conclusion must be true whenever all the premises are true. An argument is valid exactly when (premise 1 ∧ premise 2 ∧ …) → conclusion is a tautology.

Two more valid forms are worth knowing.

• Hypothetical syllogism: p → q and q → r, so p → r. If I save, I can buy a laptop; if I buy a laptop, I can study online; so if I save, I can study online.
• Disjunctive syllogism: p ∨ q and ¬p, so q. The phone is in my bag or on the desk; it is not in my bag; so it is on the desk.

Besides affirming the consequent, watch for denying the antecedent: p → q and ¬p, so ¬q. "If it rains, the ground is wet. It did not rain. So the ground is not wet." This is invalid, because a sprinkler could have wet the ground.

Validity is about form, not facts. "All fish can fly. A tilapia is a fish. So a tilapia can fly" is valid, because the conclusion follows from the premises, but it is not sound, because the first premise is false. A sound argument is valid and has true premises.

Solved examples

Follow each one line by line. The steps stay the same when the numbers change, so cover the steps and try it yourself.

Example 1: Truth value of a compound statement

Question: If p is true and q is false, what is the truth value of (p ∨ q) → ¬q?

1. Write T or F above each letter. p = T, q = F.
2. Work inside the parentheses. p ∨ q is T ∨ F = T, because a disjunction needs only one true part.
3. Do the negation. ¬q = T.
4. Combine. T → T is true. A conditional is false only for T → F.

Answer: The statement is true.

Example 2: Converse, inverse and contrapositive

Question: Write the converse, inverse and contrapositive of "If a number is divisible by 4, then it is even."

1. Label the parts. p: the number is divisible by 4. q: the number is even.
2. Converse: swap them (q → p). If a number is even, then it is divisible by 4. This is false, as 6 shows.
3. Inverse: negate both (¬p → ¬q). If a number is not divisible by 4, then it is not even. This is also false, as 6 shows.
4. Contrapositive: swap and negate (¬q → ¬p). If a number is not even, then it is not divisible by 4. This is true, like the original.

Answer: Only the contrapositive is equivalent to the original.

Example 3: Naming an argument

Question: "If a shape is a square, it has four sides. This shape does not have four sides. So it is not a square." Which rule is this?

1. Label the parts. p: the shape is a square. q: it has four sides.
2. Write the argument in symbols. p → q, then ¬q, so ¬p.
3. Compare with the known forms. Modus ponens starts from p. Modus tollens starts from ¬q and ends with ¬p, which matches.

Answer: It is modus tollens, and the argument is valid.

Common mistakes

• Thinking a false hypothesis makes p → q false. A conditional is false only when p is true and q is false.
• Using the converse as if it were the original. "If it is a square, it is a rectangle" is true, but "If it is a rectangle, it is a square" is false.
• Negating "all" with "all … not". The negation of "All are strict" is "Some are not strict".
• Keeping "and" when negating. Negating p ∧ q flips the connective to ∨.
• Confusing valid with true. A valid argument can have a false conclusion if a premise is false.

Where you will meet this

• Programming. Every if statement, and every AND, OR and NOT in a search or a spreadsheet, is a connective.
• Law and contracts. Terms such as "only if" and "unless" decide who must do what.
• Proofs. Mathematicians often prove the contrapositive because it is easier than the original.
• Everyday arguments. Spotting affirming the consequent protects you from misleading claims in advertising and politics.

Key terms

Proposition

A declarative sentence that is either true or false.

Connective

A word or symbol that joins propositions: not, and, or, if … then, if and only if.

Truth table

A table showing the truth value of a statement for every combination of its parts.

Tautology

A statement that is true in every row of its truth table.

Contrapositive

¬q → ¬p, the conditional that is equivalent to p → q.

Valid argument

An argument whose conclusion must be true whenever all its premises are true.

Summary

• A proposition has exactly one truth value; questions, commands and open sentences do not.
• ∧ needs both true, ∨ needs at least one true, and p → q fails only when p is true and q is false.
• A truth table for n propositions has 2ⁿ rows.
• The contrapositive is equivalent to the original; the converse and inverse are not.
• Negate with De Morgan’s laws and by switching "all" and "some".
• Modus ponens, modus tollens and the syllogisms are valid; affirming the consequent and denying the antecedent are fallacies.