Basic Logic — Propositions, Truth Tables, Quantifiers

⚡ Key Takeaways

Logic is the study of valid reasoning, built from propositions (statements that are true or false), connectives (and, or, not, if-then), and quantifiers (for all, there exists). A truth table mechanically computes the truth value of any compound statement from its parts. This machinery underlies all of mathematics, computer circuits, and rigorous argument. Formalized by Boole, Frege, and others in the 19th–20th centuries.

💡 The Core Insight

Truth flows mechanically. Once you fix the truth values of the atomic propositions, the truth value of any compound built from them is completely determined by fixed rules. Reasoning is reduced to calculation: validity is no longer a matter of opinion or persuasion but of a computable table.

DefinitionProposition

A proposition is a declarative statement that has exactly one truth value: true (T) or false (F). Questions, commands, and ungrammatical or vague sentences are not propositions.

"7 is a prime number" — proposition (T).
"12 is odd" — proposition (F).
"Close the door." — not a proposition (command).
"x + 1 = 5" — not a proposition until x is specified (an open sentence).

We denote propositions by letters $p, q, r, \dots$

DefinitionLogical Connectives

The five standard connectives combine propositions into compound propositions:

1

\quad \neg p \quad(\text{NOT } p),\qquad p \wedge q \quad(p \text{ AND } q)

Derivation hint: $\neg p$ flips the truth value; $p\wedge q$ is true only when both are true.

2

\quad p \vee q \quad(p \text{ OR } q),\qquad p \rightarrow q \quad(\text{IF } p \text{ THEN } q),\qquad p \leftrightarrow q \quad(p \text{ IFF } q)

Derivation hint: $\vee$ is inclusive (true if either or both); $\rightarrow$ is false only when $p$ is true and $q$ false; $\leftrightarrow$ is true when $p$ and $q$ share the same value. Symbols: $\neg$ negation, $\wedge$ conjunction, $\vee$ disjunction, $\rightarrow$ conditional (implication), $\leftrightarrow$ biconditional. In $p\rightarrow q$ , $p$ is the antecedent (hypothesis) and $q$ the consequent (conclusion).

DefinitionTruth Table

A truth table for a compound proposition lists every possible assignment of T/F to its atomic propositions (there are $2^n$ rows for $n$ atoms) together with the resulting truth value of the compound. The defining tables for the connectives are:

$p$	$q$	$\neg p$	$p\wedge q$	$p\vee q$	$p\rightarrow q$	$p\leftrightarrow q$
T	T	F	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	F	T	F	F	T	T

TheoremClassifications of Compound Propositions

A compound proposition is:

a tautology if it is true under every assignment (e.g. $p \vee \neg p$ );
a contradiction if it is false under every assignment (e.g. $p \wedge \neg p$ );
a contingency if it is true under some assignments and false under others.

Two propositions $A$ and $B$ are logically equivalent, written $A \equiv B$ , if and only if $A \leftrightarrow B$ is a tautology — i.e. they have identical truth-table columns.

DefinitionQuantifiers

For an open sentence (predicate) $P(x)$ over a domain $D$ :

3

\quad \forall x\, P(x) \;\equiv\; \text{“for every } x \text{ in } D,\ P(x) \text{ is true.”}

Derivation hint: the universal quantifier is a (possibly infinite) conjunction $P(x_1)\wedge P(x_2)\wedge\cdots$ over all elements.

4

\quad \exists x\, P(x) \;\equiv\; \text{“there is at least one } x \text{ in } D \text{ with } P(x) \text{ true.”}

Derivation hint: the existential quantifier is a (possibly infinite) disjunction $P(x_1)\vee P(x_2)\vee\cdots$ over all elements. The negation rules (De Morgan for quantifiers) are:

5

\quad \neg\big(\forall x\, P(x)\big) \equiv \exists x\, \neg P(x), \qquad \neg\big(\exists x\, P(x)\big) \equiv \forall x\, \neg P(x)

Derivation hint: to deny "all are P," exhibit one that is not P; to deny "some is P," show all fail P. Push $\neg$ inward and flip the quantifier.

ProofEstablishing

p\rightarrow q \equiv \neg p \vee q

We show the conditional is logically equivalent to "not $p$ , or $q$ " by comparing columns. 1. List assignments. With two atoms there are $2^2 = 4$ rows: $(T,T),(T,F),(F,T),(F,F)$ . 2. Compute $\neg p \vee q$ . Negate $p$ , then OR with $q$ :

