Combinational logic
Electronics · 81 questions and templates for GATE Physics, in order from warm-up to top rank. Check each answer, then read the full solution.
New to this topic? Read the lesson first: Combinational logic.
Loading questions… (they need JavaScript; nothing you type is sent anywhere)
Written questions with solutions
The same questions as a list, so you can print them or read without the practice box. Templates (fresh numbers) appear only in the practice box above.
-
MCQWarm-up
How many different Boolean functions of three variables are there?- 8
- 64
- 256
- 512
Answer and solution
Answer: C
Three variables give rows in the truth table, and each row can be 0 or 1 independently: functions. In general .Why people get this wrong: 8 is the number of rows (minterms), not of functions.
-
MCQWarm-up
A binary decoder with 4 input lines (and an enable) has how many output lines?- 16
- 8
- 4
- 32
Answer and solution
Answer: A
An -to- decoder activates exactly one output for each of the input codes: outputs, each one a minterm of the inputs.Why people get this wrong: An encoder goes the other way, from lines to .
-
MCQWarm-up
The value of is- 0
- 1
Answer and solution
Answer: D
and always differ, and XOR is 1 exactly when its inputs differ. So , while .Why people get this wrong: Mixing it up with .
-
NATWarm-up
A 16:1 multiplexer is built as a tree of 2:1 multiplexers only. The number of 2:1 multiplexers needed is ______.Answer and solution
Answer: 15
The first level pairs the 16 inputs with 8 multiplexers (select bit ), then 4, then 2, then 1: .Why people get this wrong: Answering 4 (the number of select lines) or 8 (only the first level).
-
MCQWarm-up
A half adder adds bits and . Its sum and carry outputs are- sum , carry
- sum , carry
- sum , carry
- sum , carry
Answer and solution
Answer: B
: the sum bit is 1 only when exactly one input is 1 (XOR), and the carry is 1 only when both are (AND).Why people get this wrong: The OR gets wrong.
-
MSQWarm-up
Which of these sets of operations are functionally complete (can build any Boolean function)?- {AND, NOT}
- {OR, NOT}
- {AND, OR}
- {XOR, AND, constant 1}
Answer and solution
Answer: A, B, D
AND and NOT give OR through De Morgan, so {AND, NOT} is complete; likewise {OR, NOT}. With XOR and the constant 1, , so NOT and AND are available. {AND, OR} alone can only make monotone functions: it can never produce a NOT.Why people get this wrong: AND and OR feel like "everything", but without inversion you cannot make .
-
MCQWarm-up
The complement of isAnswer and solution
Answer: C
By De Morgan, . Every OR becomes AND and every literal is complemented, keeping the grouping: the product becomes the sum .Why people get this wrong: loses the brackets; the AND with must apply to the whole of .
-
NATStandard
The function is simplified to a minimal sum of products. The total number of literals in it is ______.Answer and solution
Answer: 2
The minterms 0000, 0010, 1000, 1010 are the four corners of the K-map. They share and while and take all values, so : two literals.Why people get this wrong: Missing that the corners are adjacent (the map wraps around in both directions).
-
MCQStandard
The function simplifies toAnswer and solution
Answer: C
Minterms 1, 3, 5, 7 are exactly the odd numbers: the last bit is 1 and , take all values. So .Why people get this wrong: Reading the bit order backwards and answering .
-
NATStandard
How many prime implicants does have?Answer and solution
Answer: 6
On the 3-variable K-map the ones form a ring: each 1 has exactly two neighbouring 1s and no group of four exists. The pairs are (0,1), (1,5), (5,7), (6,7), (2,6), (0,2): six prime implicants, none essential. Such a function is called cyclic.Why people get this wrong: Counting only the terms of one minimal cover (3).
-
MCQStandard
For the cyclic function , a minimal sum of products has how many product terms?- 2
- 3
- 4
- 6
Answer and solution
Answer: B
Six ones, and each prime implicant covers two, so at least 3 terms are needed; 3 suffice, for example (or the other alternate set ). Two minimal answers exist, both with 3 terms and 6 literals.Why people get this wrong: Using all six prime implicants.
-
MCQStandard
The carry output of a full adder with inputs , and carry-in can be written asAnswer and solution
Answer: D
A carry comes out when at least two inputs are 1: , the majority function. Grouping: either and both generate it (), or exactly one of them is 1 and propagates the incoming carry (). The two forms are equal.Why people get this wrong: is the sum output.
-
NATStandard
A 4-bit ripple-carry adder uses full adders whose carry output settles 2 ns after its inputs and whose sum output settles 3 ns after its inputs. With all inputs applied at , the most significant sum bit is guaranteed correct after ______ ns.Answer and solution
Answer: 9 ns
The carry ripples through the first three stages: ns until the carry into the last stage is correct. That stage then needs 3 ns for its sum: ns.Why people get this wrong: Counting four carry delays plus a sum delay (11 ns): the last stage's carry-out is not needed for its own sum.
-
MCQStandard
The 8-bit two's-complement number 1111 1011 represents- 251
Answer and solution
Answer: C
The sign bit is 1, so the value is negative. Invert and add 1: . The number is . (Unsigned it would be 251 .)Why people get this wrong: reads it as sign-magnitude.
-
MSQStandard
Which identities hold for the exclusive-OR operation?Answer and solution
Answer: A, B, C
XOR is addition modulo 2: associative, , and adding 1 flips a bit. The last identity fails for , , : left side , right side . (AND does distribute over XOR: .)Why people get this wrong: Distributivity works one way only: AND over XOR, not XOR over AND.
-
MCQStandard
The 4-bit Gray code for the binary number 1011 is- 1101
- 1110
- 0111
- 1011
Answer and solution
Answer: B
Keep the first bit and XOR each pair of neighbouring bits: , , , . Gray code 1110. Successive Gray codes differ in one bit, which is why shaft encoders and K-map axes use it.Why people get this wrong: XORing with the wrong neighbour (shifting the other way).
-
NATStandard
The decimal numbers 47 and 38 are added in BCD with 4-bit binary adders. In how many of the two digit positions must the correction "add 0110" be applied?Answer and solution
Answer: 1
Units: , more than 9, so add 0110: , digit 5 with a carry. Tens: , valid, no correction. Result 85, with one correction.Why people get this wrong: Forgetting the carry into the tens digit, or correcting a valid digit.
-
MCQStandard
The hexadecimal number in decimal isAnswer and solution
Answer: A
. Digits after the point carry negative powers of the base, so the is , not .Why people get this wrong: Reading the fractional digit as a decimal tenth gives .
-
NATStandard
As a function of the four variables , the expression has ______ minterms.Answer and solution
Answer: 10
alone is true for of the 16 input combinations; for ; both () for . By inclusion-exclusion, minterms.Why people get this wrong: Adding counts the two minterms with twice.
-
NATExam level
The minimal sum-of-products form of contains ______ literals in total.Answer and solution
Answer: 4
Minterms 0, 2, 8, 10 are the four corners: . Minterms 5, 7, 13, 15 form the central square: . So , 4 literals. and do not matter at all.Why people get this wrong: Grouping in pairs instead of quads gives 12 literals.
-
MCQExam level
A minimal sum-of-products form of isAnswer and solution
Answer: A
covers 3, 7, 11, 15 (an essential prime). Minterm 1 is left. Using the don't-cares 0 and 2, the quad (0, 1, 2, 3) covers it with two literals. (, using don't-care 5, is an equally small alternative.) alone would include 9 and 13, which must be 0.Why people get this wrong: Not using don't-cares to enlarge a group, or using a don't-care to include a real 0.
-
MCQExam level
The minimal sum of products of isAnswer and solution
Answer: A
Prime implicants (with the don't-cares): (3, 7, 11, 15), (2, 3, 10, 11), (9, 11, 13, 15) and (1, 3, 9, 11). Minterm 7 is covered only by , 2 only by , and 13 only by : all three are essential and together cover everything. .Why people get this wrong: is a prime implicant but not needed; dropping leaves 7 uncovered.
-
MCQExam level
A 4:1 multiplexer has select lines (most significant) and ; its data inputs are , , , . The function it realises isAnswer and solution
Answer: A
. In minterms of : ; ; gives 110 and 111 = 6, 7. So .Why people get this wrong: Swapping and on the first two inputs gives .
-
MCQExam level
A 3-to-8 decoder has its outputs 1, 2, 4 and 7 joined by an OR gate. The resulting function of the inputs , , isAnswer and solution
Answer: C
Each decoder output is a minterm, so the OR gives : inputs 001, 010, 100, 111, exactly those with an odd number of ones. That is odd parity, (the full-adder sum).Why people get this wrong: The majority function (carry) is .
-
MSQExam level
The circuit for is built from AND gates and an OR gate, with an inverter making . Which statements are correct?- With , a change of can produce a brief 0 glitch at the output (a static-1 hazard)
- Adding the consensus term removes this hazard
- The glitch arises because and reach the OR gate through paths of different delay
- Reducing the expression to fewer terms is the standard cure for hazards
Answer and solution
Answer: A, B, C
With , in theory. But when falls, the term may drop before the term rises (the inverter adds delay): a momentary 0. The redundant consensus term stays 1 throughout and holds the output. Hazard-free design adds terms; it does not remove them.Why people get this wrong: A minimal expression is not necessarily glitch-free.
-
NATExam level
In a carry-lookahead adder adding and , each bit has propagate and generate . The number of bit positions with is ______.Answer and solution
Answer: 3
: three positions propagate. : bit 1 generates. Then , , : the sum is (11 + 6 = 17).Why people get this wrong: Using OR for propagate is also allowed for carries, but then the count would be 4.
-
NATExam level
A CMOS chip has gates, each switching an average load of fF, with activity factor (fraction of gates switching per cycle), at V and GHz. Its dynamic power is ______ W.Answer and solution
Answer: 5 W (±0.01)
Each switching event charges and discharges through the transistors, costing per cycle. W. Halving the voltage would quarter it.Why people get this wrong: Using (the energy stored) instead of (energy drawn from the supply per full cycle).
-
MCQExam level
A logic family has V, V, V and V. Its high and low noise margins are- both 0.4 V
- high 0.4 V, low 0.8 V
- high 2.0 V, low 0.4 V
- both 1.2 V
Answer and solution
Answer: A
V; V. Noise smaller than this cannot turn a valid output into an invalid input.Why people get this wrong: Subtracting output from output or input from input.
-
NATExam level
A Boolean function is self-dual if it equals its dual: . The number of self-dual functions of 3 variables is ______.Answer and solution
Answer: 16
The 8 input rows pair up as and its complement (4 pairs). Choosing on one row of a pair fixes it on the other. So there are self-dual functions, in general.Why people get this wrong: Answering (all functions) or 8.
-
MCQExam level
A 4-to-2 priority encoder gives input the highest priority. With , its output is- 01
- 11
- 00
- 10
Answer and solution
Answer: D
The highest-priority active input is (since ), so the output is the code of 2: . is ignored. A valid-output flag distinguishes " active" from "nothing active".Why people get this wrong: Encoding the lowest active input (01).