Propositional and Predicate Logic

A proposition is a statement that is either true or false. Propositional logic deals with Propositions and their combinations using logical connectives.

Basic connectives:

Truth tables. The implication $p \implies q$ is false only when $p$ is true and $q$ is false.

Logical equivalence. Two propositions are logically equivalent ($\equiv$) if they have the Same truth value for all assignments.

Important equivalences:

• $\neg(p \land q) \equiv \neg p \lor \neg q$ (De Morgan)
• $\neg(p \lor q) \equiv \neg p \land \neg q$ (De Morgan)
• $p \implies q \equiv \neg p \lor q$
• $p \iff q \equiv (p \implies q) \land (q \implies p)$
• $\neg(p \implies q) \equiv p \land \neg q$

Predicates extend propositional logic with variables and quantifiers.

• Universal quantifier: $\forall x\, P(x)$ — ”$P(x)$ holds for all $x$.”
• Existential quantifier: $\exists x\, P(x)$ — “there exists $x$ such that $P(x)$ holds.”

Negation of quantifiers:

$\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$

$\neg \exists x\, P(x) \equiv \forall x\, \neg P(x)$

Nested quantifiers must be read carefully. The order matters:

$\forall x\, \exists y\, P(x, y) \not\equiv \exists y\, \forall x\, P(x, y)$

The first says “for every $x$ there is a (possibly different) $y$.” The second says “there exists a Single $y$ that works for all $x$.“

A formula is valid (a tautology) if it is true under all interpretations. A formula is satisfiable if it is true under at least one interpretation.

Theorem 1.1. A formula is valid if and only if its negation is unsatisfiable.

For a propositional formula with $n$ distinct variables, the truth table has $2^n$ rows (one per Assignment). Two systematic methods ensure no assignment is missed.

Method 1: Binary counting. Treat the first variable as the most significant bit. Enumerate all Binary $n$-tuples from $(0, \ldots, 0)$ to $(1, \ldots, 1)$. The first variable changes most slowly (only every $2^{n-1}$ rows), while the last variable alternates every row.

Method 2: Recursive splitting. For $n$ variables, the table splits into two blocks of $2^{n-1}$ Rows: the top block has the first variable as $T$The bottom as $F$. Recurse on the remaining $n - 1$ variables within each block.

Worked Example. Construct the truth table for $(p \implies q) \land (q \implies r)$.

Worked Example. Verify that hypothetical syllogism $(p \implies q) \land (q \implies r) \implies (p \implies r)$ is a tautology.

Natural deduction is a …/1-number-and-algebra/3proof-and-logic system that mirrors ordinary mathematical reasoning. Each connective Has introduction rules (how to _derive a formula with that connective) and elimination rules (how to use a formula with that connective).

Rules of inference:

Square brackets $[A]$ denote an assumption that is discharged after the rule is applied.

Worked Example. Prove: $p \to q \vdash \neg q \to \neg p$ (contraposition).

Worked Example. Prove: $p \lor q, \neg p \vdash q$ (disjunctive syllogism).

Worked Example. Prove: $p \land (q \lor r) \vdash (p \land q) \lor (p \land r)$ (distribution).

:::caution Common Pitfall In natural deduction, always track which assumptions are discharged. A common mistake is to use a Discharged assumption in a later step. Each discharged assumption is only valid within the scope Indicated by the rule that discharges it. :::

A literal is a propositional variable or its negation. A clause is a disjunction of literals. A term (or cube) is a conjunction of literals.

• Disjunctive Normal Form (DNF): a disjunction of terms, e.g. $(p \land \neg q) \lor (\neg p \land r)$.
• Conjunctive Normal Form (CNF): a conjunction of clauses, e.g. $(p \lor \neg q) \land (\neg p \lor r)$.

Theorem 1.2. Every propositional formula is equivalent to a formula in CNF and to a formula in DNF.

Conversion to CNF:

1. Eliminate $\iff$ and $\implies$: $A \implies B \equiv \neg A \lor B$And $A \iff B \equiv (\neg A \lor B) \land (A \lor \neg B)$.
2. Push $\neg$ inward using De Morgan”s laws and double negation ($\neg\neg A \equiv A$) until every $\neg$ applies to a single variable.
3. Distribute $\lor$ over $\land$: $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$.

Conversion to DNF: Same steps 1—2; in step 3 distribute $\land$ over $\lor$ instead.

Worked Example. Convert $(p \land q) \lor (\neg p \land r)$ to CNF.

Worked Example. Convert $\neg(p \implies q) \lor r$ to CNF.

:::caution Common Pitfall Distributing $\lor$ over $\land$ can cause exponential blowup. A DNF formula with $n$ terms can Produce up to $2^n$ clauses when converted to CNF. This exponential growth underlies the hardness Of many satisfiability problems. :::

The resolution rule is a single inference rule that is refutation-complete for propositional Logic.

Resolution rule. From clauses $(A \lor x)$ and $(B \lor \neg x)$Derive the resolvent $(A \lor B)$Where $A$ and $B$ are (possibly empty) sets of literals and $x$ is a propositional Variable.

Resolution refutation. To show that clauses $\{C_1, \ldots, C_k\}$ entail clause $C$:

1. Add $\neg C$ to the clause set.
2. Repeatedly apply the resolution rule to derive new clauses.
3. If the empty clause $\bot$ is derived, the entailment holds.

Theorem 1.3 (Refutation completeness). If a set of clauses is unsatisfiable, the empty clause Can be derived by resolution.

Worked Example. Show that $\{p \lor q,\; \neg p \lor r,\; \neg q \lor \neg r\}$ entails $\neg r$.

The Boolean satisfiability problem (SAT) asks: given a propositional formula $\phi$Is there a Truth assignment that makes $\phi$ true?

Definition. An instance of SAT is a propositional formula. The answer is YES if $\phi$ is Satisfiable, NO otherwise.

k-SAT. A restricted version where the formula is in CNF and every clause has exactly $k$ Literals.

• 1-SAT: solvable in linear time (each clause is a single literal).
• 2-SAT: solvable in $O(n + m)$ time using the implication graph and strongly connected components, where $n$ is the number of variables and $m$ the number of clauses.
• 3-SAT: NP-complete (Cook—Levin theorem, 1971). This was the first problem proven NP-complete.

Theorem 1.4 (Cook—Levin). SAT is NP-complete. Consequently, 3-SAT is also NP-complete.

SAT solvers (DPLL, CDCL) are widely deployed in hardware verification, software model checking, and AI planning. Modern solvers routinely handle instances with millions of variables.

:::caution Common Pitfall Do not confuse satisfiability with validity. A formula is satisfiable if it is true under some Assignment; it is valid (a tautology) if true under all assignments. Checking validity is Co-NP-complete, not NP-complete.

:::