CS计算机代考程序代写 flex algorithm /Users/billy/gits/moc-2021/problem-sets/ps07.dvi

/Users/billy/gits/moc-2021/problem-sets/ps07.dvi

School of Computing and Information Systems

COMP30026 Models of Computation Problem Set 7

6–10 September 2021

Content: sets, relations, properties of relations, functions

P7.1 Compute the transitive closure and symmetric-transitive closure of the following relations on

Z. For each closure, determine if it is reflexive.

(i) {(2, 3), (5, 4), (0, 3), (2, 1), (1, 5)}

(ii)
{

(x, y) ∈ Z× Z | |x− y| ≤ 2
}

P7.2 Recall that the symmetric difference of sets A and B is the set A⊕B = (A\B)∪ (B \A). For

each of the following set equations, give an equivalent equation that does not use ⊕. However,

do not simply replace ⊕ by its definition; instead try to find the simplest equivalent equation.

(a) A⊕B = A

(b) A⊕B = A \B

(c) A⊕B = A ∪B

(d) A⊕B = A ∩B

(e) A⊕B = Ac

(f) A⊕B = ∅

P7.3 There are multiple ways of representing a relation R from A to B.

• A subset R ⊆ A×B (this is how we define it)

• A function χR : A×B → {0, 1}

• A function αR : A → P(B)

• A function βR : B → P(A)

Explain how we determine whether a ∈ A and b ∈ B are related under each representation

of R. Then show that we can convert between these representations, starting with a subset

R ⊆ A×B, and converting to and from each of the other three representations.

P7.4 Relations are sets. To say that R(x, y) ∧ S(x, y) holds is the same as saying that (x, y) is in

the relation R and also in the relation S, that is, (x, y) ∈ R ∩ S.

Suppose R and S are reflexive relations on a set A. Then ∆A ⊆ R and ∆A ⊆ S, so ∆A ⊆ R∩S.

That is, R ∩ S is also reflexive. We say that intersection preserves reflexivity. It is easy to

see that union also preserves reflexivity. Similarly, if R is reflexive then so is R−1, but the

complement A2 \R is clearly not. The following table lists these results. Complete the table,

indicating which operations on relations preserve symmetry and transitivity.

Property Reflexivity Symmetry Transitivity

preserved under ∩? yes

preserved under ∪? yes

preserved under inverse? yes

preserved under complement? no

P7.5 Continuing from the previous question, now assume that R and S are equivalence relations.

From your table’s first two rows, determine whether R∩S necessarily is an equivalence relation,

and whether R ∪ S is.

P7.6 The Cartesian product of two sets A and B is defined A×B = {(a, b) | a ∈ A∧ b ∈ B}. That

is, a pair whose first component comes from A and whose second component comes from B is

an element of A×B (and no other pairs are). Recall that ∩ and ∪ are absorptive, commutative

and associative. Does × have any of those properties?

P7.7 Suppose A is a set of cardinality 42, that is, A has 42 elements. What, if anything, can we

say about B’s cardinality if we know that some function f : A → B is injective? What, if

anything, can we say about B’s cardinality if we know that some function f : A → B is

surjective?

P7.8 Consider this conjecture: If a binary relation R on some set A is both symmetric and anti-

symmetric then R is reflexive. Prove or disprove the conjecture.

P7.9 Consider this statement: For all sets S and T , S × T = T × S iff S = T .

If the statement is true, prove it. Otherwise provide a counter-example.

P7.10 Consider this conjecture: If a binary relation R on some set A is reflexive then R is either

symmetric or anti-symmetric, or both. Prove or disprove the conjecture.

P7.11 Let R be a relation on A. Show that R ∪∆A is the reflexive closure of R.

P7.12 Let R be a transitive binary relation on A. Does it follow from the transitivity of R that its

symmetric reflexive closure R ∪R−1 ∪∆A is also transitive?

P7.13 Consider the relations on the natural numbers listed in the following table, and tick off their

properties. The successor relation is the relation given by {(n,m) | n+1 = m}. The coprime

relation C on N is given by C(n,m) iff GCD(n,m) = 1, that is, the only common factor of n

and m is 1.

< ≤ successor divides coprime irreflexive reflexive asymmetric antisymmetric symmetric transitive linear P7.14 (Optional.) Let ≤ be a partial order on a set X. We say that a function h : X → X is: • idempotent iff ∀x ∈ X (h(h(x)) = h(x)) • monotone iff ∀x, y ∈ X (x ≤ y ⇒ h(x) ≤ h(y)) • increasing iff ∀x ∈ X (x ≤ h(x)) Note that an idempotent function does all of its work “in one go”; repeated application will not change its result. A monotone function is one that respects order; if its input grows, its output must grow too (or stay the same). A function which is idempotent and monotone is a closure operator. If it is also increasing, we call it an upper closure operator. Closure operators are important and appear in many different contexts. We have met several—let R be the set of all binary relations. Then the functions refl , symm, and trans, in R → R, producing a relation’s reflexive, symmetric, and transitive closure, respectively, are all upper closure operators. Soon we will meet an “ǫ- closure” function that is part of the algorithm for turning a non-deterministic automaton into an equivalent deterministic automaton—yet another upper closure operator. Consider D = {a, b, c, d} and the partial order ≤ on D, defined by x ≤ y iff x = a ∨ x = y ∨ y = d Below is the so-called Hasse diagram for D. A Hasse diagram provides a helpful way of depicting a partially ordered set. The nodes are the elements of the set, and the order is given by the edges: x ≤ y if and only if there is a path from x to y travelling upwards only, along edges (and the path can have length 0). a b c d Define eight functions f1, . . . , f8 : D → D, exhibiting all possible combinations of the three properties. That is, find some (a) f1 which is idempotent, monotone, and increasing; (b) f2 which is idempotent and monotone, but not increasing; (c) f3 which is idempotent and increasing, but not monotone; (d) f4 which is monotone and increasing, but not idempotent; (e) f5 which is idempotent, but neither monotone nor increasing; (f) f6 which is monotone, but neither idempotent nor increasing; (g) f7 which is increasing, but neither idempotent nor monotone; (h) f8 which is neither idempotent, monotone, nor increasing.