## 502 – Propositional logic (3)

September 11, 2009

Example 13 ${\lnot(A\land B)\leftrightarrow(\lnot A\lor\lnot B)}$ is a tautology. This is an example of De Morgan’s laws.

Example 14 ${A\lor(B\land C)\leftrightarrow(A\lor B)\land(A\lor C)}$ is a tautology.

Definition 19 A formula ${A}$ is satisfiable iff there is some valuation ${v}$ such that ${v\models A.}$ Otherwise, we say that ${A}$ is contradictory, or unsatisfiable.

Remark 7 ${A}$ is unsatisfiable iff ${\lnot A}$ is a tautology.

Example 15 ${(p\rightarrow q)\rightarrow(q\rightarrow p)}$ is not a tautology, but it is satisfiable.

Definition 20 If ${v}$ is a valuation and ${S}$ is a set of formulas, ${v\models S}$ iff ${v\models A}$ for all ${A\in S.}$ For a given ${S,}$ if there is such a valuation ${v,}$ we say that ${S}$ is satisfiable, or has a model, and that ${v}$ is a model of ${S.}$ Otherwise, ${S}$ is unsatisfiable or contradictory.