Chapter 2

2.1. Pembuktian sbb:

(x + y )
(x + z ) = xx + xz + xy + yz

= x + xz + xy + yz
= x(1 + z + y) + yz

= x
1+ yz

= x + yz

2.2. Pembuktian sbb:

(x + y )
(x + y ) = xx + xy + xy + yy
= x + xy + xy + 0
= x(1 + y + y)
= x
1
= x

2.3. Bukti dengan Venn diagram:

x y x y

z z

x x+y

x y x y

z z

y⋅z x+z

x y x y

z z

x+y⋅z ( x + y)( x + z)

2-1
2.4. Proof of 15a using Venn diagrams:

x y x y

x⋅y x

x y x y

x⋅y y

x y

x⋅y

A similar proof is constructed for 15b.

2.5. Proof using Venn diagrams:

x1 x2 x1 x2

x3 x3

x1 + x2 + x3 x1 + x2

x1 x2

x3

x1 + x2 + x3

x1 x2

x3

( x1 + x2 + x3 ) ⋅ ( x1 + x2 + x3 )

2-2
2.6. A possible approach for determining whether or not the expressions are valid is to try to manipulate the left
and right sides of an expression into the same form, using the theorems and properties presented in section
2.5. While this may seem simple, it is an awkward approach, because it is not obvious what target form one
should try to reach. A much simpler approach is to construct a truth table for each side of an expression. If the
truth tables are identical, then the expression is valid. Using this approach, we can show that the answers are:

(a) Yes
(b) Yes
(c) No

2.7. Timing diagram dari bentuk gelombang dari rangkaian pada gambar 2.19a:

x2 A
C

f
B
x3
x1 D

x1

x2

x3

2-3
 2.8. Timing diagram of the waveforms that can be observed on all wires of the circuit:

x1 C
x3

f
A
D
x2
B

x1

x2

x3

2.9. Starting with the canonical sum-of-products for f get

f = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3
= x1 (x2 x3 + x2 x3 + x2 x3 + x2 x3 ) + x2 (x1 x3 + x1 x3 + x1 x3 + x1 x3 )

+x3 (x1 x2 + x1 x2 + x1 x2 + x1 x2 )

= x1 (x2 (x3 + x3 ) + x2 (x3 + x3 )) + x2 (x1 (x3 + x3 ) + x1 (x3 + x3 ))

+x3 (x1 (x2 + x2 ) + x1 (x2 + x2 ))

= x1 ( x 2
1+ x2
1) + x2 (x1
1 + x1
1) + x3 (x1
1 + x1
1)
= x1 (x2 + x2 ) + x2 (x1 + x1 ) + x3 (x1 + x1 )

= x1
1 + x2
1 + x3
1
= x1 + x2 + x3

2.10. The canonical product-of-sums for f is

f = (x1 + x2 + x3 )(x1 + x2 + x3 )(x1 + x2 + x3 )(x1 + x2 + x3 )

(x1 + x2 + x3 )(x1 + x2 + x3 )(x1 + x2 + x3 )

It can be manipulated as follows:

f = (x1 (1 + x2 + x3 )(1 + x2 + x3 )(1 + x2 + x3 )(1 + x2 + x3 ))

(x2 (x1 + 1 + x3 )(x1 + 1 + x3 )(x1 + 1 + x3 )(x1 + 1 + x3 ))

(x3 (x1 + x2 + 1)(x1 + x2 + 1)(x1 + x2 + 1)(x1 + x2 + 1))

2-4
 = (x1
1
1
1
1)(x2
1
1
1
1)(x3
1
1
1
1)
= x1 x2 x3

2.11. Derivasi dari expresi minimum sum-of-product:

f = x1 x3 + x1 x2 + x1 x2 x3 + x1 x2 x3
= x1 (x2 + x2 )x3 + x1 x2 (x3 + x3 ) + x1 x2 x3 + x1 x2 x3

= x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3

= x1 x3 + (x1 + x1 )x2 x3 + (x1 + x1 )x2 x3

= x1 x3 + x2 x3 + x2 x3

2.12. Derivasidari expresi minimum sum-of-product:

f = x1 x2 x3 + x1 x2 x4 + x1 x2 x3 x4
= x1 x2 x3 (x4 + x4 ) + x1 x2 x4 + x1 x2 x3 x4

= x1 x2 x3 x4 + x1 x2 x3 x4 + x1 x2 x4 + x1 x2 x3 x4

= x1 x2 x3 + x1 x2 (x3 + x3 )x4 + x1 x2 x4

= x1 x2 x3 + x1 x2 x4 + x1 x2 x4

2.13. Expresi POS sederhana diderivasi sebagai

f = (x1 + x3 + x4 )(x1 + x2 + x3 )(x1 + x2 + x3 + x4 )

= (x1 + x3 + x4 )(x1 + x2 + x3 )(x1 + x2 + x3 + x4 )(x1 + x2 + x3 + x4 )

= (x1 + x3 + x4 )(x1 + x2 + x3 )((x1 + x2 + x4 )(x3 + x3 ))

= (x1 + x3 + x4 )(x1 + x2 + x3 )(x1 + x2 + x4 )
1
= (x1 + x3 + x4 )(x1 + x2 + x3 )(x1 + x2 + x4 )

2.14. Derivasi dari expresi minimum product-of-sum:

f = (x1 + x2 + x3 )(x1 + x2 + x3 )(x1 + x2 + x3 )(x1 + x2 + x3 )

= ((x1 + x2 ) + x3 )((x1 + x2 ) + x3 )(x1 + (x2 + x3 ))(x1 + (x2 + x3 ))

= (x1 + x2 )(x2 + x3 )

2.15. (a) Lokasi semua minterm dalam diagram venn 3-variabel:

