Results 1 to 7 of 7

Math Help - Help with logic formulas

  1. #1
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Unhappy Help with logic formulas

    Consider a first-order language with ternary predicate P and equality predicate =. We define the formulas F1, F2, F3 as follows.
    F1: ∀x∀y∃zP(x,y,z).
    F2: ∀x∀y∀z∀u∀v∀w∀t (P(x,y,u) ∧ P(u,z,w) ∧ P(y,z,v) ∧ P(x,v,t) → =(w,t))
    F3: ∀x∀y∀z∀w (∃u(P(x,y,u) ∧ P(u,z,w)) ↔ ∃v(P(y,z,v) ∧ P(x,v,w)))

    a) Prove F1 ∧ F2 logically implies F3
    b) Prove F2 does not logically imply F3

    For B I got
    Let the domain be {0,1}
    Let P(x,y,z): x+y>z
    Set x=0 y=1 u=0 z=1 w=0 v=0 t=0
    Then F2 does not logically imply F3

    Is this ok?

    And how do I start with a) ?
    Last edited by Sneaky; August 19th 2011 at 07:47 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765

    Re: Help with logic formulas

    Let the domain be {0,1}
    Let P(x,y,z): x+y>z
    Set x=0 y=1 u=0 z=1 w=0 v=0 t=0
    Then F2 does not logically imply F3
    Strictly speaking, it is not clear how your described interpretation relates to the fact that F2 does not logically imply F3. The latter fact says that there exists an interpretation where F2 is true and F3 is false. Did you describe that alleged interpretation? Then say directly that it is in the interpretation just describes that F2 is true and F3 is false.

    First, you may need to clarify what is 1 + 1 since the domain is {0,1}. Since + is not in the formula vocabulary, it does not have to be interpreted by a function from {0,1} to {0,1}; so I assumed that you mean regular addition. I agree that F2 is true because its premise, namely P(x,v,t) is false. However, both sides of F3 are true: take u = 0 and v = 1.

    Assuming F1, it is easy to show -> implication in F3. Indeed, assume P(x,y,u) and P(u,z,w) for some u. By F1, there exist v and y such that P(y,z,v) and P(x,v,t). Then by F2, w = t, so P(x,v,w) and thus ∃v(P(y,z,v) ∧ P(x,v,w)). At the moment I am not sure about the converse implication. Are you sure it is an equivalence?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Help with logic formulas

    I am deeply lost here
    "Assuming F1, it is easy to show -> implication in F3. Indeed, assume P(x,y,u) and P(u,z,w) for some u. By F1, there exist v and y such that P(y,z,v) and P(x,v,t). Then by F2, w = t, so P(x,v,w) and thus ∃v(P(y,z,v) ∧ P(x,v,w)). At the moment I am not sure about the converse implication. Are you sure it is an equivalence?"
    Can you explain it more?

    Also by "Are you sure it is an equivalence?" do you mean that there shouldn't be a <--> in F3, actually there is, which is making it harder to show F2 !=> F3...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765

    Re: Help with logic formulas

    To prove ∀x∀y∀z∀w (∃u(P(x,y,u) ∧ P(u,z,w)) -> ∃v(P(y,z,v) ∧ P(x,v,w))) from F1 and F2:

    Fix x, y, z, w and assume ∃u(P(x,y,u) ∧ P(u,z,w)). Take u that makes P(x,y,u) ∧ P(u,z,w) true. By F1, there exists a v such that P(y,z,v) and there exists a t such that and P(x,v,t). (My post above incorrectly said y instead of t.) Thus, we have P(x,y,u) ∧ P(u,z,w) ∧ P(y,z,v) ∧ P(x,v,t). By F2, w = t, so from P(x,v,t) we get P(x,v,w). So, ∃v(P(y,z,v) ∧ P(x,v,w)).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Help with logic formulas

    Why are you using -> instead of <--> in F3?

    But since ∃u(P(x,y,u) ∧ P(u,z,w)) is true and ∃v(P(y,z,v) ∧ P(x,v,w))

    F3 will be true, so then F1 and F2 => F3
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765

    Re: Help with logic formulas

    Quote Originally Posted by Sneaky View Post
    Why are you using -> instead of <--> in F3?
    Quote Originally Posted by emakarov View Post
    At the moment I am not sure about the converse implication.
    Quote Originally Posted by Sneaky View Post
    But since ∃u(P(x,y,u) ∧ P(u,z,w)) is true and ∃v(P(y,z,v) ∧ P(x,v,w))

    F3 will be true
    ∃u(P(x,y,u) ∧ P(u,z,w)) is not true (true in which interpretation? none was specified); it is by assuming that it is true in some interpretation we can show that ∃v(P(y,z,v) ∧ P(x,v,w)) is also true there.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: Help with logic formulas

    I cant figure out how to show F2 !=> F3, I tried
    P(x,y,z): x<z<y or y<z<x
    with domain {0,1,2,3,4,5}
    with x=0 u=1 z=3 y=5 w=2 v=4 t=2
    but it's not working...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Logic: formulas, proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 29th 2010, 09:25 AM
  2. Can someone check my logic (sentential logic)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 13th 2010, 03:30 AM
  3. derive formulas in mathematical logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2010, 02:25 AM
  4. set formulas
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 30th 2008, 01:38 PM
  5. Mathematical logic - String formulas and Godel numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 10th 2007, 04:04 PM

Search Tags


/mathhelpforum @mathhelpforum