I have a logic based statement of this form:

$$ (\forall x\ ,p(x))\to (\exists y\ , q(x,y))) $$

I am trying to find out if this statement is TRUE or False. I have 2 methods of proof, and one leads to FALSE, the other leads to TRUE. I have a problem hence!


So for the first part of this logic equation I call it P and the second part I call it Q, so i get an overall implication equation:

$$ P \to Q $$

So I thought I could do a counter-example pick an x-value in order to set P to be TRUE and then pick a y-value to make Q-false. That way in an implication statement if P=TRUE and you have Q=FALSE, then overall the implication is FALSE which would disprove the overall statement.

I have seen on some other site that you can do this in order to disprove this.

BUT, I now have doubts.


Because in the first part it has the "For All" quantifier which in my notation is inside P. SO now i will take the "For ALL" into account. . I can show that the function inside P, p(x), I can find a counter-example x-value to show that the left side, capital P as FALSE.

NOW in an IMPLICATION if the first part P is FALSE, then based on truth-table for this, it does not matter if Q is TRUE or FALSE. Because as soon as P is False it makes the whole implication statement TRUE!!!

SO now I did 2 Methods, the first one shows that the overall statement is "FALSE" and I have a second Method that shows that the overall statement is "TRUE".

SO I am not sure which method is the problem.

Hope someone can clarify this.

  • $\begingroup$ So your statement is true under some interpretations and false under some other interpretations. This is perfectly normal. It doesn't make sense to ask if it's true or false unless an interpretation is specified. Now, if the question was whether the statement was valid, or whether it was satisfiable, that's another story. Your examples show that it is satisfiable but not valid. $\endgroup$ – bof Oct 15 '17 at 5:42
  • $\begingroup$ By the way, the variable $x$ occurs both free and bound in your formula. Not that there's anything wrong with that. There is something wrong with having more right than left parentheses, but I suppose that's just a typo. $\endgroup$ – bof Oct 15 '17 at 5:44
  • $\begingroup$ I just put parentheses to put some 'style' or to group the whole thing on one side and the other. I did this with q == q(x,y) just to say it contains both variables as in its a function of these 2 variables. See my specific example below for some context. $\endgroup$ – Palu Oct 15 '17 at 6:04
  • $\begingroup$ So i will drop the unnecessary brackets here: $$ \forall x\ ,p(x) \to \exists y\ , q(x,y) $$ , does this make a difference in terms of the scope for the "FOR-ALL". $\endgroup$ – Palu Oct 15 '17 at 6:06

The formula is neither true nor false in isolation.

It only gets a truth value when you select an interpretation to evaluate it, which fixes which universe the quantifiers range over and when the $p$ and $q$ predicates are true.

And even so, you also need to choose a value for the appearance of $x$ on the right-hand side of $\to$, which is not in scope of the $\forall x$.

  • $\begingroup$ Ok, so it sounds like you are saying that it depends on the context. $\endgroup$ – Palu Oct 15 '17 at 5:56
  • $\begingroup$ SO on the left side say we have x is a positive integer such that: p(x) = (x>3 and x <6), and now the right hand side we have another formula q(x,y) = ( x = 3y +1 or x = 5y +1) where y is a positive integer. $\endgroup$ – Palu Oct 15 '17 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.