Math 255 Discrete Math Final Review Autumn 2024 PDF

***Autumn 2024 (Discrete Math) review for Final*** ***Weight of the test : 35%*** ***Part A: Logic, truth tables, arguments*** ***Q1.*** *For each of the following sentences whether **[it is statement]** (true or false).* *Note we are not requesting whether the statements are True or False?*...

***Autumn 2024 (Discrete Math) review for Final*** ***Weight of the test : 35%*** ***Part A: Logic, truth tables, arguments*** ***Q1.*** *For each of the following sentences whether **[it is statement]** (true or false).* *Note we are not requesting whether the statements are True or False?* ***Sentence*** ***True/False*** ***Why true?/ why false?*** -------------------------------- ------------------ ----------------------------- ***5=8*** ***T*** ***He is smart*** ***F*** ***What is your name?*** ***F*** ***x\>5*** ***F*** ***The number 2 is not even*** ***T*** ***5 is a prime number*** ***T*** ***2^3^=8+12*** ***T*** ***Q2.*** **Symbolic notation in Compound statements Logic** let p, q , r be logic symbols, defined respectively as:   p is the sentence \"you like eat couscous\", q is the sentence \"you prefer local soft drinks\", r is the sentence \"you do not like fruits\" Use logic symbols, to express the following sentences in symbolic notation. a. You like eat couscous but you do not prefer local soft drinks P and \~Q b. You like to eat couscous but you either do not prefer local soft drinks or you do not like fruits P and ( \~Q or R) c. You like to eat couscous or you like to eat fruits ***P or \~R*** ***Q3.*** **Validity /Invalidity of a logic argument** In this problem, you must use a truth table to prove the validity/invalidity a logic argument: Given the following symbols: ***P: Score more than 84 Q: you obtain HD*** Your Task consists of three steps: (i), (ii), (iii) +-----------------------------------+-----------------------------------+ | **Premise in natural language** | **Logic statement** | +-----------------------------------+-----------------------------------+ | a\) If you score more than 84 | P Q | | then you will obtain an HD | | | | \~Q \~P | +-----------------------------------+-----------------------------------+ | b\) You obtained an HD | Q | +-----------------------------------+-----------------------------------+ | c\)  You | P | | scored more than 84 | | +-----------------------------------+-----------------------------------+ ii\. You must use a Truth Table to determine the validity/invalidity of the argument. +-------------+-------------+-------------+-------------+-------------+ | **P** | **Q** | P Q | Q | Conclusion | | | | | | | | | | | | P | +-------------+-------------+-------------+-------------+-------------+ | T | T | T | T | T | +-------------+-------------+-------------+-------------+-------------+ | T | F | F | | | +-------------+-------------+-------------+-------------+-------------+ | F | T | T | T | F | +-------------+-------------+-------------+-------------+-------------+ | F | F | T | F | | +-------------+-------------+-------------+-------------+-------------+ --------------------------------- ---------------------------------------------------------- Valid / invalid **You must provide proof for your answer to get credit** ~~Yes, this argument is valid~~ No, this argument in not Valid See the critical rows there is one False conclusion --------------------------------- ---------------------------------------------------------- ***Note: in this example the \# of critical rows=2*** ***the \# of critical rows with a True Conclusion =1*** ***Q4. Same instruction as above (three steps)*** Given the following symbols: ***P: did not score more than 84 Q: you obtain HD*** ***i)*** ---------------------------------------------------------------------- --------------------- **Premise in natural language** **Logic statement** a\) If you did not score more than 84 then you will not obtain an HD P \~Q b\) You obtained an HD Q c\) You scored more than 84 \~P ---------------------------------------------------------------------- --------------------- ii) +---------+---------+---------+---------+---------+---------+---------+ | *P* | *Q* | *\~Q* | *Premis | *Premis | Conclus | | | | | | e | e | ion | | | | | | 1* | 2* | | | | | | | | | \~P | | | | | | *P \~Q* | *Q* | | | +---------+---------+---------+---------+---------+---------+---------+ | *T* | *T* | *F* | *F* | *T* | | | +---------+---------+---------+---------+---------+---------+---------+ | *T* | *F* | *T* | *T* | *F* | | | +---------+---------+---------+---------+---------+---------+---------+ | *F* | *T* | *F* | *T* | *T* | T | **Criti | | | | | | | | cal | | | | | | | | row** | +---------+---------+---------+---------+---------+---------+---------+ | *F* | *F* | *T* | *T* | *F* | | | +---------+---------+---------+---------+---------+---------+---------+ iii) -------------------------------- ------------------------------------------------------------------------------ Valid / invalid **You must provide proof for your answer to get credit** Yes, this argument is valid Valid all critical rows (only one in our case) it is true for the conclusion No, this argument in not Valid -------------------------------- ------------------------------------------------------------------------------ ***Note: in this example the \# of critical rows=1*** ***the \# of critical rows with a True Conclusion =1*** *Q5**. Same as above*** ***P: Scoring more than 84 Q: you obtain HD*** ------------------------------------------------------------------------ --------------------- **Premise in natural language** **Logic statement** a\) scoring more than 84 is a **sufficient** condition to obtain an HD PQ b\) You obtained an HD Q c\)  You scored more than 84 P ------------------------------------------------------------------------ --------------------- ***in this example the \# of critical rows=?*** ***the \# of critical rows with a True Conclusion =?*** ***Q6. Same as above*** +-----------------------------------+-----------------------------------+ | **Premise in natural language** | **Logic statement** | +-----------------------------------+-----------------------------------+ | a\) scoring more than 84 is a | \~P \~Q or | | **necessary** condition to | | | obtain an HD | Q P | +-----------------------------------+-----------------------------------+ | b\) You obtained an HD | Q | +-----------------------------------+-----------------------------------+ | c\)  You | P | | scored more than 84 | | +-----------------------------------+-----------------------------------+ ***Q7. As above only step ii) and step 3*** Must use a truth table to prove the validity/invalidity a logic argument: Q8. (same as Q8) - P Q8' (P Q) V (Q R) Q9. (same as Q8) - \~Q ***Q10. Let the predicate P(n): 2^n^ \> n! n≥0*** i. ***Is P(0) true? 1\>0!=1 false*** ii. ***Is P(1) true? 2\>1! true*** iii. ***Is P(2) true? 4\>2! true*** iv. ***Is P(3) true? 2^3^\> 3!=6 true*** v. ***Is P(4) 2^4^\> 4!=24 false*** vi. ***Is P(5)? 2^5^\> 5!=120 false*** vii. ***Does it exists an integer n≥0 such that P(n) : answer yes (see above)*** viii. ***For every integer n≥0 we have P(n) : answer is ???*** ***Q11. Negation of Boolean expressions (for each Boolean expression write its negation)*** **Statement** **Negation** --- ---------------- ----------------- 1 P ∧ Q 2 P V Q 3 P → Q P and \~Q 4 ∀x:D, Q(x) ∃x:D, \~ Q(x) 5 ∃x:D, Q(x) ∀x:D, \~Q(x) 6 ∀x:D,P(x)→Q(X) ∃x:D, P and \~Q ***Solution*** **Statement** **Negation** --- ---------------- -------------------------------- 1 P ∧ Q \~P V \~Q (Demorgan's theorem) 2 P V Q \~P ∧ \~Q (Demorgan's theorem) 3 P → Q P ∧ \~Q 4 ∀x:D, Q(x) ∃x:D, \~Q(x) 5 ∃x:D, Q(x) ∀x:D, \~Q(x) 6 ∀x:D,P(x)→Q(X) ∃x:D, P(x) ∧ \~Q (x) ***Q12 Determine the truth value of the following Boolean Expressions*** +-------------+-------------+-------------+-------------+-------------+ | ***Boolean | *P is True* | *P is True* | *P is | *P is | | expression* | | | False* | False* | | ** | *Q is True* | *Q is | | | | | | False* | *Q is True* | *Q is | | | | | | False* | +=============+=============+=============+=============+=============+ | **P\~Q** | | ***T*** | | | +-------------+-------------+-------------+-------------+-------------+ | **(P ∧ \~Q | | ***F*** | | | | )** ∧**Q** | | | | | +-------------+-------------+-------------+-------------+-------------+ | **(P ∨ \~Q | | ***F*** | | | | ) ∧Q** | | | | | +-------------+-------------+-------------+-------------+-------------+ | ***P is | | | | | | sufficient | | | | | | for Q*** | | | | | +-------------+-------------+-------------+-------------+-------------+ | ***P is | | | | | | necessary | | | | | | for Q*** | | | | | +-------------+-------------+-------------+-------------+-------------+ | ***(PQ) V | | | | | | (\~Q P)*** | | | | | +-------------+-------------+-------------+-------------+-------------+ ***Q13.*** ***[Let P is true and Q is false]*** **P\~Q** **(P ∧ \~Q )** ∧**Q** **(P ∨ \~Q ) ∧Q** ---------- ----------------------- ------------------- ***T*** ***T*** ***T*** ***T*** ***T*** ***F*** ***T*** ***F*** ***T*** ***T*** ***F*** ***F*** ***F*** ***T*** ***T*** ***F*** ***T*** ***F*** ***F*** ***F*** ***T*** ***F*** ***F*** ***F*** ***Q14. [Let P is false and Q is false (which alternative (among the 8 alternatives) is correct for all the three compound logic statements]*** **P\~Q** **(P ∧ \~Q )** ∧**Q** **(P ∨ \~Q ) ∧Q** ---------- ----------------------- ------------------- ***T*** ***T*** ***T*** ***T*** ***T*** ***F*** ***T*** ***F*** ***T*** ***T*** ***F*** ***F*** ***F*** ***T*** ***T*** ***F*** ***T*** ***F*** ***F*** ***F*** ***T*** ***F*** ***F*** ***F*** ***Q15. Graph from the lecture***  ***16. Validity of arguments using sets*** a. ***All animals are living species*** ***Table is not a living species*** ***Therefore Table is not an animal*** ***Prove whether the above argument using set representation*** ***Solution*** ***Corresponding diagram : All animals are living species***  ***Table is not a living species*** ***Therefore: Table is not an animal*** ***Yes it is a true argument (see Ven diagram)*** ***17. If you come to my office, I will give a book*** ***If I do not give a book, you will not be happy***  ***if you will be happy, you come to office*** ***Use the following logic symbols*** ***P: you come to my office Q: I will give a book H: You will be happy*** ***Solution (pls 8*** +---------+---------+---------+---------+---------+---------+---------+ | ***P*** | ***Q*** | ***S*** | ***Prem | ***\~P* | ***Prem | ***Conc | | | | | ise | ** | ise | lusion* | | | | | 1 P | | 2*** | ** | | | | | Q*** | | | | | | | | | | ***\~Q\ | ***HP** | | | | | | | ~H*** | * | +=========+=========+=========+=========+=========+=========+=========+ | ***T*** | ***T*** | ***T*** | | | | | +---------+---------+---------+---------+---------+---------+---------+ | ***...* | ***...* | ***...* | | | | | | ** | ** | ** | | | | | +---------+---------+---------+---------+---------+---------+---------+ | ***F*** | ***F*** | ***F*** | | | | | +---------+---------+---------+---------+---------+---------+---------+ ***Hint Use Truth table*** ***Part B: Sets*** ***Sets.Q1.*** - ***Is {0}=0? Why? Why not?*** - ***How many elements are in the set {1, {1}}?*** - ***For each integer n, let U~n~={n, -n}. Find U~1~, U~2~, U~0~.*** ***Answer is in the lecture*** - ***{0} ≠0: {0} is a set with an element 0. 0 is just the symbol representing the number zero.*** - ***The set {1, {1}} has two elements: 1, {1}.*** - ***U~1~={1, -1}*** - ***U~2~={2,-2}*** - ***U~0~={0,-0}={0}*** ***Sets. Q2. Describe the following sets:*** ***Answer*** ***\]-2,5\[*** ***{-1,0,1,2,3,4}*** ***Sets.Q3*** ***Solution***  Sets.Q4. Ordered pair (tuple) with solution  Sets Q5. Cartesian Product with solution  Sets.Q6 **operations on sets with solution**: Union (∪), intersection (∩), difference − Complete the table to understand where A and B are sets and U is the universal set +-------------+-------------+-------------+-------------+-------------+ | Operation | Statement | Detail | Statement | Detail | | | | representat | | representat | | | | ion | complements | ion | +=============+=============+=============+=============+=============+ | Union | x ∈ | x ∈ A | x ∉ | x ∉ A and x | | | (A ∪**Β)** | **[or]{.und | (A ∪**Β)** | ∉ B | | | | erline}** | | | | | | x ∈ B | | | +-------------+-------------+-------------+-------------+-------------+ | Intersectio | x ∈ | x ∈ A | x | x ∉ A or x | | n | (A ∩** Β)** | **[and]{.un | ∉(A ∩** Β)* | ∉ B | | | | derline}** | * | | | | | x ∈ B | | | +-------------+-------------+-------------+-------------+-------------+ | Difference | x ∈ | x ∈ A | x ∉ | x in U. x ∉ | | | (A − **Β)** | **[and]{.un | (A − **Β)** | A or x ∈ B | | | | derline}** | | | | | | x ∉ B | | | +-------------+-------------+-------------+-------------+-------------+ Sets.Q7 **operation on sets** - Let **U** be the universal set of integers from 1 to 10 U={1,2,...,9,10} - - A={ 1,3,6,7,9} - B={ 5, 4, 7, 9} Find 1. (A ∪Β)= 2. (A ∩ Β) = 3. (A − Β)= 4. (A − Β) ∩ (Β−Α)= 5. (A ∪Β) ∩ ∅ = 6. Complement of (A-B) Sets Q8. **Power Set** and operation on sets Operation on sets ---- ------------------------- ------------------- \# Power set asked Answer with proof 1 P 2 P 3 P ---- ------------------------- ------------------- **Q9 Set Partition** **Let A={a, 1 , 3 ,b}** a. Define what is meant by partitioning a set (state the two conditions for a set to be a partition of A) b. Give four different partitions of the set A. ------------------------ -------- ------- Case Yes/No Proof   ------------------------ -------- ------- Part C. Relations and Functions Q1. Relation (with solution)  Q2. Property of relations: R⊆A×A **R is said to be** **Definition** **R is said to be** **Definition** --------------------- ----------------- --------------------- ---------------- Reflexive See cheat sheet Not Reflexive Symmetric Not Symmetric Transitive Not Transitive Q3 Relation. Property of relation: application For each relation state its properties : R: Z **→Z** and let (x,y) ∈ R +-----------------+-----------------+-----------------+-----------------+ | Relation | R is reflexive | R is symmetric | R is transitive | | | | | | | | T/F why? | T/F why? | T/F why? | +=================+=================+=================+=================+ | a\) 2 \| (x-y) | | | | +-----------------+-----------------+-----------------+-----------------+ | b\) 4\|(x-y) | | | | +-----------------+-----------------+-----------------+-----------------+ | c\) x\>y | | | | +-----------------+-----------------+-----------------+-----------------+ | d\) x=y+1 | | | | +-----------------+-----------------+-----------------+-----------------+ | e\) x+y is | | | | | divisible by | | | | | 3 | | | | +-----------------+-----------------+-----------------+-----------------+ Q4. (with solution) Define the relation R on the set A={1,2,3,4} +-----------------+-----------------+-----------------+-----------------+ | Relation | R is reflexive | R is symmetric | R is transitive | | | | | | | | T/F why? | T/F why? | T/F why? | +=================+=================+=================+=================+ | R={(2,3),(3,2)} | F | Y | NO (F) | +-----------------+-----------------+-----------------+-----------------+ | R={(2,4),(4,2), | F | F | F | | (2,3)} | | | | +-----------------+-----------------+-----------------+-----------------+ | R={(1,1).(2,2), | T | T | T | | (3,3),(4,4)} | | | | +-----------------+-----------------+-----------------+-----------------+ | R={(4,2), | F | F | T | | (3,3),(1,1)} | | | | +-----------------+-----------------+-----------------+-----------------+ **[Q5.]** Let the relation R defined A= {a,b,c} be represented by the following graph (with solution) For each property state whether it is True/False for the relation R. State why? **[Property]** **[T/F]** **[Why]** ---------------------------- ----------------------- ----------------------------------------- Reflexive **[T]** Every element x in A: xRx Symmetric **[F]** aRb but b is not related to a Transitive **[F]** aRb and b R c but a is not related to c [ ] **[Q6. Transitive closure]** Let R be a relation defined on A ={0,1,2,3} where R={(1,2),(2,1), (1,3), (3,1)} Find its transitive closure R^T^ **[R^T^ ={ (1,2),(2,1),(1,3),(3,1), (1,1),(2,2),(3,3), (2,3) , (3,2)}]** **[Functions ]** Q1. State whether the following statement are true/false a. All functions are relations T b. All relations are function F c. Some relations are functions T Q2. If **f** a function from A **→ B** a. What is its domain? A b. What is its codomain? B Q3. Given the following relation **f** from the X**→Y**  a. Is **f** a function? State why? T b. What is its domain {x1,x2,x3,x4} c. What is its codomain? { y1,y2,y3,y4,y5} d. What is its the range? {y1,y3,y4} e. What is the image of x~3\ ;~ f(x~3~) = y~3~ ? f. What are the elements of the function f={ (x~1~, y~3~) , (x~2~,y~1~), (x~3~,y~3~),(x~4~,y~4~)} } **Q4.** a. Define what is meant by a function to be a **one-to-one** function a. Is **F** a one-to-one function? state why? Yes Yes (no two elements have the same image) b. Is **G** a one-to-one function? state why? NO G(a)=G(c) a and c have the same image Q5. Proving that a function is **one-to-one** Let f : Z **→Z; f(x) = 6x-5** a. Find f(3)=13 ; f(-3)=-23 b. Show that f is **one-to-one** hint: use the definition **∀*x*~1~*, x*~2~ ∈ *X,* if *f (x*~1~*)* = *f (x*~2~*)* then *x*~1~ = *x*~2~ )** f(x~1~)=f(x~2~) 6x~1~-5 = 6x~2~-5 =\> 6x~1~=6x~2~ x~1~=x~2~ one to one Q6. Proving that a function is **not one-to-one** Let f : Z **→Z; f(x) = x^2^** c. Find f(2)=4 ; f(-2)=4 d. Show that **f** is not one-to-one hint: use the Negate ( **∀*x*~1~*, x*~2~ ∈ *X,* if *f (x*~1~*)* = *f (x*~2~*)* then *x*~1~ = *x*~2~)** **∀*x*~1~*, x*~2~ ∈ *X,* if *f (x*~1~*)* = *f (x*~2~*)* then *x*~1~ = *x*~2~)** ∃x1,x2 **∈ *X, f (x*~1~*)* = *f (x*~2~*)* and *x*~1~ ≠ *x*~2~)** [ ] **[f(2)=f(-2) but 2≠-2 ]** **[2 and -2 have the same image]** Q7. Determine whether the function *f* from {*a, b, c, d*} to {1*,* 2*,* 3*,* 4*,* 5} with - **is one-to-one** +-----------------------+-----------------------+-----------------------+ | **Proof** | | | | | | | | From the table, | | | | below, we see that | | | | the function *f* is | | | | one-to-one because | | | | *f* takes on | | | | different values at | | | | the four elements of | | | | its domain. | | | +-----------------------+-----------------------+-----------------------+ | | | | +-----------------------+-----------------------+-----------------------+ | | | | +-----------------------+-----------------------+-----------------------+ | | | | +-----------------------+-----------------------+-----------------------+ | | | | +-----------------------+-----------------------+-----------------------+ | D | | | +-----------------------+-----------------------+-----------------------+ [ ] [ ] **[Onto functions (see definition in the lecture)]** **[Q8]** [ ]  a. As given above, Is F an onto function? State why? Yes range=codomain b. What is the codomain of F? what is the range of F? Y, range=Y c. Is F a one-to one? State why? two elements from the domain have the same image **Q9.** a. As given above, Is F an onto function? State why? Range ≠codomain range is proper subset of codomain Not onto **Q10.** a. what is f(0.8) = ? = 4\*.8-1 = 2.2 b. what is the inverse of f^-1^(1.6) 4x-1=1.6 4x =2.6 x=2.6/4=0.65 c. hint find x such f(x)=1.6 d. show that f is an onto function? If **R → R yes it is onto** **Q11.** however **Define *h*: Z → Z where** ***h(n) = 4n-1*** a. what is h(2) = ? 7 b. what is the inverse : h^-1^(2) : hint find n such h(n)=2. Is n an integer 4x-1=2 =\> 4x=3 x=3/4 which is not an integer so 2 does not have a pre-image c. Is h an onto function? from above the function is not onto **Q12.** **Define *f* : R → R ; *f (x)* = 4*x* − 1 for all *x* ∈ R (same Q10)** a. Is the function f a one-to-one? f(x~1~)=f(x~2~) 4x~1~-1 = 4x~2~-1 4x~1~ = 4x~2~ x~1~ = x~2~ f is one to one b. Is f a one to one correspondence (bijective), state why? It is both 1-1 and onto f a one to one correspondence (bijective) **Q13.** Let the function *f* (*x*) = *x*^2^ from the set of integers to the set of integers **Z → Z** Is *f* (*x*) a one-to-one function? Is it onto? [One to one] ? f(2)=f(-2) it is not [Onto] ? f(x)=-4? *x*^2^ = -4 no x so (-4 does not have a pre-image) not onton Q14. Define  by the rule - Is *f* one-to-one? Prove or give a counterexample. 2n~1~=2n~2~ n~1~=n~2~ - Is *f* onto? Prove or give a counterexample **Q15.** Define  by the rule f: n → f(n)=4n-5 ∀n ∈ Z a\) Is *f* one-to-one? Prove or give a counterexample. b\) Is *f* onto? Prove or give a counterexample **Q16 The language of relations** Let *A* ={2, 4} and *B* = {1, 3, 5} and define relations *U*, *V*, from *A* to *B* as follows: a. For every (*x*, *y*) ∈ *A* x *B*: (*x*, *y*) ∈ *U* means that *y* -- *x* \> 2. b. For every (*x*, *y*) ∈ *V* means that *y*-1 = *x /* 2 YOUR TASKS? a. What are the elements of A xB? 1 3 5 --- ------- ------- ------- 2 (2,1) (2,3) (2,5) 4 (4,1) (4,3) (4,5) b. What are the elements of U (Hint use the below table to simplify your task) ---------------------------- --------------- ------------------------- **Element (x,y) of A x B** **y-x \> 2?** **Element of U or not** (2,1) F NO (2,3) F No (2,5) T Yes (4,1) F NO (4,3) F NO (4,5) F NO ---------------------------- --------------- ------------------------- c. What are the elements of V? Same as in (c) the following table will ease your work: ---------------------------- ----------------- ------------------------- **Element (x,y) of A x B** **y-1 \> x/ 2** **Element of V or not** (2,1) 0\>2/2 NO (2,3) 2\>2/2 Y (2,5) 4\>2/2 Y (4,1) 0\>4/2 No (4,3) 2\>4/2 No (4,5) 4\>4/2 Y ---------------------------- ----------------- ------------------------- Therefore **V=? { (2,3), (2.5), (4,5)}** d. Write the domain and co-domain of V +-----------------------------------------------------------------------+ | *Domain A* = | | | | Co Domain B | +-----------------------------------------------------------------------+ **e.** Write the domain and co-domain of U +-----------------------------------------------------------------------+ | Domain is A | | | | codomain is B | +-----------------------------------------------------------------------+ a. Find (f ∘ g)(1)= f(g(1))=f(1)=3 (f ∘ g)(3)= f(g(3))=f(1)=3 (f ∘ g)(5)= Part D. Methods of Proof (direct, contrapositive, induction, counter example, contradiction) Only Math induction is included Q2. **Math induction** a. Use mathematical induction to prove that for all integers We have:  Your proof must: b. Same logic as above P(n): 1+2 +... + n = n x (n+1) / 2 n≥1 c.  1 + 3 + 5 +... + (2n−1) = n^2^ n≥1 Prove that P(1) is true Show that if P(k) is True then P(k+1) is true **Q3. sequences** a. What is the general term of the following sequence (use the table shown in the workshop) 2/1 + 1/1 ; 2/2 + 2/4 ; 2/3 + 3/9 ; 2/4 +4/16; 2/5+5/25 b. Generate 4 terms of the sequence defined by its general term 3/k + k/(k+1) k≥1