## Read an Excerpt

#### Boolean Algebra

**By R. L. Goodstein**

**Dover Publications, Inc.**

**Copyright © 2014 Dover Publications, Inc.**

All rights reserved.

ISBN: 978-0-486-15497-8

All rights reserved.

ISBN: 978-0-486-15497-8

CHAPTER 1

**The informal algebra of classes**

1.0. **Classes.** Collections of objects, whether they are identified by a survey of their members or by means of some characteristic property which their members have, are called classes. The students in a particular room at a particular time form a class, the voters on an electoral roll of a certain town form a class (as do their names on the roll), the hairs on a man's head, the blood-cells in his body, the seconds of time he has lived, all these form classes. Featherless bipeds and mammals with the power of speech are classes characterized by common properties of their members; they are classes with a common membership, *equal* classes, as we shall say.

1.1. **Membership.** We shall use capital letters as names of classes. If an object *a* is a member of a class *A* we shall write

** a** ε

*A*and say that "*a* belongs to *A*", or "*a* is in *A*". The membership symbol "ε" (the Greek letter ε) is the initial letter of the Greek verb "to be". Thus "Earth ε Planets" expresses the relationship of our earth to the class of planets.

If *a* is not a member of a class *A* then we write

** a** [??]

*A*If we can write down signs for all the members of a class we represent this class by enclosing the signs in brackets. Thus {1, 2, 3} is the class containing the numbers 1, 2 and 3 (and nothing else), {2, 1, 3}, {3, 1, 2} {1, 1, 2, 3} for instance denoting the same class, and {*a, b, c, d*} is the class containing just the first four letters of the alphabet. We can represent any fairly small class in this way, but the notation is obviously impractical for large classes (like the class of all numbers from 1 to 1010) and meaningless for classes with an unlimited supply of members (like the class of all whole numbers).

The class whose sole member is some object *A*, namely the class {*A*}, must be distinguished from *A* itself. For instance if *A* = {1,2} then {*A*} is a class with only one member, but *A* is a class with two members. A class with a single member is called a unit class. "The Master of Trinity" is a unit class, and so is "The Queen of England".

1.2. **Inclusion.** If every member of a class *A* is also a member of a class *B* we say that the class *A* is contained in the class *B*, or *A* is included in *B*, and write

** A** [subset]

**.**

*B*It is important to distinguish between the membership relation "ε" and the inclusion relation "[subset]". The membership relation is the relation in which a member of a class stands to the class itself; on one side (the left) of the membership relation stands a class member, and on the other side (the right) stands a class. But inclusion is a relation between *classes*, and a class stands on each side of the relation of inclusion. If *A* [subset] *B*, we say that *A* is a *subclass* of *B*, and that *B* is a *superclass* of *A*. Every class is included in itself, thus *A* [subset] *A*, because the members of *A* (on the left) are necessarily members of the same class *A* (on the right). A subclass of a class *A* which is not just *A* itself, is called a *proper* subclass. If *A* [subset] *B* and *B* [subset] *A* then *A = B*, for every member of *A* is a member of *B*, and every member of *B* is a member of *A*, so that *A* and *B* have the same members.

1.3. **The empty class and the universal class.** A convenient fiction is the *empty*, or *null* class, the class without members. If no candidate presents himself for some examination, the class of candidates is the empty class. We denote the empty class by 0; thus the relation *x* ε 0 *is* false for every object *x* in the world. Another convenient fiction is the *universal* class, the class of everything (or everything under consideration) which we denote by 1. The null class and the universal class are each unique. The null class is considered to be a subclass of every class (for there is no object which is a member of 0 and not a member of any *A*). Any class is of course a subclass of the universal class. In particular 0 [subset] l.

1.4. **The complement of a class.** If we remove from the universal class all the members of some class *A*, the objects which remain form the *class complement of A*, denoted by *A'*. The classes *A, A'* have no members in common, but everything in the universal class is either a member of *A* or a member of *A'*. The complement of the null class is the universal class, and conversely the complement of the universal class is the null class. That is

**0' = 1, 1' = 0.**

Complementation is *involutory*, that is to say the complement of the complement is the original class.

1.5 **Union and intersection.** Given two classes *A, B* we may form the class *C, called the union of A and B* whose members are precisely those objects which are members of *A* or members of *B*; if *A* and *B* have any members in common, these common members occur once only in the union. For instance if *A* and *B* are sacks of potatoes their union is formed by emptying both sacks into a third. The union of two classes *A* and *B* is denoted by

** A** [union]

*B.*By definition union is commutative, that is

** A** [union]

**[union]**

*B = B*

*A*.

**Examples**

1. if *A = {a, b, c, d}*

and if *B = {c, d, e, f}*

