Page 77 - Discrete Mathematics and Its Applications

56 1 / The Foundations: Logic and Proofs

43. Determine whether ∀x(P(x) → Q(x)) and ∀xP(x) → 56. Given the Prolog facts in Example 28, what would Prolog
∀xQ(x) are logically equivalent. Justify your answer. return when given these queries?
44. Determine whether ∀x(P(x) ↔ Q(x)) and ∀x P(x) ↔ a) ?enrolled(kevin,ee222)
∀xQ(x) are logically equivalent. Justify your answer. b) ?enrolled(kiko,math273)
45. Show that ∃x(P(x) ∨ Q(x)) and ∃xP(x) ∨∃xQ(x) are c) ?instructor(grossman,X)
logically equivalent.
d) ?instructor(X,cs301)
Exercises 46–49 establish rules for null quantification that e) ?teaches(X,kevin)
we can use when a quantified variable does not appear in part
of a statement. 57. Suppose that Prolog facts are used to define the predicates
mother(M, Y) and father(F, X), which represent that M
46. Establish these logical equivalences, where x does not
is the mother of Y and F is the father of X, respectively.
occur as a free variable in A. Assume that the domain is Give a Prolog rule to define the predicate sibling(X, Y),
nonempty.
which represents that X and Y are siblings (that is, have
a) (∀xP(x)) ∨ A ≡∀x(P(x) ∨ A) the same mother and the same father).
b) (∃xP(x)) ∨ A ≡∃x(P(x) ∨ A)
58. Suppose that Prolog facts are used to define the predi-
47. Establish these logical equivalences, where x does not cates mother(M, Y) and father(F, X), which represent
occur as a free variable in A. Assume that the domain is that M is the mother of Y and F is the father of X,
nonempty. respectively. Give a Prolog rule to define the predicate
a) (∀xP(x)) ∧ A ≡∀x(P(x) ∧ A) grandfather(X, Y), which represents that X is the grand-
b) (∃xP(x)) ∧ A ≡∃x(P(x) ∧ A) father of Y.[Hint: You can write a disjunction in Prolog
48. Establish these logical equivalences, where x does not either by using a semicolon to separate predicates or by
occur as a free variable in A. Assume that the domain is putting these predicates on separate lines.]
nonempty. Exercises 59–62 are based on questions found in the book
a) ∀x(A → P(x)) ≡ A →∀xP(x) Symbolic Logic by Lewis Carroll.
b) ∃x(A → P(x)) ≡ A →∃xP(x) 59. Let P(x), Q(x), and R(x) be the statements “x is a
49. Establish these logical equivalences, where x does not professor,” “x is ignorant,” and “x is vain,” respectively.
occur as a free variable in A. Assume that the domain is Express each of these statements using quantifiers; log-
nonempty. ical connectives; and P(x), Q(x), and R(x), where the
a) ∀x(P(x) → A) ≡∃xP (x) → A domain consists of all people.
b) ∃x(P(x) → A) ≡∀xP (x) → A a) No professors are ignorant.
50. Show that ∀xP(x) ∨∀xQ(x) and ∀x(P(x) ∨ Q(x)) are b) All ignorant people are vain.
not logically equivalent. c) No professors are vain.
51. Show that ∃xP(x) ∧∃xQ(x) and ∃x(P(x) ∧ Q(x)) are d) Does (c) follow from (a) and (b)?
not logically equivalent. 60. Let P(x), Q(x), and R(x) be the statements “x is a clear
52. As mentioned in the text, the notation ∃!xP(x) denotes explanation,” “x is satisfactory,” and “x is an excuse,”
“There exists a unique x such that P(x) is true.” respectively. Suppose that the domain for x consists of all
If the domain consists of all integers, what are the truth Englishtext.Expresseachofthesestatementsusingquan-
values of these statements? tifiers, logical connectives, and P(x), Q(x), and R(x).
2
a) ∃!x(x > 1) b) ∃!x(x = 1) a) All clear explanations are satisfactory.
c) ∃!x(x + 3 = 2x) d) ∃!x(x = x + 1) b) Some excuses are unsatisfactory.
53. What are the truth values of these statements? c) Some excuses are not clear explanations.
a) ∃!xP(x) →∃xP(x) ∗ d) Does (c) follow from (a) and (b)?
b) ∀xP(x) →∃!xP(x) 61. Let P(x), Q(x), R(x), and S(x) be the statements “x is
c) ∃!x¬P(x) →¬∀xP(x) a baby,” “x is logical,” “x is able to manage a crocodile,”
54. Write out ∃!xP(x), where the domain consists of the in- and “x is despised,” respectively. Suppose that the domain
consists of all people. Express each of these statements
tegers 1, 2, and 3, in terms of negations, conjunctions,
using quantifiers; logical connectives; and P(x), Q(x),
and disjunctions.
R(x), and S(x).
55. Given the Prolog facts in Example 28, what would Prolog
a) Babies are illogical.
return given these queries?
b) Nobody is despised who can manage a crocodile.
a) ?instructor(chan,math273)
b) ?instructor(patel,cs301) c) Illogical persons are despised.
c) ?enrolled(X,cs301) d) Babies cannot manage crocodiles.
d) ?enrolled(kiko,Y) ∗ e) Does (d) follow from (a), (b), and (c)? If not, is there
e) ?teaches(grossman,Y) a correct conclusion?