"Boolean Algebra & K-maps" — Practice

Question 1

Simplify the expression A + not-A times B.

Accepted Answer

C

Question 2

A three-variable function has the sum-of-products form as the sum of minterms 0, 2, 4 and 6. What is its product-of-sums form?

Accepted Answer

B

Question 3

Which of the following gate sets is NOT functionally complete?

Accepted Answer

C

Question 4

Minimise F(A,B,C,D) as the sum of minterms 0, 1, 4, 5, 10, 11, 14, 15 using a K-map.

Accepted Answer

Lay out a 4-variable map with rows AB and columns CD, both labelled in Gray code order 00, 01, 11, 10.

Minterms 0, 1, 4, 5 all have A = 0 and C = 0. Check: 0 is 0000, 1 is 0001, 4 is 0100, 5 is 0101. In all four, A = 0 and C = 0, while B and D vary freely. That is a legal group of four, giving the term not-A times not-C.

Minterms 10, 11, 14, 15 all have A = 1 and C = 1. Check: 10 is 1010, 11 is 1011, 14 is 1110, 15 is 1111. In all four, A = 1 and C = 1, while B and D vary. That is a second group of four, giving the term A times C.

Every 1 is now covered, and no larger group is possible since the two groups are not adjacent.

The minimal form is F = not-A times not-C + A times C.

This is recognisable as the exclusive-NOR of A and C, which is the complement of A XOR C. The function ignores B and D entirely, and the group size of four eliminating two variables each is what makes that visible.

Question 5

Minimise F(A,B,C,D) as the sum of minterms 1, 3, 7, 11, 15 with don't cares at 0, 2, 5.

Accepted Answer

Place the five 1s and the three don't cares on a 4-variable map.

Minterms 1, 3, 7, 11 and 15 all have D = 1. Check: 1 is 0001, 3 is 0011, 7 is 0111, 11 is 1011, 15 is 1111. Every one has D = 1.

The don't cares at 5 (0101) also has D = 1, so it can be included freely.

However, D = 1 covers eight cells: 1, 3, 5, 7, 9, 11, 13, 15. Of these, 9 and 13 are neither 1s nor don't cares, so a full group of eight is not available.

Group 1, 3, 7 and 5 together with the don't care: these are the four cells with A = 0 and D = 1, giving the term not-A times D.

Group 3, 7, 11 and 15: these are the four cells with C = 1 and D = 1, giving the term C times D.

Every 1 is covered: 1 by the first group, 3 and 7 by both, 11 and 15 by the second.

The minimal form is F = not-A times D + C times D, which factors as D times (not-A + C).

Note the discipline: the don't cares at 0 and 2 were not used, because including them would have required forming groups where D = 0 that cover no genuine 1.

Question 6

Implement F = AB + CD using only two-input NAND gates. How many are required?

Accepted Answer

Use the standard transformation: in a sum-of-products expression, replace every AND with a NAND and every OR with a NAND.

The reason this works is that a NAND is an AND followed by an inversion, and the second-level NAND is an OR with inverted inputs by De Morgan. The two inversions cancel exactly.

Formally: F = AB + CD, and by double negation F equals the complement of the complement of (AB + CD). Applying De Morgan to the inner complement gives the complement of (complement of AB) times (complement of CD).

That is precisely a NAND of two NAND outputs.

So the implementation is: NAND gate 1 computes the complement of AB, NAND gate 2 computes the complement of CD, and NAND gate 3 NANDs those two outputs together.

Three NAND gates are required, and no additional inverters, since neither A, B, C nor D appears complemented in the original expression.

Question 7

For F(A,B,C,D) as the sum of minterms 0, 1, 2, 5, 6, 7, 8, 9, 10, 14, count the prime implicants and the essential prime implicants.

Accepted Answer

Place the ten 1s and find every maximal group.

