0
$\begingroup$

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

  • 0
    I thought it was intuitive, I'd need to discover g and h. I have updated the question, btw.2011-11-05

1 Answers 1

0

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

  • 0
    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.2011-11-05