代写CS 131 – Problem Set 3 – Part 2帮做R程序

CS 131 – Problem Set 3 – Part 2

Problem 1.   [10 points] Use the two-column proof format and prove that if a and b are integers and a is even, then ab is even. Recall that “a is even” is defined as “2|a” .

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 r 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 friends with every student in the other room.

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

Problem 3.   [10 points] Let a and b be two integers.  Prove that

divisors(a) ∩ divisors(b) = divisors(b) ∩ divisors(a — 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(a) ∩ divisors(b) ⊆ divisors(b) ∩ divisors(a — b)

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

divisors(b) ∩ divisors(a — b) ⊆ divisors(a) ∩ divisors(b)

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

¬∀A∀B (P(A U B) = P(A) U P(B))

Hint:  Note that to prove a NOT forall, you do not need a two-column proof.  You just need to give a counterexample.

Problem 5.   [10 points] Your domain of discourse is sets.  Prove that P(A) ∩ P(B) = P(A ∩ 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

P(A) ∩ P(B) ≤ P(A ∩ B)

Hint:  First prove that if (C ⊆ A) Λ (C  ⊆ B) then C ⊆ A ∩ B.  Write that as a separate proof. Then use this result in your main proof.

b)  [0 points — neither required nor graded] Prove that P(A ∩ B) ⊆ P(A) ∩ P(B).