realization of a formula by a truth function

Fix a countable set V={v1,v2,} of propositional variables. Let p be a well-formed formula over V constructed by a set F of logical connectives. Let S:={vk1,,vkn} be the set of variables occurring in p (S is finite as p is a string of finite length). Fix the n-tuple 𝒗:=(vk1,,vkn). Every valuationPlanetmathPlanetmath ν on V, when restricted to S, determines an n-tupe of zeros and ones: ν(𝒗):=(ν(vk1),,ν(vkn)){0,1}n. For this ν(𝒗), we associate the interpretationMathworldPlanetmath ν¯(p){0,1}.

Two valuations on V determine the same a{0,1}n iff they agree on every vki. If we set ν1ν2 iff they determine the same a{0,1}n, then is an equivalence relationMathworldPlanetmath on the set of all valuations on V. As there are 2n elements in {0,1}n, there are 2n equivalence classesMathworldPlanetmath.

From the two paragraphs above, we see that there is a truth function ϕ:{0,1}n{0,1} such that


for any valuation ν on V. This functionMathworldPlanetmath 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 assumptionPlanetmathPlanetmath that every n-tuple (vk1,,vkn) has the property that k1<<kn. Let us write ϕp the realization of p.

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

  1. 1.

    pq (p semantically implies q, or p entails q) iff ϕpϕq;

  2. 2.

    pq iff ϕp=ϕq, where denotes semantical equivalence;

  3. 3.

    p is a tautologyMathworldPlanetmath iff ϕp=1, the constant functionMathworldPlanetmath whose value is 1{0,1}.

If F={¬,,}, then every wff p over V corresponds to a realization [p] that “looks” exactly likes p. We do this by inductionMathworldPlanetmath:

  • if p is a propositional variable vi, let [vi] be the identity functionMathworldPlanetmath on {0,1};

  • if p has the form ¬q, define [p]:=¬[q];

  • if p has the form qr, define [p]:=[q][r];

  • if p has the form qr, define [p]:=[q][r];

where the ¬,, and on the right hand side of the definitions are the Boolean complementation, join and meet operationsMathworldPlanetmath on the Boolean algebraMathworldPlanetmath {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 polynomialPlanetmathPlanetmath).

Conversely, every n-ary truth function ϕ:{0,1}n{0,1} is the realization of some wff p. This is true because every n-ary operation on {0,1} has a conjunctive normal formMathworldPlanetmath. Suppose ϕ is a function in variables x1,,xn, with the form α1αm, where each αi is the join of the variables in xi. If αi is a function in xk1,,xkm (each kj{1,,n}), then let pi be the disjunctionMathworldPlanetmath of propositional variables vk1,,vkm. Then ϕ is the realization of wff p:=p1pn. Notice that we have omitted parenthesis, and p1pn is an abbreviation of ((p1p2))pn).

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

Theorem 1.

{¬,,} is functionally complete.


  • 1 H. Enderton: A Mathematical Introduction to Logic, Academic Press, San Diego (1972).
Title realization of a formulaMathworldPlanetmathPlanetmath 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