Discrete Mathematics Answers

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.

Suppose that a truth table in n propositional variables is specified. Show that a compound proposition with this truth table can be formed by taking the disjunction of conjunctions of the variables or their negations, with one conjunction included for each combination of values for which the compound proposition is true. The resulting compound proposition is said to be in disjunctive normal form.

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)

For the given sequence 2, 6, 10, ...
i- Write down the recursive formula for above sequence
ii- Write down the closed formula for above sequence
iii- Find the 11th term of the given sequence.

A detective has interviewed four witnesses to a crime. From the stories of the witnesses the detective has concluded that if the butler is telling the truth then so is the cook; the cook and the gardener cannot both be telling the truth; the gardener and the handyman are not both lying; and if the handyman is telling the truth then the cook is lying.For each of the four witnesses, can the detective determine whether that person is telling the truth or lying? Explain your reasoning.