Boolean Algebra

Boolean algebra is the theory behind digital hardware design. It is restricted to values 1 and 0 instead of from minus infinity to plus infinity in algebra of real values. It is the set of rules which are used to simplify the given logic expression without changing its functionality.

Boolean Algebra
Figure 01 Two Values Boolean Algebra.

Boolean Algebra Rules and Laws

  1. Compliment Rule :

    Complement of A = Ā or A’. So if A =1 then complement of A will be 0.

  2. AND operator

    Consider the two input operation.

    Boolean Algebra

    If you have n number of variables the you will get a 2n possible combination as the output. By referring above truth table we can say that both the operations should be high to give a output high.

    A.A = A

    A.0 = 0

    A.1 = A

    A.Ā = 0 (take the complement of another)

  3. OR operator

    Consider the two input operation. 

    Boolean Algebra                                           

    A + A = A

    A + 0 =  A

    A + 1 =  1

    A + Ā = 1

  4. Distributive Law

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

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

  5. Commutative Law

    A + B = B + A

    A.B = B.A

  6. Associative Law

    A(BC) = (AB)C

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

Operator Precedence.

  1. Parentheses
  2. NOT
  3. AND
  4. OR

De Morgan’s Law

There are two theorems in De Morgan’s Law. In the first theorem Morgan says when two inputs are “AND” and complemented. Then they are equivalent to the OR of the complement of the individual inputs.

Logic operation

Second theorem says when two inputs are “OR” and complemented, then they are equivalent to the AND of the complements of the individual inputs.

Logic operation

Boolean Functions

Boolean function is an algebraic expression consist of binary variables (0 and 1) and the logic operation symbols (+ ; .). for the given value of the binary variables, the function is either 1 or 0. As an example consider the Boolean function

F (x, y, z) = x + y’z

This function is equals to 1 when x= 1 or when y.z =0.1 and is equals to 0 otherwise. This function can be represented in a truth table.

 

Boolean Algebra

Can be transformed into a circuit diagram composed of logic gates.

Boolean Algebra

A Boolean function has a unique truth table. Also it has many algebraic forms which have equivalent logic. Manipulate Boolean function definition according to the rules of Boolean algebra, Why?

  • To obtain a simpler expression
  • Simpler and smaller circuits
  • Low cost

 

Algebraic Manipulation

Example

Draw the circuit for F = XY + X’Z + YZ’ +X’YZ

Boolean Algebra

Let’s simplify the F

F = XY + X’Z + YZ’ +X’YZ

= XY + X’Z + YZ’

= XY (1) + X’Z (1) + YZ'(1)

= XY(Z+Z’) + X’Z(Y+Y’) + YZ'(X+X’)

= XYZ + XYZ’ + X’YZ + X’Y’Z + XYZ’ + X’YZ’= XYZ + XYZ’ + X’YZ + X’Y’Z + X’YZ’

= XY(Z+Z’) + YZ(X+X’) + YZ'(X+X’) + X’Z(Y+Y’) + X’Y(Z+Z’)

= XY (1) + YZ (1) + YZ'(1) + X’Z (1) + X’Y (1)

= (XY+X’Y) + (YZ+YZ’) + X’Z

= Y(X+X’) + Y(Z+Z’) + X’Z

= Y (1) + Y (1) + X’Z

= Y + Y + X’Z

= Y + X’Z

By simplifying you can minimize the number of literals or term in expression. Again draw the circuit for the simplified version.

Boolean Algebra

Here we can see that minimizing the expression allows the designer to use minimum number of components and it reduces the complexity of the circuit. Therefore, can reduce the cost of the design.

Minterms and Maxterms

Minterm: possible product terms

 If 3 variables like X’Y’Z’, X’Y’Z, X’YZ, XY’Z’…. Each AND term is called a Minterms.

  • N variables can be combined to form 2n
  • Minterm is obtained from and AND term of the n variables

Maxterm:  possible sum terms

If 3 variables like X+Y+Z, X+Y+Z’, X+Y’+Z…. Each OR term is called a Maxterm.

  • N variables can be combined to form 2n Maxterms
  • Maxterm is obtained from and OR term of the n variables

Each Maxterm is the complement of its corresponding Minterm and vice versa.

 

Minterm and Maxterm

F1(x, y, z) = x’y’z + xy’z’ + xyz = m1 + m4 + m7

F2(x, y, z) = x’yz + xy’z + xyz’ + xyz = m3 +m5 + m6 + m7

Any Boolean function can be expressed as a sum of Minterms.

 

F1(x, y, z) = x’y’z + xy’z’ + xyz

Complement of F1 is,

F’1 (x, y, z) = x’y’z’ + x’yz’ + x’yz + xy’z + xyz’

Take the complement again + De Morgan’s Theorem,

F1(x, y, z) = (x + y + z) (x + y’ + z) (x + y’ + z’) (x’ + y + z’) (x’ + y’ +z)

                 =M0.M2.M3.M5.M6

Any Boolean Function can be expressed as a product of Maxterms.

Canonical Form

Boolean functions expressed as a sum of Minterms or product of Maxterms are said to be in Canonical Form. Canonical form is not efficient, but sometimes useful in analysis and design. In an expression in canonical form, every variable appears in every form.

F (A, B, C, D) = A B’ C D’ +A’ B C’ D +A B C D

Canonical Form (Sum of Minterms)

Example: express the function f (x, y, z) = x +y’z as a sum of Minterms.                                  If it misses one or more variables u, AND with u +u’

f(x, y, z) = x + y′z
              = x(y + y′)(z + z′) + y′z(x + x′)
              = (xy + xy′)(z + z′) + xy′z + x′y′z
              = xyz + xy′z + xyz′ + xy′z′ + xy′z + x′y′z
              = xyz + xy′z + xyz′ + xy′z′ + x′y′z
              = m7 + m5 + m6 + m4 + m1
              = m1 + m4 + m5 + m6 + m7
              =∑(1, 4, 5, 6, 7)

Canonical Form (Product of Maxterms)

Example: express the function f (x, y, z) = xy +x’z as a sum of Minterms. Use the distributive law, x + yz = (x + y) (x + z). if it misses one or more variables u, OR with uu’.

Canonical form

Conversion between Canonical Forms

If f (x, y, z) =∑ (1; 4; 5; 6; 7),

  • then f′ (x, y, z) =∑(0, 2, 3) = m0 + m2 + m3
  • Apply De Morgan’s theorem to f′,

f (x, y, z) = (m0)(m2)(m3)= M0M2M3= ∏ (0, 2, 3)

General Conversion Procedure

  • Interchange the symbols ⅀ and ℿ and list those numbers missing from the original.
  • n should be known, so that the total number of Minterms or Maxterms (2n) are known, to find missing terms.

Table of Contents

Leave a Comment

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