Section 1.2: Problem 1 Solution »

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.

Some laws

  • 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: .
    • .
  • Tautological implications:
    • iff .