Section 1.2: Truth Assignments
A set of truth values: (falsity), (truth).
A truth assignment for a set of sentence symbols is a function .
We further consider the extension defined on the set of all wffs built up from such that
a) for a sentence symbol , , and
b) for wffs ,
- for any on a set , there is a unique extension on .
For a formula containing sentence symbols from only, satisfies iff . A wff or a set of wffs is called satisfiable if there is a truth assignment that satisfies it.
(Compactness Theorem: to be proved in Section 1.7) If every finite subset of an infinite set is satisfiable, then is satisfiable.
A set of wffs (hypotheses) tautologically implies a wff (conclusion), written as , if every truth assignment for the sentence symbols used in and that satisfies all wffs in also satisfies .
- If , the we write .
- If and , then and are tautologically equivalent.
- is said to be a tautology, written as , if .
Two sets of wffs are equivalent if one tautologically implies any formula iff the other does so too. And a set of wffs is called independent iff no member of it is tautologically implied by the remaining members of the set.
- Every finite set of wffs has an equivalent independent subset, but this is not true, in general, for an infinite set of wffs.
- Associative and commutative laws for , , and .
- Distributive laws for and , and vice versa.
- De Morgan’s laws for the negation of and (and, in more general, the duality principle).
- The substitution principle: if a wff is a tautology, then by substituting wffs for sentence symbols we still get a tautology.
Tautologies including the conditional symbol:
- Contraposition: .
- Exportation: .
- iff .