My first *easy* FOL

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Gyvulys624
Posts: 35
Joined: Tue Oct 16, 2007 9:49 pm UTC

My first *easy* FOL

Postby Gyvulys624 » Tue Oct 16, 2007 10:01 pm UTC

This proof, I imagine, is past beginner easy for most of you, but I am having some trouble with it o.O

Given: "For every cube it is in front of all dodecahedrons."
Prove: "For every cube and dodecahedron, the cube is in front of the dodecahedron."


When I was discussing this with my friend who gave it to me, he said the first hurdle in logic is understanding the language. In English there is no needed to prove this. But in unambiguous, formal FOL language, there is a proof.

Thanks ahead.

joeframbach
Posts: 1478
Joined: Sun Nov 05, 2006 12:49 am UTC

Re: My first *easy* FOL

Postby joeframbach » Tue Oct 16, 2007 10:15 pm UTC

For the first statement, I denote it as
\forall x \forall y [ [dodec(x) \wedge cube(y)] \rightarrow FrontOf(y,x) ]

The second statement, I denote it as
\forall x \forall y [ [dodec(x) \wedge cube(y)] \rightarrow FrontOf(y,x) ]


yeah, you got me.

Gyvulys624
Posts: 35
Joined: Tue Oct 16, 2007 9:49 pm UTC

Re: My first *easy* FOL

Postby Gyvulys624 » Tue Oct 16, 2007 10:26 pm UTC

I have the original notation actually. This is a Tarski's World problem, as I've been told. I did a little research on that, it's interesting. However, at this point I think I need to start studying logic somewhere else so I'll put Tarkski off for now.

Here's the original notation:

Given the statement: Ax (Cube(x) -> Ay (Dodec(y) -> FrontOf(x, y)))
Prove: Ax Ay ((Cube(x) & Dodec(y)) -> FrontOf(x, y))



You were practically right. But I need the proof XD

User avatar
ATCG
Posts: 471
Joined: Sat Aug 18, 2007 3:44 am UTC
Location: Straight up the jω axis

Re: My first *easy* FOL

Postby ATCG » Tue Oct 16, 2007 11:44 pm UTC

Gyvulys624 wrote:I have the original notation actually. This is a Tarski's World problem, as I've been told. I did a little research on that, it's interesting. However, at this point I think I need to start studying logic somewhere else so I'll put Tarkski off for now.

Here's the original notation:

Given the statement: Ax (Cube(x) -> Ay (Dodec(y) -> FrontOf(x, y)))
Prove: Ax Ay ((Cube(x) & Dodec(y)) -> FrontOf(x, y))



You were practically right. But I need the proof XD

OK, I'm a trusting soul, and we're on the honor system here, so with the proviso that this is not a homework problem, here goes:
Spoiler:
Let's rewrite this slightly to make it a little clearer:
  • for Cube(x), we'll write Cx
  • for Dodec(x), we'll write Dx
  • for FrontOf(x,y), we'll write Fxy
So now we start with:
∀x(Cx → ∀y(Dy → Fxy))
It is a tautology (in this case a so-called rule of passage) that p → ∀xGx is equivalent to ∀x(p → Gx) (if x is not free in p). This lets us derive:
∀x( ∀y(Cx → (Dy → Fxy)) ) , or dropping redundant parentheses:
∀x∀y(Cx → (Dy → Fxy))
By definition, p → q is equivalent to ~p ∨ q:
∀x∀y(~Cx ∨ (~Dy ∨ Fxy))
Regrouping:
∀x∀y((~Cx ∨ ~Dy) ∨ Fxy)
One of DeMorgan's rules is that ~p ∨ ~q is equivalent to ~(p ∧ q):
∀x∀y(~(Cx ∧ Dy) ∨ Fxy)
Again, by the equivalence of ~p ∨ q to p → q:
∀x∀y((Cx ∧ Dy) → Fxy) , as desired
"The age of the universe is 100 billion, if the units are dog years." - Sean Carroll

Gyvulys624
Posts: 35
Joined: Tue Oct 16, 2007 9:49 pm UTC

Re: My first *easy* FOL

Postby Gyvulys624 » Tue Oct 16, 2007 11:50 pm UTC

Don't worry, no homework problems from me. If I ever need help on a homework problem, I'll say so. But from your post I assume theres some kind of rule against that XD

I thought this proof would be a lot easier to figure out, from what my friend said. I'll take some time to try to understand the notation, perhaps put it into some crude English.

Are you sure there isn't a simpler solution?

Edit: Trying to understand that proved to be a futile effort. I might even be reading the symbols I thought I understood wrong, more likely than not. Perhaps you could give me a low-down of the symbolism, or at least a link to find that information, at minimum the name of the notation, so I could Google it.

Ax for all x
Ex for some x
not quite sure what x represents though XD
What kills me is the functions, the FrontOf (x,y) especially when they throw in two variables in the parentheses there ~_~
Last edited by Gyvulys624 on Tue Oct 16, 2007 11:58 pm UTC, edited 1 time in total.

