Results 1 to 4 of 4

Math Help - Need Help Proving First Order Logic Equivalence

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Sky Wind City
    Posts
    2

    Need Help Proving First Order Logic Equivalence

    Hello,

    I have the following First order Logic statement:

    If F(x) is not true then no H(y,x) satisfies G(x)

    (∀x F(x)) ⇒∃y G(y) ˄ H(y,x)

    I have to change this to get:

    (y G(y) ˄ H(y,x))) ⇒ ((∀x F(x))

    Is this possible? I can possibly modify the first statement so as to prove the latter. What would be a way to do this while staying within the domain of the Logic Statement given above.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Need Help Proving First Order Logic Equivalence

    Quote Originally Posted by granprofaci View Post
    I have the following First order Logic statement:

    If F(x) is not true then no H(y,x) satisfies G(x)

    (∀x F(x)) ⇒∃y G(y) ˄ H(y,x)
    The English statement does not make sense. In first-order logic, there are two syntactic categories: terms and formulas. Semantically, terms range over objects and formulas range over properties of those objects. One can say that an object satisfies some property but not that a property satisfies another property (for this you need second-order logic). Therefore, H(y,x) cannot satisfy G(x). I think you mean that y such that H(y,x) satisfies G (and not G(x)). Also, the universal quantifier over x has to extend over the whole formula because otherwise x in H(y,x) is unbound. So, I think the English sentence should say,

    If F(x) is not true then no y such that H(y,x) satisfies G

    and its translation is

    ∀x (F(x) ⇒ ∃y (H(y,x) ˄ G(y))) (*)

    Then

    ∀x (∃y (H(y,x) ˄ G(y)) ⇒ F(x))

    is indeed equivalent to (*) because it is the contraposition of (*).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2012
    From
    Sky Wind City
    Posts
    2

    Re: Need Help Proving First Order Logic Equivalence

    I see... just to make a clarification... The sentence essentially is obtained from:

    If a square is not hot then no adjacent square contains a fire.

    From a sentence for this, the latter has to be proven..
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Need Help Proving First Order Logic Equivalence

    Quote Originally Posted by granprofaci View Post
    If a square is not hot then no adjacent square contains a fire.
    If F(x) means "x is hot," H(y,x) means "y is adjacent to x" and G(y) means "y contains a fire," then the translation is indeed ∀x (F(x) ⇒ ∃y (H(y,x) ˄ G(y))) or ∀x (F(x) ⇒ ∀y (H(y,x) ⇒ G(y))).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: May 9th 2012, 01:22 PM
  2. Equivalence with logic laws
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 12th 2010, 11:38 AM
  3. propositional logic equivalence proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 11th 2010, 12:20 AM
  4. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 09:03 AM
  5. Proving Logical equivalence
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 25th 2009, 10:35 AM

Search Tags


/mathhelpforum @mathhelpforum