Basic Logic — Propositions, Truth Tables, Quantifiers

A proposition is a declarative sentence that is definitely either true or false — never both, never neither. From simple propositions we build complex ones using logical connectives (negation, conjunction, disjunction, conditional, biconditional), and a truth table lists every possible combination of truth values to determine when the whole statement is true. Quantifiers extend this to statements about collections — "every," "some," "no" — letting us reason about infinitely many cases at once. Logic matters because it is the grammar of proof: it tells us exactly when a conclusion must follow from premises, independent of the topic. A surprising fact is that just two symbols — the connective NAND ("not and") alone — can express every logical statement, which is why a single transistor gate type can build an entire computer.

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.

Formal Statement

Proposition

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$

Logical Connectives

The five standard connectives combine propositions into compound propositions:

Symbols: $\neg$ negation, $\wedge$ conjunction, $\vee$ disjunction, $\to$ conditional (implication), $\leftrightarrow$ biconditional. In $p\to q$, $p$ is the antecedent (hypothesis) and $q$ the consequent (conclusion).

Truth 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\to 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 |

Classifications 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.

Quantifiers

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

The negation rules (De Morgan for quantifiers) are:

Why It Holds / Derivation

Establishing $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$:

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

De 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$. $■$

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.

Building 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\to 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.

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

Worked Examples

Building a truth table for $(p\rightarrow q)\wedge(q\rightarrow p)$

| $p$ | $q$ | $p\to q$ | $q\to p$ | $(p\to q)\wedge (q\to p)$ | |---|---|---|---|---| | T | T | T | T | T | | T | F | F | T | F | | F | T | T | F | F | | F | F | T | T | T |

Negating a quantified statement

Common Misconceptions

• $p\to 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\to q$ is not the same as $q\to 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.

Claim (false): "From $p\to q$ and $q$, conclude $p$."

Let $p$ = "it rained" and $q$ = "the ground is wet." Then $p\to 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 $[(p\to q)\wedge q]\to p$ to be a tautology. At the row $p=F,q=T$: $p\to q=T$, $q=T$, premise conjunction $=T$, but conclusion $p=F$. So the implication is $T\to F=F$ — not a tautology. The argument is invalid.

(Contrast with the valid modus ponens: from $p\to q$ and $p$, conclude $q$.)

Connections

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.

Real-World Applications

1. Digital circuit design. Every CPU is a vast network of AND/OR/NOT/NAND gates; Boolean algebra and truth tables specify exactly what each circuit computes, and minimization techniques (Karnaugh maps) reduce gate counts.
2. Programming conditionals. if (a && !b || c) in any language is a compound proposition; short-circuit evaluation and De Morgan's laws let programmers simplify and refactor conditions safely.
3. Database queries (SQL). WHERE age > 18 AND (city = 'Paris' OR city = 'Lyon') is propositional logic with quantifier-like behaviour over rows; query optimizers manipulate these expressions.
4. Automated theorem proving and verification. SAT solvers determine whether a Boolean formula can ever be true; they verify that aircraft software, hardware chips, and cryptographic protocols meet their specifications.
5. Legal and contractual reasoning. "The warranty is void if the seal is broken or the device is submerged" is a logical disjunction; precise drafting depends on inclusive vs. exclusive or and on correct negation.
6. Search engines and information retrieval. Boolean search — "climate" AND "policy" NOT "fiction" — uses connectives to filter results.
7. Artificial intelligence and expert systems. Rule-based systems chain conditionals ("if symptom then likely diagnosis") using modus ponens to draw conclusions.

Historical Development

• 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.

Subtleties & Limits

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.

See Also