! ! 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) There are no dragons. (b) Not everything is a dragon. (c) There is at least one dragon. (d) There are at least two dragons. (e) There is at most one dragon. (f) There is exactly one dragon. (g) Dragons breathe fire. (h) Only dragons breathe fire. Translate the following symbolic propositions into English: (i) ∀x( )P(x)∧Q(x)[ ] (j) ∀x( )Q(x) ⇒ P(x)[ ] (k) ∀x( )Q(x)[ ]⇒ ∀x( )P(x)[ ] (l) ∃x( )P(x)∧Q(x)[ ] (m) ∃x( )P(x)[ ]∧ ∃x( )Q(x)[ ] (n) ∃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 A NOR B0 0 10 1 01 0 01 1 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#$%&! ! page!4!of!4!(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(