Chapter 4

1. Associativity of AND and OR is shown in Tables 4-3 and 4-4 in the book.

   • AND and OR identity values

     x	x ∧ 1
     0	0
     1	1

     x	x ∨ 0
     0	0
     1	1

   • AND and OR commutativity

     x	y	x∧y	y∧x
     0	0	0	0
     0	1	0	0
     } 1	0	0	0
     1	1	1	1

     x	y	x∨y	y∨x
     0	0	0	0
     0	1	1	1
     } 1	0	1	1
     1	1	1	1

   • AND distributive over OR

     x	y	z	(y∨z)	(x∧y)	(x∧z)	(x∧(y∨z)	(x∧y)∨(x∧z)
     0	0	0	0	0	0	0	0
     0	0	1	1	0	0	0	0
     0	1	0	1	0	0	0	0
     0	1	1	1	0	0	0	0
     1	0	0	0	0	0	0	0
     1	0	1	1	0	1	1	1
     1	1	0	1	1	0	1	1
     1	1	1	1	1	1	1	1

   • AND annulment

     x	x ∧ 0
     0	0
     1	0

   • Involution of NOT

     x	(¬x)	¬(¬x)
     0	1	0
     1	0	1

   • OR distributive over AND is shown in Table 4-5 in book.

   • OR annulment value

     x	x ∨ 1
     0	1
     1	1

   • AND and OR complements

     x	¬x	x ∧ ¬x
     0	1	0
     1	0	0

     x	¬x	x ∨ ¬x
     0	1	1
     1	0	1

   • AND and OR idempotency

     x	x∧x
     0	0
     1	1

     x	x∨x
     0	0
     1	1

2. De Morgan’s law

   x	y	(x∧y)	¬(x∧y)	¬x	¬y	¬x ∨ ¬y
   0	0	0	1	1	1	1
   0	1	0	1	1	0	1
   1	0	0	1	0	1	1
   1	1	1	0	0	0	0

   x	y	(x∨y)	¬(x∨y)	¬x	¬y	¬x ∧ ¬y
   0	0	0	1	1	1	1
   0	1	1	0	1	0	0
   1	0	1	0	0	1	0
   1	1	1	0	0	0	0

3. Let a 4-bit integer be wxyz where each literal represents one bit. The even 4-bit integers are given by the function:

   F(w,x,y,z) = (¬w ∧ ¬x ∧ ¬y ∧ ¬z) ∨ (¬w ∧ ¬x ∧ y ∧ ¬z) ∨ (¬w ∧ x ∧ ¬ y ∧ ¬z) ∨ (¬w ∧ x ∧ y ∧ ¬z) ∨ (w ∧ ¬x ∧ ¬y ∧ ¬z) ∨ (w ∧ ¬x ∧ y ∧ ¬z) ∨ (w ∧ x ∧ ¬y ∧ ¬z) ∨ (w ∧ x ∧ y ∧ ¬z)

   Using the distributive property repeatedly we get:

   F(w,x,y,z) = ¬z ∧ ((¬w ∧ ¬x ∧ ¬y) ∨ (¬w ∧ ¬x ∧ y) ∨ (¬w ∧ x ∧ ¬ y) ∨ (¬w ∧ x ∧ y) ∨ (w ∧ ¬x ∧ ¬y) ∨ (w ∧ ¬x ∧ y) ∨ (w ∧ x ∧ ¬y) ∨ (w ∧ x ∧ y))

             = ¬z ∧ (¬w ∧ ((¬x ∧ ¬y) ∨ (¬x ∧ y) ∨ (x ∧ ¬ y) ∨ (x ∧ y)) ∨ w ∧ ((¬x ∧ ¬y) ∨ (¬x ∧ y) ∨ (x ∧ ¬ y) ∨ (x ∧ y)))

             = ¬z ∧ (¬w ∨ w) ∧ ((¬x ∧ ¬y) ∨ (¬x ∧ y) ∨ (x ∧ ¬ y) ∨ (x ∧ y))

             = ¬z ∧ (¬w ∨ w) ∧ (¬x ∧ (¬y ∨ y) ∨ x ∧ (¬ y ∨ y))

             = ¬z ∧ (¬w ∨ w) ∧ (¬x ∨ x) ∧ (¬ y ∨ y)

   And from the complement property we arrive at a minimal sum of products:

   F(w,x,y,z) = ¬z

   a simple NOT gate with the least significant bit as input.

4. Using a Karnaugh map,

   

   We get the equation:

   F(x,y,z) = (¬z) ∨ (¬x ∧ ¬y) ∨ (x ∧ y)

5. Using a Karnaugh map,

   

   We get the equation:

   ¬F(x,y,z) = (¬x ∨ ¬y) ∧ (¬y ∨ ¬z) ∧ (y ∨ z)

6. xy horizontal

   

7. xz horizontal

   

8. Five variables

   

9. The single-digit prime numbers are 2, 3, 5, and 7. Using four bits to represent them:

   F(w,x,y,z) = (¬w ∧ ¬x ∧ y ∧ ¬z) ∨ (¬w ∧ ¬x ∧ y ∧ z) ∨ (¬w ∧ x ∧ ¬ y ∧ z) ∨ (¬w ∧ x ∧ y ∧ z)

   Assuming that the numbers 0, 1, 10, 11, 12, 13, 14, and 15 will never occur, we can use a Karnaugh map to simplfy the equation:

   

   This gives us the minimization:

   F(w,x,y,z) = (¬w ∧ ¬x) ∨ (x ∧ z)