# Minimal number of binary operators to generate an arbitrary truth table

Considering: $$G(X,A,B)=(X∧A)∨(¬X∧B)$$

For all boolean unary operator $$F(X)$$, there exists a unique pair of $$A,B$$ so that $$G(X,A,B)=F(X)$$ for all $$X$$. That is, by assigning correct $$A,B$$, function $$G$$ can generate any unary boolean operator. There exists some other constructions of $$G$$ with less binary operators ($$⊕$$ means xor): $$G(X,A,B)=(X∧A)⊕B$$ $$G(X,A,B)=(X∨A)⊕B$$ Now consider an arbitrary binary operator $$F(X,Y)$$ and function $$G(X,Y,A,B,C,D)$$, a trivial construction might be: $$G(X,Y,A,B,C,D)=(X∧Y∧A)∨(¬X∧Y∧B)∨(X∧¬Y∧C)∨(¬X∧¬Y∧D)$$ Again, by changing value of $$A,B,C,D$$, function $$G$$ can generate all possible binary operator $$F$$. But this construction is computationally expensive.

My question is:

• Is there a construction of $$G(X,Y,A,B,C,D)$$ requiring only $$5$$ binary operators to connect these operands? If not, what is the min number of binary operators required? (all 16 binary operators are useable)
• For $$F(X_1,X_2 ... X_i)$$, $$G(X_1 ... X_i,A_1 ... A_{2^i})$$, how to find a construction of $$G$$ with min number of binary operators?
• "Mock" means to make fun of. I suspect you meant to write "make'. Please edit your question to make it make sense. Commented Jul 21 at 21:10
• @Rob Arthan Indeed verb "to mock" has to be repaced by another one ; Instead of "to make", I would advise "to retrieve" Commented Jul 22 at 5:34
• Ok I will change it to "retrieve". Sorry for the confusion. Commented Jul 22 at 7:16
• "Retrieve" sounds weird in this context ("retrieve" means to find something you have lost): if you don't like "make", I'd say "generate". More importantly, what binary operators are you allowing? You clearly need to take into account all 6 variables, so it looks highly unlikely that 5 binary operators would do as each variable would have to appear exactly once. Commented Jul 22 at 19:48
• Sure I'll change it to "generate". I am allowing all 16 binary operators. It will be better if the operators are commutative. Commented Jul 22 at 20:50