Chapter 11
Boolean Algebra

© Ray Wisman

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Index to the Rosen text Web site learning resources.

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter11/extra_examples.html - Extra examples with solutions.

11.1 Boolean Functions

Definition

Boolean algebra defines operations for the set {0, 1}.

Commonly used Boolean operations.

Not 1 0 0 1 0 =  1 1 =  0

. And 0 0 0 0 1 0 1 0 0 1 1 1 1 . 1 = 1

+ Or 0 0 0 0 1 1 1 0 1 1 1 1 1 + 1 = 1

Xor 0 0 0 0 1 1 1 0 1 1 1 0

Nor 0 0 1 0 1 0 1 0 0 1 1 0

Nand 0 0 1 0 1 1 1 0 1 1 1 0

Examples

(1 . 0) + 0 = 0	(1 . 0) + 1 = 1	1 Xor (0 Xor 0) = 1
1 Nand 0 = 1	1 Nor 0 = 0	(0 Nor 1) Nor 0 = 1

Question 11.1

(1 . 1) + 1 = ?	(1 . 0) + 0 = ?	1 Xor (0 Xor 1) = ?
1 Nand 1 = ?	0 Nor 0 = ?	(0 Nor 1) Nor 1 = ?

 

Boolean Expressions and Boolean Functions

Definitions

Boolean variable only assumes values from the set {0, 1}.

Bn = {(x1, x2, ..., xn) | xi ∈{0, 1} for 1 ≤ i ≤ n} is the set of all n-tuples of 0s and 1s.

Function from Bn to {0, 1} is a Boolean function of degree n.

Example

B² = {(0, 0), (0, 1), (1, 0), (1, 1)}

B² to {0, 1}

Function from B² to {0, 1}

F(x, y) = x y

Table 1 lists where F(x, y) is 1 and 0.

Example

Function from B³ to {0,1}

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

or, F(x, y, z) = 1 when:

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

Question 11.2.1

F(1, 1, 1) = ?

F(0, 1, 1) = ?

 

Example

2 binary variables have 2² = 4 possible assignments

x	y	Assignment
0	0	0 or 1
0	1	0 or 1
1	0	0 or 1
1	1	0 or 1

Each outcome can be assigned a 0 or 1

Example

4 binary variables have 2⁴ = 16 possible assignments

a	b	c	d	Assignment
0	0	0	0	0 or 1
0	0	0	1	0 or 1
0	0	1	0	0 or 1
0	0	1	1	0 or 1
0	1	0	0	0 or 1
0	1	0	1	0 or 1
0	1	1	0	0 or 1
0	1	1	1	0 or 1
1	0	0	0	0 or 1
1	0	0	1	0 or 1
1	0	1	0	0 or 1
1	0	1	1	0 or 1
1	1	0	0	0 or 1
1	1	0	1	0 or 1
1	1	1	0	0 or 1
1	1	1	1	0 or 1

Example

Below is every possible of 16 functions of 2 Boolean values.

F₁ is tautology

F₂ is Or

F₈ is And

Question 11.2.2

F₉ is ?

 

Identities of Boolean Algebra

Notice that many Boolean identities have logical analogues.

Example

x + y = y + x        Boolean + commutes

p v q ≡ q v p          and so does Logical v

 

Example

Verification of Boolean identities are similar to truth table proofs.

x(y + z) = xy + xz

Question 11.3 - Verify De Morgan's Law:

xy = x + y

 

Duality

Definition

Dual of a Boolean expression interchanges: sums and products 0s and 1s

Example

Dual of:

x(y+0) is x+(y^.1)

(x^.1) + (y+z) is (x+0)(yz)

Example

Construct an identity from the absorption law x(x+y) = x by taking duals.

Duals of both sides

 x(x+y) = x

is

x+(xy) = x

Example

Construct an identity from the commutative law x + y = y + x by taking duals.

Duals of both sides

 x+y = y + x

is

xy = yx

 

Question 11.4 - What is the dual of:

xy = x + y

 

Definition

Dual of a Boolean expression interchanges: sums and products 0s and 1s

 

11.2 Representing Boolean Functions

Sum of Products Expansion

Definition

Sum of products for Boolean function is a Boolean expression constructed by: Where each function result is a 1 form product of all variables sum each product

Example

Find Boolean expressions that represent F and G of Table 1.

F(x,y,z) = xyz                The sum of one product.

G(x,y,z) = xyz + xyz     The sum of two products.

 

Definition 1

Literal is a Boolean variable or its complement. Minterm of the Boolean variables x1, x2, ..., xn is a Boolean product y1, y2, ..., yn where yi=xi or yi=xi

Example

F and G of Table 1 are expressed as sum of minterms.

F(x,y,z) = xyz                The sum of one minterm.

G(x,y,z) = xyz + xyz     The sum of two minterms.

 

Example

Minterm that is 1 for x₁ = 0, x₂ = 0, x₃ = 1, x₄ = 1

x₁x₂x₃x₄ = 1

Example

