Discrete Mathematics for Computer Science

Operations on Sets 25

=CO((ANiB)U(BNA)) (ANfA=BNB=o)

= (C n A nf B) U (C n A n B) (Distributive Law)

Putting the reduced form of these two terms together gives a new description of

(A D B) E C.

((AeB)®C) = (AnBNC)u(ANBNeC)u(AnBnC)U(AnBnC)

By similar steps, the term A E (B E C) can be reduced to these same expression. We

leave this reduction to the reader. After this second reduction, we can conclude

A ED (B ED C) = (A ED B)C E

The Logic of Statements

Theorem 8(b) is closely tied to an issue in the logic of sentences. The issue is the relation-

ship between an if-then statement and its converse, its inverse, and its contrapositive. A

statement such as "if a, then b" can be rewritten as "if b, then a," and you might wonder

if the first statement is true whether or not you can deduce anything about the truth of the

second. We start with a statement such as "if a, then b." The obvious variants of this state-

ment are "if b, then a," "if not a, then not b," and "if not b, then not a." What we would

like to understand is whether any one of these statements being true (or false) implies that

any other of these statements is true (or false). Consider the statement

"If George is a horse, then George is an animal."

The inverse of this statement is

"If George is not a horse, then George is not an animal."

The converse of this statement is

"If George is an animal, then George is a horse."

And, finally, the contrapositive of the statement is

"If George is not an animal, then George is not a horse."

The statement and its contrapositive are both true, whereas the inverse and converse are

probably false (depending on who George is).

As another example, consider the following:

Statement: "If my cat is a horse, then my cat is an animal."

Inverse: "If my cat is not a horse, then my cat is not an animal."

Converse: "If my cat is an animal, then my cat is a horse."

Contrapositive: "If my cat is not an animal, then my cat is not a horse."

As the two examples illustrate, the if-then statements are equivalent statements to their
contrapositives. It can be shown that in general, based on logic alone, a statement is true
if and only if its contrapositive is true. In writing a proof, it may be easier to use the
contrapositive of a statement than to use the statement itself. A proof of the contrapositive
of your objective is called an indirect proof. In the cat/horse example, the statement and
its contrapositive are vacuously true, but the inverse and converse are false. An if-then