# Boolean Functions

Say you have N input Boolean function, let's use a parity tree for the example. The function outputs a one or a zero depending on the values of the N inputs. Are the N inputs considered the preimage of the function?

• @kelalaka; Thank you for replying, does that mean the answer to my question is "yes" , or is the answer "no" ? ;-) – William Hird Dec 24 '18 at 20:02

## 2 Answers

Functions don't have preimages; outputs do. Your Boolean function has domain the set of $$2^N$$ binary $$N$$-tuples, that is, the set $$\big\{(000\ldots 00),~ (000\ldots 01),~ (000\ldots 10),~ (000\ldots 11),~ \cdots , (111\ldots 10),~ (111\ldots 11)\big\}$$ and range (a.k.a. the set of outputs) the set $$\{0, 1\}$$. The outputs have preimages which are defined as the set of all inputs that are mapped onto that particular output by the specified function; in this instance the Exclusive-OR of the $$N$$ bits. For example, with $$N=3$$,

• the preimage of $$0$$ is the set $$\big\{(000),~ (011), ~ (101),~ (110)\big\}$$
• the preimage of $$1$$ is the set $$\big\{(001),~ (010), ~ (100),~ (111)\big\}$$

Notice that the preimages are a partition of the domain; every element of the domain is necessarily a member of one (and only one) of the preimages.

In short, the answer to your question

Are the N inputs considered the preimage of the function?

is No, they are not.

An $$n(=N)$$ input Boolean function $$f$$ has $$2^n$$ input space, and output 0 or 1. Formally;

$$f:\{0,1\}^n \mapsto \{0,1\}$$

The pre-image of $$\{0,1\}$$ under $$f$$ is the all input space $$\{0,1\}^n$$.

The pre-image of $$0$$ under $$f$$ is the set $$f^{-1}=\{ x \in \{0,1\}^n |\; f(x) = 0\}$$

and the pre-image of $$1$$ under $$f$$ is the set $$f^{-1}= \{ x \in \{0,1\}^n |\; f(x) = 1\}$$

And;

$$f^{-1} \cup f^{-1} = \{0,1\}^n$$

Don't confuse pre-image with the inverse function.

• I'm not a computer scientist. All your mathematical formulas make me dizzy! I'm looking for a "Boolean" answer to my question: Yes or NO. Merry Christmas by the way :-) – William Hird Dec 24 '18 at 20:41
• No, don't delete anything ! You can show future generations how really smart people cant answer simple questions sometimes ! – William Hird Dec 24 '18 at 20:49
• A function must map all of its input space into the domain. But the function doesn't have to be onto. The pre-image is in your sense is the input space. – kelalaka Dec 24 '18 at 21:06