CS 420 2024fall ibarland

home—lectures—exams—hws—D2L—zoom (snow day)

Sets and Logic
hw01

• Reading: Appendix A of the text.
• Always be clear about what kind of object your answer is (e.g. a set, or an ordered pair) and use the right kind of notation (eg {…} for sets and ‹…› for tuples).
• Exercises refer to the textbook pdf.

Due 2024-Sep-17 (Thu) 14:00 on D2L (a pdf, probably with photos/scans of hand-written work). Bring hardcopy to the start of next in-person class (Sep-24).

1. Recall that a cross-product of three sets is a set-of-3tuples.
   1. List the elements of A, as a set:
      A = {1, 2} x {a, b} x {d, e}.
   2. List the elements of B, as a set:
      B = {1, 2} x {a, b} x { }.
2. Draw a diagram that shows the proper-subset relation among the 8 elements of the power set of {1,2,3}. In your diagram, if P ⊂ Q with nothing in between (i.e. no element R where P ⊂ R ⊂ Q), then write Q somewhere above P and draw a line from P to Q.

   Note: This relation forms what is called a lattice.

3. Let the set A be {RU, VT, JMU}, and let the set B be {red, orange, purple} (or, to save writing, {r,o,p}). For each condition below, give a relation in A × B that satisfies it. List the relations as sets of ordered pairs. Each relation must have at least two elements. For each function, indicate whether it is a total or partial function. If no such relation exists, say so.
   1. A relation that is not a function.
   2. A function that is 1:1 and onto (if possible).
   3. A function that is 1:1 but not onto (if possible).
   4. A function that is onto but not 1:1 (if possible).
4. For the following, say whether or not each statement is true:
   1. T / F : ∃ y  ∈  ℕ (y < 20) ∨ (y>50).
   2. T / F : ∀ y  ∈  ℕ (y < 20) ∨ (y>50).
   3. T / F : ∃ y  ∈  ℕ (y < 20) ∨ (y>10).
   4. T / F : ∀ y  ∈  ℕ (y < 20) ∨ (y>10).
5. For the following, say whether or not each statement is true:
   1. T / F : ∃ y  ∈  ℕ ∀ z  ∈  ℕ (y +z = 20)
   2. T / F : ∀ y  ∈  ℕ ∃ z  ∈  ℕ (y +z = 20)
6. Consider the set C = {n  ∈  ℕ : ∃ m  ∈  ℕ (m≤10 ∧ 2n=m+3)}.
   1. Describe C in English.
      Your answer will start C is the set of natural numbers n such that …, but your answer should not mention m. Do not do any algebra/solving (yet); just describe the condition w/o mentioning m.
   2. Explicitly list the elements of C. (your answer will look something like C = {19, 43, 55}).
   3. If we change the “∧” to “∨”, then what is the set C?
7. Express the proposition below in English. ∀ x  ∈  ℕ (∀ y  ∈  ℕ.(∃ z  ∈  ℕ.(x = y + z)))

   Note: Your answer should start: "For all natural number x…" or better "Every natural number x…".

   Is the statement true?
8. Let the set D={1, 4, 7, 10, 13, …}, where the dots represent numbers that follow the obvious pattern. Express this set in the form D = {n  ∈  ℕ : P(n)}, where you replace P(n) with some proposition of n. I.e. a statement that is true or false depending on the particular value of n, such as “∃ k (n+k = 19)”.
9. Fill in the blanks (which may be a word-fragment, or an exponent):
   1. 1 million ~ 2      
   2. 10¹² = 1               ion ~ 2      
   3. 10     = 1K ~ 1 Ki = 2      
10. Exercise 2.3.2, p.29pdf=14book.
11. Let L₁ = {apple, pear} and L₂ = {pie, cake, ε} (over the alphabet Σ = [a-z]). List the elements of L₁L₂ in lexicographic order. This is just Exercise 2.3.2, p.29pdf=14book made a little less busy-ish.
12. Give two (small) languages L₁,L₂ such that |L₁L₂| < |L₁|⋅|L₂|. Extra credit if you have the smallest possible |L₁L₂|.
13. Exercise 2.3.6, p.29pdf=14book . Do not simply restate the math; instead describe, in English, the strings in each language so that an ITEC friend could understand. None of your answers should include the word prefix.

    For convenience: Your answers may take as understood that the underlying alphabet is Σ = {a,b} — you don't need to repeat that.

14. Exercise 2.3.7, p.29pdf=14book

    poor phrasing: (b)'s phrasing might be improved as the language of odd-length strings (over {a,b}), under the operation Kleene-star.

15. Exercise 2.3.8, p.29pdf=14book, only parts c–e. You can just assert whether the statement is true or false; you do not need to provide a proof for true but you should give a counterexample if false.

Credit: This homework originally based on Dr. Okie's homework Some problems are based on Appendix A of the text.

home—lectures—exams—hws—D2L—zoom (snow day)

This page licensed CC-BY 4.0 Ian Barland Page last generated

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu