Translating English to FO Logic

Aug 2010
32
7
Is this an accurate paraphrase of the sentence "No one has more than three grandmothers" into the predicate calculus?

∀u∀w∀x∀y∀z(((G(w,u)&G(x,u))&(G(y,u)&G(z,u)))->(((w=xvw=y)vw=z)v((x=yvx=z)vy=z)))

Where G(x,y) is a propositional function meaning "x is the grandmother of y," and the domain for all variable consists of the set of all people.

I figured I would write the negation of the statement "Someone has more than three grandmothers," i.e.,

~∃u∃w∃x∃y∃z(((Gwu&Gxu)&(Gyu&Gzu))&(((w≠x&w≠y)&w≠z)&((x≠y&x≠z)&y≠z)))

and then just move the ~ in until I got the above universal quantification. But is there a simpler way to express the proposition?
 

Ackbeet

MHF Hall of Honor
Jun 2010
6,318
2,433
CT, USA
I think your parentheses might mess things up a bit. How about this:

\(\displaystyle \forall u\,\forall w\,\forall x\,\forall y\,\forall z\,
\big((G(w,u)\land G(x,u)\land G(y,u)\land G(z,u))\to\)
\(\displaystyle ((w=x)\vee(w=y)\vee(w=z)\vee(x=y)\vee(x=z)\vee(y=z))\big).\)

This expression is not fully parenthesized, I understand. If your teacher is picky about that, then just go with your original statement, which is correct as far as I can see. My version takes advantage of the associativity of AND and OR.

I don't think there are any FOL translations of the sentence that are much clearer than this.
 
  • Like
Reactions: quiney

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
I think your parentheses might mess things up a bit. How about this:

\(\displaystyle \forall u\,\forall w\,\forall x\,\forall y\,\forall z\,
\big((G(w,u)\land G(x,u)\land G(y,u)\land G(z,u))\to\)
\(\displaystyle ((w=x)\vee(w=y)\vee(w=z)\vee(x=y)\vee(x=z)\vee(y=z))\big).\)

This expression is not fully parenthesized, I understand. If your teacher is picky about that, then just go with your original statement, which is correct as far as I can see. My version takes advantage of the associativity of AND and OR.

I don't think there are any FOL translations of the sentence that are much clearer than this.
I don't know of this is "legal", but maybe we could use indices, which would help for a statement such as "No one has more than thirty grandmothers".

\(\displaystyle \forall u\,\forall x_1\,\forall x_2\dots\forall x_{31}\,
\big((G(x_1,u)\land G(x_2,u)\land \dots\land G(x_{31},u))\to\)
\(\displaystyle (\exists i\,\exists j (i\in \mathbb{Z} \land j\in \mathbb{Z} \land 1\le i\le31 \land 1\le j \le 31 \land i\ne j \land x_i = x_j))\big).\)
 
  • Like
Reactions: quiney
Feb 2010
470
154
My guess is that he wants to do it in the pure predicate calculus with identity without use of mathematics such as you've used.