then *A* [union] *B = {a, b, c, d, e, f}*

2. If *A* is the class of even numbers and *B* is the class of odd numbers then *A* [union] *B* is the class of all whole numbers.

3. If *A* is the class of cats and *B* the class of Persian cats then *A* [union] *B = A*, for every Persian cat is a cat.

4. If *A* is the class of cats and *B* is the class of cats with tails 5 ft long then *A* [union] *B = A*, for *B* is the null class and contributes nothing to the union.

For any class *A,*

* A* [union] 0 =

**[union] 1 = 1,**

*A, A***[union]**

*A*

*A = A.*For the members of *A* [union] 0 are *either* members of *A, or* members of 0, and 0 has no members. And the members of *A* [union] 1 include the members of 1, and so include everything.

Finally, the members of *A* [union] *A* are just the members of *A*. The relation *A* [union] *A = A* is called the *idempotent* law for union. Since every object belongs either to *A* or to *A'* it follows that

*A* [union] *A'* = 1.

The class of members common to two classes is called their *intersection*. The intersection of *A, B* is denoted by

*A* [intersection] *B.*

By definition, intersection is commutative, that is *A* [intersection] *B = B* [intersection] *A*.

**Examples**

1. If *A = {a, b, c, d}, B = {c, d, e}* then *A* [intersection] *B = {c, d}*

2. If *A* is the class of green-eyed cats, and *B* is the class of long-haired cats, then *A* [intersection] *B* is the class of long-haired green-eyed cats.

3. If *A* is the class of cats and *B* the class of dogs then *A* [intersection] *B* is the null class, for no creature is both cat and dog.

For any class *A*

* A* [intersection] 1 =

**[intersection] 0 = 0,**

*A, A***[intersection]**

*A*

*A = A.*For every member of *A* is common to *A* and the universal class, and the empty class has nothing in common with *A* (even if *A* itself is null). The third relation, the indempotent law for intersection, says just that every member of *A* is common to *A* and itself. Since *A* and *A'* have no member in common we have

** A** [intersection]

*A'*= 0.1.6. We proceed to establish some of the important relations which hold between complementation, inclusion, union and intersection.

1.61. We prove first that, for any classes *A, B*

* A* [intersection]

**[subset]**

*B***[intersection]**

*A, A***[subset]**

*B*

*B*** A** [subset]

**[union]**

*A***[subset]**

*B, B***[union]**

*A*

*B.*For the *common* members of *A* and *B* (if any) are members of *A*, and members of *B*, and the union *A* [union] *B* consists of both the members of *A* and the members of *B*.

1.62. The three relations

**(i) A [subset] B, (ii) A [union] B = B, (iii) A [intersection] B = A,**

are *equivalent*, that is to say, all three hold if any one of them holds. Let (**i**) hold:

then any member of *A* [union] *B* is a member of *B*, or a member of *A*, and so of *B*, that is to say *A* [union] *B* [subset] *B*, but *B* [subset] *A* [union] *B* and so (**ii**) holds; moreover every member of *A* is a common member of *A, B* so that *A* [subset] *A* [intersection] *B*, and since *A* [intersection] *B* [subset] *A* therefore (**iii**) holds. Observe the technique by which we have proved an equation; to show that, say, *X = Y*, we prove both *X* [subset] *Y* and *Y* [subset] *X*, or in words, every member of the lefthand class is a member of the right-hand class, and every member of the righthand class is also a member of the left-hand class. Next let us suppose that (**ii**) holds: since *A* [subset] *A* [union] *B* and *A* [union] *B = B* therefore (**i**) holds, and hence (**iii**) holds. And if we are given (**iii**) then from *A* [intersection] *B* [subset] *B* follows (**i**) and hence (**ii**), which completes the proof.

1.63. **De Morgan's laws.** Union and intersection interchange under complementation. More precisely,

**( A [union] B)' = A' [intersection] B', (A [intersection] B)' = A' [union] B'.**

These relations are called De Morgan's laws. It suffices to prove one of these relations, since each is an immediate consequence of the other, under complementation. We recall that the complement of the complement is the original set; from the first relation (with *A', B'* in place of *A, B*) we have

**( A' [union] B')' = (A" [intersection] B")**

that is

**( A' [union] B')' = A [intersection] B**

whence, taking the complements of both sides, (for if two classes are equal so are their complements)

**( A' [union] B')" = (A [intersection] B)',**

that is

**( A [intersection] B)' = A' [union] B'**

as required.

*(Continues...)*

Excerpted fromBoolean AlgebrabyR. L. Goodstein. Copyright © 2014 Dover Publications, Inc.. Excerpted by permission of Dover Publications, Inc..

All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.

Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.