# Formalising a structure and determining functional completeness

Background

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?

Goal

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?

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

• $\{\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.
• 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.