Can you create a "lerp" function from simpler logic functions?

147 Views Asked by At

In continuous logic with variables in the range 0..1 we can create

$$NOT(x) = 1-x$$

$$AND(x,y)=xy$$

$$OR(x,y)=x+y-xy$$

$$MAX(x,y)$$

$$MIN(x,y)$$

but the function $ADD(x,y)$ is not allowed since the output could be a number greater than 1.

What about the $LERP(x,y,t)$ function defined by:

$$LERP(x,y,t) = xt+y(1-t)$$

This is also guaranteed to be in the correct range. Can this be formed from simpler two valued functions in the same way that $OR(x,y)=NOT(AND(NOT(x),NOT(y))$ ? You are only allowed to use two valued functions where the input and outputs are in the range 0..1.

Another function is

$$S(x) = x^2(3-2x)$$

This also gives a function in the correct range. Can it be formed from simpler functions in the same way that $OR(AND(x,x),0.5) = (x^2 + 1)/2$ for example?

1

There are 1 best solutions below

0
On

It is not even possible to do this if we fix $t=1/2$. That is, $f(x,y)=(x+y)/2$ cannot be constructed using these functions.

In particular, suppose we first ignore the $\min$ and $\max$ functions. Then, it is easy to see that every composition of these functions will be a polynomial $P(x,y)$. Define the degree $\deg(P)$ of a polynomial to be the highest $a+b$ such that $x^ay^b$ appears in the polynomial, or $-\infty$ for the zero polynomial. Then, observe that: $$\deg(PQ)=\deg(P)+\deg(Q)$$ $$\deg(P)>\deg(Q)\Longrightarrow \deg(P+Q)=\deg(P).$$ Using these, we obviously have that: $$\deg(AND(P,Q))=\deg(P)+\deg(Q)$$ Then, we note that if $P$ and $Q$ are not constants (i.e. have positive degree), we easily get: $$\deg(OR(P,Q))=\deg(P)+\deg(Q)$$ and indeed, this holds as long as neither $P$ nor $Q$ is $1$. Similarly, $\deg(NOT(P))=\deg(P)$ so long as $P$ is not $1$.

If we demand that we write an expression such that no sub-expression may be simplified to a constant, ours rules for $NOT$, $AND$, and $OR$ always hold, and we find that $AND$ and $OR$ may only appear if one of their arguments is a constant, as otherwise the degree of the whole expression would be too high. However, if we let $AND_c(x)=AND(x,c)$ and define $OR_c$ similarly for constant $c$, we see that we are only permitted to apply the functions $NOT$, $AND_c$ and $OR_c$, but these are all unary, so we can't hope to make a binary function depending on both arguments from them.

Adding $MIN$ and $MAX$ does not particularly help the case; in particular, if we have $MIN(A,B)$ for two continuous functions $A$ and $B$, then $MIN(A,B)=A$ holds on some closed set and $MIN(A,B)=B$ holds on some other closed set, such that the whole space is the union of the two. In particular, we can continue splitting the expression into finitely many cases where each $MIN$ or $MAX$ is either constantly its first or second argument on each of the cases - and then, in each of these cases, the expression coincides with one consisting only of $NOT$, $AND$, and $OR$. One may prove that one of these cases must hold on an open set, and then the degree is again well-defined on the open set, and our previous argument then holds.