Assigned: | Friday, August 30 |
Due: | Monday, September 9 |
Write each of the following using set notation.
Is {} ∪ S = S for every set S? Justify your answer.
Briefly define the following.
Explain the error in the following proof that 1 = 2.
Consider equation a = b. Multiply both sides by a, obtaining a2 = ab. Subtract b2 from both sides to get a2 − b2 = ab − b2. Factor each side, giving (a + b)(a − b) = b(a − b). Divide each side by (a − b), giving a + b = b. Now choose a = 1 and b = 1, giving 2 = 1.
Prove that, in every simple graph with at least two vertices, there are two vertices that have the same degree.
A number is rational if it is the ratio of two integers. Prove that √2 is not rational. (Hint. Reason by contradiction. Suppose that there exist two integers x and y so that x/y = √2. Square both sides. Think about prime factorizations of integers. Two positive integers are equal if and only if they have the same prime factorization.
Draw a transition diagram of a DFA that accepts exactly each of the following languages over alphabet Σ = {a, b, c}.
Show that each of the following languages is not regular. Do not use the Pumping Lemma. ak is a string of exactly k a's.