Axioms and Laws of Boolean Algebra

Boolean Algebra

Axioms and Laws of Boolean Algebra

Boolean algebra devised in 1864 by George Boole, is a system of mathematical logic. It is an algebraic system consisting of a set of element (0,1) associated with a Boolean variable and two binary operators AND and OR and a uniry operator NOT. In mathematics, an identity is a statement true for all possible values of its variable or variables.

  1. Axioms
    1.           AND Operation

0.0=0

0.1=0

1.0=0

1.1=1

2. OR Operation

0+0=0

0+1=1

1+0=1

1+1=1

3.  NOT Operation

0’ = 1

1’ = 0

Identities:

In mathematics, an identity is a statement true for all possible values of its variable or variables.

Identity Boolean Relation Symbol
Additive Identity A + 0 = A
A + 1 = 1
A  + A = A
A + A’ = 1
Multiplicative Identity A . 0 = 0
A . 1 = A
A . A = A
A . A’ = 0

To Summerize:

 

Double Complemeting
(A’)’ = A

Complementation Law

0′  =  1   ; If A = 0 then A’  = 1

1′  =  0    ; If A = 1 then A’  = 0

Properties

Another type of mathematical identity, called a “property” or a “law,” describes how differing variables relate to each other in a system of numbers

1.  The Commutative Property

we can reverse the order of variables that are either added together or multiplied together without changing the truth of the expression:

 

A+B = B+A

 A.B=B.A

The Associative Property

This property tells us we can associate groups of added or multiplied variables together with parentheses without altering the truth of the equations.

 

For Addition

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

For Multiplication

A(BC) = (AB)C  = (AC)B

The Distributive Property

A(B+C) = AB + AC

Rules for Simplification:

Rule-1  (Absorption Law)

A + AB = A

Proof:

A + AB

A (1 + B)

A.1        ( Applying  A + 1  = 1)

A

Rule-2:           A + A’B   = A  +  B

Proof:

 A     +    A’ B

= A+AB  +  A’B     (Applying A+ AB = A)

= A + B ( A + A’)           (Applying A + A’ = 1)

= A + B

 

Rule-3 for simplifying POS

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

(A+B)(A+C)

=AA + AC  + BA + BC        ; Applying distributive law

= (A   + AC)   + AB  + BC      ; Applying A+ AB=A

=      (A     +    AB)    + BC

=               A          +    BC

To summarize, here are the three new rules of Boolean simplification expounded in this section:

A  + AB = A

A + A’B = A+ B

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

Consensus Theorem

Theorem-1: AB + AC’ + BC = AB + A’C

Proof:

AB + A’C + BC

AB + A’C +BC(A+A’)

AB + A’C + ABC + A’BC

AB + ABC + A’C + A’BC

AB(1+C)  + A’C (1+B)         ; Using identity Law A+1=1

AB   +    A’C

AB + A’C + BC  =  AB   +    A’C   Prooved

Theorem-2: (A+B)(A’+C)(B+C) = (A+B)(A’+C)

Proof:

LHS    (A+B)(A’+C)(B+C)

(AA’ +AC +A’B + BC)(B+C)

(AC++A’B+BC)(B+C)

ABC +A’BB + BBC + ACC + A’BC + BCC

ABC +A’B   + BC  + AC + A’BC + BC

BC(A+1)  + A’B(1+C) +AC + BC

                     BC           +  A’B      + AC   + BC

(BC + BC) + A’B  + AC

AC + A’B + BC

(A+B)(A’+C)(B+C) = AC + A’B + BC  Proved

Transposition Theorem

Theorem   AB + A’C = (A+C) (A’+B)

Proof

RHS

(A+C)(A’+B)

AA’ + AB + A’C + AB

0  + A’C + AB + BC

A’C  + AB + BC(A+A’)

A’C  + AB  + ABC  + A’BC

AB(1+C) + A’C(1+B)

AB  +  A’C  Prooved

 

Quiz 

This quiz is for logged in users only.


  1. The output of the combinational circuit given below is : (in 2016)
    1. A + B + C
    2. A(B+C)
    3. B(A+C)
    4. C(A+B)
  2. The minimum number of 2-input NAND gates required to implement a 2-input XOR gate is : (GATE 2016)
    1. 4
    2. 5
    3. 6
    4. 7
  3. In the circuit shown, diodes D1, D2, D3 are ideal and the inputs E1, E2 and E3 are “0V” for logic ‘0’ and “10V” for logic ‘1’. What logic gate does the circuit represent? (GATE 2015)
    1. 3-input OR gate
    2. 3-input NOR gate
    3. 3-input AND gate
    4. 3-input XOR gate
  4. The Boolean expression (x+y)(x+y’)+({(xy)+x’}’ simplifies to: (GATE 2014)
    1. X
    2. Y
    3. Xy
    4. X+y
  5. In the circuit shown in figure, if C=0, the expression for Y is :                                 (GATE 2014)
    1. Y= AB’ +A’B
    2. Y=A+B
    3. Y=A’+B’
    4. Y=AB
  6. If A and B are Boolean variables, then what is (A+B)(A+B’) equals to?
    1. B
    2. A
    3. A+B
    4. AB
  7. What does the expression AD +ABCD + ACD +A’B + AC’D +(AB)’ on minimization results into ?
    1. A+D
    2. AD + A’
    3. AD
    4. A’ + D
  8. Which of the following algebra rule is correct?
    1. A.A’ = 1
    2. A + AB = A + B
    3. A + A’B = A + B
    4. A(A+B) = B
  9. The output of a logic gate is ‘1’ when all its inputs are ‘0’, the gate is either:
    1. a NAND or an X-OR gate
    2. a NOR or an X-NOR gate
    3. an OR gate or an X-OR gate
    4. an AND gate or an X-NOR gate
  10. The Boolean expression A+ BC is reduced form of which of the following:
    1. AB + BC
    2. A’B + AB’C
    3. (A + B)(A +C)
    4. None of the above
  11. The output of the given circuit is..

  1. ‘1’
  2. zero
  3. X
  4. X’
  5. 12

12. Which is the Boolean expression from the truth table shown below?

  1. B(A + C)(A’ + C’)
  2. B(A + C’)(A’ + C)
  3. B'(A + C) (A’ + C)
  4. B'(A + C) (A’ + C’)

13. When the Boolean function F(A,B,C) = Σm(0,1,2,3)+(4,5,6,7) is minimised. What does one get?

  1. ‘1’
  2. ‘0’
  3. A
  4. C

14. Which of the following statement is not correct?

  1. X + X’Y = x
  2. X(X’ + Y) = XY
  3. XY + XY’ = X
  4. ZX + ZX’Y = ZX + ZY

15. A,B,C are three boolaen variables. Which of the following Boolean expressions cannot be minimised further?

  1. Z = A.B’.C’ + A.B.C’ + A.B.C + A’.B’.C’
  2. Z = A.B’.C + A.B.C’ + A.B.C + A’.B’.C’
  3. Z = A.B’.C’ + A’.B’.C + A.B.C + A’.B.C’
  4. Z = A’.B.C’ + A.B.C’ + A.B.C + A’.B’.C

16. The minimised form of logical expression (A’B’C’ + A’BC’ +A’BC +ABC’) is ..

  1. A’.B’ + B.C’ + A’.B
  2. A’.C’ + B’.C + A’.B
  3. A’.C + B’.C + A’.B
  4. A.C’ + B’.C + A.B’

 

 

 

Leave a Reply

Top
error: Content is protected !!