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?

  • $\begingroup$ In the end of your second bullet point, notice that $A'+1=1$. $\endgroup$ – amrsa Aug 18 '19 at 19:43
  • $\begingroup$ But then again, $AA'=0$, so $f(A,A,A)=A'$ just the same... $\endgroup$ – amrsa Aug 18 '19 at 20:06
  • $\begingroup$ yess, thanks for pointing out. That was a silly mistake. Fixed now. $\endgroup$ – anir Aug 18 '19 at 20:09

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


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.

| cite | improve this answer | |
  • $\begingroup$ well, it will take some time for me to fully grasp this answer. But a quick question: can we use this approach / program to find if any arbitrary functions like $f=A'+BC'$ is functionally complete? $\endgroup$ – anir Aug 19 '19 at 5:19
  • $\begingroup$ Yes, you just call complete on it, e.g. complete (3, \[a,b,c] -> not a || b && not c). Incidentally, it returns True for this as it should. $\endgroup$ – Derek Elkins left SE Aug 19 '19 at 5:58
  • $\begingroup$ am not great at abstract algebra & never coded in Haskell. I understand this. For e.g, $\{\rightarrow,\bot\}$ is functionally complete since this set is not subset of any of the five subsets stated by Post. So I got how to use Post's idea to determine functional completeness of set of connectives. However I did not get how we can determine if any given boolean function is functionally complete. Can you explain in words? Not able to understand it through your code & earlier comment. $\endgroup$ – anir Aug 21 '19 at 19:46
  • $\begingroup$ I am trying to find if I can quickly find whether given function is functionally complete by pen and paper. Putting all 0s and all 1s in boolean function to find whether its 0-preserving or 1-preserving is easy. Also checking whether its self dual is also easy. My doubt is can we check whether the given function is monotone and linear (wikipedia calls it "affine") easily by paper and pencil? Will it require me to go through function values for each permutation of input variables? $\endgroup$ – anir Aug 22 '19 at 9:04
  • $\begingroup$ Given an opaque Boolean function, there's not much that you can do. Given a symbolic expression you can do more, though I believe it's still hard in the worst-case. A formula is monotone iff it is in each variable, so you can check whether $\psi[\bot/A]$ implies $\psi[\top/A]$ for each variable $A$. You can recurse (i.e. consider $\psi[\bot/A][\bot/B]$ etc.) to simplify checking the implication at the cost of exponentially increasing the number of cases you need to consider. Similarly, for affine you want to check if $\psi[\bot/A]\equiv\psi[\top/A]$ or $\psi[\bot/A]\not\equiv\psi[\top/A]$. $\endgroup$ – Derek Elkins left SE Aug 22 '19 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.