Chapter 1 — Key Takeaways (Propositional Logic)

A one-page reference. Reread this before an exam or before refactoring a gnarly if.

Core definitions (memorize)

Term One-line definition
Proposition A declarative statement that is true or false, but not both.
Connective An operator whose output truth value is fixed by its inputs' truth values.
Truth table All $2^n$ assignments of $n$ variables, with the resulting truth value.
Tautology True on every assignment (output column all $T$).
Contradiction False on every assignment (output column all $F$); same as unsatisfiable.
Contingency True on some assignments, false on others.
Logical equivalence ($A \equiv B$) Same truth value on every assignment (identical output columns).
De Morgan's laws Negation flips $\land\leftrightarrow\lor$ as it moves inward (see below).
Satisfiable At least one assignment makes it true.

The six connectives

Connective Symbol Python FALSE exactly when TRUE exactly when
Negation $\neg p$ not p $p$ true $p$ false
Conjunction $p \land q$ p and q some operand false both true
Disjunction (inclusive) $p \lor q$ p or q both false $\ge 1$ true
Exclusive or $p \oplus q$ p != q / p ^ q operands agree operands differ
Implication $p \rightarrow q$ (not p) or q $p$ true and $q$ false all other rows
Biconditional $p \leftrightarrow q$ p == q operands differ operands agree

Connective truth values (the 4-row block):

$p$ $q$ $\land$ $\lor$ $\oplus$ $\rightarrow$ $\leftrightarrow$
T T T T F T T
T F F T T F F
F T F T T T F
F F F F F T T

Precedence (tightest → loosest): $\;\neg \;\succ\; \land \;\succ\; \lor \;\succ\; \rightarrow \;\succ\; \leftrightarrow$ (like: $\neg$ = unary minus, $\land$ = ×, $\lor$ = +). In code, parenthesize anyway.

Equivalence laws (refactoring rules — each one is proven, so it preserves behavior)

Law Statement
Identity $p \land T \equiv p$; $p \lor F \equiv p$
Domination $p \lor T \equiv T$; $p \land F \equiv F$
Idempotent $p \land p \equiv p$; $p \lor p \equiv p$
Double negation $\neg(\neg p) \equiv p$
Commutative $p \land q \equiv q \land p$; $p \lor q \equiv q \lor p$
Associative $(p \land q)\land r \equiv p \land(q\land r)$; dual for $\lor$
Distributive $p \land (q\lor r) \equiv (p\land q)\lor(p\land r)$; $p \lor(q\land r)\equiv(p\lor q)\land(p\lor r)$
De Morgan $\neg(p\land q)\equiv \neg p\lor\neg q$; $\neg(p\lor q)\equiv \neg p\land\neg q$
Absorption $p \lor (p\land q)\equiv p$; $p \land(p\lor q)\equiv p$
Negation $p \lor\neg p \equiv T$; $p \land\neg p \equiv F$
Implication $p \rightarrow q \equiv \neg p \lor q$
Negated implication $\neg(p\rightarrow q)\equiv p\land\neg q$
Contrapositive $p\rightarrow q \equiv \neg q\rightarrow\neg p$
Biconditional $p\leftrightarrow q\equiv (p\rightarrow q)\land(q\rightarrow p)$

Bridge facts: - $A \equiv B \iff (A \leftrightarrow B)$ is a tautology. - $A$ is a tautology $\iff \neg A$ is unsatisfiable.

Decision aid — "which method / which law?"

Goal Use
Prove $A \equiv B$ with few variables, total certainty Truth table: tabulate both, compare columns.
Prove $A \equiv B$ with many variables Algebra of logic: rewrite step by step, cite a law each line.
Negate a compound statement Rewrite $\rightarrow$ as $\neg p\lor q$, then push $\neg$ in with De Morgan, then double-negation.
Simplify X or (X and Y) Absorption → X.
Simplify (p and q) or (p and ¬q) Factor (distributive) → p and (q or ¬q) → p.
Push a not through and/or De Morgan (flip the connective).
Decide if a condition is ever true Satisfiability: look for one $T$ row.
Decide if a condition is always true Tautology: all rows $T$ (or show $\neg A$ unsatisfiable).

Common pitfalls

Pitfall Reality
"or" means exactly one Logical $\lor$ is inclusive (both counts). Use $\oplus$ for exactly one.
$p \rightarrow q$ false when $p$ false False only when $p$ true and $q$ false. False hypothesis ⇒ vacuously true.
Converse $\equiv$ original No. Only the contrapositive $\neg q\rightarrow\neg p$ is equivalent. Converse $q\rightarrow p$ is not.
Swapping and operands is always safe Truth values: yes. Execution: no — short-circuit + side effects/exceptions depend on order.
Brute-forcing SAT is fine $2^n$ rows: ~$10^9$ at $n=30$, ~$10^{18}$ at $n=60$ — an exponential wall.
"Tests pass" = correct Tests check sampled cases; an equivalence proof covers all $2^n$.

Satisfiability snapshot (preview of Ch. 37)

  • Satisfiable = some row is $T$. Unsatisfiable = contradiction.
  • Easy to verify, (seemingly) hard to find a satisfying assignment ⇒ the signature of NP and P vs. NP; SAT is the emblem (NP-complete, Cook–Levin, Ch. 37).
  • Truth table has $2^n$ rows ⇒ exhaustive check is exponential.

Toolkit additions — logic.py (built Ch. 1–3)

Function Signature Returns
Truth table truth_table(fn, names) list of (assignment_tuple, output) rows
Tautology test is_tautology(fn, n) True iff fn is true on all $2^n$ assignments
Equivalence test equivalent(f, g, n) True iff f and g agree on all $2^n$ assignments

Implementation core: enumerate assignments with itertools.product([True, False], repeat=n); a proposition is just a Python function returning bool. Code tests broadly; a proof settles all cases — use both.