Chapter 4

Page 66

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

  2. AND and OR identity values

    x x ∧ 1
    0 0
    1 1
    x x ∨ 0
    0 0
    1 1

  3. 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

  4. 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

  5. AND annulment

    x x ∧ 0
    0 0
    1 0

  6. Involution of NOT

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

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

  8. OR annulment value

    x x ∨ 1
    0 1
    1 1

  9. AND and OR complements

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

  10. AND and OR idempotency

    x x∧x
    0 0
    1 1
    x x∨x
    0 0
    1 1

  11. 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

Page 87

  1. 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.