My question is more from a digital logic background, and what is possible on computers, though I am curious what the answer is for real numbers.

Consider a function that performs a bitwise AND on two inputs, perhaps implemented as logic gates in hardware or a simple function in software:

$$and_2(x,y) = x \space \& \space y$$

This function takes two variables as input, and evaluates two variables to produce the output. Now consider a three variable function:

$$and3(x,y,z) = x \space \& \space y \space \& \space z$$

This function takes three input variables, but it doesn't necessarily evaluate three at a time. It could be rewritten to only evaluate two variables at a time (and iirc this is what most hardware design software does):

$$and_3(x,y,z) = (x \space \& \space y) \space \& \space z$$

which is the same as

$$and_3(x,y,z) = and_2(and_2(x,y), z)$$

If I had to guess, I would say that rewriting a multi-input function as a combination of two-input functions is possible for any associative binary operator (I think that's part of the definition...).

I thought perhaps the ternary operator (aka if/then/else, used in C) might be a three input function, but this is straightforward to re-write as a combination of two-input functions.

$$ternary(a,b,c) = a \space ? \space b : c$$

$$ternary(a,b,c) = (a \space \& \space b) \space | \space (\tilde a \space \& \space c)$$

$$ternary(a,b,c) = or_2(and_2(a,b),and_2(not(a),c))$$

To rephrase my original question: can all multi-input functions be re-written as a combination of two input functions (specifically for digital logic, and if you have the time, for any function in general)?

If I used any terminology wrong or missed some relevant tags, please correct, I'm not too familiar with the theory side of this.

These may be related but didn't answer my question:

Can any function be written as a composition of other functions?

Non-associative, non-commutative binary operation with a identity

Non-associative commutative binary operation


2 Answers 2


well, looks like I just wasn't searching for the correct terms

Are all n-ary operators simply compositions of binary operators?


It is not hard to see that any Boolean function $f:\{0,1\}^n \to \{0,1\}$ can be written using only the AND operator $\wedge$ and the NOT operator $\neg$: you get OR by De Morgan's law : $x \vee y = \neg(\neg x \wedge \neg y)$ and then you can simply write your function as a big disjunction of terms of the form $?x_1 \wedge ?x_2 \wedge \cdots \wedge ?x_n$, where each ? is either nothing or a $\neg$ (basically, you have one such term for every cell of the truth table which shows 1 : for example, $a \textbf{ xor } b = (\neg a \wedge b) \vee (a \wedge \neg b)$).

So you can get any Boolean function with only $\wedge$ and $\neg$, which in particular proves the result you wanted.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .