Python 2, 152 150 147 136 bytes
def c(a):E=enumerate;x,y,z=map(min,*[[a[i|c]>=v,c&c-1>=w^a[0]^a[i^c]^v,v^a[~i]>=a[0]-a[-1]]for i,v in E(a)for c,w in E(a)]);print-x|-y|z
Try it online! (TIO link outputs through function return instead of stdout)
-15 bytes thanks to @ovs
Takes input as a list of boolean outputs in the same order as the question, so (for example) a two-argument function is represented by the four-element list [f(0,0),f(1,0),f(0,1),f(1,1)]. In general, for an input list a of length 2^n, we must have a[i] = f(i&1, i&2, ..., i&(1<<n-1)).
Outputs by printing to STDOUT according to the following table:
COMPLETE = -1
NOT_COMPLETE = 1
NEEDS_CONSTANT = -2
Theory
This uses Post's Characterization of Functional Completeness, which describes five terms that can describe a boolean function: monotonic, affine, self-dual, truth-preserving, and falsity-preserving. For a different explanation of what they mean, read the comments in class Char in the ungolfed code below.
These five terms completely characterize the answer, as proven by Emil Post. If a term describes every member of a set of boolean expressions, then that set of boolean functions is not functionally complete.
For example, if every function is truth-preserving, then plugging in all inputs as 1 (true) will always return 1 (true), no matter how the functions are arranged. This means that the functions cannot be arranged to take all inputs as 1 and return 0, so that set of functions is not functionally complete. Similar arguments work for the other four terms as well.
The converse (if none of the five terms describe every member of a set of functions, then that set of functions is functionally complete) is harder to prove in the general case, so I'm relying on Emil Post's proof.
Application
To answer the challenge, we calculate which of the terms describe the given function.
- If none of the terms describe the given function, then it is functionally complete. Return
COMPLETE.
- Otherwise, if the given function is either monotonic or affine, then adding the two constant functions (
true and false) would cause the new set of functions to still be monotonic or affine (because true and false are both monotonic and affine). Return NOT_COMPLETE
- Otherwise, return
NEEDS_CONSTANT. Neither of the two constant functions are self-dual, so adding either one would cause the set of functions to not all be self-dual. Similarly, the true constant is not falsity-preserving, and the false constant is not truth-preserving, so adding both handles the case where the given function is truth-preserving, falsity-preserving, or both.
Ungolfed code
from enum import Enum
# BEGIN GOLF
class Completeness(Enum):
COMPLETE = "COMPLETE"
NOT_COMPLETE = "NOT_COMPLETE"
NEEDS_CONSTANT = "NEEDS_CONSTANT"
class Char(Enum):
# changing any 0 to a 1 does not cause the result to change from 1 to 0
MONOTONIC = "MONOTONIC"
# every input variable either always or never affects the truth value
# i.e. equivalent to the logical XOR or XNOR of the inputs
AFFINE = "AFFINE"
# flipping all the 0s to 1s and 1s to 0s flips the result between a 0 and 1
SELF_DUAL = "SELF_DUAL"
# if all inputs are 1, then the output is 1
TRUTH_PRESERVING = "TRUTH_PRESERVING"
# if all inputs are 0, then the output is 0
FALSITY_PRESERVING = "FALSITY_PRESERVING"
def is_power_of_two(n):
return n & n - 1 == 0
def characterize(output):
chars = set()
u = len(output)
mask = u - 1
powers_of_two = list(filter(is_power_of_two, range(u)))
if all(output[i | c] >= output[i] for i in range(u) for c in powers_of_two):
chars.add(Char.MONOTONIC)
if all(
all(output[i ^ c] != output[i] for i in range(u))
or all(output[i ^ c] == output[i] for i in range(u))
for c in powers_of_two
):
chars.add(Char.AFFINE)
if all(output[i] != output[mask & (~i)] for i in range(u)):
chars.add(Char.SELF_DUAL)
if output[-1] == 1:
chars.add(Char.TRUTH_PRESERVING)
if output[0] == 0:
chars.add(Char.FALSITY_PRESERVING)
return chars
def completeness(output):
chars = characterize(output)
if len(chars) == 0:
return Completeness.COMPLETE
elif Char.MONOTONIC in chars or Char.AFFINE in chars:
return Completeness.NOT_COMPLETE
else:
return Completeness.NEEDS_CONSTANT
# END GOLF
tests = [
# (none)
([1, 1, 1, 0], Completeness.COMPLETE),
# affine, falsity-preserving
([0, 1, 1, 0], Completeness.NOT_COMPLETE),
# falsity-preserving
([0, 0, 1, 0], Completeness.NEEDS_CONSTANT),
# monotonic, truth-preserving
([0, 0, 0, 0, 0, 0, 0, 1], Completeness.NOT_COMPLETE),
# (none)
([1, 0, 0, 0, 0, 0, 0, 0], Completeness.COMPLETE),
# self-dual, affine
([1, 1, 1, 1, 0, 0, 0, 0], Completeness.NOT_COMPLETE),
# (none)
([1, 1, 0, 1, 0, 0, 1, 0], Completeness.COMPLETE),
# falsity-preserving, truth-preserving
([0, 0, 1, 1, 0, 1, 0, 1], Completeness.NEEDS_CONSTANT),
]
for output, expected in tests:
got = completeness(output)
if got == expected:
print("PASS")
else:
print(f"FAIL on {output}. Expected {expected} but got {got}")
print(f" Chars: {', '.join(map(str,list(characterize(output))))}")
