CMSC 250 – Jerry Alan Fails Student: __________________ Due: Friday, June 15, 2007 ID #: __________________ HW #4 Due: Friday, June 15, 2007 Page 1 of 2 HW #4 You must work alone on your homework, and homework must be written legibly, single-sided on your own lined paper, or typed, with the answers clearly labeled and in the sequential order as assigned. You must write your name and university ID number in the upper right-hand corner of your homework. Staple all pages together and be sure that your name appears on every sheet. 1. (5 points) Write your name clearly on each page. Write the time and place of the first midterm. 2. (24 points) Let the predicate E(p,f) = “person p eats food f”, where P=People and F=Foods. For each of the following statements write the meaning of the statement using informal language, then negate the statement using formal notation, and write the meaning of the negation using informal language. (a) ∀p∈P ∃f∈F E(p,f) (b) ∀f∈F ∃p∈P ~ E(p,f) (c) ∃p∈P ∃f∈F ~ E(p,f) (d) ∃f∈F ∀p∈P E(p,f) 3. (11 points) Assume all definitions are for the domain of ΖΖΖΖ+. Also assume the proposition SL(x) means x is sufficiently large. Write the following definitions using quantifiers: (a) (3 points) Define a predicate for odd numbers, Odd(x). (b) (3 points) Define a prediate for prime numbers, Prime(x). (c) (5 points) Every sufficiently large odd number can be written as the sum of three primes. 4. (20 points) Indicate which of the following statements are true and which are false. Justify your answers as best you can. (a) ∃x∈R, such that ∀y∈R, x = y + 1 (b) ∀x∈R+, ∃y∈R+, such that xy = 1 (c) ∀x∈ΖΖΖΖ+ and ∀y∈ΖΖΖΖ+, ∃z∈ΖΖΖΖ+ such that z = x – y (d) ∃u∈R+, such that ∀v∈R+, uv < v 5. (30 points) Prove the following using the rules on the sheet you were given. Assume in all cases that P is nonempty and give justification for each step. Assume that t represents a tautology and c a contradiction unless otherwise stated. Also assume a and b are members of the set P. (a) P1 ∀x∈P, C(x) → P(x) P2 ∀x∈P, ~ P(x) ∴∴∴∴ ∀x∈P, ~ C(x)CMSC 250 – Jerry Alan Fails Student: __________________ Due: Friday, June 15, 2007 ID #: __________________ HW #4 Due: Friday, June 15, 2007 Page 2 of 2 HW #4 (b) P1 ∀x∈P, P(x) → C(x) P2 ∃y∈P, P(y) ∧ ~ F(y) P3 ∀z∈P, ~ C(z) ∨ ~ E(z) ∴∴∴∴ ∃s∈P, ~ E(s) (c) P1 ∀x∈D, P(x) ∨ (E(x) → ~ C(x)) P2 ∀x∈D, S(x) ∨ (F(x) → E(x)) P3 ∃y∈D, ~ (P(x) ∨ S(x)) ∧ F(x) ∴∴∴∴ ∃x∈D, ~ E(x) ∨ (C(x) → R(x)) 6. (No points will be awarded for this assignment unless this is done) Sign your name to the following honor code statement: “I pledge on my honor that I have not given or received any unauthorized assistance on this
View Full Document
Unlocking...