## Problem of the Day #347: Evaluating Boolean ExpressionsFebruary 29, 2012

Posted by Alex in : potd , trackback

Saketh wants to evaluate the Boolean algebra expression $(AB + CD)(AC + BD)$. The values of $A$, $B$, $C$, and $D$ are randomly generated. In order to evaluate the expression, Saketh will uncover variables, revealing their values, one at a time in whatever order he desires. Given that Saketh chooses optimally, what is the expected number of variables whose values must be revealed before Saketh can evaluate the expression?

Note: $AB$ denotes $A \text{ and } B$ and $C+D$ denotes $C \text{ or } D$.

Tags: