realization of a formula by a truth function
Fix a countable set $V=\{{v}_{1},{v}_{2},\mathrm{\dots}\}$ of propositional variables. Let $p$ be a wellformed formula over $V$ constructed by a set $F$ of logical connectives. Let $S:=\{{v}_{{k}_{1}},\mathrm{\dots},{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 $\bm{v}:=({v}_{{k}_{1}},\mathrm{\dots},{v}_{{k}_{n}})$. Every valuation^{} $\nu $ on $V$, when restricted to $S$, determines an $n$tupe of zeros and ones: $\nu (\bm{v}):=(\nu ({v}_{{k}_{1}}),\mathrm{\dots},\nu ({v}_{{k}_{n}}))\in {\{0,1\}}^{n}$. For this $\nu (\bm{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 $\varphi :{\{0,1\}}^{n}\to \{0,1\}$ such that
$$\varphi (\nu (\bm{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 $\bm{v}$. From now only, we make the assumption^{} that every $n$tuple $({v}_{{k}_{1}},\mathrm{\dots},{v}_{{k}_{n}})$ has the property that $$. Let us write ${\varphi}_{p}$ the realization of $p$.
Realizations of wffs are closely related to semantical implications^{} and equivalences:

1.
$p\vDash q$ ($p$ semantically implies $q$, or $p$ entails $q$) iff ${\varphi}_{p}\le {\varphi}_{q}$;

2.
$p\equiv q$ iff ${\varphi}_{p}={\varphi}_{q}$, where $\equiv $ denotes semantical equivalence;

3.
$p$ is a tautology^{} iff ${\varphi}_{p}=1$, the constant function^{} whose value is $1\in \{0,1\}$.
If $F=\{\mathrm{\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 $\mathrm{\neg}q$, define $[p]:=\mathrm{\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 $\mathrm{\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 $\varphi :{\{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 $\varphi $ is a function in variables ${x}_{1},\mathrm{\dots},{x}_{n}$, with the form ${\alpha}_{1}\wedge \mathrm{\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}},\mathrm{\dots},{x}_{{k}_{m}}$ (each ${k}_{j}\in \{1,\mathrm{\dots},n\}$), then let ${p}_{i}$ be the disjunction^{} of propositional variables ${v}_{{k}_{1}},\mathrm{\dots},{v}_{{k}_{m}}$. Then $\varphi $ is the realization of wff $p:={p}_{1}\wedge \mathrm{\cdots}\wedge {p}_{n}$. Notice that we have omitted parenthesis, and ${p}_{1}\wedge \mathrm{\cdots}\wedge {p}_{n}$ is an abbreviation of $(\mathrm{\cdots}({p}_{1}\wedge {p}_{2})\wedge \mathrm{\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.
$\{\mathrm{\neg},\vee ,\wedge \}$ is functionally complete.
References
 1 H. Enderton: A Mathematical Introduction to Logic, Academic Press, San Diego (1972).
Title  realization of a formula^{} by a truth function 

Canonical name  RealizationOfAFormulaByATruthFunction 
Date of creation  20130322 18:52:53 
Last modified on  20130322 18:52:53 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  8 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03B05 