You are here
Hometruthvalue semantics for classical propositional logic
Primary tabs
truthvalue semantics for classical propositional logic
In classical propositional logic, an interpretation of a wellformed 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 Booleanvalued function $\nu$ on $V$ a valuation on $V$. We want to extend $\nu$ to a Booleanvalued 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)=1x$.

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_{{i1}}$ (see construction of wellformed 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 nonempty. 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$ 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\}$.
Mathematics Subject Classification
03B05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections