Boolean Expressions

Boolean Expressions

Boolean expressions are constructed by connecting the Boolean constants and variables with the Boolean operations. These Boolean expressions are also known as Boolean formulas. We use Boolean expressions to describe switching function or Boolean functions. For example, if the Boolean expression (A + ) C is used to describe the function f, then Boolean function is written as

  f(A, B, C) = (A + B) C or  f = (A + ) C

Based on the structure of Boolean expression, it can be categorized in different formulas. One such categorization are the normal formulas. Let us consider the four–variable Boolean function.

In this Boolean function the variables are appeared either in a complemented or an uncomplemented form. Each occurrence of a variable in either a complemented or an uncomplemented form is called a literal. Thus, the above Boolean function 2.6.1 consists of six literals. They appear in the product terms. A product term is defined as either a literal or a product (also called conjunction) of literals.

Function 2.6.1 contains three product terms, namely, A,  C and A C . Let us Cand AC consider another four variable Boolean function.

The above Boolean function consists of seven literals. Here, they appear in the sum terms. A sum term is defined as either a literal or a sum (also called disjunction) of literals. Function 2.6.2 contains three sum terms, namely, (B + ), (A +  + C) and ( + C). The literals and terms are arranged in one of the two standard forms:

• Sum of product form (SOP) and

• Product of sum form (POS).

In these standard forms, the terms that form the function may contains one, two or any number of literals.

 

1. Sum of Product Form

The words sum and product are derived from the symbolic representations of the OR and AND functions by + and (addition and multiplication), respectively. But we realize that these are not arithmetic operators in the usual sense. A product term is any group of literals that are ANDed together. For example, ABC, XY and so on. A sum term is any group of literals that are ORed together such as A+ B+ C, X + Y and so on. A Sum of Products (SOP) is a group of product terms ORed together. Some examples of this form are :

 Each of these sum of products expressions consist of two or more product terms (AND) that are ORed together. Each product term consists of one or more literals appearing in either complemented or uncomplemented form. For example, in the sum of products expression ABC+  A, the first product term contains literals A, B and C in their uncomplemented form. The second product term contains B and C in their complemented (inverted) form. The sum of product form is also known as disjunctive normal form or disjunctive normal formula.

 

2. Product of Sum Form

A product of sums is any groups of sum terms ANDed together. Some examples of this form are :

Each of these product of sums expressions consist of two or more sum terms (OR) that are ANDed together. Each sum term consists of one or more literals appearing in either complemented or uncomplemented form. The product of sum form is also known as conjunctive normal form or conjunctive normal formula.

 

3. Canonical SOP and Canonical POS Forms

We can realize that in the SOP form, all the individual terms do not involve all literals. For example, in expression AB + AB the first product term do not contain literal C. If each term in SOP form contains all the literals then the SOP form is known as canonical SOP form. Each individual term in the standard SOP form is called minterm. One canonical sum of products expression is as shown in Fig. 2.6.1.

If each term in POS form contains all the literals then the POS form is known as canonical POS form. Each individual term in the canonical POS form is called maxterm. One canonical product of sums expression is as shown in Fig. 2.6.2.

 

4. Converting Expressions in Canonical SOP or POS Form

Sum of product form can be converted to canonical sum of products by ANDing the terms in the expression with terms formed by ORing the literal and its complement which are not present in that term. For example for a three literal expression with literals A, B and C, if there is a term AB, where C is missing, then we form term (C + ) and AND it with AB. Therefore, we get AB (C + ) = ABC + AB.

1. Steps to Convert SOP to Canonical SOP Form

Step 1 : Find the missing literal in each product term if any.

Step 2 : AND each product term having missing literal/s with term/s form by ORing the literal and its complement.

Step 3 : Expand the terms by applying distributive law and reorder the literals in the product terms.

Step 4 : Reduce the expression by omitting repeated product terms if any. Because A+ A = A.

Examples for Understanding

Example: 1

Convert the given expression in canonical SOP form. ƒ (A, B, C) = AC + AB + BC

Solution :

Step 1 : Find the missing literal/s in each product term.

Step 2 : AND product term with (missing literal + its complement).

Step 3 :

Expand the terms and reorder literals.

Expand : f (A, B, C) = ACB+ AC + ABC + AB + BCA + B C 

Reorder : f (A, B, C) = ABC + AC + ABC + AB + ABC + BC

Note : After having sufficient practice student should expand product term and reorder literals in it in a single step.

Step 4 :

Omit repeated product terms.

Example: 2

Convert the given expression in canonical SOP form. f (A, B, C) = A + ABC

Solution :

Step 1: Find the missing literal/s in each product term.

f (A, B, C) = A + ABC

Step 2 :

AND product term with (missing literal + its complement)

Step 3 :

Expand the terms and reorder literals.

Step 4 :

Omit repeated product term

Examples with Solutions

Example: 3

Define canonical form. Express F = BC' + AC in a canonical SOP form.

Solution :

Example: 4

Convert the Boolean expression AB'C+B'CD + AC'D to canonical SOP form.

Solution :

Examples for Practice

Example: 5

Express the following function in canonical SOP form

Example: 6

Determine the canonical SOP form of 

2. Steps to Convert POS to Canonical POS Form

Step 1 : Find the missing literals in each sum term if any.

Step 2 : OR each sum term having missing literal/s with term/s form by ANDing the literal and its complement.

Step 3 : Expand the terms by applying distributive law and reorder the literals in the sum terms.

Step 4 : Reduce the expression by omitting repeated sum terms if any. Because  A . A = A.

Examples for Understanding

Example: 7

Convert the given expression in canonical POS form.

f (A, B, C) = (A + B) (B + C) (A + C)

Solution :

