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 / d / Solution

Keep the two history D flip-flops and add an output D flip-flop with previous value $q=z_{n-1}$. Its next value $q^{+}=z_n$ is one if all three inputs are one, or if the output was one and at least one of the three inputs is one. In the latter case the samples are not all zero, so the previous one must be retained. This givesIf $abc=111$, the first product sets the output. If $abc=000$, every product vanishes and the output clears. For every mixed input triple, at least one of $aq,bq,cq$ equals $q$, so the output is retained. Feed this sum of products to the output D input, use $b^{+}=a,c^{+}=b$ for the history, and use asynchronous clear or an appropriate initialization to establish $q=0$.

Minimality can be seen directly from the truth table. At $q=0$, the only one-entry is $abc=111$, forcing the product $abc$ or a narrower term. At $q=1$, the triples $100$, $010$ and $001$ must all produce one; combining any two in one product would also admit $000$, which must produce zero. Thus three more products are needed. The displayed four products achieve the minimum; removing any Boolean literal from $abc,aq,bq,cq$ would include a zero-entry.