0.3 Discrete structures logic  (Page 23/23)

a. ∃ x P(x)

b. ∀ x ¬ P(x)

c. ∃ x ¬ P(x)

d. ¬∀ x ¬ P(x)

35. Let P(x) be the statement " x > x 2." If the universe of discourse is the set of real numbers, what are the truth values of the following?

a. P(0)

b. P(1/2)

c. P(2)

d. P(-1)

e. ∃ x P(x)

f. ∀ x P(x)

36. Suppose that the universe of discourse of the atomic formula P(x,y) is {1, 2, 3}. Write out the following propositions using disjunctions and conjunctions.

a. ∃ x P(x, 2)

b. ∀ y P(3, y)

c. ∀ x ∀ y P(x, y)

d. ∃ x ∃ y P(x, y)

e. ∃ x ∀ y P(x, y)

f. ∀ y ∃ x P(x, y)

37. Let L(x, y) be the predicate " x likes y," and let the universe of discourse be the set of all people. Use quantifiers to express each of the following statements.

a. Everyone likes everyone.

b. Everyone likes someone.

c. Someone does not like anyone.

d. Everyone likes George.

e. There is someone whom everyone likes.

f. There is no one whom everyone likes.

g. Everyone does not like someone.

38. Let S(x) be the predicate " x is a student," B(x) the predicate " x is a book," and H(x,y) the predicate " x has y , " where the universe of discourse is the universe, that is the set of all objects. Use quantifiers to express each of the following statements.

a. Every student has a book.

b. Some student does not have any book.

c. Some student has all the books.

d. Not every student has a book.

e. There is a book which every student has.

39. Let B(x) , E(x) and G(x) be the statements " x is a book," " x is expensive, "and " x is good," respectively. Express each of the following statements using quantifiers; logical connectives; and B(x) , E(x) and G(x) , where the universe of discourse is the set of all objects.

a. No books are expensive.

b. All expensive books are good.

c. No books are good.

d. Does (c) follow from (a) and (b)?

40. Let G(x) , F(x) , Z(x) , and M(x) be the statements " x is a giraffe," " x is 15 feet or higher, "" x is in this zoo, "and " x belongs to me," respectively. Suppose that the universe of discourse is the set of animals. Express each of the following statements using quantifiers; logical connectives; and G(x) , F(x) , Z(x) , and M(x) .

a. No animals, except giraffes, are 15 feet or higher;

b. There are no animals in this zoo that belong to anyone but me;

c. I have no animals less than 15 feet high.

d. Therefore, all animals in this zoo are giraffes.

e. Does (d) follow from (a), (b), and (c)? If not, is there a correct conclusion?

41. Show that the statements ¬∃ x ∀ y P(x, y) and ∀ x ∃ y ¬ P(x, y) have the same truth value.

42. For each of the following arguments, explain which rules of inference are used for each step. The universe is the set of people.

a. "John, a student in this class, is 16 years old. Everyone who is 16 years old can get a driver's license. Therefore, someone in this class can get a driver's license."

b. "Somebody in this class enjoys hiking. Every person who enjoys hiking also likes biking. Therefore, there is a person in this class who likes biking."

c. "Every student in this class owns a personal computer. Everyone who owns a personal computer can use the Internet. Therefore, John, a student in this class, can use the Internet."

d. "Everyone in this class owns a personal computer. Someone in this class has never used the Internet. Therefore, someone who owns a personal computer has never used the Internet."

43. Determine whether each of the following arguments is valid. If an argument is correct, what rule of inference is being used? If it is not, what fallacy occurs?

a. "If n is a real number with n >1, then n 2>1. Suppose that n 2 ≤ 1. Then n ≤ 1.

b. "If n is a real number with n >1, then n 2>1. Suppose that n 2>1. Then n >1.

44. Show that ∃ x P(x) ⋀∃ x Q(x) and ∃ x(P(x) ⋀ Q(x)) are not logically equivalent.

45. Show that ∀ x P(x) ⋀∃ x Q(x) and ∀ x ∃ y(P(x) ⋀ Q(y)) are equivalent.