Answer to Question #132206 in Discrete Mathematics for seema

Question

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

Answer 1

We will start from the first given statement,

∀xP(x)∧∃xQ(x)

It doesn't matter if the variables are called x or called y, thus let us recall the variable in the second expression of the conjunction:

$\equiv$∀xP(x)∧∃yQ(y)

$\equiv$(∀xP(x))∧(∃yQ(y))

$\equiv$∀x(P(x)∧(∃yQ(y)))

Using the commutative law,

$\equiv$∀x((∃yQ(y))∧P(x))

$\equiv$∀x∃y(Q(y)∧P(x))

Again using the commutative law,

$\equiv$∀x∃y(P(x)∧Q(y))

Hence we can say that the statement ∀xP(x)∧∃xQ(x) is logically equivalent to ∀x∃y(P(x)∧Q(y)) where all quantifiers have the same nonempty domain.