Re: Help with logic formulas

Quote:

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?

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...

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)).

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

Re: Help with logic formulas

Quote:

Originally Posted by

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

Quote:

Originally Posted by

**emakarov** At the moment I am not sure about the converse implication.

Quote:

Originally Posted by

**Sneaky** 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.

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...