Solutions for HW 1

Solutions for CS 280 HW 1

(There are several ways to prove the problems involving set equations. This is a representative solution, others are most certainly acceptable)

Problem 1

Given A+B = (A-B) U (B –A) as defined in the problem, prove that:

A+B = φ ßà A = B

Recall from office hours that in order to prove equivalence, we can adopt one of the following strategies:

i) Prove the Left Hand Side (LHS) true à Right Hand Side RHS true, followed by prove RHS true à LHS true

ii) Prove the if LHS true à RHS true and if LHS false à RHS false

I’ll use strategy i)

Given (A-B) U (B –A) = φ

è A-B = φ = B-A b/c otherwise, the union isn’t null.

è A subset of B AND B subset of A

è A = B.

Given A = B

è A-B = φ & B-A = φ

Now φ U φ = φ

è (A-B) U (B-A) = φ

è A+B = φ

Since we have proved bidirectional equivalence, the statement in the question is proved

Question 2

In office hours we introduced the concept of Disjunctive Normal Form, and stated that any set equation could be rewritten in DNF. This is brought about by repeated applications of DeMorgan’s laws whereby we can convert any intersection into a union and vice versa.

DNF states that any set equation can be written in the following form:

C1 U C2 U C3 . . . U Cn, where C1, C2 etc are clauses of the following form:

(V1 ∩ V2 ∩ . . . ∩ Vn) where Vi is any set (or its complement).

I will use the notation X to refer to a set X and X’ to refer to the complement of X

Now we want to reduce the given problem to DNF and somehow extract all the terms with an X or X’ extracted into two distinct clauses, one containing X and the other containing X’.

So given any set equation, we use the axiom that it can be written in DNF and convert the equation into a set of clauses Unioned together.

There are 4 kinds of clauses:

i) Terms containing only X

ii) Terms Containing only X’

iii) Terms containing X and X’

iv) Terms containing neither X nor X’

With i) and ii) we are already in the form we desire, with iii), this kind of clause contains an X ∩ X’ so that term evaluates to null, making the whole clause evaluate to null. With clauses like iv) above, we need to introduce an X and X’ into the clause. We do so in the following way:

For example, let

Cp = V1 ∩ V2 ∩ V3

We can write Cp = V1 ∩ V2 ∩ V3 ∩ (X U X’) and subsequently

We can write, by distributivity

Cp = (V1 ∩ V2 ∩ V3 ∩ X) U (V1 ∩ V2 ∩ V3 ∩ X’)

Cp = Cp1 U Cp2

We have broken up Cp into two clauses Cp1 and Cp2, we preserve DNF by virtue of the structure of Cp1 and Cp2 (a variable number of sets intersected together) and the fact that Cp1 and Cp2 are unioned together.

It is easy to see that we can extend this procedure to any clause with an arbitrary number of terms.

Now that we have rewritten every term as containing an X or an X’, we then apply a ‘factoring’ step. Say C1 and C2 are two clauses containing an X term

C1 = (V1 ∩ V2 ∩ V3 ∩ X)

C2 = (V4 ∩ V5 ∩ V6 ∩ X)

And we have C = C1 U C2

We can write C = ((V1 ∩ V2 ∩ V3) U (V4 ∩ V5 ∩ V6)) ∩ X by distributivity. It is easy to extend this procedure to terms containing X’. Then it is easy to extend this to all clauses, since all clauses contain either an X or an X’. Since we can now factor out all terms containing X and X’ into a form A ∩ X and B ∩ X’, we know that when we reduced the initial set equation to DNF, these two terms were written as Unions of two clauses. This implies that we can reduce the terms to (A ∩ X) U (B ∩ X’)= φ, since the original set equation had RHS = φ. Hence proved.

Question 3

Prove that A=B= φ çè A U B = φ

Given A=B= φ

è A U B = φ U φ = φ hence proved

Given A U B = φ

Assume that A != φ OR B != φ

Let NOT φ denote a set which is non-empty.

è A U B = φ U (NOT φ)

= (NOT φ) U φ

= (NOT φ) U (NOT φ)

!= φ

Therefore, A = φ = B by contradiction.

Question 4

Again we prove bi-directional equivalence.

If B subset of X subset of A’ è simultaneous equations

B ∩ X’ = φ and A ∩ X = φ have solutions.

X subset of A’ à A ∩ X = φ

B subset of X à B ∩ X’ = φ

Hence proved that there exists a non-trivial X that satisfies the given simultaneous equations.

If simultaneous equations have a solution, then
B subset of X subset of A’

If simultaneous equations have a solution, then since B ∩ X’ = φ, then B is a subset of X

Also since A ∩ X = φ à A subset of X’ OR if we invert that argument, X subset of A’

Hence proved.

Question 5

X U C = D

There are several ways to solve this problem. Here is one solution.

However, it is NOT sufficient to do X U C – D = φ. This merely implies that D at least contains all elements in X U C, but could

Contain more. To derive an exact solution, the LHS must be a subset of the RHS and vice-versa or:

X U C = D ó X U C + D = φ from problem 1.

