truth-value semantics for classical propositional logic

In classical propositional logic, an interpretation of a well-formed formula (wff) $p$ is an assignment of truth (=1) or falsity (=0) to $p$ . Any interpreted wff is called a proposition.

An interpretation of all wffs over the variable set $V$ is then a Boolean function on $\overline{V}$ . However, one needs to be careful, for we do not want both $p$ and $\neg p$ be interpreted as true simultaneously (at least not in classical propositional logic)! The proper way to find an interpretation on the wffs is to start from the atoms.

Call any Boolean-valued function $\nu$ on $V$ a valuation on $V$ . We want to extend $\nu$ to a Boolean-valued function $\overline{\nu}$ on $\overline{V}$ of all wffs. The way this is done is similar to the construction of wffs; we build a sequence of functions, starting from $\nu$ on $V_{0}$ , next $\nu_{1}$ on $V_{1}$ , and so on… Finally, we take the union of all these “approximations” to arrive at $\overline{\nu}$ . So how do we go from $\nu$ to $\nu_{1}$ ? We need to interpret $\neg p$ and $p\vee q$ from the valuations of atoms $p$ and $q$ . In other words, we must also interpret logical connectives too.

Before doing this, we define a truth function for each of the logical connectives:

•

for $\neg$ , define $f:\{0,1\}\to\{0,1\}$ given by $f(x)=1-x$ .
•

for $\vee$ , define $g:\{0,1\}^{2}\to\{0,1\}$ given by $g(x,y)=\max(x,y)$ .

As we are trying to interpret $\neg$ (not) and $\vee$ (or), the choices for $f$ and $g$ are clear. The values $0,1$ are interpreted as the usual integers (so they can be subtracted and ordered, etc…). Hence $f$ and $g$ make sense.

Next, recall that $V_{i}$ are sets of wffs built up from wffs in $V_{i-1}$ (see construction of well-formed formulas for more detail). We define a function $\nu_{i}:V_{i}\to\{0,1\}$ for each $i$ , as follows:

•

$\nu_{0}:=\nu$
•

suppose $\nu_{i}$ has been defined, we define $\nu_{i+1}:V_{i+1}\to\{0,1\}$ given by

$\nu_{i+1}(p):=\left\{\begin{array}[]{ll}\nu_{i}(p)&\mbox{if }p\in V_{i},\\ f(\nu_{i}(q))&\mbox{if }p=\neg q\mbox{ for some }q\in V_{i},\\ g(\nu_{i}(q),\nu_{i}(r))&\mbox{if }p=q\vee r\mbox{ for some }q,r\in V_{i}.\end% {array}\right.$

Finally, take $\overline{\nu}$ to be the union of all the approximations:

\overline{\nu}:=\bigcup_{i=0}^{\infty}\nu_{i}.

Then, by unique readability of wffs, $\overline{\nu}$ is an interpretation on $\overline{V}$ .

Remark. If $\perp$ is included in the language of the logic (as the symbol for falsity), we also require that $\nu_{i}(\perp)=\overline{\nu}(\perp)=0$ .

Remark $\overline{V}$ can be viewed as an inductive set over $V$ with respect to the $\neg$ and $\vee$ , viewed as operations on $\overline{V}$ . Furthermore, $\overline{V}$ is freely generated by $V$ , since each $V_{i+1}$ can be partitioned into sets $V_{i}$ , $\{(p\vee q)\mid p,q\in V_{i}\}$ , and $\{(\neg p)\mid p\in V_{i}\}$ , and each partition is non-empty. As a result, any valuation $\nu$ on $V$ uniquely extends to a valuation $\overline{\nu}$ on $\overline{V}$ .

Definitions. Let $p, q$ be wffs in $\overline{V}$ .

•

$p$ is true or satisfiable for some valuation $\nu$ if $\overline{\nu}(p)=1$ (otherwise, it is false for $\nu$ ).
•

$p$ is true for every valuation $\nu$ , then $p$ is said to be valid (or tautologous). If $p$ is false for every $\nu$ , it is invalid. If $p$ is valid, we write $\models p$ .
•

$p$ implies $q$ for a valuation $\nu$ if $\overline{\nu}(p)=1$ implies $\overline{\nu}(q)=1$ . $p$ semantically implies if $p$ implies $q$ for every valuation $\nu$ , and is denoted by $p\models q$ .
•

$p$ is equivalent to $q$ for $\nu$ if $\overline{\nu}(p)=\overline{\nu}(q)$ . They are semantically equivalent if they are equivalent for every $\nu$ , and written $p\equiv q$ .

Semantical equivalence is an equivalence relation on $\overline{V}$ .

The above can be easily generalized to sets of wffs. Let $T$ be a set of propositions.

•

$T$ is true or satisfiable for $\nu$ if $\overline{\nu}(T)=\{1\}$ (otherwise, it is false for $\nu$ ).
•

$T$ is valid if it is true for every $\nu$ ; it is invalid if it is false for every $\nu$ . If $T$ is valid, we write $\models T$ .
•

$T$ implies $p$ for $\nu$ if $\overline{\nu}(T)=\{1\}$ implies $\overline{\nu}(p)=1$ . $T$ semantically implies $p$ if $T$ implies $p$ for every $\nu$ , and is denoted by $T\models p$ .
•

$T_{1}$ implies $T_{2}$ for $\nu$ if, for every $p\in T_{2}$ , $T_{1}$ implies $p$ for $\nu$ . $T_{1}$ semantically implies $T_{2}$ if $T_{1}$ implies $T_{2}$ for every $\nu$ , and is denoted by $T_{1}\models T_{2}$ .
•

$T_{1}$ is equivalent to $T_{2}$ for $\nu$ if for some valuation $\nu$ , $T_{1}$ implies $T_{2}$ for $\nu$ and $T_{2}$ implies $T_{1}$ for $\nu$ . $T_{1}$ and $T_{2}$ are semantically equivalent if $T_{1}\models T_{2}$ and $T_{2}\models T_{1}$ , written $T_{1}\equiv T_{2}$ .

Clearly, $\models p$ iff $\varnothing\models p$ , and $T\models p$ iff $T\models\{p\}$ .

Title	truth-value semantics for classical propositional logic
Canonical name	TruthvalueSemanticsForClassicalPropositionalLogic
Date of creation	2013-03-22 18:51:20
Last modified on	2013-03-22 18:51:20
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	20
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03B05
Synonym	entail
Defines	truth-value semantics
Defines	valuation
Defines	interpretation
Defines	valid
Defines	invalid
Defines	satisfiable