# 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