Reference no: EM132445062
Assignment - Discreate Mathematics Questions
PART A: SET 2 PRACTICE
1. Write the truth table for: ¬ (p∧q) ∨ (r∧¬p)
2. Using: p: Today is Monday.
q: It is rainy.
r: It is hot.
(a-c below) Write the English translation for:
a. ¬p →(q ∨ r)
b. ¬ (p ∨ q ) ↔ r
c. (p ∧ (q ∨ r )) → ( r ∨ ( q ∨ p ))
(d-e below) Write the following sentences using p, q, r, above, and logical connectives (logical operators):
d. "It is rainy and hot, but today is not Monday."
e. "It is not hot, but it is rainy or today is Monday."
3. Prove the following, using logical equivalences. For each step, state the name of the logical equivalence or property you used.
¬ [ (¬p ∧ q) ∨ (¬p ∧ ¬q) ] ∨ (p ∧ q) ≡ p
4. Use a truth table to prove:
p⊕q ≡ (p ∧¬q) ∨ (¬p ∧ q)
5. Do the following for each:
Write statements as needed to form the given propositions. Assign variables (p, q or as appropriate) for the statements. Write the variable along with the statement you have assigned to it.
Write the proposition using quantifier notation and the variables you have assigned for the statements.
Write the negation of the proposition in English.
Write the negation of the proposition, this time using quantifier notation, and the variables you have assigned for the statements.
6. For each statement below (a - f), do the following:
Write the statement using quantifier notation and mathematical symbols;
Determine the truth value of the statement, AND explain/show how you determined the truth value. Show counterexamples, or examples as needed.
a. For every x, for every y, x2 < y + 1
b. For every x, for some y, x2 < y + 1
c. For some x, for every y, x2 < y + 1
d. For some x, for some y, x2 < y + 1
e. For some y, for every x, x2 < y + 1
f. For every y, for some x, x2 < y + 1
7. Given:
p: Fishing is a popular sport.
q: Curling is popular in New Jersey.
For the following arguments (a - c), do the following:
Write the argument symbolically.
State which rule of inference is used.
a. Fishing is a popular sport. Therefore, fishing is a popular sport or curling is popular in New Jersey.
b. If fishing is a popular sport, then curling is popular in New Jersey. Fishing is a popular sport. Therefore, curling is popular in New Jersey.
c. Fishing is a popular sport or curling is popular in New Jersey. Curling is not popular in New Jersey. Therefore, fishing is a popular sport.
8. Prove that if n is an integer, and 3n+2 is even, then n is even.
a. Prove using a direct proof.
b. Prove using proof by contraposition.
c. Prove using proof by contradiction.
9. Use proof by cases (hint: 3 cases) to prove if n is an integer, then n2 ≥ n.
10. Use mathematical induction to prove the following, for all positive integers n. Show ALL algebraic steps!
1/(1·3 )+ 1/(3·5 )+1/(5·7 )+···+ 1/(2n-1)(2n+1) = n/(2n+1 )
11. Use mathematical induction to prove that n3 + 2n is divisible by 3, where n is a nonnegative integer. Show ALL algebraic steps!
12. In Section 2.4, we learned about recurrence relations. Section 5.3 addresses recursion. Explain how these are related. (Only 1 - 2 paragraphs maximum.)
13. On page 357, do 4a, and 4c.
14. Give a recursive definition for the sequence an, where n = 1, 2, 3, ... if an = 4n - 2.
15. On page 358, do 28 a, b, c.
16. Use proof by cases to show that: Every integer that is a perfect cube is:
a multiple of 9;
or is one more than a multiple of 9;
or is one less than a multiple of 9.
17. Prove that if n is an integer, then (the symbols below are "floor"):
⌊n/2⌋ = n/2 if n is even, and
⌊n/2⌋ = (n-1)/2 if n is odd.
PART B: EXPLORATION
ALGORITHMS, BIG-O, BIG-THETA, BIG-OMEGA
Algorithms are covered in depth in computer science classes. Most discrete mathematics classes cover a few algorithm-related topics. READ pgs. 191 - 193.
1. On pg. 196, 197 (note example at top of pg 197) , read about the "bubble sort" algorithm.
On pg. 203, above problem #41, read about "selection sort" algorithm. But also see the YouTube video "Sorting Algorithm | Selection Sort step by step guide".
Apply the bubble sort AND selection sort method to the list below. Write each step / iteration of the list until the entire list is sorted.
List: 5, 3, 1, 6, 2, 4
Big-O, Big-Theta and Big-Omega...no I am not making this up! ;-) are methods to estimate the growth of functions or algorithms, based on the complexity of the function or algorithm. Complexity theory is a topic in advanced computer science courses.
Big-O: READ pgs. 204 - 211. Make note of the graph on pg. 211.
Big-Theta, Big-Omega: READ pgs. 214 - 216.
2. On pg. 216, do problem 26, parts a, b, c, for Big-O.
3. Do problem 26 above, for Big-Theta and Big-Omega.
4. Read about little-o on pg. 218. See problem 61. DO NOT use the examples from 61, but make up three of your own examples for little-o, and solve them.