Download Midterm Exam Problems on Discrete Mathematics | MATH 3336 and more Exams Discrete Mathematics in PDF only on Docsity! Discrete Mathematics. EXAM 1 READ.ME The test is divided into three major sections: propositional and predicate calculus; proofs; sets and functions. There are many problems but you don’t have to solve them all. Most probably you cannot do it simply due time restrictions. The maximum credit for the test you can get is 100 points. The assigned sum of all points for all problems is much higher. So, do not be in a hurry, and, in order to save time during the test, spend five minutes now and read the rules. First, take a quick look to all problems and indicate which of them you can solve fast (or, mark the problems which are too hard to solve fast). Second, keep in mind that the number of credit points you can earn from each particular section does not exceed 40. If, for instance, you get 45, the five extra points will be cut off. Finally, even if you get 40 credit points from each section, you final credit won’t exceed 100. Also, there is a couple of tricky questions when you have to do something what is impossible to be done. Just recall a proper definition or a property, write down that you cannot do it and indicate the reason why. Good luck. 1 1 Propositions and predicates Problem 1.1 a) Give the definition of a proposition. (2 pt) b) Give an example of a declarative sentence which is not a proposition. Explain. (2 pt) c) Give an example of a proposition which is not a declarative sentence. Explain.(2 pt) d) Give an example of a proposition and determine its truth value. Ex- plain.(2 pt) Problem 1.2 Let p and q be the propositions “I am a criminal” and “I rob banks”. a) Express in simple English the proposition “if p then q” in several dif- ferent ways. (3 pt per variant, 15 pt max) b) Express in simple English the proposition which is a contrapositive to “if p then q” (3 pt) Problem 1.3 Let p, q, r, and s be four propositions. a) Using only the conjunction and negation operators, find a compound proposition which is true iff p = T , q = F , r = F , and s = T . (5 pt) b) Using only the negation, conjunction and disjunction operators, find a compound proposition which is true iff exactly three of the propositions p, q, r, and s are true. (8 pt) Problem 1.4 Give an example of a binary predicate P (x, y) when the ex- pression ∀x∃yP (x, y) is not the same as the expression ∃y∀xP (x, y). (2 pt) 2