1
$\begingroup$

I have an equation with the variables x and y, for this example let's say it's:

$a = (x(x+y-xy))+(x+y-xy)-(x(x+y-xy))(x+y-xy)$

The output of this equation (a), as well as the inputs x and y can only be a 0 or 1

I also have the following functions:

  • $f(x) = 1-x$
  • $g(x,y) = xy$
  • $h(x,y) = f(g(f(x), f(y))) = 1-(1-x)(1-y) = x+y-xy$

I am trying to find a way to 'simplify' a, which means it uses the least amount of the functions above, and the functions above only

Overview:

  1. What process can I use to 'simplify' any equation (a) with any set of functions?
  2. What process can I use to 'simplify' any equation (a) with any amount of variables (in the example, x and y were used. How could this be done if the variables were x, y and z)
  3. If I have multiple equations, how can I 'simplify' them both, but once a function has been used (for example g(xy,y)), if that function comes up again in the same equation or any other equation , it doesn't count towards the total amount of functions used. (The logic for this is that if I've already worked out what g(xy,y) is, I don't need to work it out again)

Note: For the example with equation a, it can be simplified to a = h(x,y)

Note2: All functions can be written as a combination of f(x) and g(x,y)

$\endgroup$
10
  • $\begingroup$ If inputs are $(x,y)$ and $x,y = 0, 1$ there are $2^2 =4$ possible inputs. $(0,0),(0,1),(1,0),(1,1)$. if the output is $0,1$ there are only $2^4$ possible functions. Find the simpliest express for each of the sixteen and out which ones these are. $\endgroup$
    – fleablood
    Mar 5, 2019 at 17:19
  • $\begingroup$ That's perfectly feasible for only two inputs x and y, however what if there are more variables? (In my case there could be hundreds) @fleablood $\endgroup$
    – Rlz
    Mar 5, 2019 at 17:21
  • $\begingroup$ Are you familiar with boolean logic. $1-x = \lnot x$ and $xy = x \land y$ and $x+y - xy = x \lor y$.... $\endgroup$
    – fleablood
    Mar 5, 2019 at 17:22
  • $\begingroup$ "however what if there are more variables?" then that would be a different question. What if Moby Dick were a tiny minnow? $\endgroup$
    – fleablood
    Mar 5, 2019 at 17:23
  • $\begingroup$ And for $a$ just factor it: $(x(x+y-xy))+(x+y-xy)-(x(x+y-xy))(x+y-xy) = (x + 1 - x)(x+y-xy)^2 = (x+y-xy)^2$. all input/output is $0$ or $1$, $w^2 = w$ so $a = x+y-xy$. $\endgroup$
    – fleablood
    Mar 5, 2019 at 17:26

0

You must log in to answer this question.

Browse other questions tagged .