10
\$\begingroup\$

A complete Boolean function is a function such that, an amount of them can be used to express any Boolean function. For example, NAND \$\left[\begin{matrix}\text{input1}&0&0&1&1\\\text{input2}&0&1&0&1\\\text{output}&1&1&1&0\end{matrix}\right]\$ is complete. Inputs may be reused any number of times, and the functions can be composed arbitrarily.


Some functions, like IMPLY \$\left[\begin{matrix}\text{input1}&0&0&1&1\\\text{input2}&0&1&0&1\\\text{output}&1&1&0&1\end{matrix}\right]\$, are not individually complete. We can prove this simply by noting that there is no way to output 0 if all inputs are 1. However, if we are allowed to use the constant functions (always 0 and always 1, aka false and true), then the set of functions becomes complete.

Given a Boolean Function with input, check whether it's complete, not complete, or only complete if constants are allowed.

Flexible IO, shortest code wins.

Test cases

(2-input)

a  0 0 1 1
b  0 1 0 1
#1 1 1 1 0 Complete
#2 0 1 1 0 Not complete
#3 0 0 1 0 Need Constant

(3-input)

a  0 0 0 0 1 1 1 1
b  0 0 1 1 0 0 1 1
c  0 1 0 1 0 1 0 1
#1 0 0 0 0 0 0 0 1 Not complete
#2 1 0 0 0 0 0 0 0 Complete
#3 1 1 1 1 0 0 0 0 Not complete
#4 1 1 0 1 0 0 1 0 Complete
#5 0 0 1 1 0 1 0 1 Need constant
\$\endgroup\$
3
  • 5
    \$\begingroup\$ Please make the challenge-description more self-contained. It should say how the functions can be composed, whether inputs can be used multiple times, and what constants being allowed means. \$\endgroup\$
    – xnor
    Jul 3, 2021 at 5:32
  • \$\begingroup\$ Proof of Post's lattice: Use the non-monotonic function to get a 0 and a 1(without order), use the non-selfdual one to get 0 and 1 (with order), use the non-affine to get one of {AND,OR,IMP,NIMP,NAND,NOR} and non-monotone as NOT, enough to solve everything. monotonic means no NOT, affine mean pure XOR, self-dual mean can't tell 0 from 1, truth-preserving blocks from getting a false \$\endgroup\$
    – l4m2
    Jul 3, 2021 at 7:34
  • 9
    \$\begingroup\$ Dude, you really need to start sorting out the issues with your past challenges before posting any new ones so you can learn from your mistakes and make your future challenges better. \$\endgroup\$
    – Shaggy
    Jul 3, 2021 at 23:49

2 Answers 2

8
\$\begingroup\$

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))))}")
\$\endgroup\$
8
  • \$\begingroup\$ How does Outputs are allowed to be reused any number of times help? We don't mind amount of such function used \$\endgroup\$
    – l4m2
    Jul 3, 2021 at 7:44
  • \$\begingroup\$ return-x|-y|z works with 0, -1 and 1 as output values. \$\endgroup\$
    – ovs
    Jul 3, 2021 at 8:16
  • 1
    \$\begingroup\$ @l4m2 This discussion should belong on the top post, but I was clearing up one of xnor's questions. It should say inputs may be used multiple times, and I've edited that to clarify. \$\endgroup\$ Jul 3, 2021 at 8:21
  • \$\begingroup\$ @ovs Nice find; added. \$\endgroup\$ Jul 3, 2021 at 8:26
  • 1
    \$\begingroup\$ @ovs Interesting that min accepts more than one iterable. \$\endgroup\$ Jul 5, 2021 at 2:34
1
\$\begingroup\$

Charcoal, 60 bytes

≔E↨⊖Lθ²X²κη✳∧⊙⮌θ⁼§θκι›§θ⁰§θ±¹›⊙η⊙θ‹§θ|ιμλ⬤ηΦ²⬤θ∨&ιξ⁼λ⁼§θ|ιξν

Try it online! Link is to verbose version of code. Can take input as a binary string or an array and outputs / for complete, - if constants are needed, nothing if incomplete. Explanation: Port of @fireflame241's solution.

≔E↨⊖Lθ²X²κη

Get the powers of 2 up to the length of the string.

✳∧⊙⮌θ⁼§θκι›§θ⁰§θ±¹

If any function value matches that of the reverse of the string (meaning that the function is not self-dual), and the first value is greater than the last value (meaning that the function is neither true- or false-preserving), then prepare to print a / rather than a -.

›⊙η⊙θ‹§θ|ιμλ⬤ηΦ²⬤θ∨&ιξ⁼λ⁼§θ|ιξν

Don't print anything if the function is monotonic or affine. The function is not monotonic if there exists a set of inputs such that changing one of the inputs to 1 changes the value from 1 to 0. (Inputs of 1 are also checked, but changing them to 1 obviously has no effect on the value.) The function is affine if for all inputs the values where that input is 1 are either equal to or the exact complement of the values where that input is 0 all at the same time. This was the part that was hardest to golf in Charcoal as it doesn't have the bitwise XOR function, nor does it have a simple way of comparing all the values in an array with each other.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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