[Discrete Math] <=> related question.

[Servo888]

Ok so I have two propositions;

for ALL x: (P(x) or Q(x))
and I have...
(for ALL x: P(x)) or (for ALL x: Q(x))

I need to show if these are logically equivalent. My original assumption was that these are <=>; but that turned out to be wrong. I'm clueless as to what to do... Some hints or guides would be nice.

 

[0rthodontist]

Are you familiar with the finite universe method? Consider a universe with 2 elements and see if you can assign values for P(x) and Q(x) so that one statement is true and not the other.

And intuitively, think about what the two statements mean. You should be able to see that they are different.

 

[Servo888]

Are you familiar with the finite universe method? Consider a universe with 2 elements and see if you can assign values for P(x) and Q(x) so that one statement is true and not the other.

And intuitively, think about what the two statements mean. You should be able to see that they are different.

This book doesn't cover the finite universe method. Though I'm googleing it to figure out what it is.

 

[0rthodontist]

Well, what does the book cover? The finite universe method is the only way I know to show that a statement in predicate logic doesn't follow. Maybe they just want you to explain, intuitively, why the two are not the same.

 

[Servo888]

Well, what does the book cover? The finite universe method is the only way I know to show that a statement in predicate logic doesn't follow. Maybe they just want you to explain, intuitively, why the two are not the same.

It's not a book problem it's a professor problem, and IMHO my professor isn't right in the head.

Anyways, here's how I think it works... For the first proposition to be true (for all X) either P(x) or Q(x) must be true. While in the second proposition all values of P(X) must be true or all values of Q(x) must be true.

I'm not sure if I'm just restating the problem, but that's what I got...

 

[matt grime]

Surely considering propositions P and Q which are jointly always true but occasionally false will do it.

I'm sure your professor thinks highly of you too.

 

[Servo888]

Surely considering propositions P and Q which are jointly always true but occasionally false will do it.

I don't follow.

 

[honestrosewater]

What if your domain is the set of natural numbers and P and Q are evenness and oddness? Does that give you an idea for a counterexample?

[tex](\forall x (Px \vee Qx)) \rightarrow ((\forall x (Px)) \vee (\forall x (Qx)))[/tex]

doesn't hold. You need to construct a counterexample -- an interpretation where [itex](\forall x (Px \vee Qx))[/itex] is True and [itex]((\forall x (Px)) \vee (\forall x (Qx)))[/itex] is False.
Let your domain D = {a, b}, a be in P, and b be in Q. Does that work?

 

[Servo888]

What if your domain is the set of natural numbers and P and Q are evenness and oddness? Does that give you an idea for a counterexample?

[tex](\forall x (Px \vee Qx)) \rightarrow ((\forall x (Px)) \vee (\forall x (Qx)))[/tex]

doesn't hold. You need to construct a counterexample -- an interpretation where [itex](\forall x (Px \vee Qx))[/itex] is True and [itex]((\forall x (Px)) \vee (\forall x (Qx)))[/itex] is False.
Let your domain D = {a, b}, a be in P, and b be in Q. Does that work?

*whoosh* Straight over my head. I'll sleep on it, maybe I just need to digest this a bit more.

 

[honestrosewater]

*whoosh* Straight over my head. I'll sleep on it, maybe I just need to digest this a bit more.

That's okay. If you don't understand, just ask. What words or parts don't you understand?

 

[Servo888]

That's okay. If you don't understand, just ask. What words or parts don't you understand?

Ok I'll try to explain where I'm having issues. It's not really understanding what your asking, it's more like finding the answers is the problem.

What if your domain is the set of natural numbers and P and Q are evenness and oddness? Does that give you an idea for a counterexample?

Doesn't turn on any light bulbs.

You need to construct a counterexample -- an interpretation where [itex](\forall x (Px \vee Qx))[/itex] is True and [itex]((\forall x (Px)) \vee (\forall x (Qx)))[/itex] is False.
Let your domain D = {a, b}, a be in P, and b be in Q. Does that work?

Well... Let P(a) = true, and P(b) = false. So [itex](Pa \vee Qb)[/itex] is true... Then [itex](Pa) \vee (Qb)[/itex] would be true as well... So from what I see it works.

PS: Thanks for the help so far, I'm not one to pick things up fast... Logic is not my strong side.

 

[honestrosewater]

1) [tex](\forall x (Px \vee Qx))[/tex]

says that you can plug in every member d of your domain for x and

(Pd v Qd)

will be true. If your domain has one member, d₁, it means that

(Pd₁ v Qd₁)

is true. If your domain has two members, it means that

(Pd₁ v Qd₁) & (Pd₂ v Qd₂)

is true. If your domain has n members, it means that

(Pd₁ v Qd₁) & (Pd₂ v Qd₂) & ... & (Pd_n v Qd_n)

is true. If your domain has r members, it means that

(Pd_r v Qd_r)

is true for every r. Does that makes sense?

2) [tex](\forall x (Px))[/tex]

says what? That you can plug in every member d of your domain for x and

(Pd)

will be true. So

3) [tex](\forall x (Px)) \vee (\forall y (Qy))[/tex]

(with different variables for clarity) says what? That you can plug in every member d of your domain for x and

(Pd)

will be true or you can plug in every member d of your domain for y and

(Qd)

will be true. That is, (3) says that every member of your domain has the property P or every member of your domain has the property Q; (1) says that every member of your domain has the property P or the property Q. For natural numbers and evenness and oddness, (1) says that every natural number is even or odd (which is true). (3) says that every natural number is even (which is false) or every natural number is odd (which is also false).

If you don't understand why I used two variables for (3), look in your book for the discussion of quantifer scope.

Do you understand why and how to go about the next step, constructing a (general) counterexample?

 

[matt grime]

Let's think about it in set theory terms. Given a set S and P a proposition about elements in S, then there are two subsets of S, those for which P is true and those for which it is false. Conversely given any partition of S into two subsets then there is a proposition whose truth set is one part of the partition and the other is the false set.Got it?

Now, what you're saying is that you cannot think of a two subsets U and V such that UuV is all of S but neither of which is S?

Come on I'm sure you can.

And if you can't do that, then surely you can at least understand the case of 'what if P is not(Q)?

Of course if you don't see honestrosewater's explicit example from the odd and even hint then no hints will give you the answer since that is practically a counterexample explicitly, indeed I'd practically give a student full marks if the handed in the statement: consider the integers, and the odd and even members thereof.

 

[Servo888]

Ok so it's false because in the case of ALL x: (P(x) or Q(x)); for this to be true either P(x) or Q(x) has to be true. While in (for ALL x: P(x)) or (for ALL x: Q(x)), it's either all of P(x) is true, or all Q(x) is true.

Am I following correctly?

 

[matt grime]

Yes, that is the entire point of the exercise.

 

[honestrosewater]

If your teacher wants you to give a general counterexample, you only need two individuals in your domain. You just need to name them D = {a, b} and assign Pa, Pb, Qa, and Qb the truth-values that make (1) = T and (3) = F.