Step 1: Find the missing literal/s in each sum term

Step 2 : OR sum term with (missing literal • its complement)

Step 3 :  Expand the terms and reorder literals

Expand :

Since A + BC = (A + B) (A + C) we have,

     f (A, B, C) = (A+B+C) (A + B + ) (B + C + A) (B + C + )  (A + C + B) (A + C + )

Reorder :

f (A, B, C) = (A + B + C) (A + B + ) (A + B + C) (Ā + B + C) ( + B + C) (A +  + C)

Step 4 : Omit repeated sum terms

f (A, B, C) (A + B + C) (A + B + C) (Ā + B + ) ( +  + C) 

Example: 8

Convert the given expression in canonical POS form. Y=A . (A+B+C)

Solution :

Step 1: Find the missing literal/s in each sum term

Step 2 : OR sum term with (missing literal •  its complement)

Step 3 :  Expand the terms and reorder literals

Since A + BC = (A + B) (A + C) we have,

Step 4 : Omit repeated sum terms

Examples with Solutions

Example: 9

Convert the given expression in canonical POS form.

f(A, B, C) = (A + B) • (B + C)

Solution :

Example: 10

Convert SOP to equivalent POS.

A'B'C + A'B'C +A'BC +AB'C +ABC

Solution :

Example: 11

Convert (A + B) (A + C) (B +) into canonical POS form.

Solution :

Step 1: OR sum term of missing literal

f(A, B, C) = [(A+B) + (C • )] [(A+ C) + (B• )] [(B + ) + (A • )]  

Step 2 : Expand the terms and reorder literals.

 f(A, B, C) = (A+B+C) (A+B+) (A+B+C) (A++C) (A+B+) (+B+)

Step 3 : f(A, B, C)  = (A+B+C) (A+B+) (A++C) (+B+) 

Example: 12

Obtain the canonical POS for F(A, B, C) = (A+B') (B+C) (A+C')

Solution :

Example for Practice

Example: 13

Convert the given expression in canonical POS form

 

5. M Notations : minterms and maxterms

Each individual term in canonical SOP form is called minterm and each individual term in canonical POS form is called maxterm. The concept of minterms and maxterms allows us to introduce a very convenient shorthand notations to express logical functions. Table 2.6.1 gives the minterms and maxterms for a three literal/variable logical function where the number of minterms as well as maxterms is 2³ = 8. In general, for an n–variable logical function there are 2ⁿ minterms and an equal number of maxterms.

As shown in Table 2.6.1 each minterm is represented by m_i and each maxterm is represented by M_i where the subscript i is the decimal number equivalent of the natural binary number. With these shorthand notations logical function can be represented as follows :

    

                      = П M (1, 3, 6)

where Σ denotes sum of product while II denotes product of sum.

We know that logical expression can be represented in the truth table form. It is possible to write logic expression in canonical SOP or POS form corresponding to a given truth table. The logic expression corresponding to a given truth table can be written in a standard sum of products form by writing one product term for each input combination that produces an output of 1. These product terms are ORed together to create the canonical sum of products. The product terms are expressed by writing complement of a variable when it appears as an input 0, and the variable itself when it appears as an input 1. Consider, for example, the truth Table 2.6.2.

The product corresponding to input combination 010 is B, the product corresponding to input combination 011 is ĀBC and product corresponding to input combination 110 is BC. Thus the canonical sum of products form is

                   =  m₂   +   m₃   +   m₆

The logic expression corresponding to a truth table can also be written in a canonical product of sums form by writing one sum term for each output 0. The sum terms are expressed by writing complement of a variable when it appears as an input 1 and the variable itself when it appears as an input 0. Consider, for example, the truth Table 2.6.3.

The sum corresponding to input combinations 010 is A +  + C, and the sum corresponding to input 101 is  + B + . Thus, the canonical product of sum form is

f (A, B, C) = (A +  + C) ( + B + ) 

                  = M₂ • M₅

 

6. Complements of Standard Forms

The POS and SOP functions derived from the same truth table are logically equivalent. In terms of minterms and maxterms we can then write

f (A, B, C)  =  m₀ + m₁ + m₃ + m₄ + m₆ + m₇

                   = M₂ + M₅

f (A, B, C)  = Σm (0, 1, 3, 4, 6, 7)

                    = π M (2,5)

From the above expressions we can easily notice that there is a complementary type of relationship between a function expressed in terms of maxterms. Using this complementary relationship we can find logical function in terms of maxterms if function in minterms is known or vice–versa. For example, for a four variables if

        f (A, B, C, D) = Σ m (0, 2, 4, 6, 8, 10, 12, 14)

then f (A, B, C, D) = л M(1, 3, 5, 7, 9, 11, 13, 15)

Examples with Solutions

Example: 14

Express the switching function f_(BA) = A in terms of minterms.

Solution :

f_(BA) = A = A (B+) = AB+ A

Example: 15

Express F = A + B'C as sum of minterms.

Solution :

F = Σ m (1, 4, 5, 6, 7)

Example: 16

Prove that the logical sum of all minterms of a Boolean function of 2 variables is 1.

Solution  :

For two variables A and B minterms are :

= 1

Example: 17

Express the Boolean function F = XY + Z in product of maxterm.

Solution :

Example: 18

Express the Boolean function as

1) POS form 2) SOP form

D= (A'+B) (B' + C)

Solution :

 

Review Questions

1. Define switching function.

2. Define literal, product term and sum term.

3. Explain sum of product form.

4. Define SOP and POS terms

5. What do you mean by standard SOP and POS forms?

6. Explain how to convert SOP or POS expressions in their standard forms.

7. What do you mean by minterms and maxterms ?

8. Differentiate between min term and max term.