1. Prove or give a counter example for the following statement: P (A ∪ B) = P (A) ∩ P (B)
Let A = {1} and B = {2}.
P(A) = {0} {1} P(B) = {0} {2}
P (A) ∩ P (B) = {0}
P(A ∪ B) = {0} {1} {2}
2. Prove that if a relation R is transitive, then so is its converse.
PROOF. Let R be any transitive relation over some set A.
Let S be the converse of R. Thus, S = {(b,a) | (a,b) in R}.
GOAL: We want to show that S is transitive.
In other words, we want to show that for any pairs (x,y)
and (y,z) in S, then (x,z) must also be in S.
Let (x,y) and (y,z) be any pairs in S.
By the definition of converse (see above),
it follows that (y,x) and (z,y) must be in R.
Since R is transitive, (z,y) and (y,x) in R implies
that (z,x) in R.
Since S is the converse of R, (z,x) in R implies that
(x,z) is in S.
Therefore, S is transitive.
3. a) A deck of playing cards is an example the cartesian product of:
{hearts, diamonds, spades, clubs} x {A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K}
b) One can partition a deck of cards based on the suit (all hearts, etc.) or by value (4 Aces, 4 2's, 4 3's, etc.)
c) Consider the relation divisible by: (a, b) is in this relation if the integer a is divisible by the integer b.
Definition: An integer is divisible by another integer if it is can be divided by that integer without a remainder.
There is a more precise definition: An integer n is divisible by another integer m if n = k*m for some integer k.
Example: 15 is divisible by 3 and for n = 15, m = 3 then k = 5. 15 is not divisble by 2.
For all integers a when a is divisible by a, a is divisble by a: Reflexive
If a = 0, then a is not divisible by a. (0,0) is not in the relation "divisible by"
because: the integer a is divisible by the integer b and a = b = 0.
For all integers a,b when a is divisible by b, b is not divisible by a. Consider a = 0 and b = 2. Not symmetric
For all integers a, b, c, if a is divisible by b and b is divisible by c, then a is divisible by c. Consider:
a = k1*b. b = k2*c. Then a = k1*k2*c. Both k1, k2 are integers. Let integer k = k1*k2. Then a = k*c. Transitive.
b = 0 and c = 0 are not in the relation, since a is not divisible by zero, b is not divisible by zero.
4. Let R be the relation where, starting in the afternoon, civilian hours and military hours are the same.
R is reflexive (given).
R is symmetric: (1,13) is in the relation, then (13,1) is in the relation.
R is transitive: as it is described, there is no c such that a != c, b != c. i.e. a = c or b = c (or both).
We include (1,4) and (7,11) in our relationship. Then we must also include the following:
Start time: (1,4) (4,1) (13,16) (16,13) (4,13) (13,4) (1,16) (16,1)
End time: (7,11) (11,7) (19,23) (23,19) (11,19)(19,11) (7,23) (23,7)
because: these values are equivalent: {1 4 13 16} and {7 11 19 23}
One partition can list sets based on ordered pairs: {2 14} {3 15} except for the start time and quit time
relations. Then, add {1 4 13 16} {7 11 19 23}.
5. A) The set A is the set of all Vassar students. The set B is the set of all cars on campus
binary relation: Vassarian a owns car b: Function
B) The set A is the set of students in the spring, 2019 semester of cmpu-145.
The set B is the set of coaches = {Amy, Daniel, Hanna}.
binary relation: student a received assistance from coach b during Tuesday’s lab. Not a function.
C) The set A is the set of students in the spring, 2019 semester of cmpu-145.
The set B is the set of grades = {A, B, C, D, F}.
binary relation: student x achieves a grade of y in cmpu-145: Function.
6. ;; DIY-FINDF
;; --------
;; INPUTS: PRED, a predicate that take an input
;; INPUT-LIST the list of inputs for PRED
;; OUTPUT: One of (the first element of INPUT-LIST that satisfies PRED) or (#f)
(define diy-findf
(lambda (PRED INPUT-LIST)
(cond
((null? INPUT-LIST) #f)
((PRED (first INPUT-LIST)) (first INPUT-LIST))
(else (diy-findf PRED (rest INPUT-LIST)))
)))
;; LOOK-FOR-BROS
;; --------
;; INPUTS: X, Y -- item
;; lop -- list of pairs
;; OUTPUT: ?
(define look-for-bros
(lambda (x y lop)
(diy-findf (lambda (my-pair)
(let ((p (first my-pair))
(q (second my-pair)))
(and (not (equal? x p))
(equal? y q))))
lop)))
A) (lambda (my-pair) ;; this set of statements is the predicate...
(let ((p (first my-pair)) ;; you can the (above) code in...
(q (second my-pair))) ;; a debugger session in DrRacket.
(and (not (equal? x p))
(equal? y q))))
B) No short circuiting. Something like ("groucho" "marxglasses") would be needed
for short circuiting to occur. Note: short circuiting occurs (or not!) when
expressions have boolean operations: and/or. The expressions are usually
coniditional expressions, but this may not be the case.
C) >(look-for-bros "groucho" "marx"
'(("buster" "keaton") ("lon" "chaney") ("harpo" "marx") ("charlie" "chaplan")))
==> '("harpo" "marx")