$(T,T)$ : $\neg p = F$ , $F \vee T = T$ .
$(T,F)$ : $\neg p = F$ , $F \vee F = F$ .
$(F,T)$ : $\neg p = T$ , $T \vee T = T$ .
$(F,F)$ : $\neg p = T$ , $T \vee F = T$ .

3. Compare with $p\rightarrow q$ (from the defining table): $T, F, T, T$ — identical column. 4. Conclude. Since the columns match in all rows, $(p\rightarrow q) \leftrightarrow (\neg p \vee q)$ is true in every row, hence a tautology, hence $p\rightarrow q \equiv \neg p \vee q$ . $\blacksquare$

∎

ProofDe Morgan's Laws

We verify $\neg(p\wedge q) \equiv \neg p \vee \neg q$ . 1. $\neg(p\wedge q)$ : $p\wedge q$ is T only at $(T,T)$ , so its negation is $F,T,T,T$ . 2. $\neg p \vee \neg q$ : This is F only when both disjuncts are F, i.e. both $p,q$ are T — namely at $(T,T)$ . So its column is $F,T,T,T$ . 3. The columns agree everywhere, so the equivalence holds. By symmetric reasoning $\neg(p\vee q)\equiv \neg p \wedge \neg q$ . $\blacksquare$

∎

mathematician · George Boole | 1815–1864

A largely self-taught English mathematician, Boole published The Mathematical Analysis of Logic (1847) and An Investigation of the Laws of Thought (1854), showing that logical reasoning could be cast as algebra with values 0 and 1. His Boolean algebra treats AND as multiplication and OR as addition, turning deduction into computation. Though largely ignored in his lifetime as a curiosity, Boole's system became the mathematical foundation of digital electronics and computer science a century later through Claude Shannon. He died at 49 of pneumonia after walking to a lecture in the rain.

🧠 Intuition

Think of each proposition as a light switch: it is either ON (true) or OFF (false). The connectives are little machines wired between switches:

AND is two switches in series — current flows only if both are ON.
OR is two switches in parallel — current flows if either is ON.
NOT is an inverter — it flips the state.

The conditional $p\rightarrow q$ is the trickiest. Read it as a promise: "If $p$ , then I promise $q$ ." The promise is broken (false) only in one situation — $p$ happened but $q$ did not. If $p$ never happens, the promise was never tested, so it counts as kept (true). This is why "if the moon is cheese, then 2+2=4" is true: a false hypothesis makes the whole conditional vacuously true. Quantifiers scale this up. $\forall$ is a demanding inspector: one counterexample condemns the whole claim. $\exists$ is an easygoing scout: one success vindicates it.

Figure

Series and parallel switch model of AND/OR, with the conditional's truth pattern

ExampleBuilding a truth table for

(p\rightarrow q)\wedge(q\rightarrow p)

Given: the compound proposition $(p\rightarrow q)\wedge(q\rightarrow p)$ . Determine its full truth table and classify it.

Step 1 — count rows. Two atoms $\Rightarrow 2^2 = 4$ rows.

Step 2 — build columns.

$p$	$q$	$p\rightarrow q$	$q\rightarrow p$	$(p\rightarrow q)\wedge(q\rightarrow p)$
T	T	T	T	T
T	F	F	T	F
F	T	T	F	F
F	F	T	T	T

Step 3 — interpret. The final column is $T,F,F,T$ — true exactly when $p$ and $q$ have the same truth value. This is precisely the biconditional column.

Boxed answer:

\boxed{(p\rightarrow q)\wedge(q\rightarrow p) \;\equiv\; (p\leftrightarrow q), \quad \text{a contingency.}}

ExampleNegating a quantified statement

Given: the statement "Every student passed the exam," with domain $D$ = students and predicate $P(x)$ = " $x$ passed." Formalize it, negate it, and translate the negation back to English.

Step 1 — formalize.

\forall x\, P(x).

Step 2 — apply the negation rule [5].

\neg\big(\forall x\, P(x)\big) \;\equiv\; \exists x\, \neg P(x).

Step 3 — translate $\exists x\, \neg P(x)$ . "There exists a student who did not pass," i.e. "At least one student failed."

Step 4 — check with a count. Suppose 30 students, 29 passed, 1 failed. The original $\forall x P(x)$ is false (the inspector found a counterexample). The negation "at least one failed" is true — consistent. The negation is not "no one passed," which would require all 30 to fail.

Boxed answer:

\boxed{\neg(\text{“all passed”}) = \text{“at least one failed,”}\quad \exists x\, \neg P(x).}

⚠️ Common mistake

The conditional is not causation, and not the biconditional.

$p\rightarrow q$ does not mean $p$ causes $q$ , nor that $p$ and $q$ are related in topic. "If grass is green, then 5 is prime" is true simply because both parts are true.
$p\rightarrow q$ is not the same as $q\rightarrow p$ . The latter is the converse and can have a different truth value.
A true conditional with a false hypothesis ("vacuous truth") confuses many students: "All unicorns are pink" is true because there are no unicorns to falsify it.
"Or" in logic is inclusive by default: $p\vee q$ is true when both hold. Everyday "either…or…" often means exclusive or, which is a different connective.

Counterexample

Affirming the consequent — an invalid argument that looks valid. Claim (false): "From $p\rightarrow q$ and $q$ , conclude $p$ ." Let $p$ = "it rained" and $q$ = "the ground is wet." Then $p\rightarrow q$ is reasonable. Suppose the ground is wet ( $q$ true). Does it follow that it rained? No — a sprinkler could have wet the ground. Truth-table check: the argument would require $\big[(p\rightarrow q)\wedge q\big]\rightarrow p$ to be a tautology. At the row $p=F, q=T$ : $p\rightarrow q = T$ , $q = T$ , premise conjunction $= T$ , but conclusion $p = F$ . So the implication is $T\rightarrow F = F$ — not a tautology. The argument is invalid. (Contrast with the valid modus ponens: from $p\rightarrow q$ and $p$ , conclude $q$ .)

connection

Propositional logic is the launchpad for the rest of formal reasoning. Boolean Algebra reinterprets the connectives as algebraic operations on $\{0,1\}$ , directly modelling Logic Gates and Digital Circuits. The study of which arguments are valid leads to Rules of Inference and Proof Methods — modus ponens, contrapositive, contradiction. Quantifiers open the door to Predicate Logic (first-order logic), the language in which essentially all of mathematics is written. The set-theoretic operations of union, intersection, and complement in Set Theory mirror $\vee$ , $\wedge$ , and $\neg$ exactly, and the Methods of Mathematical Proof used throughout algebra and geometry rest on these foundations.

🔬 Where this appears

⏳ History

- c. 350 BCE — Aristotle develops syllogistic logic in the Organon, the first systematic theory of valid inference ("All men are mortal; Socrates is a man; therefore Socrates is mortal").

- c. 300 BCE — The Stoics (Chrysippus) study propositional connectives and conditionals, anticipating modern propositional logic.

- 1666 — Leibniz dreams of a characteristica universalis and calculus ratiocinator: a symbolic language to settle disputes by calculation.

- 1847 — George Boole publishes The Mathematical Analysis of Logic, founding Boolean algebra.

- 1879 — Gottlob Frege's Begriffsschrift introduces quantifiers

\forall, \exists

and a fully formal predicate logic, transforming the field.

- 1910–1913 — Russell and Whitehead's Principia Mathematica attempts to derive all mathematics from logic, refining notation and propositional calculus.

- 1921 — Ludwig Wittgenstein popularizes the modern truth table layout in the Tractatus Logico-Philosophicus (Emil Post and Charles Peirce had similar devices).

- 1931 — Kurt Gödel's incompleteness theorems show that any sufficiently rich, consistent formal system contains true statements it cannot prove.

- 1937 — Claude Shannon's master's thesis shows that Boolean algebra describes electrical switching circuits, founding digital design and linking logic to engineering.

open-problem

Classical two-valued logic assumes every proposition is either true or false (the law of excluded middle), but this is contested at the foundations. Intuitionistic logic rejects automatic excluded middle, demanding a construction to assert existence — affecting which proofs count as valid. Many-valued and fuzzy logics allow degrees of truth (useful for vagueness: when exactly is a heap of sand still a "heap"?). Gödel's incompleteness theorems reveal a hard ceiling: no consistent axiomatic system capturing arithmetic can prove all true arithmetic statements, so logic cannot fully mechanize mathematical truth. Furthermore, while propositional satisfiability is decidable, deciding the validity of arbitrary first-order (quantified) statements is undecidable (Church–Turing, 1936) — no algorithm can always answer "is this quantified statement valid?" These boundaries mark where the tidy machinery of truth tables gives way to deep open questions about the nature and limits of formal reasoning.

Basic Logic — Propositions, Truth Tables, Quantifiers

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also