(Last modified Tue Jan 22 22:41 2008)
We saw that the semantics of propositional logic showed how to determine the truth-value of any formula except for propositional variables and formulae containing them. A propositional variable A can represent either true or false, and unless we know which, we cannot say whether the formula A is true or false.
A (propositional logic) interpretation assigns truth values to one or more propositional variables.
Example: I = { A:true, B:true, C:false }.
Thus an interpretation can enable the determination
of the truth value of a formula.
If a formula α is true
in an interpretation I,
then we say that I satisfies α.
A formula that is satisfied by at least one interpretation
is said to be satisfiable;
a formula that is satisfied by every possible interpretation
is said to be valid
(written
α);
and
a formula that is satisfied by no interpretation
is said to be unsatisfiable.
These divisions are shown in the table below.
| Satisfied by | Validity | Satisfiability |
|---|---|---|
| All interpretations | Valid | Satisfiable |
| Some but not all interpretations | Not valid | |
| No interpretation | Unsatisfiable |
Examples using I = { A:true, B:true, C:false } :
One method of determining validity and satisfiability of a formula is that of constructing a truth table for the formula and examining its rows. If the result for every row is true, the formula is valid; if the result for every row is false, the formula is unsatisfiable; and otherwise, the formula is satisfiable but not valid. To determine whether a formula is satisfiable, the table need only be filled in until a true row is encountered; similarly, to determine whether a formula is not valid, the table need only be filled in until a false row is encountered. The entire table is required to show validity or unsatisfiability. Since the number of rows in the table for a formula of n metavariables is 2n, this method is exponential in the number of metavariables.
Indeed, satisfiability of propositional logic formulae is an NP-complete problem. That is, there is no known algorithm for determining satisfiability of an arbitrary formula in polynomial time (nor any reason to believe one exists), and there is a known algorithm to verify that a specific interpretation satisfies the formula in polynomial time.
Implication is a meta-logical relationship between two formulae.
A formula α implies
a formula β
(written αβ)
if
for every interpretation I,
β is true in I
if
α is true in I.
Implication can be extended to sets of formulae:
if Γ={α1,
α2,
... ,
αn},
then
Γβ
if
for every interpretation I,
β is true in I
if each of
α1,
α2,
... ,
αn
is true in I.
The implication relation defines a partial ordering on formulae.
Logical equivalence is a meta-logical relationship between two formulae. Two formulae α and β are logically equivalent (written α ⇔β or α ≡β) if they are true in exactly the same interpretations.
Equivalently,
formulae α and β
are logically equivalent if
αβ
and
βα.
