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
