Exercise DET-02.05 – Boolean algebra (Solution)

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

Relates to DET-02 Logic operations

Task

With the rules of Boolean algebra, you can transform logic expressions without drawing a circuit. Give all results in the notation of electrical engineering that the lesson uses. Subtasks b) and d) are based on exercises in the textbook by LaMeres [5, p. 146].

a) Write the following expressions in the notation of electrical engineering: $\neg A\wedge (B\vee C)$ from mathematics, !(A && B) || C from computer science and $\neg (A\vee \neg B)\wedge C$ from mathematics.

b) Name the theorem of Boolean algebra that each of the following statements describes, and write it as an equation:

• (1) A variable combined with itself by OR yields the variable itself.
• (2) A variable that is negated twice yields the variable itself.
• (3) A variable combined with 1 by OR yields 1.
• (4) A variable that appears in several product terms can be factored out.
• (5) A term that another term of the expression already covers can be removed.
• (6) An AND gate with inverted inputs is equivalent to an OR gate with an inverted output.

c) Insert all parentheses into $Y_1=\overline{A}+B\cdot \overline{C}$ that show the order in which the expression is evaluated. Then evaluate $Y_1$ for $A=0$, $B=0$ and $C=1$.

d) Prove with a proof by exhaustion that an AND gate with inverted inputs is equivalent to an OR gate with an inverted output: $\overline{A}\cdot \overline{B}=\overline{A+B}$.

e) Prove with a truth table that $A+B\cdot C=(A+B)\cdot (A+C)$. With OR, the distributive property has no counterpart in ordinary arithmetic.

f) Simplify $Y_2=A\cdot \left(\overline{A}+B\right)$ step by step, and name the theorem that you use in each step.

g) Simplify $Y_3=A\cdot B+A\cdot B\cdot C+A\cdot \overline{B}$ step by step, and name the theorem that you use in each step.

h) Simplify $Y_4=\overline{\overline{A}+B}+\overline{A+B}$ step by step, and name the theorem that you use in each step.

◀️ Back to the task

---

Solution

Given

Given explicitly:

• a) $\neg A\wedge (B\vee C)$, !(A && B) || C and $\neg (A\vee \neg B)\wedge C$
• b) six statements about theorems of Boolean algebra
• c) $Y_1=\overline{A}+B\cdot \overline{C}$; $A=0$, $B=0$ and $C=1$
• d) $\overline{A}\cdot \overline{B}=\overline{A+B}$
• e) $A+B\cdot C=(A+B)\cdot (A+C)$
• f) to h) $Y_2=A\cdot \left(\overline{A}+B\right)$, $Y_3=A\cdot B+A\cdot B\cdot C+A\cdot \overline{B}$ and $Y_4=\overline{\overline{A}+B}+\overline{A+B}$

Known:

• Notations of mathematics, computer science and electrical engineering (DET-02)
• Precedence: NOT before AND, AND before OR (DET-02)
• Proof by exhaustion and the theorems with one variable: identity, null element, idempotence, complements and involution (DET-02)
• Theorems with several variables: commutative, associative and distributive properties, absorption and uniting (DET-02); De Morgan’s laws (DET-02)
• Transforming an expression step by step (DET-02)
• The theorems hold for any expressions in place of the variables, for example $A\cdot B$ in place of $A$.

Required

a) the three expressions in the notation of electrical engineering
b) the name and the equation of each theorem
c) the parentheses and the value of $Y_1$
d) and e) the two proofs
f) to h) the simplified expressions, with the theorem of each step

a) Notations

Mathematics writes ∧ for AND, ∨ for OR and ¬ for NOT; computer science writes &&, || and !. In electrical engineering, AND is the dot, OR the plus sign and NOT the bar (DET-02, 5.1). A negation in front of a parenthesis becomes a bar over the whole expression in the parenthesis:

