Example 13
is a tautology. This is an example of De Morgan’s laws.
Example 14
is a tautology.
Definition 19 A formula
is satisfiable iff there is some valuation
such that
Otherwise, we say that
is contradictory, or unsatisfiable.
Remark 7
is unsatisfiable iff
is a tautology.
Example 15
is not a tautology, but it is satisfiable.
Definition 20 If
is a valuation and
is a set of formulas,
iff
for all
For a given
if there is such a valuation
we say that
is satisfiable, or has a model, and that
is a model of
Otherwise,
is unsatisfiable or contradictory.