Homework: Exercise 4a

Theory: How to Approach These

Truth table: $2^n$ rows in binary order, one helper column per sub-expression; precedence is NOT, AND, OR (4.2).
Prove an equality: matching columns in every row, or one law per line with the law named (4.2).
Universal gates: draw the AND/OR/NOT circuit first, swap each gate for its NAND version (NAND with tied inputs is NOT), then cancel NOT pairs, so AND-OR becomes NAND-NAND (4.1).
Word problems: one variable per condition, each rule is a row with $F = 1$ , then simplify with a K-map with Gray-order columns $00, 01, 11, 10$ (4.3).

Jump to: Q1 · Q2 · Q3 · Q4 · Q5

Homework Solutions

Exercise Q1

Construct a truth table for the following:

a. $(x + y)(x + z)(x' + z)$

b. $xyz + x(yz)' + (xyz)'$

Part	Detail
Asks	List all 8 input rows and the output of each expression.
Needs	3 variables give $2^3 = 8$ rows. Order: brackets, NOT, AND, OR.
Look at	Each bracket or term is a helper column. $(yz)'$ is NOT of $(y \text{ AND } z)$ , not $y'z'$ .
If it changes	More variables, more rows (4 variables give 16). Still one column per sub-expression, then the output.

Show solution ↓

Solution

How to solve

Write $x, y, z$ for rows 0 to 7 ( $x$ changes slowest, $z$ fastest).
Add one column per part, for example $x+y$ , $x+z$ , $x'+z$ .
Combine: a product is 1 only if every part is 1; a sum is 1 if any part is 1.

$x$	$y$	$z$
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

Sample answer

(a)

$x$	$y$	$z$	$x+y$	$x+z$	$x'+z$	$(x+y)(x+z)(x'+z)$
0	0	0	0	0	1	0
0	0	1	0	1	1	0
0	1	0	1	0	1	0
0	1	1	1	1	1	1
1	0	0	1	1	0	0
1	0	1	1	1	1	1
1	1	0	1	1	0	0
1	1	1	1	1	1	1

Output $0, 0, 0, 1, 0, 1, 0, 1$ , so $\Sigma m(3, 5, 7) = xz + yz$ .

Check by algebra:

\begin{aligned} (x+y)(x+z)(x'+z) &= (x + yz)(x' + z) && \text{Distributive} \\ &= xx' + xz + x'yz + yz && \text{Distributive, Idempotent} \\ &= xz + yz(x' + 1) && \text{Inverse, Identity} \\ &= xz + yz && \text{Null, Identity} \end{aligned}

(b)

$x$	$y$	$z$	$xyz$	$yz$	$(yz)'$	$x(yz)'$	$(xyz)'$	$F$
0	0	0	0	0	1	0	1	1
0	0	1	0	0	1	0	1	1
0	1	0	0	0	1	0	1	1
0	1	1	0	1	0	0	1	1
1	0	0	0	0	1	1	1	1
1	0	1	0	0	1	1	1	1
1	1	0	0	0	1	1	1	1
1	1	1	1	1	0	0	0	1

$F = 1$ in every row (a tautology). Reason: $xyz + (xyz)' = 1$ (Inverse), then $1 + x(yz)' = 1$ (Null).

Watch out: $(yz)'$ is not $y'z'$ . Build one helper column per bracket instead of evaluating in your head.

Exercise Q2

Show that $x = xy + xy'$

a. Using truth tables

b. Using Boolean identities

Part	Detail
Asks	Prove both sides are always equal, in two ways.
Needs	Equal columns in every row; Distributive, Inverse ( $y + y' = 1$ ), Identity ( $x \cdot 1 = x$ ).
Look at	The common factor $x$ in both terms is the hint to use the Distributive law.
If it changes	Any “show that”: start from the longer side, one law per line, name each law.

Show solution ↓

Solution

How to solve

(a) Make 4 rows for $x, y$ with columns $y'$ , $xy$ , $xy'$ , $xy + xy'$ , and compare with the $x$ column.
(b) Factor out $x$ (Distributive), replace $y + y'$ by 1 (Inverse), then drop the 1 (Identity).

Sample answer

(a)

$x$	$y$	$y'$	$xy$	$xy'$	$xy + xy'$
0	0	1	0	0	0
0	1	0	0	0	0
1	0	1	0	1	1
1	1	0	1	0	1

The last column $0, 0, 1, 1$ equals the $x$ column in every row, so $xy + xy' = x$ ✓.

(b)

\begin{aligned} xy + xy' &= x(y + y') && \text{Distributive} \\ &= x \cdot 1 && \text{Inverse} \\ &= x && \text{Identity} \end{aligned}

Watch out: name the law on every line; an unnamed step earns no credit in a proof.

Exercise Q3

Construct the XOR operator using only NAND gates.

Note: $x \text{ XOR } y = xy' + x'y$

Part	Detail
Asks	Build a circuit of only NAND gates whose output is $x \oplus y$ , and show that it works.
Needs	$\text{NAND}(a, a) = a'$ . SOP to NAND-NAND: $ab + cd = ((ab)'(cd)')'$ .
Look at	The given SOP $xy' + x'y$ has two AND terms, one OR and two NOTs.
If it changes	Any SOP: replace each AND and the OR by NAND, and make each complement with $\text{NAND}(x, x)$ .

Show solution ↓

Solution

How to solve

Draw the circuit with ordinary NOT, AND and OR gates, straight from the formula.
Replace every gate with its NAND version.
Wherever two NOTs end up in a row, remove both: flipping a signal twice gives it back.
Prove it with a truth table.

Step 1: the ordinary circuit. Read $xy' + x'y$ piece by piece. $y'$ needs a NOT on $y$ , and $x'$ needs a NOT on $x$ . $xy'$ needs an AND of $x$ and $y'$ , and $x'y$ needs an AND of $x'$ and $y$ . The $+$ needs an OR that joins the two ANDs. That makes 2 NOT, 2 AND and 1 OR.

Step 2: each gate made from NAND. A NAND is an AND whose answer is flipped: it outputs 0 only when both inputs are 1.

Gate we need	Built from NAND	Why it works
NOT $a$	NAND( $a$ , $a$ )	NAND(0, 0) = 1 and NAND(1, 1) = 0, so the output is always the opposite of the input.
$a$ AND $b$	NAND( $a$ , $b$ ), then a NOT	The NAND gives the flipped AND; the NOT flips it back.
$a$ OR $b$	NOT $a$ and NOT $b$ , then NAND	The table below shows it gives OR.

$a$	$b$	$a'$	$b'$	NAND( $a'$ , $b'$ )	$a + b$
0	0	1	1	0	0
0	1	1	0	1	1
1	0	0	1	1	1
1	1	0	0	1	1

The last two columns match, so NOT both inputs and then NAND gives OR ✓. (In algebra: $(a'b')' = a + b$ by DeMorgan.)

Step 3: swap and cancel. Follow the wire from each AND gate to the OR gate:

Stage	Gates on the path
Ordinary circuit	AND → OR
Swap each gate for its NAND version	NAND → NOT → NOT → NAND
Remove the two NOTs in a row	NAND → NAND

So each AND becomes a single NAND, and the OR becomes a single NAND. The two input NOTs ( $x'$ and $y'$ ) are still needed, so each becomes NAND with its inputs joined.

Sample answer

Method 1 (5 NAND gates, built from Steps 1–3):

Gate	Inputs	Output	Replaces
$G_1$	$x$ , $x$	$x'$	NOT $x$
$G_2$	$y$ , $y$	$y'$	NOT $y$
$G_3$	$x$ , $G_2$	$(xy')'$	AND $xy'$
$G_4$	$G_1$ , $y$	$(x'y)'$	AND $x'y$
$G_5$	$G_3$ , $G_4$	$\big((xy')'(x'y)'\big)' = xy' + x'y$	OR

Check one row by hand, $x = 1$ , $y = 0$ (XOR should give 1): $G_1 = \text{NAND}(1,1) = 0$ , $G_2 = \text{NAND}(0,0) = 1$ , $G_3 = \text{NAND}(1,1) = 0$ , $G_4 = \text{NAND}(0,0) = 1$ , $G_5 = \text{NAND}(0,1) = 1$ ✓.

Method 2 (standard 4 NAND gates): instead of two separate inverters, use one shared gate $n_1 = (xy)'$ , which means “not both are 1”. AND-ing $x$ with it leaves only the case where $x = 1$ and $y = 0$ : $x(xy)' = x(x' + y') = xx' + xy' = xy'$ . Likewise $y(xy)' = x'y$ . So $n_2$ and $n_3$ below give the same outputs as $G_3$ and $G_4$ , with one gate fewer.

Gate	Inputs	Output
$n_1$	$x$ , $y$	$(xy)'$
$n_2$	$x$ , $n_1$	$(x\,n_1)'$
$n_3$	$y$ , $n_1$	$(y\,n_1)'$
$out$	$n_2$ , $n_3$	$(n_2 n_3)'$

Algebra:

\begin{aligned} out &= (n_2 n_3)' = n_2' + n_3' && \text{DeMorgan} \\ &= x\,n_1 + y\,n_1 && \text{Double complement} \\ &= (x + y)(xy)' && \text{Distributive} \\ &= (x + y)(x' + y') && \text{DeMorgan} \\ &= xy' + x'y && \text{Distributive, Inverse, Identity} \end{aligned}

$x$	$y$	$n_1$	$n_2$	$n_3$	$out$	$x \oplus y$
0	0	1	1	1	0	0
0	1	1	1	0	1	1
1	0	1	0	1	1	1
1	1	0	1	1	0	0

$out = x \oplus y$ in every row ✓, using four NAND gates (one 7400 chip).

Watch out: “only NAND” means no separate NOT gates; build each inverter as $\text{NAND}(a, a)$ . Always add the truth-table check.

Exercise Q4

Little Susie is trying to train her new puppy. She is trying to figure out when the puppy should get a dog biscuit as a reward. She has concluded the following:

Give the puppy a biscuit if it sits and wiggles but does not bark.
Give the puppy a biscuit if it barks and wiggles but does not sit.
Give the puppy a biscuit if it sits but does not wiggle or bark.
Give the puppy a biscuit if it sits, wiggles and barks.
Don’t give the puppy a treat otherwise.

Hint: Use the following: S: Sit (0 for not sitting; 1 for sitting) W: Wiggles (0 for not wiggling; 1 for wiggling) B: Barking (0 for not barking; 1 for barking) F: Biscuit function (0, don’t give the puppy a biscuit; 1, give the puppy a biscuit)

Construct a truth table and find the minimized Boolean function to implement the logic telling Susie when to give her dog a biscuit.

Part	Detail
Asks	Turn the sentences into truth-table rows, then simplify $F$ with a K-map.
Needs	“does” = 1, “does not” = 0; each rule is one minterm; K-map grouping rules (4.3).
Look at	Variable order $S\,W\,B$ from the hint. Rule 5 means every other row is 0.
If it changes	Different rules mean different $F = 1$ rows; the method (rules, rows, K-map, expression, check) stays.

Show solution ↓

Solution

How to solve

Translate each rule into $SWB$ : rule 1 = 110, rule 2 = 011, rule 3 = 100, rule 4 = 111.
Fill the truth table: $F = 1$ on those rows, 0 elsewhere. $F = \Sigma m(3, 4, 6, 7)$ .
Put the 1s on a K-map (rows $S$ , columns $WB$ in order $00, 01, 11, 10$ ) and make the biggest groups.
Read each group, write $F$ , and check all 8 rows.

$S \backslash WB$	00	01	11	10
0
1

Sample answer

$S$	$W$	$B$	$F$	Rule
0	0	0	0	5
0	0	1	0	5
0	1	0	0	5
0	1	1	1	2
1	0	0	1	3
1	0	1	0	5
1	1	0	1	1
1	1	1	1	4

$S \backslash WB$	00	01	11	10
0	0	0	1	0
1	1	0	1	1

Group A (column 11, both rows: m3, m7): $W = 1$ , $B = 1$ constant, so $WB$ .
Group B (bottom row, columns 00 and 10 joined by wrap-around: m4, m6): $S = 1$ , $B = 0$ constant, so $SB'$ .

F = SB' + WB

In words: give a biscuit if the puppy sits without barking, or wiggles while barking. Check on every row: 011 gives 1, 100 gives 1, 110 gives 1, 111 gives 1; 000, 001, 010, 101 give 0 ✓.

Circuit: one inverter ( $B'$ ), two ANDs, one OR.

Watch out: K-map columns run $00, 01, 11, 10$ , not binary order. The left and right columns are neighbours, which is how m4 and m6 group.

Exercise Q5

Given the function: $F(x,y,z) = xy'z + x'y'z + xyz$

a. List the truth table for F.

b. Draw the logic diagram using the original Boolean expression.

c. Simplify the expression using Boolean algebra and identities.

d. Simplify the expression using KMap.

e. List the truth table for your answer in Part d.

f. Draw the logic diagram for the simplified expression in Part d.

Part	Detail
Asks	The full workflow: table, circuit, simplify two ways, check, then a smaller circuit.
Needs	Minterms: $x'y'z = m_1$ , $xy'z = m_5$ , $xyz = m_7$ . Idempotent, Distributive, Inverse, Identity; K-map rules.
Look at	$xy'z$ differs by one variable from both other terms, so it is used twice.
If it changes	Any 3-variable function: write its minterms, fill the K-map, compare with algebra; (e) and (f) re-check and redraw (d).

Show solution ↓

Solution

How to solve

(a) $F = 1$ only on rows 1, 5, 7: $F = \Sigma m(1, 5, 7)$ .
(b) Draw the original: 2 NOTs, three 3-input ANDs, one 3-input OR.
(c) Copy $xy'z$ (Idempotent), pair it with each other term, factor, use $y + y' = 1$ and $x + x' = 1$ .
(d) K-map: group $m_1 + m_5$ and $m_5 + m_7$ .
(e) The table of the simple answer must equal (a). (f) Draw the smaller circuit.

Sample answer

(a)

$x$	$y$	$z$	$xy'z$	$x'y'z$	$xyz$	$F$
0	0	0	0	0	0	0
0	0	1	0	1	0	1
0	1	0	0	0	0	0
0	1	1	0	0	0	0
1	0	0	0	0	0	0
1	0	1	1	0	0	1
1	1	0	0	0	0	0
1	1	1	0	0	1	1

(b) 2 inverters, 3 three-input ANDs, 1 three-input OR (6 gates):

(c)

\begin{aligned} F &= (xy'z + x'y'z) + (xy'z + xyz) && \text{Idempotent, Associative} \\ &= y'z(x + x') + xz(y' + y) && \text{Commutative, Distributive} \\ &= y'z \cdot 1 + xz \cdot 1 && \text{Inverse} \\ &= y'z + xz && \text{Identity} \end{aligned}

(d)

$x \backslash yz$	00	01	11	10
0	0	1	0	0
1	0	1	1	0

Group A (column 01: m1, m5): $y = 0$ , $z = 1$ constant, so $y'z$ .
Group B (bottom row, columns 01 and 11: m5, m7): $x = 1$ , $z = 1$ constant, so $xz$ .

$F = xz + y'z = z(x + y')$ , the same as (c) ✓.

(e)

$x$	$y$	$z$	$xz$	$y'z$	$xz + y'z$
0	0	0	0	0	0
0	0	1	0	1	1
0	1	0	0	0	0
0	1	1	0	0	0
1	0	0	0	0	0
1	0	1	1	1	1
1	1	0	0	0	0
1	1	1	1	0	1

The last column $0, 1, 0, 0, 0, 1, 0, 1$ matches (a) ✓.

(f) 1 inverter, two 2-input ANDs, one 2-input OR (4 gates):

The factored form $z(x + y')$ needs only 3 gates: one inverter, one OR, one AND.

Watch out: a term may be used twice only after writing the Idempotent law first. Do not “cancel” terms; combine pairs that differ in exactly one variable.

$x$	$y$	$z$	$xyz$	$yz$	$(yz)'$	$x(yz)'$	$(xyz)'$	$F$
0	0	0	0	0	1	0	1	1
0	0	1	0	0	1	0	1	1
0	1	0	0	0	1	0	1	1
0	1	1	0	1	0	0	1	1
1	0	0	0	0	1	1	1	1
1	0	1	0	0	1	1	1	1
1	1	0	0	0	1	1	1	1
1	1	1	1	1	0	0	0	1

$x$	$y$	$z$	$xyz$	$yz$	$(yz)'$	$x(yz)'$	$(xyz)'$	$F$
0	0	0	0	0	1	0	1	1
0	0	1	0	0	1	0	1	1
0	1	0	0	0	1	0	1	1
0	1	1	0	1	0	0	1	1
1	0	0	0	0	1	1	1	1
1	0	1	0	0	1	1	1	1
1	1	0	0	0	1	1	1	1
1	1	1	1	1	0	0	0	1

$x$	$y$	$z$	$xyz$	$yz$	$(yz)'$	$x(yz)'$	$(xyz)'$	$F$
0	0	0	0	0	1	0	1	1
0	0	1	0	0	1	0	1	1
0	1	0	0	0	1	0	1	1
0	1	1	0	1	0	0	1	1
1	0	0	0	0	1	1	1	1
1	0	1	0	0	1	1	1	1
1	1	0	0	0	1	1	1	1
1	1	1	1	1	0	0	0	1