Exercise DET-03.02 – Algebraic minimization (Solution)

Prof. Dr. Thorsten Jungmann (last updated 2026-10-19)

Relates to DET-03 Representation and minimization of logic functions

Task

With the theorems of Boolean algebra, you can minimize an expression step by step, without a map. Minimize each of the following functions as far as possible, and name the theorems that you use in each step. Where a function is given as a minterm list, first write down its canonical disjunctive normal form (DNF).

a) $Y_1=\overline{A}\cdot B+A\cdot B$

b) $Y_2=A\cdot \overline{B}\cdot \overline{C}+A\cdot \overline{B}\cdot C$

c) $Y_3(A,B,C)=\sum m(1,5,7)$

d) $Y_4(A,B,C)=\sum m(0,2,4,6)$

◀️ Back to the task

---

Solution

Given

Given explicitly:

• a) $Y_1=\overline{A}\cdot B+A\cdot B$
• b) $Y_2=A\cdot \overline{B}\cdot \overline{C}+A\cdot \overline{B}\cdot C$
• c) $Y_3(A,B,C)=\sum m(1,5,7)$
• d) $Y_4(A,B,C)=\sum m(0,2,4,6)$

Known:

• Minterms and the canonical DNF (DET-03, DET-03)
• The uniting theorem as three steps: distributive property, complements and identity (DET-03)
• Idempotence, to use a term twice (DET-03)
• The theorems with one and with several variables (DET-02, DET-02)

Required

a) to d) the minimized expressions $Y_1$ to $Y_4$, with the theorems of each step

a) Uniting two terms

Both terms contain $B$; they differ only in $A$, which appears once negated and once as it is. The uniting theorem removes $A$ in three steps (DET-03, 3.2): the distributive property factors out the common part $B$, the complements theorem replaces $\overline{A}+A$ by 1, and the identity theorem removes the 1:

$$\begin{array}{rlrl}{Y}_1& =\overline{A}\cdot B+A\cdot B& & \\ & =B\cdot \left(\overline{A}+A\right)& & \text{commutative and distributive properties}\\ & =B\cdot 1& & \text{commutative property, complements}\\ & =B& & \text{identity}\end{array}$$

The commutative property moves $B$ to the front, so that the distributive property can factor it out; in the second step, it turns $\overline{A}+A$ into $A+\overline{A}$, the form of the complements theorem. Read: $Y_1$ is 1 whenever $B$ is 1, whatever $A$ is.

Check with the minterm lists: $\overline{A}\cdot B$ is the minterm of row 1 and $A\cdot B$ that of row 3, so that $Y_1(A,B)=\sum m(1,3)$. $B$ is 1 exactly in rows 1 and 3 ✓

b) Uniting with three variables

The two terms differ only in $C$; their common part $A\cdot \overline{B}$ already stands in front, so the distributive property alone factors it out (DET-03, 3.2):

$$\begin{array}{rlrl}{Y}_2& =A\cdot \overline{B}\cdot \overline{C}+A\cdot \overline{B}\cdot C& & \\ & =A\cdot \overline{B}\cdot \left(\overline{C}+C\right)& & \text{distributive property}\\ & =A\cdot \overline{B}\cdot 1& & \text{commutative property, complements}\\ & =A\cdot \overline{B}& & \text{identity}\end{array}$$

Two terms with three literals each have become one term with two literals.

Check with the minterm lists: the two terms are the minterms of rows 4 and 5, so that $Y_2(A,B,C)=\sum m(4,5)$. $A\cdot \overline{B}$ is 1 if $A$ is 1 and $B$ is 0, whatever $C$ is, that is, in rows 4 and 5 ✓

c) A minterm used twice

First, the canonical DNF. In a minterm, a variable that is 0 in the row appears negated (DET-03, 2.1): row 1 is 001, row 5 is 101 and row 7 is 111. The middle minterm $A\cdot \overline{B}\cdot C$ differs from $\overline{A}\cdot \overline{B}\cdot C$ only in $A$ and from $A\cdot B\cdot C$ only in $B$. To unite it with both, you need it twice. Idempotence allows this, because a term ORed with itself stays the same (DET-03, 3.3):

$$\begin{array}{rlrl}{Y}_3& =\overline{A}\cdot \overline{B}\cdot C+A\cdot \overline{B}\cdot C+A\cdot B\cdot C& & \\ & =\overline{A}\cdot \overline{B}\cdot C+A\cdot \overline{B}\cdot C+A\cdot \overline{B}\cdot C+A\cdot B\cdot C& & \text{idempotence}\\ & =\overline{B}\cdot C\cdot \left(\overline{A}+A\right)+A\cdot C\cdot \left(\overline{B}+B\right)& & \text{commutative and distributive properties}\\ & =\overline{B}\cdot C\cdot 1+A\cdot C\cdot 1& & \text{commutative property, complements}\\ & =\overline{B}\cdot C+A\cdot C& & \text{identity}\\ & =C\cdot \left(A+\overline{B}\right)& & \text{commutative and distributive properties}\end{array}$$

The fifth line is a minimized DNF with two terms of two literals each. The last line factors out $C$ and saves a gate: an OR gate and an AND gate instead of two AND gates and an OR gate (DET-03, 3.3). Read: $Y_3$ is 1 if $C$ is 1 and if $A$ is 1 or $B$ is 0.

Check with the minterm list: $C\cdot \left(A+\overline{B}\right)$ is 1 in the rows with $C=1$, that is, rows 1, 3, 5 and 7, except where $A+\overline{B}$ is 0. This is the case only for $A=0$ and $B=1$, in row 3. Rows 1, 5 and 7 remain ✓

d) Uniting twice

First, the canonical DNF of rows 0, 2, 4 and 6; in all four, $C$ is 0. The minterms of rows 0 and 2 differ only in $B$, and so do those of rows 4 and 6. A first round of uniting removes $B$ from both pairs. The two results differ only in $A$ and unite once more (DET-03, 3.2):

$$\begin{array}{rlrl}{Y}_4& =\overline{A}\cdot \overline{B}\cdot \overline{C}+\overline{A}\cdot B\cdot \overline{C}+A\cdot \overline{B}\cdot \overline{C}+A\cdot B\cdot \overline{C}& & \\ & =\overline{A}\cdot \overline{C}\cdot \left(\overline{B}+B\right)+A\cdot \overline{C}\cdot \left(\overline{B}+B\right)& & \text{commutative and distributive properties}\\ & =\overline{A}\cdot \overline{C}\cdot 1+A\cdot \overline{C}\cdot 1& & \text{commutative property, complements}\\ & =\overline{A}\cdot \overline{C}+A\cdot \overline{C}& & \text{identity}\\ & =\overline{C}\cdot \left(\overline{A}+A\right)& & \text{commutative and distributive properties}\\ & =\overline{C}\cdot 1& & \text{commutative property, complements}\\ & =\overline{C}& & \text{identity}\end{array}$$

Four terms with three literals each have become a single literal: instead of four AND gates and an OR gate, $Y_4$ only needs an inverter. Read: $Y_4$ is 1 whenever $C$ is 0.

Check with the minterm list: $\overline{C}$ is 1 in all rows with $C=0$, that is, in the rows with an even number, 0, 2, 4 and 6 ✓