Studyledge

Processor Architectures and Boolean Algebra: Question 5

Syllabus 15.2

Structured A2 8 marks

(a) Apply De Morgan's laws to write an equivalent expression for

NOT(A.B) + NOT(A+C)

that contains no NOT applied to a bracketed term, and simplify your answer as far as possible, naming any further law you use. [2]

(b) A logic circuit implements the Boolean expression

X = A.B.C + A.B.NOT C + A.NOT B.C

Simplify this expression algebraically to a minimal sum-of-products form, showing each step and naming the Boolean law used at each step. [3]

(c) The truth table for X (as defined in part (b)) is given below.

A B C X
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

(i) Complete the Karnaugh map below for X, using rows for A and columns for BC. [1]

A \ BC 00 01 11 10
0 ? ? ? ?
1 ? ? ? ?

(ii) Draw loop(s) around the appropriate group(s) of 1s in your Karnaugh map, and hence write the minimal sum-of-products expression for X. Confirm that it matches your answer to part (b). [2]

Show worked solution Hide worked solution

Worked solution

Part (a): Applying De Morgan’s laws

De Morgan’s laws state:

  • NOT(X.Y) = NOT X + NOT Y
  • NOT(X+Y) = NOT X . NOT Y

Applying these to each bracketed term of NOT(A.B) + NOT(A+C):

  • NOT(A.B) = NOT A + NOT B (first law, with X = A, Y = B)
  • NOT(A+C) = NOT A.NOT C (second law, with X = A, Y = C)

So:

NOT(A.B) + NOT(A+C) = (NOT A + NOT B) + (NOT A.NOT C)
                     = NOT A + NOT B + NOT A.NOT C

This can be simplified further. The terms NOT A and NOT A.NOT C fit the pattern X + X.Y, which is always equal to X (the absorption law: if X is already true, adding X.Y on top with OR cannot add any new true cases, since X.Y can only be true when X is already true). Here X = NOT A and Y = NOT C, so NOT A + NOT A.NOT C = NOT A, and the third term is absorbed:

NOT A + NOT B + NOT A.NOT C = NOT A + NOT B

Final simplified answer: NOT A + NOT B. [2 marks: 1 for correctly applying De Morgan’s laws to both bracketed terms, 1 for the correct fully simplified answer via absorption]

Part (b): Simplifying X algebraically

Starting expression: X = A.B.C + A.B.NOT C + A.NOT B.C

Step 1, factor A.B from the first two terms (distributive law), then apply the complement and identity laws:

A.B.C + A.B.NOT C = A.B.(C + NOT C)     [distributive law]
                   = A.B.1              [complement law: C + NOT C = 1]
                   = A.B                [identity law: X.1 = X]

So X = A.B + A.NOT B.C.

Step 2. Factor A from the remaining two terms (distributive law):

X = A.B + A.NOT B.C = A.(B + NOT B.C)

Step 3. Simplify B + NOT B.C to B + C:

B + NOT B.C = (B + NOT B).(B + C)       [distributive law: X + Y.Z = (X+Y).(X+Z)]
             = 1.(B + C)                 [complement law: B + NOT B = 1]
             = B + C                     [identity law: 1.X = X]

Step 4. Substitute back and expand (distributive law):

X = A.(B + C) = A.B + A.C

Final minimal sum-of-products: X = A.B + A.C. [3 marks: 1 for correctly reducing A.B.C + A.B.NOT C to A.B using the complement and identity laws, 1 for correctly reducing B + NOT B.C to B + C, 1 for the final correct minimal expression A.B + A.C]

Part (c): Confirming the simplification with a Karnaugh map

(i) Completing the Karnaugh map

Reading the value of X directly from the truth table for each combination of A and BC (using the Gray-code column order 00, 01, 11, 10 so that adjacent columns differ in only one variable):

A \ BC00011110
00000
10111

Row A = 0 is all 0s, since X = 0 whenever A = 0 in the truth table. Row A = 1 is 0 at BC = 00 (A=1,B=0,C=0, where X = 0), and 1 at BC = 01, 11 and 10 (A=1,B=0,C=1; A=1,B=1,C=1; A=1,B=1,C=0, all X = 1 in the truth table). [1 mark for the fully correct K-map]

(ii) Grouping and the minimal expression

Three 1s appear in a row, at BC = 01, 11 and 10 (all in the A = 1 row). Since a Karnaugh map group must have a size that is a power of two, these three 1s are covered using two overlapping groups of two, reusing the middle cell (BC = 11) in both groups. This is a normal and required part of the K-map method:

  • Group 1: BC = 01 and BC = 11 (both in row A = 1). Across these two cells, A = 1 and C = 1 stay fixed, while B changes, so B is eliminated, giving the term A.C.
  • Group 2: BC = 11 and BC = 10 (both in row A = 1). Across these two cells, A = 1 and B = 1 stay fixed, while C changes, so C is eliminated, giving the term A.B.

Combining both groups gives the minimal sum-of-products expression:

X = A.C + A.B = A.B + A.C

This is exactly the same minimal expression found algebraically in part (b), confirming that the algebraic route and the Karnaugh map route agree. [2 marks: 1 for identifying the two correct overlapping groups (or equivalent valid grouping) of adjacent 1s, 1 for the correct final expression A.B + A.C matching part (b)]

Final answers

  • (a) NOT(A.B) + NOT(A+C) = NOT A + NOT B
  • (b) X = A.B.C + A.B.NOT C + A.NOT B.C simplifies to X = A.B + A.C
  • (c)(i) K-map: row A=0 is 0 0 0 0; row A=1 is 0 1 1 1 (for BC = 00, 01, 11, 10)
  • (c)(ii) Groups give A.C and A.B, so X = A.B + A.C, matching part (b)