• $\neg A\wedge (B\vee C)=\overline{A}\cdot (B+C)$
• !(A && B) || C: !(…) negates the whole parenthesis, && is AND and || is OR, so that the expression becomes $\overline{A\cdot B}+C$
• $\neg (A\vee \neg B)\wedge C=\overline{A+\overline{B}}\cdot C$

Check by evaluating the original and the new notation for the same values. For $A=0$, $B=1$ and $C=0$:

• $\neg A\wedge (B\vee C)=\neg 0\wedge (1\vee 0)=1\wedge 1=1$ and $\overline{A}\cdot (B+C)=\overline{0}\cdot (1+0)=1\cdot 1=1$ ✓
• !(A && B) || C becomes !(0 && 1) || 0, that is !0 || 0 and 1 || 0, and thus 1; $\overline{A\cdot B}+C=\overline{0\cdot 1}+0=\overline{0}+0=1+0=1$ ✓
• $\neg (A\vee \neg B)\wedge C=\neg (0\vee \neg 1)\wedge 0=\neg (0\vee 0)\wedge 0=\neg 0\wedge 0=1\wedge 0=0$ and $\overline{A+\overline{B}}\cdot C=\overline{0+\overline{1}}\cdot 0=\overline{0+0}\cdot 0=\overline{0}\cdot 0=1\cdot 0=0$ ✓

b) Theorems

Statement	Theorem	Equation
(1)	idempotence	$A+A=A$
(2)	involution	$\overline{\overline{A}}=A$
(3)	null element	$A+1=1$
(4)	distributive property	$A\cdot B+A\cdot C=A\cdot (B+C)$
(5)	absorption	$A+A\cdot B=A$
(6)	De Morgan’s laws	$\overline{A}\cdot \overline{B}=\overline{A+B}$

Statement (4) reads the distributive property from right to left (DET-02, 5.4): factoring out is multiplying out in reverse. Statement (6) is the second of De Morgan’s laws, read from right to left (DET-02, 5.5).

Check of (5) with contact logic: a contact $A$ lies in parallel with the series of the contacts $A$ and $B$. Whenever the series conducts, $A$ alone conducts as well, so that the series adds nothing ✓

c) Precedence

Without parentheses, NOT comes first, then AND, then OR (DET-02, 5.2). The bars over $A$ and $C$ are evaluated first, then the product of $B$ and $\overline{C}$, and finally the sum:

$$Y_1=\left(\overline{A}\right)+\left(B\cdot \left(\overline{C}\right)\right)$$

For $A=0$, $B=0$ and $C=1$:

$$Y_1=\overline{A}+B\cdot \overline{C}=\overline{0}+0\cdot \overline{1}=1+0\cdot 0=1+0=1$$

Check: with $A=0$, the term $\overline{A}$ is already 1, and $1+B\cdot \overline{C}=1$ by the null element, whatever $B$ and $C$ are ✓

Why the precedence matters

Evaluated from left to right, the expression would become $\left(\overline{A}+B\right)\cdot \overline{C}$. For the same values, $A=0$, $B=0$ and $C=1$, it gives $\left(\overline{A}+B\right)\cdot \overline{C}=\left(\overline{0}+0\right)\cdot \overline{1}=(1+0)\cdot 0=1\cdot 0=0$ – a different result. VHDL knows no precedence between AND and OR; wherever AND and OR are mixed, the parentheses have to be written (DET-02, 5.2).

d) De Morgan’s law

In a proof by exhaustion, both sides are evaluated for every combination of the inputs (DET-02, 5.3):

$A$	$B$	$\overline{A}$	$\overline{B}$	$\overline{A}\cdot \overline{B}$	$A+B$	$\overline{A+B}$
0	0	1	1	🟢1	0	🟢1
0	1	1	0	🟢0	1	🟢0
1	0	0	1	🟢0	1	🟢0
1	1	0	0	🟢0	1	🟢0

The columns $\overline{A}\cdot \overline{B}$ and $\overline{A+B}$ agree in all four rows: an AND gate with inverted inputs does the same as a NOR gate. This is the second of De Morgan’s laws, $\overline{A+B}=\overline{A}\cdot \overline{B}$.

