Section 1.2: Problem 1 Solution »

# Section 1.2: Truth Assignments

A set of truth values: $F$ (falsity), (truth).
A truth assignment for a set $S$ of sentence symbols is a function $v:S\rightarrow\{F,T\}$ .
We further consider the extension $\overline{v}:\overline{S}\rightarrow\{F,T\}$ defined on the set $\overline{S}$ of all wffs built up from $S$ such that
a) for a sentence symbol $A\in S$ , $\overline{v}(A)=v(A)$ , and
b) for wffs $\alpha,\beta\in\overline{S}$ ,
 $\alpha$ $\beta$ $(\neg\alpha)$ $(\alpha\wedge\beta)$ $(\alpha\vee\beta)$ $(\alpha\rightarrow\beta)$ $(\alpha\leftrightarrow\beta)$ $T$ $T$ $F$ $T$ $T$ $T$ $T$ $T$ $F$ $F$ $F$ $T$ $F$ $F$ $F$ $T$ $T$ $F$ $T$ $T$ $F$ $F$ $F$ $T$ $F$ $F$ $T$ $T$
• for any $v$ on a set $S$ , there is a unique extension $\overline{v}$ on $\overline{S}$ .
For a formula $\phi$ containing sentence symbols from $S$ only, $v$ satisfies $\phi$ iff $\overline{v}(\phi)=T$ . 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 $\Sigma$ is satisfiable, then $\Sigma$ is satisfiable.
A set $\Sigma$ of wffs (hypotheses) tautologically implies a wff $\tau$ (conclusion), written as $\Sigma\vDash\tau$ , if every truth assignment for the sentence symbols used in $\Sigma$ and $\tau$ that satisfies all wffs in $\Sigma$ also satisfies $\tau$ .
• If $\Sigma=\{\sigma\}$ , the we write $\sigma\vDash\tau$ .
• If $\sigma\vDash\tau$ and $\tau\vDash\sigma$ , then $\tau$ and $\sigma$ are tautologically equivalent.
• $\tau$ is said to be a tautology, written as $\vDash\tau$ , if $\emptyset\vDash\tau$ .
• 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 $\wedge$ , $\vee$ , and $\leftrightarrow$ .
• Distributive laws for $\wedge$ and $\vee$ , and vice versa.
• De Morgan’s laws for the negation of $\wedge$ and $\vee$ (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: $((A\rightarrow B)\leftrightarrow((\neg B)\rightarrow(\neg A)))$ .
• Exportation: $(((A\wedge B)\rightarrow C)\leftrightarrow(A\rightarrow(B\rightarrow C)))$ .
• $(((A\wedge B)\rightarrow C)\leftrightarrow((A\rightarrow C)\vee(B\rightarrow C)))$ .
• Tautological implications:
• $\Sigma;\alpha\vDash\beta$ iff $\Sigma\vDash(\alpha\rightarrow\beta)$ .