# Decompose boolean function of multiple variables into multiple functions of one variable

say I have a function $$f(x, y) : bool$$ of two variables x and y - whose type can be anything - returning either true or false. I would like to create two functions of one variable each $g(x)$, $h(y)$ so that $$f(x, y) = g(x)\ AND\ h(y)$$

In other words I would like to retrieve two functions of one variable which ANDed together give the same result as the original function. I realize there doesn't always exist such functions, for example when part of the original function is expressed in terms of both variables (i.e. $f(x,y)=x>y$). In other cases instead they exist, the straightforward case being $f(x,y)=x\ AND\ y$ where $g(x)=x$ and $h(y)=y$.

How do I get those two functions?

Thanks

-
I think you forgot to ask a question. – joriki Nov 5 '11 at 12:54
I thought it was intuitive, I'd need to discover g and h. I have updated the question, btw. – bibendus Nov 5 '11 at 12:58

If you don't know whether $f(x,y)$ factors into $g(x)\land h(y)$, you'd have to try out all possible pairs of arguments to ensure that this is the case. However, if you do know that $f$ factors, you can factorize it like this: Find some pair $x_0,y_0$ with $f(x_0,y_0)=\mathrm{true}$. Then $g(x_0)$ and $h(y_0)$ are both true, so $g(x)=g(x)\land h(y_0)=f(x,y_0)$ and $h(y)=g(x_0)\land h(y)=f(x_0,y)$, that is,
$$f(x,y)=f(x,y_0)\land f(x_0,y)\;.$$