Digital Logic Important Topics and Concepts for GATE CS/IT

Find most important Digital logic topics and short notes for GATE CS/IT which you can use for quick revision. I prepared this article to make it easy for Quick Revision. I will keep updating this post with important and easy things that you should definately study for GATE Exam.

Actual GATE Exam Weightage of Digital Logic- 3 to 5 Marks

Topics Covered

  • Logic Gates
  • Functionally complete Operations
  • Dual and Complements of functions
  • De Morgan’s Law
  • Self Dual function
  • Functional Properties
  • SOP and POS
  • Number of NAND, NOR Gate Required- Table
  • K Map
  • Mux, Demux
  • Encoder, Decoder
  • Flip Flops
  • Number System

Logic Gates

Associativity Cummutative
AND Yes Yes
OR Yes Yes
XOR Yes Yes
XNOR Yes Yes

Important Points for XOR and XNOR:

  • For n bit input, if number of 1’s are odd then XOR Output = 1
  • For n bit input, if number of 0’s are Even then XNOR Output = 1

Important Result:

When n is Odd :  XOR=XNOR

When n is Even :  XOR=(XNOR)c

Functionally Complete Operations

A set of operation is functionally complete or universal if and only if every switching function can be expressed by means of operation on it.

{OR,complement} – Functionally Complete

{AND,complement} – Functionally Complete

Note: A Set is set to be functionally complete if we can derive a set which is already functionally complete.

Example: f (A,B,C)= A’+ BC’

Solution: modify this function as f(A,A,A) we will get A’+AA’=A’ . So, we can get complement by puting (A,A,A)

Now, we have to get either AND or OR by using combination of A,B,C. Here we can also use complement form of A,B,C because we have already shown above that complement will exist for this function.




we got OR and Complement, Hence it is functionally complete.

Example to Test your Understanding

  1. f(A,B)= A’ + B
  2. f(A,B)=A’B
  3. f(A,B,C)=AB+BC+CA
  4. f(x,y)=x’y+xy’

Ans : No, No, No, No

More Examples

  1. XOR,NOT
  2. XOR,1,OR
  3. XOR,1,NOT
  4. XNOR,1,NOT

Ans: No, Yes, No, No

Hint: To solve this part make functions.

For Ex: XOR can be written as f(x,y)=x’y+xy’

Note: XOR and XNOR are not functionally complete.

Dual and Complements of a function

How to Make Dual:

  • Replace AND with OR
  • Replace OR with AND
  • Replace 0 with 1
  • Replace 1 with 0

How to do complement:

  • Replace AND with OR
  • Replace OR with AND
  • Replace 0 with 1
  • Replace 1 with 0
  • Negate Variables

So difference between dual and complement is that in complement we also negate variables.

De Morgans law

( A ∪ B) = A ∩ B
( A ∩ B) = A ∪ B

Self Dual functions

Self Dual function means:

  • Neutral function and
  • function do not contain two mutually exclusive term (means if AB contain in function then its variables complement (i.e A’B’) should not contain in function)

Number of Self dual function= 22n-1

Functional Properties

Click Here to Download my Notes on this Topic (3 Pages)


Click Here to Download my Notes on this Topic (3 Pages)

Number of NAND,NOR Gate Required

Number of NAND Gate Number of NOR Gate
Half Adder 5 5
Full Adder 9 9
Half Subtractor 5 5
Full Subtractor 9 9
XOR 4 5
XNOR 5 4
AND 2 3
OR 3 2

Next Topic is Minimization – To be Added Soon…

About Anup Patel

Anup PatelM.Tech Student at Indian Institute of Science
AIR 2 ISRO SC Written Test Dec 2017
AIR 142 GATE 2018

Leave a Reply

Your email address will not be published. Required fields are marked *