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?

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

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}[0]=\{ x \in \{0,1\}^n |\; f(x) = 0\}$$

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


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

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

  • $\begingroup$ 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 :-) $\endgroup$ – William Hird Dec 24 '18 at 20:41
  • $\begingroup$ No, don't delete anything ! You can show future generations how really smart people cant answer simple questions sometimes ! $\endgroup$ – William Hird Dec 24 '18 at 20:49
  • $\begingroup$ 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. $\endgroup$ – kelalaka Dec 24 '18 at 21:06

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.