2

In a formula of the form ~ for all x, for all y (l(x,y) -> r(x,y)) how do we apply negation to the formula "(l(x,y) -> r(x,y))" ? And similarly if we have a formula with different quantifiers, such as, ~ for all x, there is a y (l(x,y) and r(x,y)).

1

I think you are asking about this sentence: ~(∀x)(∀y)(Ixy → Rxy)

I think you are asking which sentence, logically equivalent to that one, includes ~(Ixy → Rxy). The answer is (∃x)(∃y)~(Ixy → Rxy).

As we move the quantifier in past the (∀x), it becomes (∃x). That is because, to take a simpler example, “~(∀x)Px” means “not everything is P,” while “(∃x)~Px” means that “something is not P,” which amounts to the same thing.

So, equally logically equivalent is the intermediate sentence (∃x)~(∀y)(Ixy → Rxy). Move the negation inward once more and you get (∃x)(∃y)~(Ixy → Rxy).

For your second example, ~(∀x)(∃y)(Ixy & Rxy) is logically equivalent to (∃x)(∀y)~(Ixy & Rxy).

  • So the negation applies to all quantifiers? What if we had a formula of the form, ~ for all x, ~ for all y (phi) where both (all, if you have more than two) quantifiers are being negated? – user8083 Dec 27 '14 at 21:18
  • ~(∀x)~(∀y)φ is logically equivalent to (∃x)~~(∀y)φ which is logically equivalent to (∃x)(∀y)φ and (∃x)~(∃y)~φ. – ChristopherE Dec 27 '14 at 23:13
  • 1
    Is the confusion here about binding in quantifier statements? In First Order Logic there is a very precise distinction between "for all x, for all y" and "for all y, for all x". Think of it like this - after each case of "for all x..." there is an implicit bracketing around the rest of the sentence. What ChristopherE should technically have written is ~(∀x(∀y(Ixy → Rxy) ) ), but the bracketing conventions for this make it a little unwieldy so we tend to leave them out and assume that people know how quantifiers bind to their sentences. – Paul Ross May 1 '15 at 9:49
  • 1
    @PaulRoss -- indeed perhaps that's the reason for the confusion, though I wouldn't say that's technically more correct. It depends on particular systems' grammar; mine is grammatical in some systems. But yes, a possible source of confusion. – ChristopherE May 1 '15 at 15:32
0

Switching both quantifiers, applying the definition of implication (the conjunctive form), and removing all resulting double negations, you can obtain:

(1) There exists x such that there exists y such that L(x,y) and ~R(x,y).

(2) There exists x such that for all y, L(x,y) => ~R(x,y).

-1

For the first case, read this and this. The first link treats general quantification (or variation as Russell calls) and existential, and how you can apply rules of symbolism with it. The second link explains the philosophy, or the interpretation, behind the symbolism, which helps you understand what you can and can't do, regarding rules of inference. I.e, the texts contain everything to solve the guy's question, and still give him a general understanding of what he is doing.

For the second case, just consider enter image description here as being enter image description here. I.e, consider enter image description here.

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.