# Functionally Complete 3-Input Logical Connectives

There are 16 2-input logical connectives in 2-valued logic. Those include AND, OR, XOR, NAND, NOR, etc. Most of them have common names, but some don't. In this set, only NAND and NOR are "functionally complete", meaning that any connective can be represented as a combination of NANDs or a combination of NORs. We can work that out essentially with brute force because the number of expressions we need to iterate through before producing all connectives is small. However, if we consider connectives with more inputs, the number of expressions we need to search quickly becomes astronomical.

I created a new graph-based method for finding functionally complete connectives and for finding the minimum expressions to produce them (with various definitions of "minimum"). There have been existing methods for listing the functionally complete connectives, but not for finding the minimum expressions.

The image shows a few of the minimal expressions (by leaf count) to express some 3-input connectives in terms of the 3-input connective 27 (*f(p,q,r)* has a truth table coresponding to 27 in binary).

(Due to its computational complexity, the main program is written in parallelized C++. The working notebook here contains the code to parse and analyze the output of the C++ program.)