edited by
1,603 views
0 votes
0 votes

Can someone please explain the following solution.

Ques: Show that ∀x(P(x) ∧ Q(x)) and ∀xP(x) ∧ ∀xQ(x) are logically equivalent (where the same domain is used throughout). This logical equivalence shows that we can distribute a universal quantifier over a conjunction. Furthermore, we can also distribute an existential quantifier over a disjunction. However, we cannot distribute a universal quantifier over a disjunction, nor can we distribute an existential quantifier over a conjunction.

Solution: To show that these statements are logically equivalent, we must show that they always
take the same truth value, no matter what the predicates P and Q are, and no matter which
domain of discourse is used. Suppose we have particular predicates P and Q, with a common
domain. We can show that ∀x(P(x) ∧ Q(x)) and ∀xP(x) ∧ ∀xQ(x) are logically equivalent
by doing two things. First, we show that if ∀x(P(x) ∧ Q(x)) is true, then ∀xP(x) ∧ ∀xQ(x)
is true. Second, we show that if ∀xP(x) ∧ ∀xQ(x) is true, then ∀x(P(x) ∧ Q(x)) is true.
So, suppose that ∀x(P(x) ∧ Q(x)) is true. This means that if a is in the domain, then
P(a) ∧ Q(a) is true. Hence, P(a) is true and Q(a) is true. Because P(a) is true and Q(a) is
true for every element in the domain, we can conclude that ∀xP(x) and ∀xQ(x) are both true.
This means that ∀xP(x) ∧ ∀xQ(x) is true.
Next, suppose that ∀xP(x) ∧ ∀xQ(x) is true. It follows that ∀xP(x) is true and ∀xQ(x) is
true. Hence, if a is in the domain, then P(a) is true and Q(a) is true [because P(x) and Q(x)
are both true for all elements in the domain, there is no conflict using the same value of a here].
It follows that for all a, P(a) ∧ Q(a) is true. It follows that ∀x(P(x) ∧ Q(x)) is true. We can
now conclude that
∀x(P(x) ∧ Q(x)) ≡ ∀xP(x) ∧ ∀xQ(x).

edited by

1 Answer

2 votes
2 votes

case1:  ∀x(P(x) ∧ Q(x))    =.    ∀xP(x) ∧ ∀xQ(x)

assume a set  S={6,12,18,24}

let p(x) = "x divisible by 2 "

   q(x)  = "x divisible by 3 "

LHS

∀x(P(x) ∧ Q(x))  is true always for above p(x) & q(x)....as  for every x (  "x divisible by 2 " & "x divisible by 3 ")

..RHS:::∀xP(x) ∧ ∀xQ(x)  is also true ...as {for every x "x is divisible by 2" &  for every x " x is divisible by 3"}

∀x(P(x) ∧ Q(x))    =.    ∀xP(x) ∧ ∀xQ(x)

          T                =             T

        as LHS & RHS are equal

so we can distribute....a universal quantifier over a conjunction

case 2:∀x(P(x) v Q(x))    =    ∀xP(x) v ∀xQ(x)

let set S={2,6,4,8,9}

let p(x) = "x divisible by 2 "

   q(x)  = "x divisible by 3 "

LHS :∀x(P(x) v Q(x)) ...this is true..always bcoz for all x ("x divisible by 2 "OR "x divisible by 3 ")

∀xP(x) v ∀xQ(x)...this is false   bcoz for all x ("x divisible by 2 ") OR  for all x( "x divisible by 3 ")

counter example : "element 9 is divisible by 2  OR element 8 is divisible by 3"   this is false

∀x(P(x) v Q(x)) = ∀xP(x) v ∀xQ(x) 

                T    =      F

                 as LHS & RHS are not equal

        ...hence ...a universal quantifier cannot be distributed over a disjunction.

case 3:   ∃x(P(x) v Q(x)) = ∃xP(x) v xQ(x) 

  lets set S={2,6,4,8,9}

let p(x) = "x divisible by 2 "

   q(x)  = "x divisible by 3 "

LHS::::∃x(P(x) v Q(x)...is true..boz there exist "x' for which ( "x divisible by 2 " OR "x divisible by 3 ")...u can take any element..lets takeEXP1-  ===="9 divisible by 2 " OR "9 divisible by 3"  ::: F V T = T

              take EXP2-  ::: "6 divisible by 2 " OR "6 divisible by 3" T V T = T

RHS ::::∃xP(x) v xQ(x)  ..is true bcoz {there exist "x' for which ( "x divisible by 2) " OR exist "x' for which "x divisible by 3 }")

let take EXP1-   === "9 divisible by 2 " OR "6 divisible by 3" F V T = T

let takeEXP2 - ==="2 divisible by 2 " OR "9 divisible by 3"  T V T = T

  ∃x(P(x) v Q(x)) =∃xP(x) v xQ(x) 

             T          ======     T

        as LHS & RHS are equal

 we can distribute an existential quantifier over a disjunction.

case4:x(P(x) Q(x)) = ∃xP(x)  xQ(x) 

assume a set  S={2,4,3,9}

let p(x) = "x divisible by 2 "

   q(x)  = "x divisible by 3 "

LHS :::∃x(P(x) Q(x))   is false always...as there exist no number which divisible by both 2 & 3..in above set

RHS  ::∃xP(x) ∧∃xQ(x)  is true always...as "there exist a number which divisible by 2 "  and "there exist a number which divisible by 3 "

x(P(x) Q(x)) = ∃xP(x)  xQ(x) 

      F                =     T

        as LHS & RHS are  not  equal                 

...so  we cannot distribute an existential quantifier over a conjunction.

edited by

Related questions