Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/digital-systems-linear-algebra-introduction-to-formal-proof/1/e/solution

The unconstrained cases can be treated as don't-care conditions during Boolean function minimization. One particularly small, deliberately asymmetric choice is
Use the same two history D flip-flops and one output D flip-flop, with this expression at the output D input. It requires two two-input AND gates and one OR gate.
To verify every required case, first set . If zero occurs at least twice among , then , so as required. If all three samples are one, then , so . The remaining triples have exactly two ones and hence exactly one sample agreeing with the old zero; either output is allowed.
Now set . If at least two samples are one, either or , giving . If all three samples are zero, both terms vanish, giving . The remaining triples have exactly one one and are the allowed don't-care conditions. Thus the expression meets both requirements, including every constant-input triple.
For minimality, consider these required one-entries in order: , , and have no common literal. Therefore a product covering all four would be the constant one, which violates required zero-entries. Also no single-literal product is safe: each of is one at some required zero-entry, and each complemented literal is one at . Hence at least two products with at least two Boolean literals each are needed. The displayed expression attains two products and four literals.

New to topics? Read the docs here!