Current Slide
Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.
Models and Satisfiability

A propositional formula A is satisfiable iff v ( A ) = T in some interpretation v; s uch an interpretation is called a model for A .

A is unsatisfiable (or, contradictory) if it is false in every interpretation

A set of formulas U = { A 1 ,A 2 ,…,A n } is satisfiable iff there exists an interpretation v such that v ( A 1 ) = v ( A 2 ) = … = v ( A n ) = T; such an interpretation is called a model of U.

U is unsatisfiable if no such interpretation exists

Relevant properties:

If U is satisfiable, then so is U − {Ai} for any i = 1, 2,…, n

If U is satisfiable and B is valid, then U U { B } is also satisfiable

If U is unsatisfiable and B is any formula, U U { B } is also unsatisfiable

If U is unsatisfiable and some A i is valid, then U − {Ai} is also unsatisfiable