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.

Read the rest of this entry »

Advertisement

Leave a Comment » | 502: Logic and set theory | Tagged: , | Permalink
Posted by andrescaicedo