Mathematics → Logic

Logic

Mathematical logic is the study of formal reasoning — the rules by which conclusions follow necessarily from premises. It underlies every proof in mathematics and every program in computer science.

Propositions

A proposition is a declarative statement that is either true or false, but not both. We denote propositions with letters like $p, q, r$ and their truth values with $T$ (true) or $F$ (false).

"7 is prime" — proposition (true). "x + 1 = 5" — not a proposition (truth depends on x). "Read this!" — not a proposition (imperative).

Logical Connectives

Propositions are combined using connectives to form compound propositions:

\lnot p

Negation

True when p is false.

p \land q

Conjunction

True when both p and q are true.

p \lor q

Disjunction

True when at least one is true.

p \to q

Implication

False only when p is true and q is false.

p \leftrightarrow q

Biconditional

True when p and q have the same truth value.

The implication $p \to q$ is often the most counterintuitive: a false hypothesis makes the whole statement vacuously true. "If the moon is made of cheese, then 2+2=5" is a true implication.

Truth Tables

A truth table lists all possible truth values for a compound proposition. For $n$ variables there are $2^n$ rows.

Implication

p	q	p → q	p ↔ q
T	T	T	T
T	F	F	F
F	T	T	F
F	F	T	T

Converse, Inverse, Contrapositive

Given $p \to q$ , three related implications arise — only the contrapositive is logically equivalent to the original:

Converse

q \to p

Not equivalent

Inverse

\lnot p \to \lnot q

Not equivalent

Contrapositive

\lnot q \to \lnot p

Logically equivalent ✓

Original

p \to q

Logical Equivalence

Definition — Logical Equivalence

Two propositions

P

and

Q

are logically equivalent, written

P \equiv Q

, if they have identical truth values for every assignment of truth values to their variables.

Key equivalences

Double Negation

\lnot\lnot p \equiv p

Contrapositive

(p \to q) \equiv (\lnot q \to \lnot p)

De Morgan 1

\lnot(p \land q) \equiv \lnot p \lor \lnot q

De Morgan 2

\lnot(p \lor q) \equiv \lnot p \land \lnot q

Implication

(p \to q) \equiv (\lnot p \lor q)

Absorption

p \lor (p \land q) \equiv p

A proposition that is always true is a tautology (e.g. $p \lor \lnot p$ ). One that is always false is a contradiction (e.g. $p \land \lnot p$ ).

Predicate Logic

Propositional logic treats propositions as atomic. Predicate logic (first-order logic) adds variables, predicates, and quantifiers — allowing statements about entire domains.

A predicate $P(x)$ is a proposition-valued function: $P(x) = \text{``}x \text{ is prime''}$ is true for $x=7$ , false for $x=9$ .

Quantifiers

\forall x\, P(x)

Universal

"For all x, P(x)." True if P(x) holds for every x in the domain.

\exists x\, P(x)

Existential

"There exists an x such that P(x)." True if P(x) holds for at least one x.

\exists! x\, P(x)

Unique existence

"There exists exactly one x such that P(x)."

Negating quantifiers

\lnot\,\forall x\, P(x) \;\equiv\; \exists x\, \lnot P(x)

\lnot\,\exists x\, P(x) \;\equiv\; \forall x\, \lnot P(x)

"Not all integers are even" is the same as "there exists an integer that is not even."

Rules of Inference

A rule of inference is a valid argument form — a pattern that guarantees the conclusion is true whenever the premises are true.

Modus Ponens

p,\quad p \to q \;\vdash\; q

Modus Tollens

\lnot q,\quad p \to q \;\vdash\; \lnot p

Hypothetical Syl.

p \to q,\quad q \to r \;\vdash\; p \to r

Disjunctive Syl.

p \lor q,\quad \lnot p \;\vdash\; q

Addition

p \;\vdash\; p \lor q

Simplification

p \land q \;\vdash\; p

The symbol $\vdash$ means "therefore." Modus Ponens is the most fundamental rule: if we know $p$ is true, and we know $p \to q$ , we can conclude $q$ .

Next: Number Theory →

On this page

Propositions

Logical Connectives

Truth Tables

Logical Equivalence

Predicate Logic

Rules of Inference