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


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

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

| cite | improve this answer | |

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.

| cite | improve this answer | |

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.