0

Question from the title. I'm just starting with Boolean algebra and my first set of exercises contains multiple problems which simplify to a variant of this. Am I "done" these problems, or can I still simplify further?

Pp..
  • 5,973
Mike Dumycz
  • 37
  • Your question is not clear – Extremal Feb 06 '15 at 20:01
  • 3
    Can I simplify the expression within the brackets to remove y or z as a variable? Can I simplify the whole of the expression to remove one of the three variables completely, leaving me with only x and y or x and z? – Mike Dumycz Feb 06 '15 at 20:03
  • @Mathi The question is not clear to you is not the same as the question is not clear. – Pp.. Feb 06 '15 at 20:04
  • Correct, you are done. –  Feb 06 '15 at 20:08
  • @Pp..ya true. I just needed an elaboration from the person who posted this question.You don't have to worry about it. – Extremal Feb 06 '15 at 20:22
  • 1
    If x, y, z are distinct variables, (and none is the negation of the other), then no, you cannot simplify to two variables. You can write it as the product of sums $x(y+z)$ or as the sum of products: $xy + xz$. – amWhy Feb 06 '15 at 21:14

1 Answers1

2

In general,

A completely-specified Boolean function essentially depends on a variable if there exists an input combination such that the value of the function changes when the variable is toggled.

Obviously $x$ toggles your function when $y=z=1$; $y$ toggles the function when $x=1$ and $z=0$, and a symmetric argument can be made for $z$. Finding such combinations in general can be challenging because the problem is a version of SAT.

For the usual CNF and DNF formulas, there are some standardized ways to test/prove this. If we put your formula in DNF, both $xy$ and $xz$ are essential prime implicants; that's because they are both [trivially] prime implicants and you can immediately check that neither one implies the other.

Wikipedia [alas] does not cover the dual [and less used] notion of essential prime implicate (sometimes called essential prime implication), which is what you need to reason about the formula directly in CNF (instead of DNF which is what implicants are for), but you can find it in some books e.g. [1] [2] [3]. In your original formula, $y+z$ is a prime implicate and so is $x$, and it is even easier to see that neither is an implicate of the other, so both are essential prime implicates.

the gods from engineering
  • 2,173