ITEC 420 2023fall 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 2023-Sep-07 (Thu) at start of class.

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 you and two of your friends, and let the set B be the set of your car and your friends' cars. (Assume that each friend has exactly one car.) 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. To save writing, you may use initials or first names for people and abbreviations for cars. 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).
   You might want to ponder what each of these relations might represent.
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}).
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 of n, such as ∃ k (n+k = 19).
9. Express the result in 5 or fewer characters/digits: 2⁶⁰ · 2⁴ =         

   Hint: For Express 10·16 in 3 characters (instead of 5), an answer would be 160.

10. Express the result in 5 or fewer characters: How many distinct numbers can be represented with 64 bits?
11. Show that the set 3ℤ (the multiples of 3, i.e. …, -6, -3, 0, 3, 6, …) are countable, by explicitly giving a bijection f between ℕ and this 3ℤ. You do not need to prove your function is 1:1,onto, but you should satisfy yourself of that in your head.
12. Exercise 2.3.2, p.29pdf=14book.
13. 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.
14. Give two (small) languages L₁,L₂ such that |L₁L₂| < |L₁|⋅|L₂|. Extra credit if you have the smallest possible |L₁L₂|.
15. 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.

16. Exercise 2.3.7, p.29pdf=14book, only parts b,c.

    poor phrasing: (b) could better be phrased as the language of odd-length strings (over {a,b}), under the operation Kleene-star.

17. 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.

This homework 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