Boolean algebra is an algebraic structure defined on a set of elements together with two binary operators (+) and (.)

- A
**variable**is a symbol, for example,*Α,*used to represent a logical quantity, whose value can be**0**or**1**. - The
**complement**of a variable is the inverse of a variable and is represented by an overbar, for example ' .' - A
**literal**is a variable or the complement of a variable.

**Closure: **For any x and y in the alphabet A, x + y and x.y are also in A.

**Boolean Value**

The value of the Boolean variable can be either 1 or 0. The base for this number system is 2.

**Boolean Operators**

There are four Boolean operators

- AND (∙) operator = The output will be like Y= (A.B)

A | B | Y |

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

- OR (+) operator= The output will be like Y= (A + B)

A | B | Y |

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1 |

- NOT (A') operator= The output will be like Y= Complement of A

A | Y |

0 | 1 |

1 | 0 |

**XOR (⊕****) operator**= The output will be like

A | B | Y |

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

It is also known as inequality checking gate.

A | B | Y |

0 | 0 | 1 |

1 | 0 | 0 |

0 | 1 | 0 |

1 | 1 | 1 |

**It is also known as equality checking gate.**

**Operator Precedence**

The operator for evaluating Boolean expression is

- Parenthesis
- NOT
- AND
- OR.

**Duality**

If an expression contains only the operations AND, OR and NOT. Then, the dual of that expression is obtained by replacing each AND by OR, each OR by AND, all occurrences of 1 by 0, and all occurrences of 0 by 1. Principle of duality is useful in determining the complement of a function.

Example:Logic expression: (*x *•*y' *•*z*)* + *(*x *•*y *•*z' *)* + *(*y *•*z*) + 0 ,

Duality of above logic expression is: (*x* + *y'* + *z*) • (*x* + *y* + *z'* ) • (*y* + *z*) • 1

Literals remain same while calculating the above expression.

**Boolean Function**

- Any Boolean functions can be formed from binary variables and the Boolean operators •, +, and
*'*(for AND, OR, and NOT, respectively). - For a given value of variable, the function can take only one value either 0 or 1.
- A Boolean function can be shown by a truth table. To show a function in a truth table we need a list of the 2
^{n}combinations of 1's and 0's of the n binary variables and a column showing the combinations for which the function is equal to 1 or 0. So, the table will have 2^{n}rows and columns for each input variable and tile final output. - A function can be specified or represented in any of the following ways:
- A truth table
- A circuit
- A Boolean expression
- SOP (Sum Of Products)
- POS (Product of Sums)
- Canonical SOP
- Canonical POS

**Important Boolean operations over Boolean values:**

**Table of Some Basic Theorems**

**Important Theorems used in Simplification**

- NOT-Operation theorem:
- AND-Operation theorem:
- OR-Operation theorem:

- Distribution theorem: A + BC = A (A + B)(A + C)

**Note:**

- Demorgan's Theorem:
- Transposition Theorem: (A + B) (A + C) = A + BC
- Consensus Theorem: This theorem is used to eliminate redundant term. It is applicable only when if a boolean function contains three variables. Each variable used two times. Only one variable is complemented or uncomplemented. Then the related terms so that complemented or uncomplemented variable is the answer.

**Universal Logic Gate:** A gate is considered as universal logic gate if it is capable to obtain all the operations just by using that single gate. The two universal logic agtes are NAND, NOR.

**NAND**: AND followed by NOT

it is represented by (↑).

The output will be like Y=

The truth table will be

A | B | Y |

0 | 0 | 1 |

1 | 0 | 1 |

0 | 1 | 1 |

1 | 1 | 0 |

**NOR:**OR followed BY NOT

It is represented by (↓).

The truth table will be

A | B | Y |

0 | 0 | 1 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 0 |

No of Gate Required:

Operations | NAND Gates Needed | NOR Gates Needed |

NOT | 1 | 1 |

OR | 3 | 2 |

AND | 2 | 3 |

XOR | 4 | 5 |

ExNOR | 5 | 4 |

You can follow the detailed champion study plan for GATE CS 2021 from the following link:

**Detailed GATE CSE 2021 Champion Study Plan**

Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with Test Series check the following link:

## Click Here to Avail GATE CSE Test Series!(100+ Mock Tests)

Get unlimited access to 21+ structured Live Courses all 112+ mock tests with Online Classroom Program for GATE CS & PSU Exams:

## Click here to avail Online Classroom Program for Computer Science Engineering

**Thanks**

## Comments

write a commentHanika KashyapMay 9, 2017

Vipul AhujaAug 14, 2017

Poojitha SudabattulaNov 25, 2017

ashwin kadelFeb 19, 2018

Gaurav RaulFeb 26, 2018

Rakesh NamaSep 21, 2019

Pages from Digital Logic (CSE, EE, ECE).pdfAkash YadavSep 26, 2019

Pratiksha UdawantDec 8, 2019

BasheeraJun 8, 2020

Vijay GaikwadSep 20, 2020