Discrete Mathematics for Computer Science

Basic Definitions 7

are used in the standard mathematical expression if and only if. The statement

a if and only if b

means that if a is true then b is true (a =# b) and that ifb is true then a is true (b => a).

Equivalently, it means that a and b are either both true or both false.

In a proof of an if and only if statement, a proof of "if a, then b" is usually labeled

(=>), whereas a proof of "if b, then a" is usually labeled (.=). The if and only if statement

is often denoted by .=*. The arrow notation is used in Theorem 2.

Theorem 2. Let A and B be sets. Then, A = B if and only if A C B and B C A.

(What the Proof entails:) We must prove two things. The first that A = B implies that A C

B and B C A. The second is that if A C B and B c A, then A = B.

Proof

(==•) Prove that if A = B, then A C B and B C A. Suppose A = B. Then, A C B and

B C A by Theorem 1.

(•<=) Prove that if A C B and B C A, then A = B. To prove this, begin by supposing

that A C B and B C A. Then, for any x, if x E A, x E B, since A c B. Furthermore, if

x E B, then x e A, since B C A. Therefore, the sets A and B have the same elements. By

Definition 1, A = B. 0

1.1.6 Venn Diagrams

In most discussions, attention is limited to elements and subsets of a fixed set. For example,
elementary arithmetic is usually limited to elements and subsets of Z (the integers) or of
Q (the rationals). In a study of some period of history, attention may be limited to the set
of all persons living at that time. In computer science, it may be the set of all file names on
a hard disk. Such sets are called universal sets, or universes. They are the "universes of
discourse" for a time.
There is a very convenient type of diagram, called a Venn diagram, for illustrating set-
theoretic relationships. Start with a rectangle, and let the points in the rectangle represent
the elements of a universal set, as shown in Figure 1.1.

U

Figure 1.1 Venn diagram of a universal set U.

Subsets of the universal set are represented by circles or ovals in the rectangle, as
shown in Figure 1.2. For example, suppose that A, B, and C are subsets of the universal
set U. The region within the circle for A represent the elements of A, and similarly for B
and C. Figure 1.2 shows A, B, and C where A C B. A and C have no elements in common,
and B and C have elements in common but neither is a subset of the other.