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:\lbrace 0,1\rbrace \to \lbrace 0,1\rbrace$ given by $f(x)=1-x$ .
• for $\vee$ , define $g:\lbrace 0,1\rbrace^2 \to \lbrace 0,1\rbrace$ given by $g(x,y)=\max(x,y)$ .

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 \lbrace 0,1\rbrace$ for each $i$ , as follows:

• $\nu_0:=\nu$
• suppose $\nu_i$ has been defined, we define $\nu_{i+1}:V_{i+1} \to \lbrace 0,1\rbrace$ given by
  

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 $\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$ , $\lbrace (p \vee q) \mid p,q \in V_i\rbrace$ , and $\lbrace (\neg p) \mid p\in V_i\rbrace$ , 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)=\lbrace 1\rbrace$ (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)=\lbrace 1\rbrace$ 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 \lbrace p\rbrace$ .