joeframbach
Posts: 1478
Joined: Sun Nov 05, 2006 12:49 am UTC

Re: My first *easy* FOL

Postby joeframbach » Tue Oct 16, 2007 11:52 pm UTC

I had to use Tarski's world last year for class. I recognized the problem right away, really. It was that bad. If you're not using it for class and just interested in it for leisure, then I would not recommend it.

If you insist on continuing, then I recommend this book: http://www-csli.stanford.edu/LPL/

Gyvulys624
Posts: 35
Joined: Tue Oct 16, 2007 9:49 pm UTC

Re: My first *easy* FOL

Postby Gyvulys624 » Tue Oct 16, 2007 11:59 pm UTC

I'll take your advice on that. But I still need to understand it to some extent so I could get this problem...

Gyvulys624
Posts: 35
Joined: Tue Oct 16, 2007 9:49 pm UTC

Re: My first *easy* FOL

Postby Gyvulys624 » Wed Oct 17, 2007 12:09 am UTC

Just to clarify (again) THIS IS NOT MY HOMEWORK, or something I've ever studied. As such I have never seen this notation before. I find myself at a loss to some of the notation.

Does -> mean yield?
What is V and ^
How do I read the functions? (FrontOf, BackOf, etc)

I know since this is the first time I've encountered this, that I should look at basics. But the faster I answer this the better. As such I've been doing a duel search while researching this problem:
1. The Answer
2. A place to start looking into the study of logic. Logology? XD

Edit: When I started posting this there was another post, apparently someone removed it because they thought this was for homework or something...

User avatar
ATCG
Posts: 471
Joined: Sat Aug 18, 2007 3:44 am UTC
Location: Straight up the jω axis

Re: My first *easy* FOL

Postby ATCG » Wed Oct 17, 2007 12:20 am UTC

Gyvulys624 wrote:Don't worry, no homework problems from me. If I ever need help on a homework problem, I'll say so. But from your post I assume theres some kind of rule against that XD
Just flat-out doing somebody's homework is frowned upon. It is an abuse of peoples' time and good intentions and is of no intellectual benefit to the questioner. On the other hand, we've all found ourselves stuck on problems with no way forward. In this case, people are more than happy to help, and we are all the better for it.

Gyvulys624 wrote:I thought this proof would be a lot easier to figure out, from what my friend said. I'll take some time to try to understand the notation, perhaps put it into some crude English.

Are you sure there isn't a simpler solution?
Given that you are a relative newcomer to first-order logic, I thought a longer proof with the details spelled out would be more helpful than an abbreviated explanation. Just like with an algebra problem, you can compress a lot of the steps once you are comfortable, but lots of small steps (as opposed to a few large ones) are more likely to keep you on the path if you are just starting out. In logic, it is very easy to get ahead of one's self and arrive at an invalid conclusion. I speak from experience here.
"The age of the universe is 100 billion, if the units are dog years." - Sean Carroll

Gyvulys624
Posts: 35
Joined: Tue Oct 16, 2007 9:49 pm UTC

Re: My first *easy* FOL

Postby Gyvulys624 » Wed Oct 17, 2007 12:22 am UTC

I trust your sagacity.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: My first *easy* FOL

Postby Token » Wed Oct 17, 2007 12:29 am UTC

Gyvulys624 wrote:Does -> mean yield?
What is V and ^
How do I read the functions? (FrontOf, BackOf, etc)

X -> Y is read "X implies Y" or "If X, then Y".
X ∨ Y means "X or Y"
X ∧ Y means "X and Y"

While there is no set way to read a function in general, in this case FrontOf(X,Y) is read "X is in front of Y", and similarly for BackOf(X,Y). Generally you can work it out from context.
Last edited by Token on Wed Oct 17, 2007 12:33 am UTC, edited 1 time in total.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

Gyvulys624
Posts: 35
Joined: Tue Oct 16, 2007 9:49 pm UTC

Re: My first *easy* FOL

Postby Gyvulys624 » Wed Oct 17, 2007 12:32 am UTC

Thank you for bearing with me. The beginning will be a bit rough, but I see a continued interest in logic and soon enough I'll be helping answer questions, not just ask them XP

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: My first *easy* FOL

Postby Token » Wed Oct 17, 2007 12:35 am UTC

Gyvulys624 wrote:Thank you for bearing with me. The beginning will be a bit rough, but I see a continued interest in logic and soon enough I'll be helping answer questions, not just ask them XP

Never be embarrassed about asking questions if your desire is to learn.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

Gyvulys624
Posts: 35
Joined: Tue Oct 16, 2007 9:49 pm UTC

Re: My first *easy* FOL

Postby Gyvulys624 » Wed Oct 17, 2007 12:37 am UTC

Can you recommend any books or websites that might be beneficial for someone at my level to look at?

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: My first *easy* FOL

