Are These Predicate Logic Equivalences Valid?

[rooski]

Homework Statement

state whether the equivalences are valid for P and Q

(latex is screwing up, wherever a letter has been made into superscript it should be normal and there should be a ^ in front of it).

1.. $$poop \exists x [ P(x) ^ \wedge p Q(x) ] \equiv \exists x P(x) \wedge \exists x Q(x)$$

2.. $$\exists x \exists y [ P(x) \wedge Q(y) ] \equiv \exists x P(x) \wedge \exists x Q(x)$$

The Attempt at a Solution

I get the jist of what I'm supposed to prove, but i don't know how to properly formulate my response. I think there are some holes in my logic too. Can i get some critique?

Q1: Assume the LHS is true. It follows that the RHS is also true. This means we have a variable k Such that P(k) ^ Q(k) (on the LHS) is true. It follows that P(k) is true and Q(k) is true. Since P(k) is true for the variable k then we can say that $$\exists x P(x)$$ holds true if we choose x = k. This logic can also be applied to Q(x). Thus we conclude that the equivalence is valid.

Q2: Assume the LHS and RHS are true. This means that for 2 values k and n, P(k) and Q(n) are both true. Looking at the RHS we can say that $$\exists x P(x)$$ holds true if we choose x = k. The same can be said for $$\exists x Q(x)$$ if we choose x = n. Thus we conclude the equivalence is valid.

 

[HallsofIvy]

Homework Statement

state whether the equivalences are valid for P and Q

(latex is screwing up, wherever a letter has been made into superscript it should be normal and there should be a ^ in front of it).

1.. $$\exists x [ P(x) ^ \wedge p Q(x) ] \equiv \exists x P(x) \wedge \exists x Q(x)$$

2.. $$\exists x \exists y [ P(x) \wedge Q(y) ] \equiv \exists x P(x) \wedge \exists x Q(x)$$

The Attempt at a Solution

I get the jist of what I'm supposed to prove, but i don't know how to properly formulate my response. I think there are some holes in my logic too. Can i get some critique?

Q1: Assume the LHS is true. It follows that the RHS is also true. This means we have a variable k Such that P(k) ^ Q(k) (on the LHS) is true. It follows that P(k) is true and Q(k) is true. Since P(k) is true for the variable k then we can say that $$\exists x P(x)$$ holds true if we choose x = k. This logic can also be applied to Q(x). Thus we conclude that the equivalence is valid.

No. The LHS says that there exist a value of x such that both P(x) and Q(x) are true for that value of x. The RHS says that there exist a value of x such that P(x) is true and that the exist a value of x (possibly different) such that Q(x) is true. Suppose P(x) is "x+ 1= 0" and Q(x) is "x- 2= 0". Then $\exists x P(x) \wedge \exists x Q(x)$ is true- P(-1) is true so $\exists x P(x)$ is true and Q(2) is true so $\exists x Q(x)$ is true. That is $\exists x P(x)\wedge \exists x Q(x)$ is true.
But $\exists x P(x)\wedge Q(x)$ is false because there does NOT exist a single value of x that makes both P(x) and Q(x) true.

Q2: Assume the LHS and RHS are true. This means that for 2 values k and n, P(k) and Q(n) are both true. Looking at the RHS we can say that $$\exists x P(x)$$ holds true if we choose x = k. The same can be said for $$\exists x Q(x)$$ if we choose x = n. Thus we conclude the equivalence is valid.

Yes, this is valid.

 

[rooski]

No. The LHS says that there exist a value of x such that both P(x) and Q(x) are true for that value of x. The RHS says that there exist a value of x such that P(x) is true and that the exist a value of x (possibly different) such that Q(x) is true. Suppose P(x) is "x+ 1= 0" and Q(x) is "x- 2= 0". Then $\exists x P(x) \wedge \exists x Q(x)$ is true- P(-1) is true so $\exists x P(x)$ is true and Q(2) is true so $\exists x Q(x)$ is true. That is $\exists x P(x)\wedge \exists x Q(x)$ is true.
But $\exists x P(x)\wedge Q(x)$ is false because there does NOT exist a single value of x that makes both P(x) and Q(x) true.


Yes, this is valid.

Thanks for clarifying. Your example helps make it clear that they cannot be valid, i think i'll start using examples like that in proving equivalences are not valid.

Is my wording in Q2 good? I feel as though i didn't quite illustrate well enough that the equivalence is valid.

 

[HallsofIvy]

I would not have said "Assume the LHS and RHS are true". You want to prove that if one is true, the other must be. Rather what you should do is say "Assume the LHS is true", determine under what conditions on P(x) and Q(y) that is correct and show that those conditions lead to the RHS being true. Then, of course, turn around, assume the RHS is true and show that leads to the LHS is true.