Logic & Its Applications
Propositional logic, predicates and quantifiers, and Boolean algebra — the language every other topic on this exam is written in. Master this and the rest follows.
1.1 Propositional Logic
A proposition is a declarative sentence that is either true or false — never both, never neither. Everything in this course either is one, is a combination of them, or quantifies over them.
Examples of propositions (✓) and non-propositions (✗)
- ✓ "$2 + 3 = 5$" — true.
- ✓ "$7$ is an odd number." — true.
- ✓ "Every even integer $> 2$ is the sum of two primes." — Goldbach's conjecture; nobody knows the truth value yet, but it has one, so it counts.
- ✗ "$x + 1 = 3$" — depends on $x$; this is a predicate, not a proposition.
- ✗ "Close the window." — a command, not declarative.
- ✗ "What time is it?" — a question.
Logical connectives
We build complex propositions from simpler ones using connectives. Memorize these — they are the building blocks of everything.
| Symbol | Name | Read as | When it's true |
|---|---|---|---|
| $\lnot p$ | Negation | "not $p$" | $p$ is false |
| $p \land q$ | Conjunction | "$p$ and $q$" | both true |
| $p \lor q$ | Disjunction (inclusive) | "$p$ or $q$" | at least one true |
| $p \oplus q$ | XOR | "$p$ xor $q$" | exactly one true |
| $p \to q$ | Implication | "if $p$ then $q$" | except when $p=T, q=F$ |
| $p \leftrightarrow q$ | Biconditional | "$p$ iff $q$" | both have same value |
The implication is the tricky one
$p \to q$ is only false when $p$ is true and $q$ is false. If $p$ is false, the implication is vacuously true — "If the moon is cheese, then I'm a billionaire" is a true statement, because the antecedent is false. This is the rule that confuses students most.
Truth tables for the connectives
| $p$ | $q$ | $\lnot p$ | $p\land q$ | $p\lor q$ | $p\oplus q$ | $p\to q$ | $p\leftrightarrow q$ |
|---|---|---|---|---|---|---|---|
| T | T | F | T | T | F | T | T |
| T | F | F | F | T | T | F | F |
| F | T | T | F | T | T | T | F |
| F | F | T | F | F | F | T | T |
Building truth tables for compound propositions
To find the truth value of any compound proposition, you build a truth table over all combinations of the variables. With $n$ atomic propositions, you get $2^n$ rows.
Worked Example. Construct the truth table for $(p \land q) \to (p \lor q)$.
| $p$ | $q$ | $p\land q$ | $p\lor q$ | $(p\land q)\to(p\lor q)$ |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | T |
| F | T | F | T | T |
| F | F | F | F | T |
Always true — this is a tautology. Notice that the antecedent $p \land q$ logically implies the consequent $p \lor q$.
Tautologies, contradictions, contingencies
- Tautology: true for every truth assignment. e.g. $p \lor \lnot p$.
- Contradiction: false for every assignment. e.g. $p \land \lnot p$.
- Contingency: sometimes true, sometimes false.
Logical equivalences — your toolkit
Two compound propositions $\varphi$ and $\psi$ are logically equivalent ($\varphi \equiv \psi$) if they have the same truth value under every assignment. Equivalently, $\varphi \leftrightarrow \psi$ is a tautology.
| Name | Equivalence |
|---|---|
| Identity | $p \land T \equiv p$, $\;\;p \lor F \equiv p$ |
| Domination | $p \lor T \equiv T$, $\;\;p \land F \equiv F$ |
| Idempotent | $p \lor p \equiv p$, $\;\;p \land p \equiv p$ |
| Double negation | $\lnot(\lnot p) \equiv p$ |
| Commutative | $p \lor q \equiv q \lor p$, etc. |
| Associative | $(p\lor q)\lor r \equiv p\lor(q\lor r)$ |
| Distributive | $p \land (q \lor r) \equiv (p\land q) \lor (p \land r)$ |
| De Morgan | $\lnot(p\land q)\equiv \lnot p\lor\lnot q$, $\;\;\lnot(p\lor q)\equiv \lnot p\land\lnot q$ |
| Absorption | $p \lor (p\land q)\equiv p$ |
| Negation | $p \lor \lnot p \equiv T$, $\;\;p \land \lnot p \equiv F$ |
| Implication | $p \to q \equiv \lnot p \lor q$ |
| Contrapositive | $p \to q \equiv \lnot q \to \lnot p$ |
| Biconditional | $p\leftrightarrow q \equiv (p\to q)\land(q\to p)$ |
The two equivalences you must memorize
Implication as disjunction: $p \to q \equiv \lnot p \lor q$. This single rewrite unlocks half of all simplification problems.
De Morgan: negation distributes by flipping $\land \leftrightarrow \lor$.
Satisfiability
Unsatisfiable: no assignment makes it true (i.e., it's a contradiction).
Useful facts that you can be asked to prove:
- $\varphi$ is unsatisfiable $\iff$ $\lnot\varphi$ is a tautology.
- $\varphi$ is a tautology $\iff$ $\lnot\varphi$ is unsatisfiable.
Worked Example. Is $(p \lor \lnot q) \land (\lnot p \lor q) \land (\lnot p \lor \lnot q)$ satisfiable?
Solution. Try $p = F$: then $\lnot p = T$ kills the second and third clauses easily. The first clause requires $p \lor \lnot q$, i.e. $\lnot q$, so $q = F$. Check: clause 1 = $F\lor T = T$ ✓, clause 2 = $T \lor F = T$ ✓, clause 3 = $T\lor T = T$ ✓. Satisfiable with $p=F, q=F$.
Sudoku as a SAT problem
A classic application. We encode the rules of Sudoku as a compound proposition over Boolean variables. For an $n \times n$ Sudoku using digits $\{1,\ldots,n\}$, define $$p(i,j,k) = \text{“cell }(i,j)\text{ contains digit }k\text{”}.$$ Then the rules become:
- Every cell has at least one number. $$\bigwedge_{i,j}\bigvee_k p(i,j,k)$$
- Each row $i$ contains digit $k$. The single-row condition is $\bigvee_j p(i,j,k)$; combining over all $i$ and $k$: $$\bigwedge_i \bigwedge_k \bigvee_j p(i,j,k)$$
- Each column $j$ contains digit $k$. $$\bigwedge_j \bigwedge_k \bigvee_i p(i,j,k)$$
- Each 3×3 block (for 9×9) contains each digit. For each block $B$ and each $k$: $$\bigvee_{(i,j)\in B} p(i,j,k)$$
- No cell has two numbers. $$\bigwedge_{i,j} \bigwedge_{k \neq k'} \lnot(p(i,j,k) \land p(i,j,k'))$$
1.2 Predicate Logic & Quantifiers
Propositions alone can't say things like "every integer has a successor." For that we need predicates and quantifiers.
The two quantifiers
- Universal $\forall x\, P(x)$ — "for all $x$ in the domain, $P(x)$ is true." True iff $P$ holds for every element.
- Existential $\exists x\, P(x)$ — "there exists an $x$ such that $P(x)$." True iff at least one element makes $P$ true.
Domain matters
$\forall x\,(x^2 \geq 0)$ is true if the domain is $\mathbb{R}$, but $\forall x\,(2x > x)$ is false on $\mathbb{R}$ (try $x = 0$ or $x < 0$) and true on positive reals. Always state your domain.
Nested quantifiers
Order matters when you mix $\forall$ and $\exists$.
Let $L(x,y)$ mean "$x$ loves $y$" with domain = all people.
- $\forall x\, \exists y\, L(x,y)$ — "Everyone loves someone (not necessarily the same person)."
- $\exists y\, \forall x\, L(x,y)$ — "There is someone whom everyone loves." Much stronger!
- $\forall x\, \forall y\, L(x,y)$ — "Everyone loves everyone."
- $\exists x\, \exists y\, L(x,y)$ — "Some pair loves each other (or themselves)."
Rule of thumb: swapping $\forall \exists$ to $\exists \forall$ makes a stronger statement. The implication $\exists y \forall x \to \forall x \exists y$ always holds; the reverse does not.
Negating quantified statements
Two formulas you must know cold (sometimes called the quantifier De Morgan rules):
$\lnot \exists x\, P(x) \;\equiv\; \forall x\, \lnot P(x)$
Pushing a negation through a quantifier flips the quantifier and negates the body. Apply repeatedly to negate nested statements.
Worked Example. Negate: "Every student in this class has taken some math course."
Formally: $\forall x\, \exists y\, (\text{Student}(x) \to \text{Took}(x,y))$.
Negation: $\exists x\, \forall y\, (\text{Student}(x) \land \lnot \text{Took}(x,y))$. In English: "There is a student in this class who has not taken any math course."
Translating English to predicate logic
Strategy:
- Identify the variables and their domain.
- Define predicates (with clear meaning).
- Read the English carefully — "only if", "unless", "some", "every", "no" all carry quantifier meaning.
- Watch for hidden conditionals. "Every dog barks" is really $\forall x\,(\text{Dog}(x) \to \text{Barks}(x))$ — not $\forall x\,(\text{Dog}(x) \land \text{Barks}(x))$, which would say everything is a barking dog.
"Only if" trap
"$p$ only if $q$" means $p \to q$, NOT $q \to p$. "$p$ if $q$" means $q \to p$. "$p$ if and only if $q$" means both.
1.3 Boolean Algebra & Computer Architecture
Boolean algebra is propositional logic in different clothing. We use $1$ for $T$, $0$ for $F$, and the connectives are written:
| Logic | Boolean | Gate |
|---|---|---|
| $p \land q$ | $pq$ or $p \cdot q$ | AND |
| $p \lor q$ | $p + q$ | OR |
| $\lnot p$ | $\bar p$ | NOT |
| $p \oplus q$ | $p\bar q + \bar p q$ | XOR |
Sum-of-products (SOP) & Product-of-sums (POS)
SOP / DNF: a sum (OR) of minterms — one minterm per row of the truth table where the function is 1.
Maxterm: a sum of literals, one for each variable. POS / CNF: a product of maxterms — one per row where the function is 0.
How to write the SOP. Build the truth table. For each row where $F = 1$, write the minterm using each variable directly if it's 1 in that row, negated if it's 0. Then OR all the minterms.
Worked Example. $F(x,y,z) = x + yz$. Truth table:
| $x$ | $y$ | $z$ | $F$ | Minterm (when $F=1$) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | — |
| 0 | 0 | 1 | 0 | — |
| 0 | 1 | 0 | 0 | — |
| 0 | 1 | 1 | 1 | $\bar x y z$ |
| 1 | 0 | 0 | 1 | $x\bar y\bar z$ |
| 1 | 0 | 1 | 1 | $x\bar y z$ |
| 1 | 1 | 0 | 1 | $xy\bar z$ |
| 1 | 1 | 1 | 1 | $xyz$ |
SOP: $F = \bar x y z + x\bar y\bar z + x\bar y z + xy\bar z + xyz$.
Karnaugh Maps (K-Maps) — minimizing SOP
A K-map is a 2D grid layout of a truth table where adjacent cells differ in exactly one variable (Gray code ordering). Group adjacent 1s into rectangles of size $2^k$ to eliminate variables.
Rules for grouping
- Groups must be rectangular and contain $1, 2, 4, 8, \ldots$ cells (powers of 2).
- Each group must contain only $1$s.
- Groups should be as large as possible (each doubling eliminates one variable).
- Every $1$ must be covered by at least one group; use the fewest groups possible.
- K-maps wrap around — left ↔ right, top ↔ bottom edges are adjacent.
K-map layout (3 variables)
| $yz=00$ | $yz=01$ | $yz=11$ | $yz=10$ | |
|---|---|---|---|---|
| $x=0$ | $\bar x\bar y\bar z$ | $\bar x\bar y z$ | $\bar x y z$ | $\bar x y\bar z$ |
| $x=1$ | $x\bar y\bar z$ | $x\bar y z$ | $x y z$ | $x y\bar z$ |
Note the column ordering $00,01,11,10$ (Gray code).
Worked Example. Minimize $f(x,y,z) = xy\bar z + x\bar y z + \bar x y z + \bar x \bar y \bar z$ using a K-map.
Fill the map:
| $yz=00$ | $yz=01$ | $yz=11$ | $yz=10$ | |
|---|---|---|---|---|
| $x=0$ | 1 | 0 | 1 | 0 |
| $x=1$ | 0 | 1 | 0 | 1 |
Notice all four 1s are isolated — no two are adjacent. So no simplification beats the original. Each 1 must stay as its own minterm. Minimized form is the original. This is the XOR pattern: $f = x \oplus y \oplus z$ when an odd number of the three are 1.
When K-map gives no reduction
If 1s form a "checkerboard," your function is an XOR/XNOR — common in parity circuits. Don't try to force it; report it as XOR.
Representing arithmetic with propositional logic
A favorite exam question: given a 4-bit number $x$ with bits $x_3 x_2 x_1 x_0$ (LSB first), write a proposition checking arithmetic properties.
- $x \geq 8$: $x_3$ (the high bit must be 1).
- $x$ divisible by $4$: $\lnot x_0 \land \lnot x_1$ (low two bits are 0).
- $x$ divisible by $2$: $\lnot x_0$.
- $x$ is a power of $2$: exactly one $x_i$ is true. Express via "at least one is true AND for each pair at most one is true," or just enumerate: $(x_0\land\lnot x_1\land\lnot x_2\land\lnot x_3)\lor(\lnot x_0\land x_1\land\lnot x_2\land\lnot x_3)\lor\ldots$
- $x = y$: $(x_0\leftrightarrow y_0)\land(x_1\leftrightarrow y_1)\land(x_2\leftrightarrow y_2)\land(x_3\leftrightarrow y_3)$.
- $x = 2y$: shifting $y$ left by 1: $\lnot x_0 \land (x_1 \leftrightarrow y_0) \land (x_2 \leftrightarrow y_1) \land (x_3 \leftrightarrow y_2) \land \lnot y_3$ (so $y \leq 7$, else overflow).
Interactive tools
Two small tools to help you check your work without flipping back and forth — build a truth table from a proposition, or minimize a Boolean expression on a K-map.
Use letters for variables, and ! or ~ for NOT, & AND, | OR, ^ XOR, -> implies, <-> iff. Parentheses supported. Up to 5 variables.
Click cells to toggle 0/1. Variables: rows = wx, columns = yz, both in Gray code. Minimal SOP appears below.
Problem Bank — Logic
Drawn from DPP 1–4, Logic worksheets, and the midsem paper. Try each on paper first; reveal the solution to check your reasoning.
Construct a truth table for $p \oplus (p \lor q)$.
Show solution
| $p$ | $q$ | $p\lor q$ | $p\oplus(p\lor q)$ |
|---|---|---|---|
| T | T | T | F |
| T | F | T | F |
| F | T | T | T |
| F | F | F | F |
This equals $\lnot p \land q$ — a useful observation.
Translate to propositional logic: "You can borrow the rare book only if you are a faculty member and have a valid ID." Let $F$ = faculty, $I$ = ID, $B$ = borrow.
Show solution
"Only if" puts the consequent on the right. "You can borrow $B$ only if (faculty AND ID)" means: $$B \to (F \land I)$$ Pitfall: students often write $(F\land I) \to B$. That's "if faculty and ID, then can borrow," which is the converse and wrong.
Which of the following is NOT a tautology?
- $(a\to b)\land(b\to c) \to (a\to c)$
- $(a\leftrightarrow c)\to(\lnot b \to (a\land c))$
- $(a\land b\land c)\to(c\lor a)$
- $a \to (b \to a)$
Show solution
(a) is hypothetical syllogism — always a tautology.
(c) is trivial: $a\land b\land c$ implies $c\lor a$.
(d) $a\to(b\to a)$: if $a$ is true, $b\to a$ is true. Tautology.
(b) Counterexample: $a = T, c = T, b = T$. Then $a\leftrightarrow c = T$, $\lnot b = F$. The inner $\lnot b \to (a\land c)$ is "F → T" = T. Overall T → T = T. Try $a=F, c=F, b=F$: $a\leftrightarrow c = T$, $\lnot b = T$, $a\land c = F$. Inner: T → F = F. Overall: T → F = F. So (b) is NOT a tautology. Answer: (b).
Determine whether $(p \to q) \land (p \to \lnot q) \land (\lnot p \to q) \land (\lnot p \to \lnot q)$ is satisfiable.
Show solution
Rewrite each implication: $\lnot p \lor q$, $\lnot p \lor \lnot q$, $p\lor q$, $p\lor\lnot q$.
Case $p=T$: need $q$ (from clause 1) and need $\lnot q$ (from clause 2). Contradiction.
Case $p=F$: need $q$ (from clause 3) and need $\lnot q$ (from clause 4). Contradiction.
Unsatisfiable.
Show that the negation of an unsatisfiable proposition is a tautology, and conversely.
Show solution
Let $\varphi$ be unsatisfiable. By definition, $\varphi$ is false under every assignment $\Rightarrow$ $\lnot\varphi$ is true under every assignment $\Rightarrow$ $\lnot\varphi$ is a tautology.
Conversely, $\varphi$ is a tautology iff $\varphi$ is true everywhere iff $\lnot\varphi$ is false everywhere iff $\lnot\varphi$ is unsatisfiable. ∎
$x,y$ are Boolean (0 or 1). Translate the C-style condition "if (x * (1 - y)) + ((1 - x) * y) ..." into propositional logic.
Show solution
$x \cdot (1-y) = 1$ iff $x=1, y=0$, i.e. $x \land \lnot y$. Similarly $(1-x)\cdot y = \lnot x \land y$. The sum is nonzero iff at least one term is 1: $(x \land \lnot y) \lor (\lnot x \land y) = x \oplus y$.
$x \in \{0,\ldots,15\}$ with bits $x_3x_2x_1x_0$. Write a proposition asserting that $x$ is divisible by 5.
Show solution
The multiples of 5 in $\{0,\ldots,15\}$ are $\{0, 5, 10, 15\}$:
$0 = 0000$, $5 = 0101$, $10 = 1010$, $15 = 1111$.
Pattern: $x_3 = x_1$ AND $x_2 = x_0$. So
$$\text{Div}_5(x) = (x_3 \leftrightarrow x_1) \land (x_2 \leftrightarrow x_0).$$
Verify by listing all 16 inputs if you want.
Express in predicate logic: "Some students have never been asked a question by a faculty member." Use $S(x)$ = "$x$ is a student," $F(x)$ = "$x$ is a faculty member," $A(x,y)$ = "$x$ has asked $y$ a question."
Show solution
"Some student $x$ such that no faculty $y$ has ever asked $x$ a question": $$\exists x\, \big(S(x) \land \forall y\,(F(y) \to \lnot A(y,x))\big)$$ Equivalent: $\exists x\, \big(S(x) \land \lnot \exists y\,(F(y) \land A(y,x))\big)$.
Express the negation, in quantifiers and in English: "There is a student in this class who has taken every mathematics course offered at this school."
Show solution
Original: $\exists x\, \forall y\, (\text{Stud}(x) \land (\text{Course}(y) \to \text{Took}(x,y)))$.
Negation: $\forall x\, \exists y\, (\lnot\text{Stud}(x) \lor (\text{Course}(y) \land \lnot\text{Took}(x,y)))$.
In English: "Every student in this class has not taken some math course offered" — i.e., "For every student, there is some math course they haven't taken."
Suresh: "In every region there is a town where all inhabitants are happy." Which sentence correctly negates this?
- There is a region where there is a town where all inhabitants are happy.
- In every region in all towns all inhabitants are happy.
- In every region there is a town where at least one inhabitant is unhappy.
- There is a region where in all towns at least one inhabitant is unhappy.
Show solution
Suresh: $\forall r\, \exists t \in r\, \forall i \in t\, H(i)$. Negate: $$\exists r\, \forall t \in r\, \exists i \in t\, \lnot H(i)$$ — "There is a region where every town has at least one unhappy inhabitant." That's option (d).
Translate using $P(x)$="hummingbird," $Q(x)$="large," $R(x)$="lives on honey," $S(x)$="richly colored":
(a) All hummingbirds are richly colored.
(b) No large birds live on honey.
(c) Birds that do not live on honey are dull in color.
(d) Hummingbirds are small. (conclusion)
Show solution
(a) $\forall x\,(P(x)\to S(x))$
(b) $\forall x\,(Q(x)\to\lnot R(x))$ — equivalently $\lnot\exists x\,(Q(x)\land R(x))$.
(c) $\forall x\,(\lnot R(x)\to\lnot S(x))$ — contrapositively $\forall x\,(S(x)\to R(x))$.
(d) $\forall x\,(P(x)\to\lnot Q(x))$.
Find the sum-of-products expansion of $F(x,y,z) = (x+z)y$.
Show solution
Distribute: $(x+z)y = xy + yz$. Now expand each term to full minterms (each variable must appear):
$xy = xy(z + \bar z) = xyz + xy\bar z$.
$yz = yz(x + \bar x) = xyz + \bar x y z$.
Union (drop duplicates): $F = xyz + xy\bar z + \bar x y z$.
Use a K-map to find the minimal SOP for $xy + x\bar y + \bar x y + \bar x \bar y$.
Show solution
This function equals 1 on every input — it's the constant 1. K-map:
| $y=0$ | $y=1$ | |
|---|---|---|
| $x=0$ | 1 | 1 |
| $x=1$ | 1 | 1 |
Minimize $f(x,y,z) = xy\bar z + x\bar y z + \bar x y z + \bar x \bar y \bar z$ using a K-map.
Show solution
K-map (Gray code columns $00, 01, 11, 10$):
| $yz=00$ | $yz=01$ | $yz=11$ | $yz=10$ | |
|---|---|---|---|---|
| $x=0$ | 1 ($\bar x\bar y\bar z$) | 0 | 1 ($\bar x y z$) | 0 |
| $x=1$ | 0 | 1 ($x\bar y z$) | 0 | 1 ($xy\bar z$) |
It's a checkerboard pattern — no two 1s are adjacent (recall wrap-around). So no minterm can be merged. The minimal SOP is the original four-minterm expression. Equivalently, $f = x \oplus y \oplus z$.
For 4×4 Sudoku with digits $\{1,2,3,4\}$ and predicate $p(i,j,k)$ = "cell $(i,j)$ contains $k$", write:
(a) WFF for Rule 1: every row contains $\{1,2,3,4\}$ exactly once.
(b) WFF for Rule 2: every column contains $\{1,2,3,4\}$ exactly once.
(c) WFF for Rule 3: every 2×2 subgrid contains $\{1,2,3,4\}$ exactly once.
(d) WFF asserting no cell has more than one number.
Show solution
(a) Rows: for every row $i$ and every digit $k$, $k$ appears in row $i$, AND no two cells in row $i$ have the same digit: $$\bigwedge_{i=1}^{4}\bigwedge_{k=1}^{4}\exists j\, p(i,j,k) \;\;\land\;\; \bigwedge_{i,k}\bigwedge_{j\neq j'}\lnot(p(i,j,k)\land p(i,j',k))$$ Or compactly: $\forall i\, \forall k\, \exists j\, p(i,j,k)$ combined with uniqueness (the second conjunct).
(b) Columns: $\forall j\, \forall k\, \exists i\, p(i,j,k)$ + uniqueness $\forall j,k\, \forall i\neq i'\,\lnot(p(i,j,k)\land p(i',j,k))$.
(c) 2×2 subgrids: The four blocks are indexed by $(a,b)$ with $a, b \in \{0,1\}$, covering rows $\{2a+1, 2a+2\}$ and columns $\{2b+1, 2b+2\}$. For each block and each $k$, there's a cell with that digit: $$\bigwedge_{a,b\in\{0,1\}}\bigwedge_{k=1}^{4}\bigvee_{i=2a+1}^{2a+2}\bigvee_{j=2b+1}^{2b+2} p(i,j,k)$$ plus uniqueness within each block.
(d) No cell has two digits: $$\forall i,j\, \forall k \neq k'\, \lnot(p(i,j,k) \land p(i,j,k'))$$
Show that $\lnot(p \to q) \equiv p \land \lnot q$ using equivalences (not a truth table).
Show solution
$\lnot(p \to q) \equiv \lnot(\lnot p \lor q)$ [implication as disjunction]
$\equiv \lnot\lnot p \land \lnot q$ [De Morgan]
$\equiv p \land \lnot q$ [double negation]. ∎
Explain how a $4 \times 4$ Sudoku puzzle can be modeled as a Satisfiability problem; mention the types of logical constraints needed.
Show solution
Variables: For each cell $(i,j)$ and each digit $k\in\{1,2,3,4\}$, define a Boolean $p(i,j,k)$ meaning "cell $(i,j)$ holds $k$." That's $4\cdot4\cdot4 = 64$ variables.
Constraints (conjunction of all the following):
- Cell-fills — each cell has at least one digit. $$\bigwedge_{i,j}\bigvee_k p(i,j,k)$$
- Cell-uniqueness — each cell has at most one digit. $$\bigwedge_{i,j,\;k\neq k'}\lnot\!\big(p(i,j,k)\land p(i,j,k')\big)$$
- Row constraint — each row contains each digit. $$\bigwedge_{i,k}\bigvee_j p(i,j,k)$$
- Column constraint — each column contains each digit. $$\bigwedge_{j,k}\bigvee_i p(i,j,k)$$
- Block constraint — each $2\times 2$ block contains each digit.
- Givens — for each pre-filled cell $(i,j)$ with value $k$, add the unit clause $p(i,j,k)$.
The puzzle is solvable iff this big CNF is satisfiable; a satisfying assignment encodes the solution.
Show that $(p\to q)\land(\lnot q\to\lnot p)$ is a tautology.
Show solution
By the contrapositive law, $\lnot q \to \lnot p \equiv p \to q$. So the conjunction becomes $(p\to q) \land (p\to q) \equiv p\to q$, which is contingent — but the question asks whether the original is a tautology. It's not in general (it's just $p \to q$). But note this is equivalent to "$p \to q$", which is a contingent proposition. So the statement is wrong unless interpreted as: $(p\to q) \leftrightarrow (\lnot q \to \lnot p)$ — that biconditional IS a tautology by contrapositive.
- Implication direction: "only if" $\Rightarrow$ arrow points to the right of "only if". "$p$ if $q$" $\Rightarrow$ $q \to p$.
- Negate quantifiers: $\lnot\forall = \exists\lnot$, $\lnot\exists = \forall\lnot$.
- Empty domain trick: $\forall x\, P(x)$ is vacuously true; $\exists x\, P(x)$ is vacuously false.
- K-map ordering: always use Gray code (00, 01, 11, 10) — adjacent cells must differ in one variable.
- For SAT, build a truth table when you can; for problems with $\leq 3$ variables it's the safest method.