$\begingroup$

What is a non-degenerate function? Can this have different meanings depending on some context?

For reference, this came up in this question:
Number of 'unique' one bit binary functions with N-bit inputs
And two different sequences in oeis claim to be "Number of nondegenerate Boolean functions of n variables."

$\endgroup$ 2

2 Answers

$\begingroup$

You described nondegenerate for boolean functions via

Now potentially reduce this set by restricting to only considering functions which have a dependence on every input bit (ie. there is no bit such that inverting the bit on the input never effects the output: there is no bit such that f(x XOR bit)=f(x) for all x).

This description makes a function degenerate if it ignores one (or more) bits of its input. An abstraction of this is "a thing is degenerate if its description makes it appear more complicated than it actually is".

qwr gives the related examples of a rectangle that "ignores" one of its sides, so is actually a simpler object (a triangle) and a circle that "ignores" its radius so is actually a simpler object (a point).

$\endgroup$ 2 $\begingroup$

Degenerate has many different meanings, but it seems like from your example you were describing if a bit in a function has no effect on the output if it's 0 or 1 (only the other bits matter).

Degenerate means some kind of element of a class belongs to a simpler class. In geometry, if a rectangle or triangle has side length 0, then it's degenerate. Similarly, if a circle has radius 0 it's degenerate. In graph theory, a graph is degenerate if every vertex has at most d neighbors later than it in ordering, something like that here.

$\endgroup$ 1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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