Page 2 of 3 FirstFirst 123 LastLast
Results 16 to 30 of 37

Math Help - Want to negate the following statements

  1. #16
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Want to negate the following statements

    I used "Introduction to Mathematical Logic" by Mendelson, but it may not be the best choice. I am not sure about newer editions, but it used Hilbert proof calculus, which is extremely difficult to use in practice. Also, its proofs of GŲdel's completeness and incompleteness theorems were detailed, but pretty dense and not very illuminating.
    Follow Math Help Forum on Facebook and Google+

  2. #17
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: Want to negate the following statements

    Quote Originally Posted by emakarov View Post

    The negated formula is correct. Concerning English, I think "there is someone who doesn't like everyone" means \exists x \neg\forall y M(x,y). To express \exists x \forall y \neg M(x,y), I would say, "there is someone who doesn't like anybody."
    Makarov,

    "there is someone who doesn't like everyone" doesn't mean \exists x \neg\forall y M(x,y)

    Because \exists x \neg\forall y M(x,y) is

    \exists x \exists y \neg M(x,y)

    which means "there is someone who doesn't like someone". am I right ?
    Follow Math Help Forum on Facebook and Google+

  3. #18
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Want to negate the following statements

    I would say that the meaning of "I don't like everyone" is similar to that of "I don't like someone," however strange this may seem. Granted, there is an a priori ambiguity concerning the place of the universal quantifier ("everyone") with respect to the negation. I found an article "Navigating negative quantificational space" that says the following (pp. 3-4). When a universally quantified noun phrase is the subject, as in "Every student didnít solve the problem," then there is indeed an ambiguity. (I've often seen this interpreted as "Not every student solved the problem," but I personally much rather prefer the latter way of saying this.) However, the article says that when a universally quantified phrase is in object position, there is no ambiguity and the quantifier is inside the scope of negation, so "The students didnít solve every problem" is interpreted as "It is not the case that the students solved every problem."

    However, the article also claims that the "some" in the object position must be interpreted outside the scope of negation. So, "John didnít see some students" means "There are some students that John did not see." Interestingly, "any" is left inside negation: "John didnít see any students" means "It is not the case that John saw some students."
    Follow Math Help Forum on Facebook and Google+

  4. #19
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: Want to negate the following statements

    Thanks for the detailed explanation. I hope such ambiguities don't arise while dealing with mathematical statements.
    Follow Math Help Forum on Facebook and Google+

  5. #20
    Banned
    Joined
    Jul 2009
    Posts
    107

    Re: Want to negate the following statements

    Quote Originally Posted by issacnewton View Post
    Hi

    I have to negate the following statements and then express again
    in English. I need to know if I am making any mistakes.

    a)Everyone who is majoring in math has a friend who needs
    help with his homework.

    b)Everyone has a roommate who dislikes everyone.

    c)There is someone in the freshman class who doesn't
    have a roommate.

    d)Everyone likes someone,but no one likes everyone.

    My answers are as follows--------

    a) Let P(x)= x is majoring in math
    Q(x)=x needs help with homework
    M(x,y)=x and y are friends

    The statement would be

    \exists x (P(x))\rightarrow \exists y (M(x,y)\wedge Q(y))

    So the negated statement would be

    \neg \left[\exists x (P(x))\rightarrow \exists y (M(x,y)\wedge Q(y))\right]

    \neg \left[\neg(\exists x (P(x)) \vee \exists y (M(x,y)\wedge Q(y))\right]

    \neg \left[\forall x \neg P(x) \vee \exists y (M(x,y)\wedge Q(y))\right]

    \neg (\forall x \neg P(x)) \wedge \neg \exists y (M(x,y)\wedge Q(y))

    \exists x P(x) \wedge \forall y \neg (M(x,y)\wedge Q(y))

    \exists x P(x) \wedge \forall y (\neg M(x,y) \vee \neg Q(y))

    To translate this statement back to English would be

    Some person is majoring in math and everyone is either not a
    friend of this person or doesn't need help in homework.

    b) let Q(x,y)=x and y are roommates
    M(x,y)=x likes y

    The statement would be

    \forall x \left[\exists y (Q(x,y) \wedge \forall z(\neg M(y,z)))\right]

    so the nagated statement would be

    \neg \forall x \left[\exists y (Q(x,y)\wedge \forall z(\neg M(y,z)))\right]

    \exists x \forall y \left[\neg Q(x,y) \vee \exists z(M(y,z)) \right]

    Translation:

    Either there is some person who is not roommate with anybody or there is
    someone who is liked by all.

    c)let P(x)= x is in freshman class.
    M(x)=x has a roommate.

    The statement would be

    \exists x \left[ P(x)\wedge \neg M(x) \right]

    So the negated statement is

    \neg \exists x \left[ P(x)\wedge \neg M(x) \right]

    \forall x \left[ \neg P(x) \vee M(x) \right]

    Translation:

    Everyone either is not in freshman class or has a roommate.

    d)let M(x,y)= x likes y

    The statement would be

    \forall x \left[ \exists y (M(x,y))\wedge \exists z \neg M(x,z) \right]

    The negated statement would be

    \neg \forall x \left[ \exists y (M(x,y))\wedge \exists z \neg M(x,z) \right]

    \neg \left[\forall x \exists y (M(x,y))\wedge \forall x \exists z \neg M(x,z) \right]

    (\neg \forall x \exists y M(x,y)) \vee (\neg \forall x \exists z \neg M(x,z) )

    \left[\exists x \forall y \neg M(x,y)\right] \vee \left[\exists x \forall z M(x,z)\right]

    Translation:

    Either there is someone who likes everyone or there is someone who doesn't like
    everyone.



    Please comment

    Thanks
    What laws of logic did you apply in proving that:

    ~ \forall x (P(x))\rightarrow \exists y (M(x,y)\wedge Q(y))\Longleftrightarrow \exists x P(x) \wedge \forall y (\neg M(x,y) \vee \neg Q(y))
    Follow Math Help Forum on Facebook and Google+

  6. #21
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Want to negate the following statements

    You are right that the left-hand side should start with \neg\forall, not \neg\exists, as in the OP. The scope of the universal quantifier should be the rest of the statement. Then we have the following.

    ~∀x (P(x) -> ∃y (M(x,y) /\ Q(y))) <=>
    ∃x ~(P(x) -> ∃y (M(x,y) /\ Q(y))) <=>
    ∃x (P(x) /\ ~∃y (M(x,y) /\ Q(y))) <=>
    ∃x (P(x) /\ ∀y ~(M(x,y) /\ Q(y))) <=>
    ∃x (P(x) /\ ∀y (M(x,y) -> ~Q(x,y)))
    Follow Math Help Forum on Facebook and Google+

  7. #22
    Banned
    Joined
    Jul 2009
    Posts
    107

    Re: Want to negate the following statements

    Quote Originally Posted by emakarov View Post
    You are right that the left-hand side should start with \neg\forall, not \neg\exists, as in the OP. The scope of the universal quantifier should be the rest of the statement. Then we have the following.

    ~∀x (P(x) -> ∃y (M(x,y) /\ Q(y))) <=>
    ∃x ~(P(x) -> ∃y (M(x,y) /\ Q(y))) <=>
    ∃x (P(x) /\ ~∃y (M(x,y) /\ Q(y))) <=>
    ∃x (P(x) /\ ∀y ~(M(x,y) /\ Q(y))) <=>
    ∃x (P(x) /\ ∀y (M(x,y) -> ~Q(x,y)))
    O.k ,but which laws of logic did you use in the above proof?

    Can the four quantification rules ( UE,UI,EE,EI) PLUS the propositional calculus rules solve the above problem??
    Follow Math Help Forum on Facebook and Google+

  8. #23
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Want to negate the following statements

    In this problem we are using equivalences, e.g., ~∀x P(x) <=> ∃x ~P(x). I am not sure what UE and UI stand for, but if it is universal elimination and universal introduction, then those are things of completely different nature. In any case, quantifier rules are propositional rules are sufficient to derive any true formula.

    The proof in post #21 used the following equivalences:

    ~∀x P(x) <=> ∃x ~P(x)
    ~∃x P(x) <=> ∀x ~P(x)
    ~(A /\ B) <=> A -> ~B
    ~~A <=> A
    Follow Math Help Forum on Facebook and Google+

  9. #24
    Banned
    Joined
    Jul 2009
    Posts
    107

    Re: Want to negate the following statements

    Quote Originally Posted by emakarov View Post
    In this problem we are using equivalences, e.g., ~∀x P(x) <=> ∃x ~P(x). I am not sure what UE and UI stand for, but if it is universal elimination and universal introduction, then those are things of completely different nature. In any case, quantifier rules are propositional rules are sufficient to derive any true formula.

    The proof in post #21 used the following equivalences:

    ~∀x P(x) <=> ∃x ~P(x)
    ~∃x P(x) <=> ∀x ~P(x)
    ~(A /\ B) <=> A -> ~B
    ~~A <=> A
    How do you prove :~∀x P(x) <=> ∃x ~P(x)
    Follow Math Help Forum on Facebook and Google+

  10. #25
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Want to negate the following statements

    Could you answer the question in this sticky thread?
    Follow Math Help Forum on Facebook and Google+

  11. #26
    Banned
    Joined
    Jul 2009
    Posts
    107

    Re: Want to negate the following statements

    Quote Originally Posted by emakarov View Post
    Could you answer the question in this sticky thread?
    As i said by using :

    Universal Elimination,Universal Introduction,Existensial Elimination,Existential Introduction.

    Plus the proposional rules

    In any system whether axiomatic or not
    Follow Math Help Forum on Facebook and Google+

  12. #27
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Want to negate the following statements

    Quote Originally Posted by alexandros View Post
    How do you prove :~∀x P(x) <=> ∃x ~P(x)
    Copi gives the following set of QUANTIFIER NEGATION, QN
    \begin{align*}\left( {\forall \nu } \right)\Phi (\nu ) &\equiv \neg \left( {\exists \nu } \right)\neg \Phi (\nu ) \\  \neg \left( {\forall \nu } \right)\Phi (\nu ) &\equiv \left( {\exists \nu } \right)\neg \Phi (\nu ) \\  \left( {\forall \nu } \right) \neg \Phi (\nu ) &\equiv \neg \left( {\exists \nu } \right) \Phi (\nu ) \\  \neg \left( {\forall \nu } \right) \neg \Phi (\nu ) &\equiv \left( {\exists \nu } \right) \Phi (\nu ) \end{align*}.

    However, I think that you may be asking a more historical type question.
    A question that has many centuries of thought behind it.
    Here is a good reference to The Square of Opposition.
    Follow Math Help Forum on Facebook and Google+

  13. #28
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Want to negate the following statements

    Quote Originally Posted by alexandros View Post
    As i said by using :

    Universal Elimination,Universal Introduction,Existensial Elimination,Existential Introduction.
    It sounds like you have natural deduction (ND) in mind. However, the following:

    In any system whether axiomatic or not
    confuses me. If you are talking about ND, then it is not "any" system; it is a specific system. Also, it is not axiomatic; it uses inference rules instead of axioms. If, on the other hand you take some system like Hilbert calculus, then it does not have introduction and elimination rules.

    Could you state more precisely which calculus you are using? For example, are your rules similar to the ones from the ND link above?
    Follow Math Help Forum on Facebook and Google+

  14. #29
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Want to negate the following statements

    Here is a Fitch-style natural deduction derivation of ∃x ~P(x) from ~∀x P(x). The other direction is easier because it does not use double-negation elimination.

    Code:
    ~∀x P(x)
      ~∃x ~P(x)
        ~P(x)
          ∃x ~P(x)
          ⊥
        ~~P(x)
        P(x)
        ∀x P(x)
        ⊥
      ~~∃x ~P(x)
      ∃x ~P(x)
    Follow Math Help Forum on Facebook and Google+

  15. #30
    Banned
    Joined
    Jul 2009
    Posts
    107

    Re: Want to negate the following statements

    Quote Originally Posted by emakarov View Post
    Here is a Fitch-style natural deduction derivation of ∃x ~P(x) from ~∀x P(x). The other direction is easier because it does not use double-negation elimination.

    Code:
    ~∀x P(x)
      ~∃x ~P(x)
        ~P(x)
          ∃x ~P(x)
          ⊥
        ~~P(x)
        P(x)
        ∀x P(x)
        ⊥
      ~~∃x ~P(x)
      ∃x ~P(x)
    I have my doubts w.r.t the above proof.

    For example instead of x we could have used, a ,for Antony and proceed in part of the proof as follows:

    \neg Pa ...........................Let Pa stand for : Antony is a phony

    \exists x\neg Px

    \neg\exists x\neg Px\wedge\exists x\neg Px...........................contradiction

    Hence : \neg\neg Pa and

    Pa

    \forall x Px

    Thus we proved that:

    IF Antony is not phony ,then every body is phony

    Is that reasonable??
    Follow Math Help Forum on Facebook and Google+

Page 2 of 3 FirstFirst 123 LastLast

Similar Math Help Forum Discussions

  1. Can one negate whenever they want?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 3rd 2011, 06:55 PM
  2. Negate a statement
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 7th 2010, 05:12 AM
  3. Negate and simplify
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: July 21st 2010, 09:37 PM
  4. Negate and simplify more questions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 21st 2010, 05:02 PM
  5. Statements
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 23rd 2009, 09:48 AM

Search Tags


/mathhelpforum @mathhelpforum