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


Speaker notes:

Content Tools

Sources

There are currently no sources for this slide.