# realization of a formula by a truth function

Fix a countable set $V=\{v_{1},v_{2},\ldots\}$ of propositional variables. Let $p$ be a well-formed formula over $V$ constructed by a set $F$ of logical connectives. Let $S:=\{v_{k_{1}},\ldots,v_{k_{n}}\}$ be the set of variables occurring in $p$ ($S$ is finite as $p$ is a string of finite length). Fix the $n$-tuple $\boldsymbol{v}:=(v_{k_{1}},\ldots,v_{k_{n}})$. Every valuation $\nu$ on $V$, when restricted to $S$, determines an $n$-tupe of zeros and ones: $\nu(\boldsymbol{v}):=(\nu(v_{k_{1}}),\ldots,\nu(v_{k_{n}}))\in\{0,1\}^{n}$. For this $\nu(\boldsymbol{v})$, we associate the interpretation $\overline{\nu}(p)\in\{0,1\}$.

Two valuations on $V$ determine the same $a\in\{0,1\}^{n}$ iff they agree on every $v_{k_{i}}$. If we set $\nu_{1}\sim\nu_{2}$ iff they determine the same $a\in\{0,1\}^{n}$, then $\sim$ is an equivalence relation on the set of all valuations on $V$. As there are $2^{n}$ elements in $\{0,1\}^{n}$, there are $2^{n}$ equivalence classes.

From the two paragraphs above, we see that there is a truth function $\phi:\{0,1\}^{n}\to\{0,1\}$ such that

 $\phi(\nu(\boldsymbol{v}))=\overline{\nu}(p)$

for any valuation $\nu$ on $V$. This function is called a realization of the wff $p$. Since $p$ is arbitrary, it is easy to see that every wff admits a realization. It is also not hard to see that a realization of $p$ is unique up to the order of the variables in the $n$-tuple $\boldsymbol{v}$. From now only, we make the assumption that every $n$-tuple $(v_{k_{1}},\ldots,v_{k_{n}})$ has the property that $k_{1}<\cdots. Let us write $\phi_{p}$ the realization of $p$.

Realizations of wffs are closely related to semantical implications and equivalences:

1. 1.

$p\models q$ ($p$ semantically implies $q$, or $p$ entails $q$) iff $\phi_{p}\leq\phi_{q}$;

2. 2.

$p\equiv q$ iff $\phi_{p}=\phi_{q}$, where $\equiv$ denotes semantical equivalence;

3. 3.

$p$ is a tautology iff $\phi_{p}=1$, the constant function whose value is $1\in\{0,1\}$.

If $F=\{\neg,\vee,\wedge\}$, then every wff $p$ over $V$ corresponds to a realization $[p]$ that “looks” exactly likes $p$. We do this by induction:

• if $p$ is a propositional variable $v_{i}$, let $[v_{i}]$ be the identity function on $\{0,1\}$;

• if $p$ has the form $\neg q$, define $[p]:=\neg[q]$;

• if $p$ has the form $q\vee r$, define $[p]:=[q]\vee[r]$;

• if $p$ has the form $q\wedge r$, define $[p]:=[q]\wedge[r]$;

where the $\neg,\vee,$ and $\wedge$ on the right hand side of the definitions are the Boolean complementation, join and meet operations on the Boolean algebra $\{0,1\}$. Again by an easy induction, for each wff $p$, the function $[p]$ is the realization of $p$ (a function written in terms of symbols in $F$ is called a polynomial).

Conversely, every $n$-ary truth function $\phi:\{0,1\}^{n}\to\{0,1\}$ is the realization of some wff $p$. This is true because every $n$-ary operation on $\{0,1\}$ has a conjunctive normal form. Suppose $\phi$ is a function in variables $x_{1},\ldots,x_{n}$, with the form $\alpha_{1}\wedge\cdots\wedge\alpha_{m}$, where each $\alpha_{i}$ is the join of the variables in $x_{i}$. If $\alpha_{i}$ is a function in $x_{k_{1}},\ldots,x_{k_{m}}$ (each $k_{j}\in\{1,\ldots,n\}$), then let $p_{i}$ be the disjunction of propositional variables $v_{k_{1}},\ldots,v_{k_{m}}$. Then $\phi$ is the realization of wff $p:=p_{1}\wedge\cdots\wedge p_{n}$. Notice that we have omitted parenthesis, and $p_{1}\wedge\cdots\wedge p_{n}$ is an abbreviation of $(\cdots(p_{1}\wedge p_{2})\wedge\cdots)\wedge p_{n})$.

Since every wff, regardless of logical connectives, has a realization, what we have just proved in fact is the following:

###### Theorem 1.

$\{\neg,\vee,\wedge\}$

## References

• 1 H. Enderton: A Mathematical Introduction to Logic, Academic Press, San Diego (1972).
Title realization of a formula by a truth function RealizationOfAFormulaByATruthFunction 2013-03-22 18:52:53 2013-03-22 18:52:53 CWoo (3771) CWoo (3771) 8 CWoo (3771) Definition msc 03B05