Formal Logic

A proposition is a declarative sentence that is either true or false, but not both. Whether it is actually true doesn't matter: 12 + 9 = 3 − 2 is a proposition, a false one.

Propositional variable

A letter standing for a proposition: p, q, r (or A, B, C).

Simple (primitive) statement

A single propositional variable, with no connective.

Compound statement

Variables joined or modified by connectives, e.g. p ∧ ¬q.

Truth value

T (true, 1) or F (false, 0).

Five connectives build compound statements, plus negation, which flips one statement: ¬p is “it is not the case that p”.

Conjunction p ∧ q

“p and q”: true only when both are true.

Disjunction p ∨ q

“p or q” (inclusive): false only when both are false.

Exclusive or p ⊕ q

True when exactly one of p and q is true.

Conditional p → q

“If p, then q”: false only when p is T and q is F.

Biconditional p ↔ q

“p if and only if q”: true when p and q have the same value.

Precedence, from tightest: ¬, ∧, ∨, →, ↔. So ¬p ∧ q is (¬p) ∧ q, and p ∧ q → r is (p ∧ q) → r. Brackets override it; when in doubt, write them.

In C the same ideas are &&, || and !, with 1 for true and 0 for false: if c = 5 and d = 2, (c == 5) || (d > 5) is 1.

A truth table lists the value of a compound proposition for every combination of values of its variables. With n variables there are 2ⁿ rows: 4 for two, 8 for three. List them in the standard order, the first variable changing slowest: TT, TF, FT, FF.

Tautology

True in every row, e.g. p ∨ ¬p, [(A → B) ∧ A] → B.

Contradiction

False in every row, e.g. p ∧ ¬p, (A ∨ B) ∧ (¬A ∧ ¬B).

Contingency

Neither: true in some rows and false in others, e.g. (A ∨ B) ∧ ¬A.

In p → q, p is the hypothesis (antecedent, premise) and q is the conclusion (consequence). The statement only promises something when p is true, so it is broken only by p true and q false. When p is false, p → q is true whatever q is.

Turning a conditional around gives three relatives:

A conditional and its contrapositive are equivalent. So are the converse and the inverse, since each is the other's contrapositive. Neither the converse nor the inverse is equivalent to the original.

Two compound propositions A and B are logically equivalent, written A ≡ B, when their truth tables have the same final column. Put another way, A ≡ B exactly when A ↔ B is a tautology. To show two formulas are not equivalent, one row where they differ is enough.

De Morgan's laws say the same thing for sets (complement of a union or an intersection) and for logic gates. “It is not true that Alice is smart and honest” means “Alice is not smart or not honest.”

An argument is a list of premises followed by a conclusion, written with ∴. It is valid when the conclusion is true in every row of the truth table where all the premises are true. Equivalently, (P₁ ∧ P₂ ∧ … ) → C is a tautology. Validity is about the argument's form, not about whether the premises are actually true.

1. 1.Make a truth table with a column for each premise and one for the conclusion.
2. 2.Mark the critical rows, where every premise is T.
3. 3.If the conclusion is T in every critical row, the argument is valid. A critical row with a false conclusion is a counterexample, and the argument is invalid.