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,

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.

If a|b and b|c then a | c.
Since a|b, b = m*a and since b|c then c = n*b. Therefore c = n*m*a and a | c
because a | a*m*n. Hence proved.

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.