Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
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
up vote 0 down vote accepted

You didn't say anything about what form you have these functions in, so I'll assume they're just black boxes where you can put argument values in and get function values out. Obviously if you have the functions in some other form you might be able to use that form but then we'd need to know something about that form.

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)\;.$$

share|cite|improve this answer
Thank you, it makes a lot of sense. Any idea - if possible - how I would find out whether factorization is possible without trying all possible values of the input arguments? As I wrote, input arguments can be anything, and they can be used in any way inside the function, therefore trying to combine all their values is just not feasible. – bibendus Nov 5 '11 at 15:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.