Results 1 to 2 of 2

Math Help - Quantified Propositions to English

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    23

    Quantified Propositions to English

    I need help with this problem.

    Let P(x, y) be x has been to y, where the domain of discourse for x is all students in this class, and the domain of discourse for y is all towns in Illinois. Express the following propositions in English.
    a) ∃x ∀y P(x, y)
    b) ∀y ∃x P(x, y)

    I know a is There is a student in this class who has been to all towns in Illinois.

    What is b?

    Also - the next problem is for me to negate the above statements, can anyone help with that?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,506
    Thanks
    765
    b) ∀y ∃x P(x, y)
    So, what's the problem? ∀ stands for "for all", ∃ for "there exists", so the sentence is, "For every town y there exists a student x such that x has been to y". (Here y is a town, not a student, because it is the second argument of P.) In fact, it is easy to write a computer program that translates formulas into English. Of course, it is possible to improve the style of this sentence and in particular remove variables x and y, which should be done.

    The thing to note here is that the meaning changes dramatically if we swap the universal and existential quantifier. (The meaning does not change if one swaps two consecutive universal or two consecutive existential quantifiers.) In a), there is a single student who has been everywhere, whereas in b), every town may have a different student who visited it.

    For negation, it is not clear if you need negations as formulas or as English sentences. In any case, there are (at least) two options. The easy one is to add "It is not the case that" or \neg to the beginning of a sentence or formula. This should always work. The second option is to move the negation inside the formula. To do this, one has to change each quantifier into the other kind and add the negation before the quantifier-free inner part of the formula. E.g., the negation of \exists x\,\forall y\,P(x,y) is \forall x\,\exists y\,\neg P(x,y). The translation of English sentences is done similarly.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] induction problem on set of propositions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 15th 2011, 01:44 AM
  2. Universal quantified statements
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 5th 2010, 08:06 AM
  3. rules of inference for quantified statements
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 5th 2010, 01:16 PM
  4. [SOLVED] Proof of Propositions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 26th 2009, 03:15 AM
  5. propositions and logic help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 22nd 2009, 04:57 PM

Search Tags


/mathhelpforum @mathhelpforum