page 1 of 4 CSE 2321 Foundations I Autumn 2015 Prof Supowit Homework 2 Due Wednesday September 9 1 Let P x be the predicate x is a dragon Let Q x be the predicate x breathes fire Let R x y be the predicate x and y are the same object Rewrite the following English statements in symbolic language using the predicates P Q and R and universal and existential quantifiers and connectives a b c d e f g h There are no dragons Not everything is a dragon There is at least one dragon There are at least two dragons There is at most one dragon There is exactly one dragon Dragons breathe fire Only dragons breathe fire Translate the following symbolic propositions into English i j k l m n x P x Q x x Q x P x x Q x x P x x P x Q x x P x x Q x x Q x P x page 2 of 4 2 Using only symbols logical connectives constants 0 1 and 2 variables and quantifiers write the following predicates concerning natural numbers The simpler your answer the better Part a is solved as an example a x is a sum of two squares of natural numbers SOLUTION y z x y y z z b x is a common multiple of y and z c x is the least common multiple of y and z d x is a prime number NOTE we consider 2 to be the smallest prime 3 Given the predicates Cloud c which says that c is a cloud and Above c d which says that c is above d write a statement in first order logic that says Above each cloud is another cloud 4 Write the following maxim attributed to Abraham Lincoln in first order logic You can fool some of the people all of the time and all of the people some of the time but you cannot fool all of the people all of the time Your solution must use the following predicates and no others Person p meaning p is a person Time t meaning t is a moment in time YouCanFool p t meaning You can fool p at time t page 3 of 4 5 Express the following sentence in first order logic The witness told the truth the whole truth and nothing but the truth Your solution must use the following predicates and no others True x means x is true WitnessTold x means The witness told x 6 Define the binary Boolean operation NOR as follows A B 0 0 0 1 1 0 1 1 A NOR B 1 0 0 0 Is NOR universal Prove your answer 7 Let A a b c and B b d f We ll write POW S to denote the power set of a set S a What is POW A POW B b What is POW A B c What is POW A POW B 8 Determine the truth of each of the following sentences supporting your answer with a Venn diagram or perhaps a specific counter example a set A set B A B B A b set A set B A A B A c set A set B A A B A d set A set B A B B A A e set A set B A B A A f set A set B A B A A g set A set B set C A B C A B C page 4 of 4