Propositional Logic

Syntax and semantics of propositional logic, truth tables, validity, satisfiability and entailment, the key logical equivalences, converting to CNF, sound inference rules (modus ponens, modus tollens, resolution), proof by resolution refutation, Horn clauses with forward and backward chaining, and knowledge-based agents.

Syntax

Atomic propositions ( $p, q, r$ , or names like Raining) are combined with connectives:

Connective	Symbol	Read as
negation	$\neg p$	not $p$
conjunction	$p \wedge q$	$p$ and $q$
disjunction	$p \vee q$	$p$ or $q$ (inclusive)
implication	$p \to q$	if $p$ then $q$
biconditional	$p \leftrightarrow q$	$p$ if and only if $q$

Precedence (highest first): $\neg$ , $\wedge$ , $\vee$ , $\to$ , $\leftrightarrow$ .

Semantics

A model (interpretation) assigns true/false to every atom; the truth of compound sentences follows the truth tables:

$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

Term	Meaning
Valid (tautology)	true in every model, e.g. $p \vee \neg p$
Satisfiable	true in at least one model
Unsatisfiable (contradiction)	true in no model, e.g. $p \wedge \neg p$
Entailment $\text{KB} \models \alpha$	$\alpha$ is true in every model of KB
Equivalence $\alpha \equiv \beta$	same truth value in every model

Key facts: $\alpha$ is valid iff $\neg\alpha$ is unsatisfiable; $\text{KB} \models \alpha$ iff $\text{KB} \to \alpha$ is valid iff $\text{KB} \wedge \neg\alpha$ is unsatisfiable.

Logical equivalences

Law	Equivalence
Double negation	$\neg\neg p \equiv p$
De Morgan	$\neg(p \wedge q) \equiv \neg p \vee \neg q$ ; $\neg(p \vee q) \equiv \neg p \wedge \neg q$
Implication elimination	$p \to q \equiv \neg p \vee q$
Contrapositive	$p \to q \equiv \neg q \to \neg p$
Biconditional	$p \leftrightarrow q \equiv (p \to q) \wedge (q \to p)$
Distributivity	$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$ ; dually
Commutativity, associativity	for $\wedge$ and $\vee$
Exportation	$(p \wedge q) \to r \equiv p \to (q \to r)$
Absorption	$p \vee (p \wedge q) \equiv p$

Normal forms

Literal: an atom or its negation. Clause: a disjunction of literals.
CNF (conjunctive normal form): a conjunction of clauses — the input to resolution and SAT solvers.
DNF: a disjunction of conjunctions of literals.

Conversion to CNF: (1) eliminate $\leftrightarrow$ and $\to$ ; (2) push $\neg$ inwards with De Morgan and double negation; (3) distribute $\vee$ over $\wedge$ .

Inference rules

Rule	Premises	Conclusion
Modus ponens	$\alpha \to \beta$ , $\alpha$	$\beta$
Modus tollens	$\alpha \to \beta$ , $\neg\beta$	$\neg\alpha$
And-elimination	$\alpha \wedge \beta$	$\alpha$
Hypothetical syllogism	$\alpha \to \beta$ , $\beta \to \gamma$	$\alpha \to \gamma$
Disjunctive syllogism	$\alpha \vee \beta$ , $\neg\alpha$	$\beta$
Resolution	$\ell_1 \vee \dots \vee \ell_k \vee p$ , $\neg p \vee m_1 \vee \dots \vee m_n$	$\ell_1 \vee \dots \vee \ell_k \vee m_1 \vee \dots \vee m_n$

A procedure is sound if it derives only entailed sentences and complete if it can derive every entailed sentence.

Resolution refutation

To prove $\text{KB} \models \alpha$ : convert $\text{KB} \wedge \neg\alpha$ to CNF and repeatedly resolve pairs of clauses; deriving the empty clause (a contradiction) proves entailment. Resolution refutation is sound and complete for propositional logic.

Horn clauses and chaining

A Horn clause has at most one positive literal: facts ( $q$ ), rules ( $p_1 \wedge \dots \wedge p_k \to q$ ), and goals/constraints ( $\neg p_1 \vee \dots \vee \neg p_k$ ). For Horn knowledge bases, inference takes linear time:

Forward chaining (data-driven): repeatedly fire rules whose premises are all known, adding conclusions until the query appears or nothing changes.
Backward chaining (goal-driven): to prove $q$ , find a rule concluding $q$ and recursively prove its premises (the basis of Prolog).

Knowledge-based agents

An agent keeps a knowledge base, TELLs it percepts, ASKs it what to do, and acts. The Wumpus world is the textbook example: from "breeze in [1,2]" and the rule "a square is breezy iff a neighbour has a pit", the agent infers where pits might be. Propositional logic is limited because it cannot express general statements about objects compactly — that is what predicate logic adds.

Syntax

Semantics

Logical equivalences

Normal forms

Inference rules

Resolution refutation

Horn clauses and chaining

Knowledge-based agents

Quick revision

Practice questions