x y z F G H 0 0 0 0 1  x y z 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1  xyz 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1  xyz 0 1 1 1 1 0 1  xyz 1

Sum of Products   F(x,y,z) = xyz + xyz   G(x,y,z) = x y z + xyz

Question 11.5 - What is H(x,y,z) as sum of minterms (products)?

Question 11.6 - Give the function definition table for:

I(x,y,z) = x y z + x y z + x y z

 

Definition

Sum-of-products expansion is the sum of minterms. Disjunctive normal form is the same as sum-of-products.

Example

Find the sum-of-products for: F(x,y,z) = (x+y)z

F(x,y,z) = (x+y)z     = xz+yz Distributive Law   = xz(y+y) +yz(x+x) Identity and Unit property Law   = xyz+x y z + xyz+xyz Distributive Law   = xy z + xyz + xyz Idempotent Law

Example

Find the sum-of-products for: F(x,y,z) = (x+y)z 

x	y	z	x+y	z	(x+y)z	minterms
0	0	0	0	1	0
0	0	1	0	0	0
0	1	0	1	1	1	x y z
0	1	1	1	0	0
1	0	0	1	1	1	x y z
1	0	1	1	0	0
1	1	0	1	1	1	x y z
1	1	1	1	0	0

F(x,y,z) = (x+y)z  = xy z + xyz + xyz

 

Question 11.7.1  - Find the sum-of-products for: F(x,y,z) = x z + y 

x	y	z	z	xz	xz+y	minterms
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

 

Functional Completeness

Definition

Functionally complete (universal) operators are the set of sum, product and complement, can represent every Boolean function. Nand and Nor operations are also functionally complete alone.

Means circuits of And, Or and Not gates can be replaced with Nor or Nand gates exclusively.

Example

↓ Nor 0 0 1 0 1 0 1 0 0 1 1 0

| Nand 0 0 1 0 1 1 1 0 1 1 1 0

x+y = x ↓ y        Not OR = Nor

xy = x | y           Not AND = Nand

x = x | x    

x = x ↓ x           

Example

                                  
x + y =  x + y =  x  y =  x | y = (x | x)| (y | y)

x	y	x+y	(x | x)	(y | y)	(x | x)| (y | y)
0	0	0	1	1	0
0	1	1	1	0	1
1	0	1	0	1	1
1	1	1	0	0	1

                              
x y =  x y =  x + y =  x ↓ y  )= (x ↓ x)↓(y ↓ y)

x	y	x y	(x ↓ x)	(y ↓ y)	(x ↓ x) ↓ (y ↓ y)
0	0	0	1	1	0
0	1	0	1	0	0
1	0	0	0	1	0
1	1	1	0	0	1

Result is often more operations but can build logic on a chip from a single operation device type, usually more efficient use of chip area.

Question 11.7.2    Complete the following table proving that: 

                     
x y =  x y =   x | y =  (x | y)| (x | y)

| Nand 0 0 1 0 1 1 1 0 1 1 1 0

x y x y x | y x | y (x | y) | (x | y) 0 0         0 1         1 0         1 1

11.3 Logic Gates

Logic gates implement Boolean operations.

All computer logic can be performed using these three logic gates.

x y . And 0 0 0 0 1 0 1 0 0 1 1 1 1 . 1 = 1

x y + Or 0 0 0 0 1 1 1 0 1 1 1 1 1 + 1 = 1

x    Not 1 0 0 1 0 =  1 1 =  0

The following gates implement the Boolean operations above.

 

Multiple input logic gates.

 

Combinations of Gates

The three logic gates can be combined to implement complex logic operations.

Examples

(a) x y x x+y (x+y)x 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 1 0 1 0

Sum-of-products x y

Question 11.8

a. Add the logic produced at the output of each gate.

b. Give the corresponding table.

c. Give the corresponding sum-of-products.

 

Question 11.9

a. Add the logic produced at the output of each gate.

b. Give the corresponding table.

c. Give the corresponding sum-of-products.

 

Question 11.10

a. Using the devices below, give the circuit for:

(x+y)(x y)

b. Using the devices below, give the circuit for:

(xyz)+(x y)

 

 

 

Example of Circuits

Critical processes (e.g. Space Shuttle control) may use majority voting to settle conflicting evidence, two out of three voting in favor win.

A circuit that requires at least two to agree the evidence is true:

x y z xy xz yz xy+xz+yz 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1

 

Example

A room with 3 doors normally has three light switches, flipping any will change lights from ON to OFF, or OFF to ON.

With switches all 0, x y z, light is OFF, 0.

Flipping the z switch, x y z, lights are ON, 1.

 

Adders

Binary numbers are represented in a positional system similar to decimal numbers.

563₁₀ = 5*10² + 6*10¹ + 3*10⁰

1101₂ = 1*2³ + 1*2² + 0*2¹ + 1*2⁰ = 8 + 4 + 1 = 13

10101₂ = 1*2⁴ + 0*2³ + 1*2² + 0*2¹ + 1*2⁰ = 16 + 4 + 1 = 21

Question 11.11.1 - Convert to base 10.

