H446 Revision

Quiz

1.4.3 Boolean algebra

  1. How many rows does a truth table need for a logic circuit with three inputs?

    1. 3
    2. 6
    3. 8
    4. 9
    Show answer

    Answer: 8

    Each input can be 0 or 1, so three inputs give 2 × 2 × 2 = 23 = 8 combinations, one row for each.

  2. Which expression is equivalent to ¬(A ∧ B)?

    1. ¬A ∨ ¬B
    2. ¬A ∧ ¬B
    3. A ∨ B
    4. ¬A ∧ B
    Show answer

    Answer: ¬A ∨ ¬B

    By De Morgan's law, negating an AND gives an OR of the negated terms: change the operator and negate each term. ¬A ∧ ¬B negates the terms but keeps the operator, which is a common mistake; it is equivalent to ¬(A ∨ B) instead.

  3. Simplify (A ∨ B) ∧ (A ∨ ¬B).

    1. A
    2. B
    3. A ∧ B
    4. A ∨ B
    Show answer

    Answer: A

    Distribution takes out the common A: A ∨ (B ∧ ¬B). B ∧ ¬B is always 0, so this becomes A ∨ 0, which is A. The output is 1 exactly when A is 1, whatever B is.

  4. A half adder has inputs A = 1 and B = 1. What are its outputs?

    1. Sum = 0, Carry = 1
    2. Sum = 1, Carry = 0
    3. Sum = 1, Carry = 1
    4. Sum = 0, Carry = 0
    Show answer

    Answer: Sum = 0, Carry = 1

    In binary 1 + 1 = 10. The sum is A ⊻ B, which is 0 when both inputs are 1, and the carry is A ∧ B, which is 1.

  5. The data input D of a D-type flip-flop changes from 0 to 1 between two rising edges of the clock. What happens to the output Q?

    1. Q keeps its previous value until the next rising edge of the clock
    2. Q changes to 1 straight away
    3. Q becomes the opposite of D
    4. Q changes value on every clock edge, whatever D is
    Show answer

    Answer: Q keeps its previous value until the next rising edge of the clock

    A D-type flip-flop only copies D to Q on the rising edge of the clock. Between edges, Q holds whatever it stored last, which is what lets it act as one bit of memory. Changing value on every clock edge describes a different circuit, a toggle.

  6. When simplifying with a Karnaugh map, why can three neighbouring 1s in a row not form a single group?

    1. Groups must contain a power-of-two number of cells: 1, 2, 4, 8 or 16
    2. Groups must be square
    3. Groups cannot include cells at the edge of the map
    4. A row can only contain one group
    Show answer

    Answer: Groups must contain a power-of-two number of cells: 1, 2, 4, 8 or 16

    Only groups of 1, 2, 4, 8 or 16 cells correspond to a single simplified term, because each doubling of the group size removes one variable from the term. Three 1s in a row are covered by two overlapping pairs. Groups can be long rectangles as well as squares, and they may wrap around the edges.

  7. A plant-watering pump (P) switches on when the soil is dry (S) and either the timer has run out (R) or the manual button is pressed (M). Which expression describes this?

    1. P ≡ S ∧ (R ∨ M)
    2. P ≡ (S ∧ R) ∨ M
    3. P ≡ S ∨ (R ∧ M)
    4. P ≡ S ∧ R ∧ M
    Show answer

    Answer: P ≡ S ∧ (R ∨ M)

    The pump needs dry soil in every case, so S is joined by AND to the whole of the second condition. "Either the timer or the button" is R ∨ M, and the brackets make sure it is worked out first. Without them, (S ∧ R) ∨ M would run the pump whenever the button is pressed, even in wet soil.

  8. For Q ≡ (A ∧ B) ∨ ¬C, which set of inputs makes Q false?

    1. A = T, B = F, C = T
    2. A = T, B = T, C = T
    3. A = F, B = F, C = F
    4. A = F, B = T, C = F
    Show answer

    Answer: A = T, B = F, C = T

    Q is false only when both parts of the OR are false: A ∧ B must be false and ¬C must be false, so C must be true. With A = T, B = F and C = T, A ∧ B is F and ¬C is F, so Q is F. In the other sets, either both A and B are true or C is false, which makes Q true.

  9. What is the simplest expression for this Karnaugh map?

    BC = 00011110
    A = 01001
    A = 10011
    1. (¬A ∧ ¬C) ∨ (A ∧ B)
    2. ¬C ∨ (A ∧ B)
    3. (¬A ∧ ¬B ∧ ¬C) ∨ (A ∧ B)
    4. (¬A ∧ ¬C) ∨ (A ∧ B) ∨ (B ∧ ¬C)
    Show answer

    Answer: (¬A ∧ ¬C) ∨ (A ∧ B)

    In the A = 0 row, the 1s at BC = 00 and BC = 10 are neighbours because the map wraps around; A is 0 and C is 0 in both, giving ¬A ∧ ¬C. In the A = 1 row, the 1s at 11 and 10 pair up; A and B are 1 in both, giving A ∧ B. These two pairs cover every 1. Grouping the 00 and 10 columns together as ¬C would include the 0 at A = 1, BC = 00. Adding a third pair down the 10 column is not wrong, but it is not the simplest, because those 1s are already covered.

  10. A full adder has inputs A = 1, B = 1 and carry in Cin = 1. What are its outputs?

    1. Sum = 1, Carry out = 1
    2. Sum = 0, Carry out = 1
    3. Sum = 1, Carry out = 0
    4. Sum = 0, Carry out = 0
    Show answer

    Answer: Sum = 1, Carry out = 1

    Adding three 1s gives three, which is 11 in binary. The sum bit is the right-hand 1 and the carry out is the left-hand 1. Using the expressions, S ≡ A ⊻ B ⊻ Cin is 1 because an odd number of inputs are 1, and Cout is 1 because A ∧ B is 1.

  11. A D-type flip-flop holds Q = 0. D changes to 1 while the clock stays low. What is Q now?

    1. 0
    2. 1
    3. It changes back and forth with every change of D
    4. It cannot be known
    Show answer

    Answer: 0

    Q only takes the value of D on a rising edge of the clock. Until the clock rises, Q holds its old value, 0, however D changes.

  12. In a full adder built from two half adders, what joins the two half adders' carry outputs to give the carry out?

    1. An OR gate
    2. An AND gate
    3. A NAND gate
    4. A NOT gate
    Show answer

    Answer: An OR gate

    There should be a carry out if either half adder produces a carry, so the two carries go into an OR gate. An AND gate would only carry when both did, and a NAND gate would give a carry out when neither half adder carries.