m0
x1 x2
m6
m4 m2
m7
m5 m3

x3
m1

2-5
 (b) For f = x1 x2 x3 + x1 x2 + x1 x3 have:

x1 x2 x1 x2 x1 x2

x3 x3 x3

x1 ⋅ x2 ⋅ x3 x1 ⋅ x2 x1 ⋅ x3

Therefore, f is represented as:

x1 x2

x3

f = x3 + x1 x2

2.16. The function in Figure 2.18 in Venn diagram form is:

x1 x2

x3

2.17. In Figure P2.1a it is possible to represent only 14 minterms. It is impossible to represent the minterms
x1 x2 x3 x4 and x1 x2 x3 x4 .

In Figure P2.1b, it is impossible to represent the minterms x1x2x3 x4 and x1x2x3 x4.

2.18. Venn diagram for f = x1 x2 x3 x4 + x1 x2 x3 x4 + x1 x2 is

x4

x1 x2 x1 x2

x3 x3

2-6
2.19. Implementasi fungsi sederhana SOP adalah

f = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3

= (x1 + x1 )x2 x3 + x1 (x2 + x2 )x3

= x2 x3 + x1 x3

2.20. Implementasi fungsi sederhana SOP adalah

f = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3
= x1 (x2 + x2 )x3 + x1 (x2 + x2 )x3 + (x1 + x1 )x2 x3

= x1 x3 + x1 x3 + x2 x3

kemungkinan lain adalah

f = x1 x3 + x1 x3 + x1 x2

2.21. Implementasi fungsi sederhana POS adalah

f = (x1 + x2 + x3 )(x1 + x2 + x3 )(x1 + x2 + x3 )

= ((x1 + x3 ) + x2 )((x1 + x3 ) + x2 )(x1 + x2 + x3 )

= (x1 + x3 )(x1 + x2 + x3 )

2.22. Implementasi fungsi sederhana POS adalah

f = (x1 + x2 + x3 )(x1 + x2 + x3 )(x1 + x2 + x3 )(x1 + x2 + x3 )

= ((x1 + x2 ) + x3 )((x1 + x2 ) + x3 )((x1 + x3 ) + x2 )((x1 + x3 ) + x2 )

= (x1 + x2 )(x1 + x3 )

2.23. Rangkaian yang termurah didapat dengan

f (x1 ; x2; x3 ) = x1 x2 + x1 x3 + x2 x3

2-7
2.24. The truth table that corresponds to the timing diagram in Figure P2.3 is

x1 x2 x3 f

0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0

The simplest SOP expression is f = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 .

2.25. The truth table that corresponds to the timing diagram in Figure P2.4 is

x1 x2 x3 f

0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1

The simplest SOP expression is derived as follows:

f = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3
= x1 (x2 + x2 )x3 + x1 x2 (x3 + x3 ) + (x1 + x1 )x2 x3 + x1 x2 x3

= x1
1
x3 + x1 x2
1 + 1
x2 x3 + x1 x2 x3

= x1 x3 + x1 x2 + x2 x3 + x1 x2 x3

2-8
2.26. (a)
x1 x0 y1 y0 f

0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 1
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 1

(b) f = (x1 + y 1 )(x1 + y1 )(x0 + y 0 )(x0 + y0 )

2.27. (a)
x1 x0 y1 y0 f

0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1

(b) Expresi canonik SOP adalah

f = x1 x0 y 1 y 0 + x1 x0 y 1 y 0 + x1 x0 y 1 y0 + x1 x0 y 1 y 0 + x1 x0 y 1 y0 + x1 x0 y1 y 0

+x1 x0 y 1 y 0 + x1 x0 y 1 y0 + x1 x0 y1 y 0 + x1 x0 y1 y0

2-9
 (c) The simplest SOP expression is

f = x1 x0 + y 1 y0 + x1 y 0 + x0 y 1

2.30. LIBRARY ieee ;

USE ieee.std logic 1164.all ;

ENTITY prob2 30 IS
PORT ( x1, x2, x3, x4 : IN STD LOGIC ;
f1, f2 : OUT STD LOGIC ) ;
END prob2 30 ;

ARCHITECTURE LogicFunc OF prob2 30 IS

BEGIN
f1 <= (x1 AND NOT x3) OR (x2 AND NOT x3) OR
NOT x3 AND NOT x4) OR (x1 AND x2) OR
x1 AND NOT x4) ;
f2 <= (x1 OR NOT x3) AND (x1 OR x2 OR NOT x4) AND
x2 OR NOT x3 OR NOT x4) ;
END LogicFunc ;

2.31. For the functions given in this question, it is not true that f 1 = f 2. The function f1 is given in the form (SOP-
term) AND (SOP-term). If these same two SOP terms are used for the different function f1 = (SOP-term)
OR (SOP-term) then for this new f1 it is true that f 1 = f 2 . Complete VHDL code using this new function
f1 is shown below.

LIBRARY ieee ;
USE ieee.std logic 1164.all ;

ENTITY prob2 31 IS
PORT ( x1, x2, x3, x4 : IN STD LOGIC ;
f1, f2 : OUT STD LOGIC ) ;
END prob2 31 ;

ARCHITECTURE LogicFunc OF prob2 31 IS

BEGIN
f1 <= ((x1 AND x3) OR (NOT x1 AND NOT x3)) OR
((x2 AND x4) OR (NOT x2 AND NOT x4)) ;
f2 <= (x1 AND x2 AND NOT x3 AND NOT x4) OR
(NOT x1 AND NOT x2 AND x3 AND x4) OR
(x1 AND NOT x2 AND NOT x3 AND x4) OR
(NOT x1 AND x2 AND x3 AND NOT x4);
END LogicFunc ;

2-10