5
$\begingroup$

How to prove that a set of logical connectives is functionally complete(incomplete)? For example, we are given this set:

$ \left\{\begin{matrix} f = (01101001) \\ g = (1010) \\ h = (01110110) \\ \end{matrix}\right. $

I would appreciate any examples, helpful information or links\books where this subject is accessibly explained.

$\endgroup$
6
  • $\begingroup$ Can you explain your coding for the functions above? $\endgroup$
    – copper.hat
    Jan 14, 2013 at 19:32
  • $\begingroup$ What does $"f=(01101001)"$ mean? Does that mean that $f$ is a three-place connective whose value is true when exactly one or three of its arguments is true? $\endgroup$
    – MJD
    Jan 14, 2013 at 19:34
  • $\begingroup$ These are vectors of boolean functions $\endgroup$
    – Max Malysh
    Jan 14, 2013 at 19:53
  • $\begingroup$ Probably relevant $\endgroup$
    – MJD
    Jan 14, 2013 at 19:53
  • $\begingroup$ It appears to me that they are vectors of bits, not vectors of boolean functions. Can you please explain more fully? $\endgroup$
    – MJD
    Jan 14, 2013 at 20:00

2 Answers 2

Reset to default
10
$\begingroup$

Proving that the set of connectives complete is typically done by showing that they can express each of a known complete set such as {AND,NOT} or {NOR} -- only occasionally will it be easier to provide a direct procedure for expressing an arbitrary truth table.

On the other hand, proving a set of connectives is incomplete is usually done by an argument along the lines of:

All expressible functions of $n$ variables have such-and-such-property, because the set of functions with this property is closed under each of the connectives and the function that just returns one of the variable also has this property. However, this-or-that particular function of $n$ variables doesn't have such-and-such property, and therefore it cannot be expressed, Q.E.D.

The proof will be more or less elegant according to how simple a "such-and-such" property you can get away with. At worst, such-and-such property will be something like "is one of these 27 particular functions", and it will be quite tedious (but not difficult) to verify that the 27 given functions are indeed closed under each connective.

A systematic procedure when a set of connectives are given is to start by working out which functions of a single variable can be produced. If one of the four possible functions can't be expressed, there's your answer. Then look for which functions of two variables can be expressed -- start with $\{0,1,x,y,\bar x,\bar y\}$ and try all combinations of those with the given connectives. Either you will quickly reach a dead end (which gives you a small "such-and-such" property for the incompletness proof), or you reach a sufficiently nontrivial combination of $x$ and $y$ that you can produce NOR by combining it with appropriate negations, and then you have a complete set of connectives.

In your particular case, we quickly notice that $g(x,y)$ is the negation of either $x$ or $y$ (depending on how your notation works), and $h(x,x,x)$ is the constant function $0$. This takes care of all one-argument functions.

Now what happens if you let one of the inputs to $h$ be one of these constants, and the other two be free variables?

$\endgroup$
3
  • $\begingroup$ Out of curiosity, do you know what the canonical complexity of the problem is? (I'm presuming a presentation where the input is a list of arrays representing the truth tables for some set of arbitrary boolean functions and the input size is naturally the total size of the arrays). Or would this be better-served as its own question? $\endgroup$
    – Steven Stadnicki
    Jan 14, 2013 at 20:34
  • 1
    $\begingroup$ Actually, nevermind - it looks as though by Post's work this is just a matter of checking the functions themselves for the critical properties (non-self-duality, etc.) and could be done in total time linear in the input... $\endgroup$
    – Steven Stadnicki
    Jan 14, 2013 at 20:36
  • $\begingroup$ @StevenStadnicki: I've edited to sketch a decision procedure which I think runs in $O(n^3)$ time. The biggest time sink is the phase that looks through all two-variable combinations -- if one of the given connectives has $k$ operands, there will be $6^k$ (or $8^k$ if XOR and NXOR have been produced) cases to check. But the length of the truth table in that case is $2^k$, so for $n=2^k$ the number of cases is at most $n^3$. Each of the $n^3$ cases take constant time because we're only looking at 2-variable functions. $\endgroup$
    – hmakholm left over Monica
    Jan 14, 2013 at 20:44
4
$\begingroup$

We use the connectives $\neg$. $\vee$, and $\wedge$ (a redundant set of connectives). We show that they form a functionally complete set. Take a truth-functional $\mathbf{F}$ of the propositions $P_1,\ldots,P_n$. Now, write down all assignments that make $\mathbf{F}$ true. We construct a sentence that says one of these assignments holds true. We do this by example. We have the variables $P_1$ ,$P_2$, $P_3$, $P_4$. The following assignments are mapped by $\mathbf{F}$ to $T$.

$$\begin{array}{|c|c|c|c|} \hline T & T & F & F \\ \hline T & F & T & F\\ \hline F & F & F & F\\ \hline \end{array}$$

We can translate this as a sentence that says the assignment of the first, second, or third line holds:

$$(P_1\wedge P_2\wedge \neg P_3\wedge\neg P_4)\vee(P_1\wedge \neg P_2\wedge P_3\wedge\neg P_4)\vee(\neg P_1\wedge \neg P_2\wedge \neg P_3\wedge\neg P_4).$$

It should be clear that every truth-table and hence every truthfunctional can be represented in this way (the disjunctive normal form).

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .