Vectors and Vector Operations



1.3 Boolean Algebra

Regular algebra is concerned with algebraic expressions that have the same value when any numerical values are substituted for the variables. For example,

x2 - 16 = (x - 4)(x + 4)

=

No matter what numerical value we substitute for x in x2 - 16 and (x - 4)(x + 4), we get the same thing. This is helpful when we are solving equations.

Boolean algebra is concerned with logical expressions that have the same value when any logical values are substituted for the variables. For example, in the previous section we showed that

(pq)' = p' + q'

which is one of De Morgan's formulas. No matter what logical values (1 or 0) we substitute for p and q in (pq)' and p' + q' we get the same thing. This is helpful when we are designing logic circuits and doing other things with logical expressions.

In the previous section we looked at the eight logical operations: and, or, not, exclusive-or, nand, nor, if-then and if-and-only-if. In this section we shall look at the algebra of these operations. Recall, from the last section

a logical expression is a combination of logical variables and logical operators

For example, (p + q)(pq)' and pq' + p'q are logical expressions. Often we use a capital letter, e.g. P or Q, to denote a logical expression. For example, we might write P = (p + q)(pq)' or Q = pq' + p'q. In the following we shall just say expression for logical expression if there is no danger of confusion with other types of expressions such as arithmetic expressions or mixed arithmetic/logical expressions.

Expressions are equivalent if they give the same result for every possible combination of logical values for the logical variables appearing in them.

This occurs precisely if they have the same truth table. We write P = Q if P and Q are equivalent. In the previous section we showed that (p + q)(pq)' = pq' + p'q.

Boolean algebra is the algebra of these equivalences. An equivalence is also called an identity.

Some of the equivalences that we showed in the previous section were the following.