ó (X U C – D) U (D – (X U C) = φ from the definition of “+”

ó ((X U C) ∩ D’) U (D ∩ (X U C)’) = φ def of “-”

ó ((X ∩ D’)U(C ∩ D’)) U (D ∩ (X’ ∩ C’)) = φ distributivity of ∩ over U, deMorgan

ó (X ∩ D’) U [(C ∩ D’) ∩ (X U X’)] U (D ∩ X’ ∩ C’) = φ using trick from prob 2

ó (X ∩ D’) U [(C ∩ D’ ∩ X) U (C ∩ D’ ∩ x’)] U (D ∩ X’ ∩ C’) = φ distributivity

ó (X ∩ (D’ U (C ∩ D’))) U (X’ ∩ ((D ∩ C’) U (C ∩ D’))) = φ undistributing twice (i.e. factoring)

\____”A”____/ \_______”B”_______/

ó (X ∩ A) = φ and (X’ ∩ B) = φ from problem 3

Therefore the pair of simultaneous equations has a solution iff B is a subset of A’, from problem 4.

Note that A = (D’ U (C ∩ D’) = D’ from rule 12 on the Algebra of Sets handout.

Note that B = ((D ∩ C’) U (C ∩ D’)) = D + C. So we have

D + C is a subset of D

Which is equivalent to

C is a subset of D

which therefore is our necessary and sufficient condition for a solution existing for X U C = D.

Question 6

To prove an equivalence relation, we need to satisfy the rules of reflexivity, transitivity and symmetry.

i) Reflexivity: (a,b) ~ (b,a) for all (a,b)
By the definition of the relation, (b,a) ~ (a,b) è a+b = b+a which is true for all (a,b)

ii) Symmetry: if (a,b) ~ (c,d) then (c,d) ~ (a,b)
Given that a+d = b+c, (c,d) ~(a,b) è c+b = a+d, which is true from the fact that a+d = b+c as assumed.

iii) Transitivity: if (a,b) ~ (c,d) and (c,d) ~ (e,f) then (a, b) ~ (e, f)

We know that a + d = c + b and c + f = d + e. Therefore c-d = e-f. But c-d = a-b, therefore e-f = a-b or a + f = e + b. Hence proved.

Since we have satisfied all conditions, it is an equivalence relation

When we look at the description of the relation, we see that if we think about each pair of integers (a,b) and the next pair, (c,d) they are defined by the relation if a-d = b-c. or, if a-c = b-d. Now if we think about each pair defining an (x,y) co-ordinate, the above translates into:

delta(x) = delta(y). These are lines of slope 1. So if we draw a 4-quadrant graph, representing integers, since our relation is only defined over pairs of +’ve integers, we only consider the top right quadrant. So an equivalence class is defined by all (x,y) pairs sitting on a line of slope 1 in the first quadrant of such a graph.

Question 7

I will describe the solution rather than draw it.

a) Create a single vertical column of dots, numbered from 2 to 15, top to bottom. Draw a small circular line from each dot to itself, with an arrow at one end. Then draw a line WITH AN ARROW from 2 to 4, 2 to 6, ..., 2 to 14. Next draw from 3 to 6, 3 to 9, 3 to 12, 3 to 15. Continue in this fashion, drawing from a value N to all other values k*N in the range 2 to 15.

b) A nice way to draw this graph is to create the following clusters of dots: 0,4,8,12 1,5,9 2,6,10, and 3,7,11. Every dot will have an arrow pointing to itself. Then is each group, every dot will have an arrow pointing to each other dot IN THE CLUSTER. This means that there are 2 arrows connecting each pair of points that are equivalent mod 4, one pointing in either direction, because of the fact that equivalence implies reflexivity.

c) As you might expect that are probably 85 different graphs that are possible answers. You need to remember to keep the arrows in a directed graph in mind: AàB iff A is a parent of B. Why is this a ‘tree’? In a tree, there is no way to get back to a node in the graph you already visited, i.e. there are no ‘cycles’ in the graph. This makes sense because at no stage can some person A be a parent of a person B who will later be a parent of some person C who will be a parent of A, unless we are talking about time travel in which case every answer here is wrong.

d) If carefully drawn, this graph can resemble a cube, with dots representing each vertex. Note that the power set of {a,b,c} = { φ , {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}. Draw an arrow between two sets A and B IFF |A| < |B| (cardinality A less than cardinality B) and B contains all the elements in A. Note that φ is a subset of the seven other sets, and that all subsets other than {a,b,c} are a subset of {a,b,c}.

Question 9

P < q iff p | q

To prove that this is an partial order, we have to prove transitivity, reflexivity and anti-symmetry and that it’s not a total order

Not a total order à there exists some a, b such that a does not divide b and b does not divide a. An example is a =2 and b=3. Hence proved

Reflexivity.

For all a in Z+, a | a. This is true for any integer a

Transitivity.

Anti-symmetry

If a|b and b|a then a = b.

a|bà b = m*a and b|a à a = n*b. But then, a = n*m*a à n*m = 1 and since we are in the domain of positive integers, m=n=1. Therefore a=b.