Check with contact logic: the NOR gate consists of two normally closed contacts in series (DET-02, 4.2). Inverted inputs are normally closed contacts, and AND is a series – the same circuit ✓

e) Distributive property with OR

$A$	$B$	$C$	$B\cdot C$	$A+B\cdot C$	$A+B$	$A+C$	$(A+B)\cdot (A+C)$
0	0	0	0	🟢0	0	0	🟢0
0	0	1	0	🟢0	0	1	🟢0
0	1	0	0	🟢0	1	0	🟢0
0	1	1	1	🟢1	1	1	🟢1
1	0	0	0	🟢1	1	1	🟢1
1	0	1	0	🟢1	1	1	🟢1
1	1	0	0	🟢1	1	1	🟢1
1	1	1	1	🟢1	1	1	🟢1

The columns $A+B\cdot C$ and $(A+B)\cdot (A+C)$ agree in all eight rows; the distributive property with OR holds (DET-02, 5.4).

Check by multiplying out the right-hand side:

$$\begin{array}{rlrl}(A+B)\cdot (A+C)& =A\cdot A+A\cdot C+B\cdot A+B\cdot C& & \text{distributive property}\\ & =A+A\cdot C+A\cdot B+B\cdot C& & \text{idempotence, commutative property}\\ & =A+B\cdot C& & \text{absorption, twice}\end{array}$$

✓

f) Simplification of $Y_2$

Each step applies one theorem (DET-02, 5.6):

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

Check with a truth table:

$A$	$B$	$A\cdot \left(\overline{A}+B\right)$	$A\cdot B$
0	0	🟢0	🟢0
0	1	🟢0	🟢0
1	0	🟢0	🟢0
1	1	🟢1	🟢1

The last two columns agree in all rows ✓

g) Simplification of $Y_3$

$$\begin{array}{rlrl}{Y}_3& =A\cdot B+A\cdot B\cdot C+A\cdot \overline{B}& & \\ & =A\cdot B+A\cdot \overline{B}& & \text{absorption, with }A\cdot B\text{ in place of }A\text{ and }C\text{ in place of }B\\ & =A& & \text{uniting}\end{array}$$

The term $A\cdot B\cdot C$ is 1 only where $A\cdot B$ is 1 already; it adds nothing. Then $B$ appears once plain and once negated, and has no influence.

Check with a truth table:

$A$	$B$	$C$	$A\cdot B+A\cdot B\cdot C+A\cdot \overline{B}$
🟢0	0	0	🟢0
🟢0	0	1	🟢0
🟢0	1	0	🟢0
🟢0	1	1	🟢0
🟢1	0	0	🟢1
🟢1	0	1	🟢1
🟢1	1	0	🟢1
🟢1	1	1	🟢1

The column of $Y_3$ agrees with the column $A$ in all rows ✓

h) Simplification of $Y_4$

$$\begin{array}{rlrl}{Y}_4& =\overline{\overline{A}+B}+\overline{A+B}& & \\ & =\overline{\overline{A}}\cdot \overline{B}+\overline{A}\cdot \overline{B}& & \text{De Morgan’s laws}\\ & =A\cdot \overline{B}+\overline{A}\cdot \overline{B}& & \text{involution}\\ & =\overline{B}\cdot \left(A+\overline{A}\right)& & \text{commutative and distributive properties}\\ & =\overline{B}\cdot 1& & \text{complements}\\ & =\overline{B}& & \text{identity}\end{array}$$

Alternatively, uniting gives the last three steps at once: $A\cdot \overline{B}+\overline{A}\cdot \overline{B}=\overline{B}$.

Check with a truth table:

$A$	$B$	$\overline{\overline{A}+B}+\overline{A+B}$	$\overline{B}$
0	0	🟢1	🟢1
0	1	🟢0	🟢0
1	0	🟢1	🟢1
1	1	🟢0	🟢0

The last two columns agree in all rows ✓