How to determine if given function is functionally complete

Question

Given any random boolean function, is their any step wise procedure to find out whether it is functionally complete?

The simplest approach I came across is this:

1. We need to find whether given boolean function can derive operators either in the set $\{\neg,\vee\}$ or in the set $\{\neg,\wedge\}$.

2. Finding whether given boolean functon can derive $\neg$ is quite easy. It involves putting single variable for all input variables and checking whether it results in $\neg$.
   For example, if $f(A,B,C)=A'+BC'$.
   Then $f(A,A,A)=A'+AA'=A'+0=A'$

3. However I dont know how can we systematically determine if given function can emulate AND ($\vee$) or OR ($\wedge$) operators. Is their any concrete procedure to determine the same or we have to take help of intuition?

4. Or is their any known fundamentally different approach apart from the one specified in steps 1 to 3?

Answer 1

The section you link to tells you. All the properties that identify the five clones of Post's lattice are mechanically checkable. You can simply provide all possible inputs to your operator (i.e. build the truth table) and check that all of the properties do not hold, in which case the operator is functionally complete. You can, of course, be a lot smarter than that.

It is not hard to write a program that checks each of these properties. Indeed, here's a Haskell program that does just that though it could definitely be made smarter.

import Control.Monad ( filterM, replicateM )
import Data.Foldable ( all, and, mapM_ )
import Data.List ( replicate, transpose )

inserts :: a -> [a] -> [[a]]
inserts x [] = [[x]]
inserts x (y:ys) = (x:y:ys):map (y:) (inserts x ys)

type B = [Bool]

type BF = (Int, B -> Bool)

b  :: Int -> [B]
b n = replicateM n [False, True]

truthPreserving :: BF -> Bool
truthPreserving (n, f) = f (replicate n True)

falsePreserving :: BF -> Bool
falsePreserving (n, f) = not (f (replicate n False))

selfDual :: BF -> Bool
selfDual (n, f) = all (\bs -> not (f bs) == f (map not bs)) (b n)

monotonic :: BF -> Bool
monotonic (n, f) = all (\(bs, cs) -> f bs <= f cs) [(bs, cs) | bs <- b n, cs <- b n, bs `leq` cs]
    where bs `leq` bs' = and (zipWith (<=) bs bs')

affine :: BF -> Bool
affine (n, f) = any allEqual $ transpose $ do
    bs <- b (n-1)
    let trueArg = map f (inserts True bs)
        falseArg = map f (inserts False bs)
    return (zipWith (==) trueArg falseArg)
  where allEqual (b:bs) = all (b==) bs

complete :: BF -> Bool
complete bf = not (truthPreserving bf 
                || falsePreserving bf 
                || selfDual bf 
                || monotonic bf 
                || affine bf)

truthTableToFunction :: Int -> [B] -> BF
truthTableToFunction n tt = (n, \bs -> bs `elem` tt)

main = do
    let n = 2
    let allTruthTables = filterM (\_ -> [False, True]) (b n)
    mapM_ print $ filter (\tt -> complete (truthTableToFunction n tt)) allTruthTables

The output with $n=2$ is

[[False,False]]
[[False,False],[False,True],[True,False]]

which indicates that there are two complete binary functions. One that is true only on input (False, False) i.e. the NOR function, and one that is false only on input (True, True), i.e. the NAND function.