First look for groups of four. Minterms 0, 2, 8, 10 all have B = 0 and D = 0, forming a corner-style group with wrap-around: the term is not-B times not-D. Minterms 2, 6, 10, 14 all have C = 1 and D = 0: the term is C times not-D. Minterms 0, 1, 8, 9 all have B = 0 and C = 0: the term is not-B times not-C. Minterms 5, 7 combine with 1, 3 only if 3 were present, which it is not, so instead 1, 5 pair on A = 0, C = 0, D = 1, and 5, 7 pair on A = 0, B = 1, D = 1. Minterms 6, 7 pair on A = 0, B = 1, C = 1.

Checking each pair for extension: 1 and 5 extend to 1, 5, 9, 13 only if 13 were present, which it is not, so not-A times not-C times D is prime. Similarly not-A times B times D covering 5 and 7 is prime, and not-A times B times C covering 6 and 7 is prime.

That gives six prime implicants: not-B not-D, C not-D, not-B not-C, not-A not-C D, not-A B D, not-A B C.

Now find the essential ones by looking for 1s covered exactly once. Minterm 14 appears only in C times not-D, so that is essential. Minterm 9 appears only in not-B times not-C, so that is essential. Minterm 7 appears in both not-A B D and not-A B C, so neither is forced by it alone; minterm 5 appears in not-A not-C D and not-A B D.

The count is 6 prime implicants and 2 essential prime implicants.

Question 8

Explain both phases of the Quine-McCluskey method and state why it is preferred over a K-map beyond five variables.

Accepted Answer

Phase one finds all prime implicants. Write every minterm in binary and group the terms by how many ones each contains, so that only adjacent groups need comparing — two terms can differ in exactly one bit only if their one-counts differ by exactly one.

Compare every term in each group with every term in the next group. When two terms differ in exactly one bit position, combine them into a new term with a dash in that position, and tick both originals as having been used.

Repeat the process on the newly formed terms, matching dashes in the same position, until no further combination is possible. Every term left unticked at the end of any round is a prime implicant, since it could not be enlarged.

Phase two selects a minimum cover. Build a chart with prime implicants as rows and the original minterms as columns, marking which implicant covers which minterm. Any column containing exactly one mark identifies an essential prime implicant, because that minterm has no alternative cover. Select all essential prime implicants, delete the columns they cover, and then choose the fewest remaining implicants to cover whatever columns are left.

The advantage over a K-map is that it is purely mechanical and dimension-independent. A K-map depends on visual adjacency, which is manageable for four variables, awkward for five, and effectively impossible beyond six because the geometry can no longer be drawn on paper. Quine-McCluskey has no such limit and can be programmed directly, although the number of comparisons grows quickly enough that heuristic minimisers are used for large real circuits.

Question 9

Prove that NAND alone is functionally complete, and explain what property a single gate must have to be complete.

Accepted Answer

It suffices to construct NOT, AND and OR from NAND alone, since those three generate every Boolean function through canonical sum-of-products form.

NOT: tie both inputs of a NAND to the same signal. The output is the complement of A times A, which is the complement of A. One gate.

AND: a NAND already computes the complement of A times B, so following it with the NOT construction above recovers A times B. Two gates.

OR: by De Morgan, A + B equals the complement of (complement of A times complement of B), which is a NAND applied to the two complements. Each complement costs one NAND, so three gates in total.

With NOT, AND and OR available, any function can be built from its truth table, so NAND is complete.

As to what makes a single gate complete: it must be able to produce a non-monotonic function and a non-linear one. NAND fails to preserve 0, meaning an all-zero input does not give 0 output, and it fails to preserve 1 likewise; it is also non-monotonic and non-self-dual. A gate that preserves 0, or preserves 1, or is monotonic, or is linear in the XOR sense, or is self-dual, cannot be complete on its own, because each of those properties is preserved under composition. NAND and NOR are the only two-input gates that escape all five, which is exactly why they are the only two-input gates that are complete alone.

Practice — "Boolean Algebra & K-maps"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities