Suppose we have switches and [boxes with light bulb]. We can put both switches or boxes inside a box. Depending on the type of box it is, we need a certain number of switches or boxes inside to be "on" in order to turn the box itself "on". So this definition of "on" is recursive. At first, these boxes are modelled after logical connectives:

  • In an $\land$-box, everything inside must be turned on to also turn on the box itself.
  • In an $\lor$-box, only at least 1 thing inside have to be turned on.
  • In an unary $\lnot$-box, the thing inside have to be off for the box to be on.

As far as I understand, these will give me functionally complete set of connectives. Now suppose I also want to model a radio-box in which the box will be on iff exactly 1 thing inside it is on.
For a radio-box of size 2, I get:

\begin{array}{cc|c|c} A & B & \text{Exactly 1} & \lnot(A\iff B)\\ \hline T & T & F & F\\ T & F & T & T\\ F & T & T & T\\ F & F & F & F \end{array}

For size 3 or more, there's a simple, but lengthy pattern of writing the disjunction of the conjunction of the negation of all variables except one where in each disjunct, the one non-negated variable ranges from the first variable to the last (which is equivalent to the negation of biconditional I got for size 2):
$(A_1\land \lnot A_2 \land \ldots \land \lnot A_n)\lor (\lnot A_1 \land A_2 \land \lnot A_3 \land \ldots \land \lnot A_n) \lor \ldots \lor (\lnot A_1 \land \lnot A_2 \land \ldots \land \lnot A_{n-1} \land A_n)$

After a bit of research, I found out that the problem of coming up with a (simple) expression that gives the desired truth table is used in designing circuits and that this can always be done with $\land$, $\lor$, and $\lnot$.1 Am I right to say that this is also what it means for a set of connectives to be functionally complete?


These are all fine and dandy, but in the end, I want to keep things simple and use only 1 type of box: an $[m,M]$-box that will be on iff $n \in [m,M]$ where $n$ is the number of things inside that is on.

The goal is so that we can easily model boxes that require a specific number of minimum and maximum number of things that are on without having to come up with long, convoluted solution with a lot of nested boxes.
My question is: Will the $[m,M]$-box be expressive enough?

Thoughts and Attempts
First, I consider if it's possible to express the other logical connectives in terms of this new operation.
Let $s$ be the number of items (size) in the box, and denote $[A_1, A_2, \ldots , A_s]_{m,M}$ for the $[m,M]$-box of size $s$. Then I can model other connectives as follow:

\begin{array}{cc|cc|cc|cc} A & B & A\land B & [A,B]_{2,2} & A\lor B & [A,B]_{1,2} & \lnot A & [A]_{0,0}\\ \hline T & T & T & T & T & T & F & F \\ T & F & F & F & T & T & F & F \\ F & T & F & F & T & T & T & T \\ F & F & F & F & F & F & T & T \\ \end{array}

Then, we can get everything $\land$, $\lor$, and $\lnot$ can get, just using different formulation that we prefer. Is this correct?

1. Foundation of Computer Science by Aho and Ullman, Section 12.5


1 Answer 1


All your claims seem correct to me.

  • $\{\wedge, \vee, \neg\}$ is a truth-functionally complete set of connectives. By the way, $\{\wedge, \neg\}$ and $\{\vee, \neg\}$ are also both truth-functionally complete.
  • Such completeness means that any truth table (or, to be a bit more precise, any course of truth values) can be generated using only these connectives.
  • You also gave the reason why $[m,M]$ boxes are all you need. It's important, of course, that you can nest these boxes, which you indeed allow.

Be it noted, you could even live with a $[0,0]$-type box only. This is because $[A,B]_{0,0}$ is on iff neither $A$ nor $B$ are on, so $[A,B]_{0,0} \Leftrightarrow \neg (A \vee B) \Leftrightarrow A \downarrow B$, where $\downarrow$ is the Peirce Arrow. And the Peirce Arrow is functionally complete by itself. However, you will need many nestings if you do it like this.

  • $\begingroup$ Thank you for such a clear and concise answer! I've heard of the sort of connectives like the Peirce Arrow you mentioned before. I think the one I came across was Sheffer's Stroke. It looks like it will require more nestings as well. So in effect, I thought I would need to generalise the connectives rather than to simplify them to reduce the length of expressions. $\endgroup$ Oct 12, 2015 at 14:45

You must log in to answer this question.

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