Discrete Mathematics Answers

(4) Find a common domain for the variables x, y, and z for which the statement
∀x∀y((x=/=y) => ∀z((z=x)v(z=y)))
is true and another domain for which it is false.

Determine the truth value of each of ∀x∀y∃z(z=(x+y)/2)

1. Let U = {l, 2, 3, 4, 5, 6, 7, 8, 9, and 10} be a universal set. Let A, B, C such that A= {l, 3, 4, 8},
B = {2, 3, 4, 5, 9, 10}, and C = {3, 5, 7, 9, 10}. Use bit representations
for A, B, and C together with UNION,
INTER, DIFF, and COMP to find the bit representation for the following:
(a) AU B
(b) An B n C
(f)) (AU C) n B
(d) (A - B) UC
(e) An (B - (C n B))
(f) A - (B - C)
(g) (AU B) U (C - B)

Show that ∀xP(x)∧∃xQ(x) is logically equivalent to ∀x∃y(P(x)∧Q(y)), where all quantifiers have the same nonempty domain.

Show that ∀xP(x)∨∀xQ(x) and ∀x∀y(P(x)∨Q(y)), where all quantifiers have the same nonempty domain, are logically equivalent.

Express each of these statements using quantifiers. Then form the negation of the statement so that no negation is to the left of a quantifier. Next,express the negation in simple English.
(a) There is a student in this class who has chatted with exactly one other student.
(b) No student has solved at least one exercise in every section of this book.
(c) Every movie actor has either been in a movie with Kevin Bacon or has been in a movie with someone who has been in a movie with Kevin Bacon.

Show that (p∧q=⇒ r and (p=⇒r)∧(q=⇒ r) are not logically equivalent.

(3) Express the negations of each of these statements so that all negation symbols
immediately precede predicates.
(a)∃z∀y∀xT(x, y, z)
(b)∃x∃yP(x, y)^∀x∀yQ(x, y)
(c)∃x∃y(Q(x, y)<=>Q(y,x))
(d)∀y∃x∃z(T(x, y, z)∨Q(x, y))

(2) Determine the truth value of each of these statements if the domain of each variable consists of all real numbers.
(a)∀x∃y(x^2=y)
(b)∀x∃y(x=y^2)
(c)∃x∀y(xy= 0)
(d)∃x∃y(x+y=/=y+x)
(e)∀x(x=/= 0 => ∃y(xy= 1))
(f)∃x∀y(y=/= 0 => xy= 1)
(g)∀x∃y(x+y= 1)
(h)∃x∃y(x+ 2y= 2^2x+ 4y= 5)
(i)∀x∃y(x+y= 2^2xy= 1)
(j)∀x∀y∃z(z= (x+y)=2)

(1) Let Q(x, y) be the statement "x+y=xy." If the domain for both variables consists of all integers, what are the truth values?
(a)Q(1,1)
(b)Q(2,0)
(c)∀yQ(1, y)
(d)∃xQ(x,2)
(e)∃x∃yQ(x, y)
(f)∀x∃yQ(x, y)
(g)∃y∀xQ(x, y)
(h)∀y∃xQ(x, y)
(i)∀x∀yQ(x, y)