Propositional Logic

Reasoning with True and False

A proposition is a statement that is definitely true or false — "7 is prime" (true), "$3 > 5$" (false). Propositional logic builds compound statements from simple ones using connectives, and gives rules to determine their truth. This is the logic underlying both mathematical proof and the boolean circuits of the previous unit — the connectives are exactly the logic gates.

The connectives, with the same truth behavior as gates:

• Negation $\neg p$ ("not $p$") — flips the truth value.
• Conjunction $p \land q$ ("$p$ and $q$") — true only when both are true.
• Disjunction $p \lor q$ ("$p$ or $q$") — true when at least one is true.
• Implication $p \to q$ ("if $p$ then $q$") — the subtle one.
• Biconditional $p \leftrightarrow q$ ("$p$ if and only if $q$") — true when $p$ and $q$ match.

Implication deserves care: $p \to q$ is false in exactly one case — when $p$ is true but $q$ is false. In particular, when $p$ is false, the implication is vacuously true regardless of $q$ ("if the moon is cheese, then $2+2=5$" is a true implication). This trips up nearly everyone at first.

A tautology is a proposition true under every assignment (like $p \lor \neg p$); a contradiction is false under every assignment. Two propositions are logically equivalent if they have the same truth table — for example, $p \to q$ is equivalent to $\neg p \lor q$, and the contrapositive $\neg q \to \neg p$ is equivalent to $p \to q$ (a fact heavily used in proofs).

Common pitfall: misreading implication. $p \to q$ is not false when $p$ is false — it is vacuously true. The only way an implication fails is a true premise with a false conclusion ($p$ true, $q$ false). Also, $p \to q$ is not the same as its converse $q \to p$; confusing the two is a classic logical error.