Discrete Math. (Logically equivalent)

by persian52
Tags: discrete math proofs, equivalent, inference, logically
persian52 is offline
Jan30-13, 03:00 PM
P: 13
See attachment for the question.

∀x ∈ D, if P(x) then Q(x). this means ∀x P(x) -> Q(x).
all you have to do is find a value for x
∀x this means for ALL x right
so you can choose ANY element
but for the E its only things in the domain
so all you have to do is choose an x that's not in E's domain
and then you can say therefore its not logically equivalent.

I think am wrong.

Please help me out with this problem.
thank you in advance.
Attached Thumbnails
hmassig.jpg   table2.png  
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
nomadreid is offline
Jan31-13, 12:54 AM
P: 502
The question is a little unclear. First, you list four rules of inference for quantifiers in cut form. OK. Then, since you are talking about the all quantifier, I presume you want to refer to the first one. So, you start with
[itex]\forall[/itex] x [itex]\in[/itex] D (P(x)[itex]\Rightarrow[/itex] Q(x))
Then, instance with c, P(c)[itex]\Rightarrow[/itex] Q(c). No problem here.
But then you say that you can choose any c, including one not in the domain (of the quantifier, I presume you mean, in this case D), which contradicts your original statement which bounded your quantifier to D.
Then you start mentioning "E": I am not sure whether you are referring to the existential quantifier [itex]\exists[/itex] or the set membership relation [itex]\in[/itex].
Then you say that "it's" not logically equivalent. So far, no equivalence has been mentioned, so what is "it"? and what is it not equivalent to?
Please clarify your question, and then I would be glad to help.
Ocifer is offline
Feb10-13, 09:21 PM
P: 30
^There were two pages to what he posted. The question asks about:

[itex] \exists x ( P(x) \rightarrow Q(x) ) [/itex], and
[itex] (\forall x) P(x) \rightarrow (\exists x) Q(x) [/itex]

Are they logically equivalent? No. There is more than one way to argue it. One obvious thing to take note of is that the in the first statement, the existential binds both instances of little x.
This statement can be translated as "there exists an object such that P(x) implies Q(x)" (same x)

There is more than one structural difference between the first statement and the second. Can you think of any?

nomadreid is offline
Feb11-13, 02:37 AM
P: 502

Discrete Math. (Logically equivalent)

Before one could even touch the question as to whether the two statements are equivalent, one would have to make sure that they both make sense. The first one, of course, does, but the second one does not even make sense. What is meant, I think, is
[itex]\forall[/itex]x P(x) [itex]\rightarrow[/itex][itex]\exists[/itex]y Q(y).

Once that has been cleaned up, one can proceed to show that they are not equivalent.
Ocifer is offline
Feb11-13, 11:41 PM
P: 30
^Come to think of it, nomadreid is absolutely correct. I had parsed the notation to the only thing that made sense in my mind (what you wrote), assuming it was just a strange notation. But I haven't seen it elsewhere.
persian52 is offline
Feb13-13, 09:01 PM
P: 13
thank you guys for the help!

Register to reply

Related Discussions
Q-Q plot equivalent for discrete variable? Set Theory, Logic, Probability, Statistics 4
Discrete Math question on creating a logically equivalent compound proposition Engineering, Comp Sci, & Technology Homework 0
Discrete Math: Proving something is logically equivalent Calculus & Beyond Homework 4
Logic - Logically equivalent Set Theory, Logic, Probability, Statistics 2
DISCRETE MATH: Determine if two statements are logically equivalent... Calculus & Beyond Homework 1