Postby Token » Wed Oct 17, 2007 1:01 am UTC

The wikipedia article on FOL links to this pdf, which doesn't seem too bad from the perspective of a complete beginner to logic.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

User avatar
ATCG
Posts: 471
Joined: Sat Aug 18, 2007 3:44 am UTC
Location: Straight up the jω axis

Re: My first *easy* FOL

Postby ATCG » Wed Oct 17, 2007 1:25 am UTC

I would observe that your friend seems to have dumped you into the deep end of the pool by giving you a problem in first-order logic right off the bat. It's kind of traditional to start off with a simpler system of logic called propositional calculus. Most logic textbooks will introduce this first as a warmup and then build upon it to reach first-order logic, where things like quantifiers (e.g. ∀x, ∃y) and predicates (e.g. Cube(x), FrontOf(x,y)) enter the picture.

There are plenty of texts that do things just in this order, and I think by starting at the beginning rather than jumping directly into the middle of the plot, you'll find things make a lot more sense.

And I've just looked at the Wikipedia entry for "Propositional calculus". Do not go there. It would scare off anybody who was just starting out.
"The age of the universe is 100 billion, if the units are dog years." - Sean Carroll

Gyvulys624
Posts: 35
Joined: Tue Oct 16, 2007 9:49 pm UTC

Re: My first *easy* FOL

Postby Gyvulys624 » Wed Oct 17, 2007 1:53 am UTC

Naturally the first thing I did was go here: http://en.wikipedia.org/wiki/Propositional_calculus

It's intimidating, but scanning through it, I understand the notation a bit more than FOL.

User avatar
Forthur
Posts: 163
Joined: Sat Jun 02, 2007 8:19 pm UTC
Location: Behind a computer, as always.
Contact:

Re: My first *easy* FOL

Postby Forthur » Wed Oct 17, 2007 1:08 pm UTC

Re: the original problem, can't you just try to prove it by
Spoiler:
Assuming the opposite of what we want to prove, and showing that that's impossible?

The statement we want to prove is:
B) For every cube and dodecahedron, the cube is in front of the dodecahedron.
The opposite:
~B) There is a combination of a cube and a dodecahedron, where the cube is not in front of the dodecahedron.

However, this would mean that there is a cube for which the given statement:
A) For every cube it is in front of all dodecahedrons.
is false. And since that cannot be (as it's a given axiom), statement ~B must be false, which makes statement B true.

Of course, all of this could be spelled out using the aforementioned notation.
Life's biggest adventures are the dreams you try to make real.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: My first *easy* FOL

Postby Token » Wed Oct 17, 2007 1:33 pm UTC

Forthur wrote:Re: the original problem, can't you just try to prove it by
Spoiler:
Assuming the opposite of what we want to prove, and showing that that's impossible?

The statement we want to prove is:
B) For every cube and dodecahedron, the cube is in front of the dodecahedron.
The opposite:
~B) There is a combination of a cube and a dodecahedron, where the cube is not in front of the dodecahedron.

However, this would mean that there is a cube for which the given statement:
A) For every cube it is in front of all dodecahedrons.
is false. And since that cannot be (as it's a given axiom), statement ~B must be false, which makes statement B true.

Of course, all of this could be spelled out using the aforementioned notation.

Well, yes, but I think the idea is to prove it in FOL.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

User avatar
BiggAl
Posts: 45
Joined: Wed Oct 17, 2007 2:04 pm UTC

Re: My first *easy* FOL

Postby BiggAl » Wed Oct 17, 2007 4:21 pm UTC

proof by contradiction rocks - so much quicker for some things, and the only answer for some others, however I remember getting an analysis seminar leader tied up in knots when I tried to prove something by contradiction which ended up being solvable in under a page by conventional methods - we spent over four hours ironing out faults and unraveling logic to create a correct proof that took three pages to rigorously explain.

That was one of my hobbies for the course, no wonder I only got a 2-2 on it...

Gyvulys624
Posts: 35
Joined: Tue Oct 16, 2007 9:49 pm UTC

Re: My first *easy* FOL

Postby Gyvulys624 » Wed Oct 17, 2007 10:27 pm UTC

Token wrote:
Forthur wrote:Re: the original problem, can't you just try to prove it by
Spoiler:
Assuming the opposite of what we want to prove, and showing that that's impossible?

The statement we want to prove is:
B) For every cube and dodecahedron, the cube is in front of the dodecahedron.
The opposite:
~B) There is a combination of a cube and a dodecahedron, where the cube is not in front of the dodecahedron.

However, this would mean that there is a cube for which the given statement:
A) For every cube it is in front of all dodecahedrons.
is false. And since that cannot be (as it's a given axiom), statement ~B must be false, which makes statement B true.

Of course, all of this could be spelled out using the aforementioned notation.

Well, yes, but I think the idea is to prove it in FOL.


Too bad it wasn't, guess I should have made that point XD


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests