Discrete Mathematical Structures
CS2233 Discrete Mathematical Structures Fall 2021 Homework 2 Due 9/23/19 before 11:59pm 1. Predicates and Quanti ers (7 points) (1) (3 points) Let L(x ) denote the statement x has used calculus.” and D denote the domain of all students in our class. Express each of these quanti ed propositions in English: (a) 8 x2 D : L (x ) (b) :9 x2 D : L (x ) (c) 9 x2 D : : L(x ) (2) (2 points) Let Q(x ) denote the statement 2 x > 3x ” and Zdenote all integers (i.e., : : : ; 3; 2; 1;0 ;1 ;2 ;3 ; : : : ). Determine the truth value of each of these statements: (a) Q(2) (b) Q(4) (c) 8 x2 Z : ( Q(x ) _ x < 4) (d) 9 x2 Z : ( Q(x ) ^ x < 4) (3) (2 points) Translate the following statements to English where B(x ) is x understands boolean algebra" and M(x ) is xhas taken discrete math" and the domain Dis all students at UTSA. (a) 8 x2 D : ( M (x ) ! B(x )) (b) 9 x2 D : ( B(x ) ^ : M(x )) 2. Nested Quanti ers (3 points) Let K(x; y ) denote the statement x knows y" and Ddenote the domain of all people. Express the following English sentences as a quanti ed proposition using the de nitions above: (1) Everybody knows somebody. (2) There is somebody that no one knows. (3) There is no one who knows everybody. 3. Negating Quanti ers (3 points) Rewrite each of these statements such that all of the negation symbols (i.e., : ) are in front of the propositional functions Por Q. (1) :9 x: ( P(x ) ^ Q(x )) (2) :8 x9 y8 z : ( P(x; y )! Q(z; y )) Continued on the back ,! 4. Negation (6 points) Let S(x; y ) denote the statement x has seen y" and Ddenote the set of all students in our class and Mbe the set of all movies. (1) (2 points) Express the following English sentence as a quanti ed propo- sition using the de nitions above: For every movie there is a pair of students in our class who have both seen it." Hint: Use three quanti ers for this one. (2) (2 points) Negate the quanti ed proposition you wrote for part (1) (i.e., place a :" in front of it). Use de Morgan's law for quanti ers to move the negation inside the quanti ers. (3) (2 points) Translate you answer for part (2) back to plain English.