Logic: propositional and predicate

Propositional logic

Definition. A proposition is a statement that is either true or false. Formulas are built from propositional variables $p, q, r, \dots$ with the connectives $\neg$ (not), $\wedge$ (and), $\vee$ (or), $\rightarrow$ (implies) and $\leftrightarrow$ (if and only if).

Implication. $p \rightarrow q$ is false only when $p$ is true and $q$ is false. So it is equivalent to $\neg p \vee q$. Its contrapositive $\neg q \rightarrow \neg p$ is equivalent to it; its converse $q \rightarrow p$ and inverse $\neg p \rightarrow \neg q$ are not.

$p$	$q$	$p \wedge q$	$p \vee q$	$p \rightarrow q$	$p \leftrightarrow q$
T	T	T	T	T	T
T	F	F	T	F	F
F	T	F	T	T	F
F	F	F	F	T	T

Useful equivalences.

• De Morgan: $\neg(p \wedge q) \equiv \neg p \vee \neg q$ and $\neg(p \vee q) \equiv \neg p \wedge \neg q$.
• Distribution: $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$.
• $p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)$.
• Exportation: $(p \wedge q) \rightarrow r \equiv p \rightarrow (q \rightarrow r)$.

Kinds of formula. A tautology is true under every assignment (e.g. $p \vee \neg p$); a contradiction is false under every assignment; a formula is satisfiable if at least one assignment makes it true. A formula $\alpha$ is valid exactly when $\neg\alpha$ is unsatisfiable.

Entailment. A knowledge base $KB$ entails $\alpha$, written $KB \models \alpha$, if $\alpha$ is true in every model (assignment) where $KB$ is true. Equivalently, $KB \wedge \neg\alpha$ is unsatisfiable. A formula over $n$ variables has $2^n$ assignments, so model checking by truth table takes $O(2^n)$ time.

Solved examples

Example 1: is it a tautology? Check $((p \rightarrow q) \wedge p) \rightarrow q$ (modus ponens). The only way an implication fails is a true premise with a false conclusion: $q$ false and $(p \rightarrow q) \wedge p$ true. But $p$ true and $q$ false make $p \rightarrow q$ false. So it never fails: a tautology.

Example 2: equivalent forms. $\neg(p \rightarrow q) \equiv \neg(\neg p \vee q) \equiv p \wedge \neg q$.

Inference rules and resolution

Sound rules derive only entailed conclusions:

• Modus ponens: from $p \rightarrow q$ and $p$, infer $q$.
• Modus tollens: from $p \rightarrow q$ and $\neg q$, infer $\neg p$.
• Hypothetical syllogism: from $p \rightarrow q$ and $q \rightarrow r$, infer $p \rightarrow r$.
• Disjunctive syllogism: from $p \vee q$ and $\neg p$, infer $q$.

Fallacies (not valid): affirming the consequent ($p \rightarrow q$, $q$, so $p$) and denying the antecedent ($p \rightarrow q$, $\neg p$, so $\neg q$).

Conjunctive normal form (CNF): a conjunction of clauses, each a disjunction of literals. Every formula has an equivalent CNF: remove $\leftrightarrow$ and $\rightarrow$, push $\neg$ inward with De Morgan, then distribute $\vee$ over $\wedge$.

Resolution: from clauses $(A \vee x)$ and $(B \vee \neg x)$ infer $(A \vee B)$. To prove $KB \models \alpha$: convert $KB \wedge \neg\alpha$ to CNF and resolve repeatedly; deriving the empty clause proves entailment (refutation). Resolution is sound and refutation-complete.

Horn clauses have at most one positive literal, e.g. $\neg p \vee \neg q \vee r$, i.e. $p \wedge q \rightarrow r$. For Horn knowledge bases, forward chaining (fire rules whose premises are known) and backward chaining (work back from the goal) decide entailment in time linear in the size of the KB.

Solved example

Example 3: resolution proof. KB: $p \rightarrow q$, $q \rightarrow r$, $p$. Goal: $r$.

1. Clauses: $(\neg p \vee q)$, $(\neg q \vee r)$, $(p)$, and the negated goal $(\neg r)$.
2. Resolve $(\neg q \vee r)$ with $(\neg r)$: $(\neg q)$.
3. Resolve $(\neg p \vee q)$ with $(\neg q)$: $(\neg p)$.
4. Resolve $(\neg p)$ with $(p)$: the empty clause.

So $KB \models r$.

Predicate (first-order) logic

Definition. First-order logic adds objects, predicates (properties and relations, such as $\text{Student}(x)$ or $\text{Likes}(x,y)$), functions, and the quantifiers $\forall$ (for all) and $\exists$ (there exists).

Translating English.

• "All students study": $\forall x\, (\text{Student}(x) \rightarrow \text{Studies}(x))$. Use $\rightarrow$ with $\forall$.
• "Some student studies": $\exists x\, (\text{Student}(x) \wedge \text{Studies}(x))$. Use $\wedge$ with $\exists$.
• "No student studies": $\forall x\, (\text{Student}(x) \rightarrow \neg\text{Studies}(x))$, equivalently $\neg\exists x\, (\text{Student}(x) \wedge \text{Studies}(x))$.

Exam point. $\exists x\,(\text{Student}(x) \rightarrow \text{Studies}(x))$ is a classic mistake: it is true as soon as anything is not a student.

Negating quantifiers. $\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$ and $\neg \exists x\, P(x) \equiv \forall x\, \neg P(x)$.

Order matters. $\forall x\, \exists y\, \text{Loves}(x, y)$ (everyone loves someone) differs from $\exists y\, \forall x\, \text{Loves}(x, y)$ (someone is loved by everyone). The second implies the first, not the other way round. Quantifiers of the same kind commute: $\forall x \forall y \equiv \forall y \forall x$.

Distribution. $\forall x\,(P \wedge Q) \equiv \forall x P \wedge \forall x Q$ and $\exists x\,(P \vee Q) \equiv \exists x P \vee \exists x Q$. But $\forall$ does not distribute over $\vee$, and $\exists$ does not distribute over $\wedge$.

Inference in first-order logic. Universal instantiation replaces a $\forall$ variable with any ground term; existential instantiation replaces an $\exists$ variable with a new constant (a Skolem constant). Unification finds a substitution that makes two expressions identical, e.g. $\text{Knows}(John, x)$ and $\text{Knows}(y, Mary)$ unify with $\{y/John, x/Mary\}$. Generalised modus ponens combines unification with modus ponens.

Solved example

Example 4. From $\forall x\,(\text{Man}(x) \rightarrow \text{Mortal}(x))$ and $\text{Man}(Socrates)$: instantiate $x = Socrates$, then modus ponens gives $\text{Mortal}(Socrates)$.