Home / Courses / GATE Physics / Practice / Logic gates and Boolean algebra

Logic gates and Boolean algebra

Electronics · 23 questions and templates for GATE Physics, in order from warm-up to top rank. Check each answer, then read the full solution.

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.

  1. MCQWarm-up

    The smallest number of bits that can represent every whole number from 0 to 100 in plain binary is
    1. 6
    2. 7
    3. 8
    4. 10
    Answer and solution

    Answer: B

    n bits cover 0 to 2n−1. 26−1=63 is too small; 27−1=127≥100. So 7 bits (100=11001002).

    Why people get this wrong: Choosing 8 because data usually comes in whole bytes: 7 bits already reach 127.

  2. NATStandard

    A memory chip stores 4 KB, organised as one byte per address (1 KB =1024 bytes). The number of address lines it needs is ______.
    Answer and solution

    Answer: 12

    4 KB =4×1024=4096=212 addresses, and n address lines select 2n locations. So 12 lines. The 8 data lines carry the byte itself and are not part of the count.

    Why people get this wrong: Counting bits (4096×8=215, giving 15) instead of addressable words.

  3. MCQStandard

    In excess-3 code, the decimal digit 5 is written as
    1. 0101
    2. 0010
    3. 0111
    4. 1000
    Answer and solution

    Answer: D

    Excess-3 adds 3 to each decimal digit and writes the result in 4-bit binary: 5+3=8=1000. The code is self-complementing: the 9's complement of a digit is obtained by inverting its bits (4→0111, 5→1000).

    Why people get this wrong: 0101 is plain BCD; 0010 subtracts 3 instead of adding.

  4. NATExam level

    A synchronous counter uses flip-flops with clock-to-output delay 10 ns and setup time 5 ns; the logic that forms each flip-flop's next input adds at most 5 ns. The highest clock frequency at which it works reliably is ______ MHz.
    Answer and solution

    Answer: 50 MHz

    In one clock period the outputs must change (10 ns), ripple through the next-state logic (5 ns) and be stable at the next flip-flop inputs for the setup time (5 ns). Tmin⁡=20 ns, so fmax⁡=1/20 ns=50 MHz. Unlike a ripple counter, this does not grow with the number of bits (as long as the logic delay does not).

    Why people get this wrong: Leaving out the setup time (66.7 MHz) or multiplying by the number of flip-flops as in a ripple counter.

  5. MSQExam level

    Which statements are correct?
    1. A shift register is a sequential circuit.
    2. A multiplexer needs a clock to choose which input to pass.
    3. A latch is level-sensitive, while an edge-triggered flip-flop responds only at a clock edge.
    4. A ROM used as a look-up table is a combinational circuit: its output depends only on the present address.
    Answer and solution

    Answer: A, C, D

    A circuit is sequential if its output depends on past inputs (it has memory). A ROM read is a fixed function of the address: combinational. A shift register stores bits in flip-flops: sequential. A multiplexer is pure gating, with select lines and no clock. A latch is transparent while its enable is active; a flip-flop samples only at an edge.

    Why people get this wrong: A ROM "stores" data, but reading it involves no state that changes with time, so it counts as combinational.

  6. MCQExam level

    A 16-bit ripple-carry adder is built from full adders, each taking 2 ns from carry-in to carry-out. The worst-case time for the carry to settle is about
    1. 32 ns
    2. 2 ns
    3. 8 ns
    4. 64 ns
    Answer and solution

    Answer: A

    In the worst case (e.g. adding 1 to 0111…1) a carry made in the lowest stage must pass through all 16 stages in turn: 16×2=32 ns. Carry-lookahead adders compute the carries in parallel, so their delay grows only as log⁡n; 8 ns is the kind of figure such a design would give.

    Why people get this wrong: Assuming all full adders work at once (2 ns): each one has to wait for the carry from below.

  7. NATHard

    With A as the most significant bit, f(A,B,C,D)=∑m(0,1,2,3,4,6,8,9,10,11,12,14). The total number of literals in its minimal sum-of-products form is ______.
    Answer and solution

    Answer: 2

    Look at the missing minterms: 5,7,13,15, i.e. 0101,0111,1101,1111, which are exactly the rows with B=1 and D=1. So f‾=BD and f=BD=B‾+D‾: two groups of eight on the K-map, two literals in all.

    Why people get this wrong: Grouping into quads (A‾B‾, AB‾, BD‾...) gives a correct but not minimal answer. Looking at the 0s first is often faster.

  8. MSQHard

    Which statements about flip-flops are correct?
    1. The output of a D flip-flop after an active clock edge equals the value of D just before the edge.
    2. A T flip-flop with T=1 divides the clock frequency by 2.
    3. A level-triggered JK latch with J=K=1 can toggle many times while the clock is high (race-around).
    4. An SR flip-flop can safely be given S=R=1.
    Answer and solution

    Answer: A, B, C

    A D flip-flop samples D at the edge: Qn+1=D. A T flip-flop with T=1 toggles once per clock, so its output completes one cycle every two clock cycles. A level-triggered JK latch with J=K=1 keeps toggling as long as the clock stays high, if the clock pulse is longer than the gate delay; edge triggering or master-slave designs fix this. S=R=1 is the forbidden input of an SR flip-flop.

    Why people get this wrong: Race-around is a problem of level triggering, not of the JK idea itself.

  9. MCQHard

    A 4-bit ripple counter uses flip-flops with a propagation delay of 25 ns each. If every count must have settled at all four outputs before the next clock edge, the highest usable clock frequency is
    1. 10 MHz
    2. 40 MHz
    3. 2.5 MHz
    4. 100 MHz
    Answer and solution

    Answer: A

    In a ripple counter each flip-flop is clocked by the one before, so the worst case (e.g. 0111→1000) needs all four to toggle one after another: 4×25=100 ns. The clock period must be at least that, so fmax⁡=1/(100 ns)=10 MHz. A synchronous counter avoids the build-up because all flip-flops share one clock.

    Why people get this wrong: Using one flip-flop delay (40 MHz) and forgetting that the delays add up along the ripple chain.

  10. MCQHard

    Two 8-bit two's complement numbers are added. Overflow (a wrong signed result) has occurred exactly when
    1. there is a carry out of the most significant bit
    2. the carry into the most significant bit differs from the carry out of it
    3. the two numbers have opposite signs
    4. the sum is negative
    Answer and solution

    Answer: B

    Overflow happens only when two numbers of the same sign give a sum of the other sign. That is the same as saying the carry into the sign bit and the carry out of it differ (V=C7⊕︎C8). A carry out alone is harmless: e.g. −1+1 gives a carry out and the correct answer 0. Numbers of opposite sign can never overflow.

    Why people get this wrong: Treating the carry-out bit as the overflow flag; that is right only for unsigned numbers.

  11. MSQHard

    With A the most significant bit, f(A,B,C,D)=∑m(1,3,7,11,15)+d(0,2,5), where d lists don't-care terms. Which statements are correct?
    1. CD+A‾D is a minimal sum-of-products form of f.
    2. CD+A‾B‾ is also a minimal sum-of-products form of f.
    3. Every minimal sum-of-products form of f has three product terms.
    4. Every minimal form must treat the don't-care m0 as 1.
    Answer and solution

    Answer: A, B

    CD covers 3,7,11,15. Only m1 is left. It can be covered by A‾D (cells 1,3,5,7, using don't-care 5) or by A‾B‾ (cells 0,1,2,3, using don't-cares 0 and 2); both are two-literal terms, so both two-term forms are minimal (A, B true, C false). The form CD+A‾D leaves m0 at 0, so D is false.

    Why people get this wrong: Assuming the minimal form is unique, or that don't-cares must all be used.

  12. NATHard

    A linear-feedback shift register made of 5 flip-flops, with XOR feedback chosen for the longest possible sequence, steps through ______ different states before repeating.
    Answer and solution

    Answer: 31

    Five bits have 25=32 states. With XOR feedback the all-zeros state maps to itself, so it can never be part of the main cycle. A maximal-length (primitive-polynomial) LFSR visits all the others: 25−1=31 states. Such registers make pseudo-random bit sequences and CRC checks.

    Why people get this wrong: Answering 32: the all-zero state is a lock-up state, not part of the cycle.

  13. MCQHard

    The circuit Y=AB+A‾C, built as two AND gates into an OR gate, can glitch (a brief 0) when B=C=1 and A changes. The extra product term that removes this static hazard is
    1. AC
    2. A‾B
    3. BC
    4. ABC‾
    Answer and solution

    Answer: C

    With B=C=1, Y=A+A‾=1, but as A changes one AND gate turns off before the other turns on (the inverter adds delay), so Y can dip. The consensus term BC equals 1 throughout that change and holds the output high. Logically AB+A‾C+BC=AB+A‾C (consensus theorem), so the function is unchanged; only the timing improves.

    Why people get this wrong: Minimising the expression removes exactly the redundant term that prevents the glitch.

  14. MSQHard

    Which of these sets of operations are functionally complete (able to build every Boolean function)?
    1. {NAND}
    2. {AND,OR}
    3. {AND,NOT}
    4. {XOR,AND,the constant 1}
    Answer and solution

    Answer: A, C, D

    NAND alone gives NOT (AA) and AND (NAND then NOT), and hence OR by De Morgan. AND with NOT gives OR as A‾B‾. XOR with the constant 1 gives NOT (A⊕︎1=A‾), and with AND that is complete. AND and OR alone can only build functions that never fall when an input rises (monotone functions); they can never make NOT.

    Why people get this wrong: Thinking AND and OR are enough because sums of products use them: the complements of the variables are needed as well.

  15. MSQTop rank

    Consider F(A,B,C)=A⊕︎B⊕︎C. Which statements are correct?
    1. F is self-dual: its dual function equals F.
    2. No two 1s of F are adjacent on its K-map, so its minimal SOP has four terms of three literals each.
    3. F can be built from two two-input XOR gates.
    4. F is the carry output of a full adder.
    Answer and solution

    Answer: A, B, C

    Dual: Fd(A,B,C)=F(A‾,B‾,C‾). Complementing all three inputs flips the parity (odd number of flips), so F(A‾,B‾,C‾)=F‾ and Fd=F. On the K-map the 1s (minterms 1, 2, 4, 7) form a checkerboard: changing any one input changes F, so no cells can be grouped and F=A‾B‾C+A‾BC‾+AB‾C‾+ABC. (A⊕︎B)⊕︎C uses two XOR gates. F is the SUM of a full adder; the carry is the majority function.

    Why people get this wrong: Parity functions are the worst case for K-maps: no grouping is possible at all.

  16. NATTop rank

    Three D flip-flops are clocked together with D2=Q1, D1=Q0 and D0=Q‾2. Starting from Q2Q1Q0=000, the number of distinct states in the sequence before it repeats is ______.
    Answer and solution

    Answer: 6

    Apply the rule Q2Q1Q0→Q1Q0Q‾2 step by step: 000→001→011→111→110→100→000. Six states. This is a 3-bit Johnson (twisted-ring) counter; with n flip-flops it has 2n states, and the other two (010, 101) form a separate unused loop.

    Why people get this wrong: Answering 23=8 assumes a binary counter; a ring with one inversion gives 2n.

  17. MCQTop rank

    The expression Y=AB+A‾C+BC simplifies to
    1. AB+BC
    2. A‾C+BC
    3. A+C
    4. AB+A‾C
    Answer and solution

    Answer: D

    The term BC is the consensus of AB and A‾C: whenever BC=1, either A=1 (then AB=1) or A=0 (then A‾C=1). So it adds nothing: BC=BC(A+A‾)=ABC+A‾BC, which is absorbed by AB and A‾C. Y=AB+A‾C.

    Why people get this wrong: The redundant term is the one that does NOT contain the variable appearing both plain and barred.

  18. NATTop rank

    Two 8-bit two's complement numbers, 01100100 and 01010000, are added in an 8-bit adder and the carry out is discarded. Read as an 8-bit two's complement number, the result is ______ in decimal.
    Answer and solution

    Answer: -76

    The numbers are 100 and 80. Their true sum 180 is above 127, the largest 8-bit signed value. The adder gives 10110100, whose top bit is 1: as a signed number it is 180−256=−76. Two positive numbers giving a negative result is the sign of OVERFLOW.

    Why people get this wrong: Answering 180 ignores the 8-bit range: the hardware cannot hold it.

  19. NATTop rank

    A Boolean function of A, B, C is called symmetric if swapping any two inputs never changes it (so it depends only on how many inputs are 1). The number of different symmetric functions of three variables is ______.
    Answer and solution

    Answer: 16

    A symmetric function is fixed by its value for each possible count of 1s: 0,1,2 or 3. That is 4 independent choices of 0 or 1, giving 24=16 functions (among them the constants, AND, OR, majority and XOR of all three). In general there are 2n+1 symmetric functions of n variables, against 22n=256 functions of three variables in all.

    Why people get this wrong: Counting 223=256 (all functions) or 23=8 (input rows).

← All topics · Timed mock test →