You are here
Homerealization of a formula by a truth function
Primary tabs
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 wellformed 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<k_{n}$. Let us write $\phi_{p}$ the realization of $p$.
Realizations of wffs are closely related to semantical implications and equivalences:
1. 2. $p\equiv q$ iff $\phi_{p}=\phi_{q}$, where $\equiv$ denotes semantical equivalence;
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\}$ is functionally complete.
References
 1 H. Enderton: A Mathematical Introduction to Logic, Academic Press, San Diego (1972).
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