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 / a

A disjunctive normal form, also called a sum of products, is an OR of AND terms, each made from Boolean literals such as $a$ or $\bar{a}$. For example,Here juxtaposition means logical conjunction, $+$ means logical disjunction, and a bar means negation. The expression need not be canonical: a term can omit variables, and need not name a single row of the truth table.

Implement each product by an AND gate and combine the products with an OR gate. Supply complemented inputs with NOT gates. ThusThis is the usual two-level combinational logic realization, counting complemented inputs as available. If NOT gates are counted, a complemented input can traverse three gates. The two-level depth statement also assumes sufficiently large gate fan-in: using only two-input logic gates requires trees for long products or sums. Constant, single-product and single-literal Boolean functions may need fewer levels, so the two-level construction is a general bound, not a claim that every expression requires exactly two layers.