p ( q = (p + q)(pq)' = pq' + p'q

(1) p nand q = (pq)' = p' + q'

(2) p nor q = (p + q)' = p'q'

p ( q = p' + q

(3) p ( q = (p ( q)(q ( p) = (p ( q)' = p ( q'

The right equivalences in (1) and (2) are called the DeMorgan laws. Here is a list of some useful identities in Boolean algebra. The DeMorgan identities on the right of (1) and (2) are included as formulas (7) in this list.

(4) pq = qp p + q = q + p commutative laws

(5) p(qr) = (pq)r p + (q + r) = (p + q) + r associative laws

(6) p(q + r) = pq + pr p + (qr) = (p + q)(p + r) distributive laws

(7) (pq)' = p' + q' (p + q)' = p'q' DeMorgan’s laws

(8) p1 = p p + 0 = p identity laws

(9) p0 = 0 p + 1 = 1 domination laws

(10) pp = p p + p = p idempotent laws

(11) pp' = 0 p + p' = 1 negation laws

(12) (p')' = p double negation law (or involution law)

One of the main reasons we are interested in equivalences is because they give us alternative ways to design logic circuits.

Example 1. Consider the circuit at the right whose output is r = q + p'q'.

If we use the second distributive law in (7) and (11) and (8) we have

r = q + p'q' = (q + p')(q + q') = (q + p')(1) = q + p'

So a simpler circuit to produce r is the one at the right.

Example 2. Consider the circuit at the right whose output is r = q + p'q.

If we use the first distributive law in (7) and (8) and (9) we have

r = q + p'q = (1)(q) + p'q = (1+ p')q = (1)(q) = q

So a simpler circuit to produce r would be q ((( r = q.

For more applications of Boolean algebra to logic design, see Fundamentals of Logic Design by Charles H. Roth, Jr. (published by Thomson).

Some of the equivalences in the list (4) – (12) follow directly from the definition. Consider pq = qp. The left side pq is 1 only if both p and q are 1. The right side qp is 1 only if both q and p are 1. However both p and q are 1 precisely if both q and p are 1. So pq and qp are 1 under the same circumstances. So pq = qp.

The equivalences that are less obvious can be shown to be true using truth tables.

Example 3. Show the first distributive law is valid.

One way is simply to make the truth table; see right. Note that both p(q + r) and pq + pr are true precisely in the last three rows.

However, we can save ourselves some work if we argue as follows. First consider the case where p = 0. Then p(q + r) = 0(q + r) = 0 since anything and'ed with 0 is 0. On the other hand pq + pr = 0q + 0r = 0 + 0 = 0. So p(q + r) and pq + pr are the same if p = 0. Now consider the case where p = 1. Then p(q + r) = 1(q + r) = q + r since anything and'ed with 1 is unchanged. On the other hand pq + pr = 1q + 1r = q + r. So p(q + r) and pq + pr are the same if p = 1. So they are the same in all cases.

The equivalences (4) – (11) are examples of dual pairs of equivalences. Every logical expression has a dual expression that is obtained by interchanging and and or and 0 and 1. For example, the dual of the expression p(q + r) is p + qr. One way to get the dual of an expression is to do the following three steps.

1. complement the expression

2. Use the DeMorgan laws

3. Replace each variable by its complement

For example, if we do that with p(q + r) we get the following.

p(q + r) (p(q + r))' p' + (q + r)'

p' + q'r' p + qr

If two expressions are equivalent then the duals of the two expressions are equivalent. So in each of the equivalence (4) – (11) the right equivalence follows from the left and vice-versa.

Example 4. Go through this argument to prove the commutative law for "or" from the commutative law for "and".

We start with the commutative law for and, i.e. pq = qp. Next we not both sides giving (pq)' = (qp)'. Next we use the first DeMorgan law giving p' + q' = q' + p'. Since this holds for all p and q we can replace p by p' and q by q', giving p'' + q'' = q'' + p''. Finally we use (12) which gives p + q = q + p.

In this argument we used some properties of equivalences that we usually use without taking note that we are actually using them. Here are three useful properties of equivalences.

First, suppose P = Q and P and Q contain the logical variable p and R is another expression. If we replace all occurrences of p in P and Q by R the resulting expressions are equivalent. In symbols

(13) if P = Q then P//p(R = Q//p(R

Here P//p(R denotes the expression obtained by replacing all occurrences of p in P by R and similarly for Q//p(R. We used (13) to go from p' + q' = q' + p' to p'' + q'' = q'' + p''.

Second, suppose P = Q and R is another expression containing P within it. If we replace some occurrences of P in R by Q then the resulting expression is equivalent. In symbols

(14) if P = Q then R/P(Q = R

Here R/P(Q denotes the expression obtained by replacing some, but not necessarily all, occurrences of P in R by Q. We used (14) to go from p'' + q'' = q'' + p'' to p + q = q + p.

Third, two expressions equivalent to the same expression are equivalent. In symbols

(15) if P = Q and Q = R then P = R

The commutative and associative laws are similar in structure to the commutative and associative laws in regular algebra. So is the first of the two distributive laws in (6), i.e. p(q + r) = pq + pr. However, the second, p + (qr) = (p + q)(p + r), is not true in regular algebra. This is one thing that distinguishes Boolean algebra from regular algebra. The reason p + (qr) = (p + q)(p + r) is called a distributive law is because it is obtained from the first distributive law p(q + r) = pq + pr by interchanging + and ..

Problem 1. Show the second distributive law is valid. Either make a truth table or consider separately the cases p = 0 and p = 1.

Let’s look at some examples of the two distributive laws.

Example 1. Suppose

p = “the Pistons win”

q = “the Lions win”

r = “the Red Wings win”

Then the statement

(16) The Pistons win and either the Lions win or the Red Wings win

has the form p(q + r). The distributive law p(q + r) = pq + pr says that (16) is equivalent to

(17) Either both the Pistons and Lions win or both the Pistons and Red Wings win

Both statements are valid in the following three situations.

The pistons win, the Lions lose, the Red Wings win

The pistons win, the Lions win, the Red Wings lose

The pistons win, the Lions win, the Red Wings win

Example 2. On a certain river there are two sets of rapids. To go past the first set of rapids boats must go through lock A. For the second set of rapids boats can choose between lock B and lock C.

To get by both sets of rapids boats must go through lock A and either lock B or lock C. So to get by both sets of rapids the following statement must be true.

(18) Lock A is working and either lock B is working or lock C is working.

If we let

p = "Lock A is working"

q = "Lock B is working"

r = "Lock C is working"

then (18) has the form p(q + r). By the first distributive law this is equivalent to pq + pr. Thus an alternative condition for a boat to get by both sets of is the following statement be true.

Either both locks A and B are working or both locks A and C are working.

The algebra of exclusive-or. In many cases and, or and not are regarded as the most basic of the logical operations and expressions involving the other operations are reduced to expressions involving and, or and not. In which case the identities (4) – (12) play an important role. However, in some cases it is convenient to work with exclusive or instead of regular or. In that case the following identities involving exclusive or are useful. Some of these are similar to regular or while others are different.

(19) p ( q = q ( p commutative

(20) p ( (q ( r) = (p ( q) ( r associative

(21) p(q ( r) = pq ( pr distributive

(22) p ( 0 = p zero is an identity

(23) p ( p = 0 p is its own inverse

(24) p ( 1 = p' exclusive or'ing with 1 inverts

(25) p ( p' = 1

(19), and (22) – (25) can be proved using the definition of exclusive or. For example, the commutative property is true since p ( q is 1 if exactly one of p and q is 1 and the same is true for q ( p. Similarly, p ( 0 is 1 if exactly one of p and 0 is 1, i.e. if p is 1.

The associative and distributive properties can be shown to be true either using truth tables or by expressing exclusive or in terms of and, or and not using p ( q =  pq' + p'q and using (4) – (12).

Example 3. Prove that exclusive or satisfies the associative law.

Solution. Again, one way is to use truth tables. Here is a truth table for p ( (q ( r).

We can see that

(26) p ( (q ( r) = 1 precisely if an odd number of p, q and r are 1

Now consider (p ( q) ( r. Using the commutative property for exclusive or, one has (p ( q) ( r = r ( (p ( q). The right side has the form p ( (q ( r) but p, q and r are replace by r, p and q respectively. From (26) it follows that r ( (p ( q) is 1 if an odd number of r, p and q are 1. However, this occurs if an odd number of p, q and r are 1. So p ( (q ( r) and (p ( q) ( r are both 1 if an odd number of p, q and r are 1. So they are equivalent.

Another way to show exclusive or is associative is to consider separately the cases p = 0 and p = 1. If p = 0 then p ( (q ( r) = 0 ( (q ( r) = q ( r by (23). On the other hand (p ( q) ( r = (0 ( q) ( r = q ( r which is the same as p ( (q ( r). If p = 1 then p ( (q ( r) = 1 ( (q ( r) = (q ( r)' = q ( r by (24) and (3). On the other hand (p ( q) ( r = (1 ( q) ( r = q' ( r = q ( r by (3). So they are the same if p = 1.

Remark 1. Because exclusive or satisfies the associative law we usually don't use parentheses if we are exclusive or'ing more than two things. For example, we write p ( q ( r for both p ( (q ( r) and (p ( q) ( r.

Remark 2. (26) can be generalized to the following

(27) p1 ( p2 ( … ( pn = 1 precisely if an odd number of p1, p2, …, pn are 1

Let's show that this holds for n = 4. The proof of the general case is the same. Consider p ( q ( r ( s. We want to show that

(28) p ( q ( r ( s = 1 precisely if p ( q ( r ( s has an odd number of 1's

There are four cases. The first case is when p ( q ( r has an even number of 1's and s = 0. Then p ( q ( r = 0 and p ( q ( r ( s = 0 and p ( q ( r ( s has an even number of 1's. So (28) is true in the first case.

The second case is when p ( q ( r has an even number of 1's and s = 1. Then p ( q ( r = 0 and p ( q ( r ( s = 1 and p ( q ( r ( s has an odd number of 1's. So (28) is true in the second case.

The third case is when p ( q ( r has an odd number of 1's and s = 0. Then p ( q ( r = 1 and p ( q ( r ( s = 1 and p ( q ( r ( s has an odd number of 1's. So (28) is true in the third case.

The last case is when p ( q ( r has an odd number of 1's and s = 1. Then p ( q ( r = 1 and p ( q ( r ( s = 0 and p ( q ( r ( s has an even number of 1's. So (28) is true in this case.

Application. You have a light that is controlled by four different switches. Each switch has two positions. You want to wire it so that changing the position of any switch turns the light on if it off and turns the light off if it is on.

Solution. Label the switch positions on the four switches 1 and 0. Let s1, s2, s3 and s4 be lines coming out of each switch. Each si is either 1 or 0. Let x be the line going into one end of the light. The other end is connected to ground. Then we want

x = s1 ( s2 ( s3 ( s4 =

Here is a wiring diagram.

Example 4. Prove that exclusive or satisfies the distributive law (21).

Solution. We could do this with a truth table. However, let's do by expressing exclusive or in terms of and, or and not and using properties (4) – (12). In section (1.2) we showed that p ( q = pq' + p'q. Using this one has

p(q ( r) = p(qr' + q'r) = pqr' + pq'r

and

pq ( pr = pq(pr)' + (pq)'pr

Using DeMorgan, some of the other properties (4) – (12) one has

pq(pr)' + (pq)'pr = pq(p' + r') + (p' + q')pr

= pqp' + pqr' + p'pr + q'pr

= pp'q + pqr' + pp'r + pq'r

= 0q + pqr' + 0r + pq'r

= 0 + pqr' + 0 + pq'r

= pqr' + pq'r

So p(q ( r) and pq ( pr are equivalent to the same thing and hence are equivalent.

Identities involving if-then (().

(29) p ( q = p' + q (material implication)

(30) p ( q = q' ( p' (transposition or contrapositive)

(31) (pq) ( r = p ( (q ( r) (exportation)

We already proved and discussed material implication in the previous section.

Here is an example of transposition. The following two propositions (or predicates depending on the situation) have the same truth value.

If it is raining then I have my umbrella

If I don't have my umbrella then it is not raining

We can prove transposition as follows. By material implication

p ( q = p' + q

Again, by material implication, double negation and commutativity one has

q' ( p' = q'' + p' = q + p' = p' + q

So (30) is true.

Here is an example of exportation. The following two propositions (or predicates depending on the situation) have the same truth value.

If it is raining and I am outside then I have my umbrella

If it is raining then if I am outside then I have my umbrella

We can prove exportation as follows. By material implication, De Morgan, associative, and material implication twice again

(pq) ( r = (pq)' + r = (p' + q') + r = p' + (q' + r) = p' + (q ( r)

= p ( (q ( r)

So (31) is true.

Interesting identity: if-and-only-if ((, =) is associative. In symbols

(p ( q) ( r = p ( (q ( r)

-----------------------

p

p

q

r = q + p'q'

p

p

q

r = q + p'

p

p

q

r = q + p'q

|p |q |r |q + r |p(q + r) |pq |pr |pq + pr |

|0 |0 |0 |0 |0 |0 |0 |0 |

|0 |0 |1 |1 |0 |0 |0 |0 |

|0 |1 |0 |1 |0 |0 |0 |0 |

|0 |1 |1 |1 |0 |0 |0 |0 |

|1 |0 |0 |0 |0 |0 |0 |0 |

|1 |0 |1 |1 |1 |0 |1 |1 |

|1 |1 |0 |1 |1 |1 |0 |1 |

|1 |1 |1 |1 |1 |1 |1 |1 |

boat

lock A

lock B

lock C

rapids #1

rapids #2

|p |q |r |q ( r |p ( (q ( r) |

|0 |0 |0 |0 |0 |

|0 |0 |1 |1 |1 |

|0 |1 |0 |1 |1 |

|0 |1 |1 |0 |0 |

|1 |0 |0 |0 |1 |

|1 |0 |1 |1 |0 |

|1 |1 |0 |1 |0 |

|1 |1 |1 |0 |1 |

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download