COMPSCI 250: Spring 2023 Homework 2

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMPSCI 250: Spring 2023

Homework 2

Due Date : Friday, March 10

This assignment has 9 problems. There is also 1 Extra Credit problem. The extra credit is 10 points.

Please submit a single PDF file with the problems in order (as below) and legible.  Look at your PDF before submitting it – it is fine to scan or photograph a handwritten document but if the graders can’t read it, they won’t grade it.

Please assign pages to problems in Gradescope.  Graders will click on the problem number. If no page shows up because it’s not assigned, the assumption is you have not solved the problem.

Be sure you are doing Problems in the book and not Exercises: the numbers should start with P rather than E.

For full credit, show your work, explaining your reasoning. This also helps assign partial credit.

You are responsible for following the academic honesty guidelines on the Grading and Require- ments page.  This means that what you present must be your own work in presentation, and you must acknowledge all sources of aid other than course staff and the textbook.

B-1(5 points)   Prove that if you have 31 cookies that you will distribute to 6 children, at least one child will get more than 5 cookies. What proof method in section 1.8 of the textbook did you use?

B-2(10 points)   Prove that f(n) = 3n + 5 is one-to-one, where the domain and co-domain of f is Z+ . Show that f is not onto.

P2.1.7   Let X be a set of at least two people. We will ask each person in X to write down the name (10 points)   of a person in X other than themself.  Let R be the relation { : a\ s chosen name is

b}. Suppose we start with a given person a, move to the person that a wrote down, then to the person that they wrote down, and so forth until we reach a given person b. Let S be the relation { : Starting from a, we eventually reach b by this process}.

(a)   If from a, we reach a again before finding b, explain why we will never reach b.            (b)   If is not in S, when can we give up on the process? Will we definitely reach a?

(c)   (uses Java) If the elements of X are represented by the integers {0, ··· ,n − 1} for some n, and the relation R is given by a two-dimensional boolean array, write a method that will test whether a given pair is a member of S .


P2.3.3 (12 points) Let A and B be two types such that A is a proper subset of B (so that B contains all the elements of A plus at least one other element). Let P be a unary predicate on A, and let Q be a unary predicate on B . Suppose that ∀a : ∀b : P(a) → Q(b) is true. Which of the following four statements is guaranteed to be true? For each statement, explain why it is always true or give an example where it is false. (Hint: Consider the case where A is empty.)

(a)   (∀a : P(a)) → (∀b : Q(b))

(b)   (∀b : Q(b)) → (∀a : P(a))

(c)   (∃a : P(a)) → (∃b : Q(b))

(d)   (∃b : Q(b)) → (∃a : P(a))

P2.5.3 (12 points) Let Σ = {a,b}, X = {aaa,ab}, Y = {a,b,bb}, and Z = {a,aa,ab}. List the elements of the following languages:

(a)   XY

(b)   ZY

(c)   XYX

(d)   XYZ ∪ ZXY

P2.6.2 (11 points) In Robert Heinlein’s novel The Number of the Beast, the following two logic puzzles occur, in which one is to derive a conclusion from six premises.  (Heinlein designed these in the spirit of Lewis Carroll.)  Your task is to give formal proofs that the conclusions are valid.  In the first, the type of the variables is “my ideas”, and the premises are:

•   Every idea of mine, that cannot be expressed as a syllogism, is really ridiculous; (∀x : ¬ES(x) → RR(x))

•   None of my ideas about Bath-buns are worth writing down; (∀x : B(x) → ¬WWD(x)).

•   No idea of mine, that fails to come true, can be expressed as a syllogism; (∀x : ¬T(x) → ¬ES(x))

•   I never have any really ridiculous idea, that I do not at once refer to my solicitor; (∀x : RR(x) → RS(x))

•   My dreams are all about Bath-buns; (∀x : D(x) → B(x))

•   I never refer any idea of mine to my solicitor, unless it is worth writing down.  (∀x : RS(x) → WWD(x))

The conclusion is “all my dreams come true”, or ∀x : D(x) → T(x). Prove this from the premises using the rules of propositional and predicate calculus.

P2.8.4 (a,b,c,e,g (15 points) Let A and B be sets and let R ⊆ A × B be a relation.  The inverse relation of R is the subset R −1 of B × A defined so that R −1 = { : ∈ R}. Prove or disprove each of the following statements:

(a)   R is total if and only if R −1 is total.

(b)   R is well-defined if and only if R −1 is well-defined.

(c)   R is a function if and only if R −1 is a function.

(e)   If R ⊆ A × A ,R is symmetric if and only if R −1 is symmetric.

(g)   If R ⊆ A × A ,R is transitive if and only if R −1 is transitive.

P2.9.4   If f is a function from a set A to itself, we can compose f with itself. We call the composition (10 points)   of f with itself k times the k’th iterate of f, and write it f(k) .

(a)   If f(x) = x + 2, what is the function f(3)?

(b)   If i and j are any naturals, is it always true that (f(j))(k)  is equal to f(jk)? Why or why not?

(c)   How should we define f(0)? Why?

P2.10.4   In general, a string u is defined to be a substring of a string v if v = xuy for some strings x (15 points)   and y, either or both possibly empty.

(a)   Prove that the substring relation on any set of strings is a partial order.

(b)   Draw the Hasse diagram for the substring relation on the strings of two or fewer letters over the alphabet {a,b,c}.

(c)   Draw the Hasse diagram for the same relation on the substrings of the string abbac. Repeat for the string cababa.

Extra credit:

P2.11.2 (a,b,c)   Let f be any function from A to B . Let R be the binary relation on A defined so that R(x,y) (10 points)   is true if and only if f(x) = f(y).

(6 points)   Prove that R is an equivalence relation.

(2 points)   What do we know about the equivalence classes of R if f is one-to-one? (2 points)   What do we know about the equivalence classes of R if f is onto?


2023-03-13