Exercises 33
- Which of the following statements are correct? Prove each correct statement. Disprove
each incorrect statement by finding a counterexample.
(a) A and B are disjoint if and only if B and A are disjoint. (Read the statement
carefully-the order in which the sets are listed might matter!)
(b) A U B and C are disjoint if and only if both the following are true: (i) A and C are
disjoint and (ii) B and C are disjoint.
(c) A n B and C are disjoint if and only if both the following are true: (i) A and C are
disjoint and (ii) B and C are disjoint.
(d) A U B and C are disjoint if and only if one of the following is true: (i) A and C
are disjoint or (ii) B and C are disjoint.
(e) A n B and C are disjoint if and only if one of the following is true: (i) A and C
are disjoint or (ii) B and C are disjoint.
(f) Let U be a universal set with A, B C U. A and B are disjoint if and only if A and
B are disjoint.
- For (a) and (b), prove the stated result. For (c) and (d), find a counterexample to show
that these conjectures are false.
(a) AE)B=(AUB)-(ANB)
(b) A n (B e C) = (A n B) ® (A n C)
(c) (AOB)@(CND)C(AEC)fA(BED)
(d) (A U B) @ (C U D) _ (A U C) ® (B U D)
- Given any four integers xI, X2, X3, and x4, none of which is even and none of which is
a multiple of 5, prove that some consecutive product of these integers ends in the digit
- A consecutive product is one term, two terms in a row, three terms in a row, or all
four terms in a row using the order in which the integers appear in the list xl, x2, X3, X4.
(Hint: Use a proof by cases.)
- Prove by contradiction that 7 is a prime number.
- Prove by contradiction that V/2 is not a rational number.
- Prove by contradiction that Z has no smallest element.
- Complete the proof of Example 12.
- For parts (a) and (b), let U be any set, and let X = P(U).
(a) Prove that X with the operations n for meet and U for join is a distributive lattice.
(b) Prove that X with the operations U for meet and n for join is a distributive lattice.
- Let U be any set, and let X = P(U). Prove that X with the operations U for meet and
n for join is a complemented lattice.
- Recall that in the definition of a boolean algebra, we did not require that T, I, and
each -x be specified; we merely said they must exist. So, it is natural to ask whether
there might be several elements that could equally well be chosen as T or I or, for
some element x of the boolean algebra, several different possible choices for -x. Show
that in a complemented lattice:
(a) There is only one possible choice of elements T and I satisfying the definition
of a complemented lattice. (Hint: Suppose there were two possible choices for T,
say, T" 1 and T 2 .Evaluate T 1 A T 2 in two different ways.)
(b) For each element x of a complemented, distributive lattice, there is only one possi-
ble choice for -x that satisfies the definition of -x. (Hint: Suppose there were two
choices, say, -xl and -x2, for --x. Find two ways to evaluate --xl A x V -X2.)
