Results 1 to 14 of 14

Math Help - Help with prenex normal form

  1. #1
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Question Help with prenex normal form

    LEQV = Logically equivalent

    I need help changing
    ∀xA(x) ^ ∀xB(x) ^ ∀xC(x) → ∀xD(x)
    into PNF (such that the only connectives in the quantifier free portion have to be →)

    ∀xA(x) ^ ∀xB(x) ^ ∀xC(x) → ∀xD(x)
    LEQV
    ¬ ( ∀xA(x) ^ ∀xB(x) ^ ∀xC(x) ) v ∀xD(x) [→ Law]
    LEQV
    ( ∃x¬A(x) v ∃x¬B(x) v ∃x¬C(x) ) v ∀xD(x) [Duality of quantifiers law]
    LEQV
    ∃x1∃x2∃x3∀x ( ( ¬A(x1) v ¬B(x2) v ¬C(x3) ) v D(x) ) [pulling quantifiers out]
    LEQV
    ∃x1∃x2∃x3∀x ( ¬ ( A(x1) ^ B(x2) ^ C(x3) ) v D(x) ) [pulling¬ out]
    LEQV
    ∃x1∃x2∃x3∀x ( ( A(x1) ^ B(x2) ^ C(x3) ) → D(x) ) [reverse → Law ]

    I got here but I need the only connectives in the quantifier free portion to be →, right now the last step includes ^ symbols...

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Help with prenex normal form

    Delete.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Help with prenex normal form

    Hmm is this right?


    ∀xA(x) ^ ∀xB(x) ^ ∀xC(x) → ∀xD(x)
    LEQV
    ¬ ( ∀xA(x) ^ ∀xB(x) ^ ∀xC(x) ) v ∀xD(x) [→ Law]
    LEQV
    ∃x¬A(x) v ∃x¬B(x) v ∃x¬C(x) v ∀xD(x) [Duality of quantifiers law]
    LEQV
    ∃x1∃x2∃x3∀x ( ¬A(x1) v ¬B(x2) v ¬C(x3) v D(x) ) [pulling quantifiers out]
    LEQV
    ∃x1∃x2∃x3∀x ( A(x1) → (¬B(x2) v ¬C(x3) v D(x) ) ) [reverse → Law ]
    LEQV
    ∃x1∃x2∃x3∀x ( A(x1) →( B(x2) →( ¬C(x3) v D(x) )) ) [reverse → Law ]
    LEQV
    ∃x1∃x2∃x3∀x ( A(x1) →( (B(x2) → (C(x3) → D(x) )) ) [reverse → Law ]
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Help with prenex normal form

    → v D(x)

    is not syntactical.

    I guess you mean:

    Ax1-> (Bx2 -> (Cx3-> Dx))
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Help with prenex normal form

    yeah, i edited the last post to fix it, but other than it, is each line logically equivilant?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Help with prenex normal form

    Darn, I messed up. I better doublecheck. I need to doublecheck the order of the quantifiers.
    Last edited by MoeBlee; July 12th 2011 at 02:13 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Help with prenex normal form

    Unless I'm missing something (and I'll use 'V' and 'E' as the quantifiers), we have:

    (VyAy & VzBz & VwCw) -> VxDx

    equivalent to

    VxEyzw(Ay -> (Bz -> (Cw -> Dx)))

    But I don't see how you would get

    (VyAy & VzBz & VwCw) -> VxDx

    equivalent to

    EyzwVx(Ay -> (Bz -> (Cw -> Dx)))

    I think I was correct when I said (before edits) that you reversed the correct order of quantifiers when you "pulled out".
    Last edited by MoeBlee; July 12th 2011 at 02:53 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Help with prenex normal form

    Now I am confused...
    I thought I could do what I did in post#3, and since it ended up leqv to the last one, it has to be leqv.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Help with prenex normal form

    Look at your line where you pulled out the quantifiers. I think you incorrectly reversed the order.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Help with prenex normal form

    I don't see how this is wrong
    ∃x1∃x2∃x3∀x ( ¬A(x1) v ¬B(x2) v ¬C(x3) v D(x) ) [pulling quantifiers out]
    because when I pull out the quantifiers, I renamed the variables using this law
    Discrete Structures, Logic, and ... - Google Books

    so each variable in the quantifiers are different, so the order shouldn't matter right?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Help with prenex normal form

    Suppose \mathcal{Q}_1 and \mathcal{Q}_2 are quantifiers (∀ or ∃) and \star is ∧ or ∨. Then

    (\mathcal{Q}_1x\,A(x))\star(\mathcal{Q}_2y\,B(y))

    is equivalent to both

    \mathcal{Q}_1x\,\mathcal{Q}_2y\,(A(x)\star B(y))

    and

    \mathcal{Q}_2y\,\mathcal{Q}_1x\,(A(x)\star B(y))

    (assuming x does not occur freely in B and y does not occur freely in A). Therefore, in this problem the order of quantifiers in the prenex form does not matter.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Help with prenex normal form

    So post#3 is right?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Help with prenex normal form

    Yes.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Help with prenex normal form

    Yeah, my mistake. Both are correct.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Prenex Normal Forms
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 11th 2011, 12:26 PM
  2. takens normal form
    Posted in the Differential Equations Forum
    Replies: 3
    Last Post: November 2nd 2010, 05:32 AM
  3. Prenex normal form: moving quantifiers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 23rd 2010, 08:01 AM
  4. Negating normal form
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: February 26th 2009, 02:14 AM
  5. Jordan normal form
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: June 8th 2008, 06:28 PM

Search Tags


/mathhelpforum @mathhelpforum