Boolean Algebra (OLD) - 12 Computer Sc 04 introduction to Boolean Algebra

 CBSE Class 12 Computer Science 4

introduction to Boolean Algebra
(Boolean Algebra)


Boolean Algebra: is the algebra of logic that deals with binary variables and logic operations.

Boolean Variable: A boolean variable is a symbol, usually an alphabet used to represent a logical quantity. It can have a 0 or 1 value

Boolean Function: consists of binary variable, constants 0 & 1, logic operation symbols, parenthesis and equal to operator.

Complement: A complement is the inverse of a variable and is indicated by a' or bar over the variable. A binary variable is one that can assume one of the two values 0 and 1.

Literal: A Literal is a variable or the complement of a variable

Truth table: is atable which represents all the possible values of logical variables along with all the possible results of the given combinations of values.

List of axioms and theorems:

Identity

  A + 0 = A

  A. 1 = A

Complement

  A + A' = 1

  A. A' = 0

Commutative

  A + B = B + A

  A. B = B. A

Assosiative

  A + (B + C) = (A + B) + C

  A. (B. C) = (A. B). C

Distributive

  A. (B + C) = A. B + A. C

  A + (B. C) = (A + B). (A + C)

Null Element

  A + 1 = 1

  A. 0 = 0

Involution

  (A')' = A

 

Indempotency

  A + A = A

  A. A = A

Absorption

  A + (A. B) = A

  A. (A + B) = A

3rd Distributive 

  A + A'. B = A + B

  

De Morgan's

  (A + B)' = A'. B'

  (A. B)' = A'. B'

(Boolean Functions and Reduce Forms)

A Boolean function can be expressed algebraically from a given truth table by forming a minterm and then taking the OR of all those terms.

Minterm: An n variable minterm is a product term with n literals resulting into 1.

Maxterm: An n variable maxterm is a sum term with n literals resulting into 0.

A sum-of-product expression is logical OR of two or more AND terms

A product-of-sum is logical AND of two or more OR terms

If each term in SOP / POS form contains all the literals, then it is canonical form of expression.

To convert from one canonical form to another, interchange the symbol and list those numbers missing from the original form.

The Karnaugh map (K-map) provides a systematic way of simplifying Boolean algebra expressions.

For minimizing a given expression in SOP form, after filling the k map look for combination of adjascent one's.

Combine these one's in such a way that the expression is minimum.

For minimizing expression in POS form we mark zeros, from the truth table, in the map. Combine zeros in such a way that the expression is minimum.

Sum Term: is a single literal or the logical sum of two or more literals.

Product term: is a single literal or the logical product of two or more literals.

(Application of Boolean Logic)

Gate is an electronic system that performs a logical operation on a set of input signal(s). They are the building blocks of Integrated Circuits.

An SOP expression when implemented as circuit - takes the output of one or more AND gates and OR's them together to create the final output.

An POS expression when implemented as circuit - takes the output of one or more OR gates and AND's them together to create the final output.

Universal gates are the ones which can be used for implementing any gate like AND, OR and NOT, or any combination of these basic gates; NAND and NOR gates are universal gates.

Implementation of a SOP expression using NAND gates only

1) All 1st level AND gates can be replaced by one NAND gate each.

2) The output of all 1st level NAND gate is fed into another NAND gate. This will realize the SOP expression

3) If there is any single literal in expression, feed its complement directly to 2nd level NAND gate. Similarly, POS using NOR gate can be  implemented by replacing NAND by NOR gate.

Implementation of POS / SOP expression using NAND / NOR gates only.

1) All literals in the first level gate will be fed in their complemented form.

2) Add an extra NAND / NOR gate after 2nd level gate to get the resultant output.