437₁₀ = ?

11₂ = ?

1011₂ = ?

 

Adding decimal numbers carries out 10, 100, 1000, etc. from one column to the next.

Adding binary numbers carries out 10, 100, 1000, etc. (2, 4, 8, etc.) from one column to the next.

11    carry   6710 + 5810  ___  12510    sum

11    carry   012 + 112  ___  1002    sum

111    carry  1012 +1112  ___ 11002    sum

Question 11.11.2

85610 +46710  ____

1012 +0012  ____

11112 +11012  ____

 

Example  Parallel 2-bit adder

Adding 2-bits:

  0 1
 +1 1
 ____
1 0 0

c s₁ s₀

 produces a carry, c, and a 2-bit sum, s₁s₀.

x1	x0	y1	y0	c	s1	s0
0	0	0	0	0	0	0
0	0	0	1	0	0	1
0	0	1	0	0	1	0
0	0	1	1	0	1	1
0	1	0	0	0	0	1
0	1	0	1	0	1	0
0	1	1	0	0	1	1
0	1	1	1	1	0	0
1	0	0	0	0	1	0
1	0	0	1	0	1	1
1	0	1	0	1	0	0
1	0	1	1	1	0	1
1	1	0	0	0	1	1
1	1	0	1	1	0	0
1	1	1	0	1	0	1
1	1	1	1	1	1	0

Question 11.11.3

Give the minterms for c.

There are 16 (2⁴) rows for a 2-bit adder. How many rows for the 64-bit adder in your PC?

 

Example Half-adder

Adding two bits produces a sum bit and a carry out bit.

All possible values of sum and carry out for 1-bit values:

x + y ___ C S a u r m r y

0 x + 0 y ___ 0 0

0 + 1 ___ 0 1

1 + 0 ___ 0 1

1 + 1 ___ 1 0

s = x y  + x y = (x+y)(xy) c = xy

Half-adder

Question 11.12 - What is c and s? Consult the table above.

x + y ___ C S a u r m r y

0 x + 0 y ___

0 x + 1 y ___

1 x + 0 y ___

1 x + 1 y ___

 

Example

Full-adder

Adding two bits and a carry-in produces a sum and carry-out bit.

All possible values for sum and carry out:

ci      x    + y    ___ ci+1  s   0   0 + 0  __ 0 0   0   0 + 1 ___ 0 1   0   1 + 0 ___ 0 1   0   1 + 1 ___ 1 0   1   0 + 0 ___ 0 1   1   0 + 1 ___ 1 0   1   1 + 0 ___ 1 0   1   1 + 1 ___ 1 1 Question 11.13 What is the sum-of-products from Table 4 for ci+1? What is ci+1  and s from Table 4?      ci      x    + y    ___  ci+1  s   0   0 + 0  __   0   0 + 1 ___   0   1 + 0 ___   0   1 + 1 ___   1   0 + 0 ___   1   0 + 1 ___   1   1 + 0 ___   1   1 + 1 ___

Question 11.15 - Determine the above full-adder results. x=1    y=1    ci = 1    Bottom half-adder output = ?            Top half-adder output = ?    s = ? ci+1 = ?

 

Example

Multiple bit adder

Adding two bits and a carry-in (c_i) produces a sum and carry-out (c_i+1) bit.

The carry-out of a lower column (right) is the carry-in of the next column (left).

All possible values for sum and carry out:

ci      x    + y    ___  ci+1  s

0   0 + 0  __ 0 0

0   0 + 1 ___ 0 1

0   1 + 0 ___ 0 1

0   1 + 1 ___ 1 0

1   0 + 0 ___ 0 1

1   0 + 1 ___ 1 0

1   1 + 0 ___ 1 0

1   1 + 1 ___ 1 1

Question 11.16 - For the 1-bit full-adder below, from Table 4, what is:

x=1    y=0    ci = 1    s = ?    ci+1 = ?

 

Adding multiple bits using multiple 1-bit full-adders:

The first carry-in is 0.

Binary     1110 ci      101 x    + 111 y      ____    1 100 ci+1  s

Decimal     110  ci     567    + 685     ___   1 252 ci+1  s

Question 11.17 - What is: c_i+1   s

         c_i
     111 x
   + 101 y
     ____
  
c_i+1  s

 

Full-adders used by connecting the low-order adder carry-in to 0.

1110 ci      111 x    + 101 y      ____    1 100 ci+1  s

 

Half-adder used in lowest order bit because no carry-in.

111  ci      111 x    + 101 y      ____    1 100 ci+1  s

2's complement

Negative values can be represented by defining the left-most bit to be a sign:

0 is positive

1 is negative

2's complement represents a negative number by forming one's complement and adding 1.

0101                                +5

 

1010    1's complement

  + 1

1011    2's complement    -5

 

Question 11.18 - 2's complement of 01101?

 

2's complement allows an adder to perform subtraction and addition.

 1101            -3

+0101            +5

10010             2

The carry out is ignored.

 

Question 11.19

 1011            -5

+0010            +2