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 |

NAND | Yes | |

NOR | 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.

f(f(A,A,A),B,f(B,B,B))=f(A’,B,B’)

=(A’)’+B(B’)’

=A+B

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

**Example to Test your Understanding**

- f(A,B)= A’ + B
- f(A,B)=A’B
- f(A,B,C)=AB+BC+CA
- f(x,y)=x’y+xy’

Ans : No, No, No, No

**More Examples**

- XOR,NOT
- XOR,1,OR
- XOR,1,NOT
- 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= 2 ^{2n-1}**

### Functional Properties

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

### SOP and POS

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…