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 well-formed 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 $𝒗:=(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 (𝒗):=(\nu (v_{k_1}),\mathrm{\dots },\nu (v_{k_n}))\in {\{0,1\}}^n$. For this $\nu (𝒗)$, 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 (𝒗))=\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 $𝒗$. 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.

Title	realization of a formula by a truth function
Canonical name	RealizationOfAFormulaByATruthFunction
Date of creation	2013-03-22 18:52:53
Last modified on	2013-03-22 18:52:53
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	8
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03B05