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)$ .

Subpages

Section 1.2: Truth Assignments

Section 1.2: Truth Assignments

Some laws