Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 131 – Problem Set 3 – Part 2

Problem 1. [10 points] Suppose a and b are two odd integers. Use the two-column proof format and prove that a · b is odd.

Note: a · b means a times b. For example 5 · 3 = 15

Solution.

a is odd                                    Hypothesis           (1)

b is odd                                    Hypothesis           (2)

3q e Z(a = 2q + 1)          Definition of odd numbers, 1           (3)

3q e Z(a = 2q + 1)          Definition of odd numbers, 2           (4)

Let k1  be the particular element of Z,a = 2k1 + 1            Existential Instantiation, 3           (5)

Let k2  be the particular element of Z,b = 2k2 + 1            Existential Instantiation, 4           (6)

ab = (2k1 + 1)(2k2 + 1)                                   Algebra, 5,6           (7)

ab = 4k1 k2+ 2k1+ 2k2 + 1                                     Algebra, 7           (8)

ab = 2(2k1 k2 + k1 + k2 ) + 1                                     Algebra, 8           (9)

2k1 k2 + k1 + k2  is a particular element of Z                                     Algebra, 5,6         (10)

3q e Z(ab = 2q + 1) Existential Generalization, 9,10         (11)

∴ ab is odd                      Definition of odd, 11         (12)

Problem 2. [10 points] Let D be the set of BU dorm buildings. Each dorm building contains a  set of rooms. Each room is a set of students. For two students a,b, let F(a,b) be“a is friend of b.” Express the following using quantifiers.

Hint 1: To specify a given student t, one needs to specify the room b to which t belongs, and the dorm building d to which b belongs.

Hint 2: A person can be their own friend.  For example Joy is a Friend of herself but Vahid is not a friend of himself. Therefor, F(Joy,Joy) = True but F(Vahid,Vahid) = False.

a) There are two rooms in different dorms such that every student in one room is not friends with every student in the other room.

Solution. 3d e D 3c e D (c d V 3 r e c 3s e d Aa e r Ab e s 一F(a,b)).

b) For every pair of rooms in different dorms, there is a student in one who is friends with a student in the other.

Solution. Apply De Morgan’s to the previous line, and recall that X ^ Y = 一X 一 Y .

Ad e D Ac e D (c = d ^ A r e c As e d 3a e r 3b e s F(a,b)) =

Ad e D Ac e D (c d 一 A r e c As e d 3a e r 3b e s F(a,b))

Problem 3. Let a and b be two integers. Prove that

divisors(b) U divisors(a — b) = divisors(a) U divisors(b),

via the following two steps. We will grade only the first part; the second part is very similar and thus we do not require you to submit it and will not grade it.

a) [10 points] Use the two-column proof format and prove that

divisors(b) U divisors(a — b) 天 divisors(a) U divisors(b)

Solution. We follow a similar outline as above:

Suppose x is an arbitrary element of divisors(b) U divisors(a — b)                                                   (1)

x e divisors(b) V x e divisors(a — b)                     Definition of U      (2)

x e divisors(b)                   Simplification, 2      (3)

3q e Z(b = xq)          Definition of divisor, 3      (4)

x e divisors(a — b)                   Simplification, 2      (5)

3p e Z(a — b = xp)          Definition of divisor, 5      (6)

Let r be the particular element of Z such that b = rx   Existential Instantiation, 4      (7)

Let s be the particular element of Z such that a — b = sx   Existential Instantiation, 6      (8)

a = rx + sx = (r + s)x                     Subtraction, 7,8      (9)

x|a                  Definition of  |  ,9    (10)

x e divisors(a)        Definition of divisor, 10    (11)

x e divisors(b) V x e divisors(a)                 Conjunction, 5,11    (12)

x e divisors(a) U divisors(b)                Definition of U, 13    (13)

A(x e divisors(b) U divisors(a — b))x e divisors(a) U divisors(b) Universal general’n, 1,13    (14)

∴ divisors(b) U divisors(a — b) 天 divisors(a) U divisors(b)               Definition of  天, 14    (15)

b) (0 points — neither required nor graded) Use the two-column proof format and prove that divisors(a) U divisors(b) 天 divisors(b) U divisors(a — b)

Problem 4. [10 points] The domain of discourse is sets. Prove that

3A3B (P(A) n P(B) P(A n B))

Hint: Think about this question before starting your proof: Do you need a full two-column proof or a counterexample?

Solution. Let A = {0} and B = {1} be one-element sets. P(A) = {9, {0}} and P(B) = {9, {1}}, and thus P(A)n(B) = {9, {0}, {1}}. On the other hand, AnB = {0, 1} and therefore P(AnB) = {9, {0}, {1}, {0, 1}}. Thus, for these A and B , P(A) n P(B) P(A n B) and we have the desired counterexample.

Problem 5. Your domain of discourse is sets.  Prove that P(A U B) = P(A) U P(B), via the following two steps. We will grade only the first part; the second part is very similar and thus we do not require you to submit it and will not grade it.

a) [10 points] Prove that P(A U B) 天 P(A) U P(B).

Suppose C is an arbitrary element of P(A ∩ B)                                                                     (1)

C ⊆ A ∩ B                  Definition of powerset, 1              (2)

C ⊆ A ∧ C ⊆ B                                       Lemma 1, 2              (3)

C ∈ P(A)∧ C ∈ P(B)                 Definition of powerset, 3              (4)

C ∈ P(A) ∩ P(B)                            Definition of ∩, 4              (5)

Ax(x ∈ P(A ∩ B) → (x ∈ P(A) ∩ P(B))) Universal Generalization, 1, 5              (6)

P(A ∩ B) ⊆ P(A) ∩ P(B)                            Definition of ⊆, 6              (7)

b) (0 points — neither required nor graded) Use the two-column proof format and prove that

P(A) ∩ P(B) ⊆ P(A ∩ B)