Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to convert the following sentence to a well formed formula using first-order logic(Predicate logic).

All towers are of the same color.

I have defined the following predicates:

Tower(x) :: x is a tower.

Color(x, y) :: x is of color y

I am not able to convert the aforementioned sentence into a well formed formula using the above predicates. Is it possible to convert it using the above predicates or some new predicate should be required. Please advise.

share|improve this question
there exists x st x is a color and for all y tower(y) implies color(y,x) –  yoyo Apr 11 '11 at 22:11
Forgot to add a detail. There are only three available colours in the world (red, green, blue). Does that make any difference to the solution? –  stressed_geek Apr 11 '11 at 22:19
If you want you can define 3 constants $r,g,b$ (for red, green and blue) and then say: "there exists an $x$ such that $x=r$ or $x=g$ or $x=b$ such that for every $y$ we have $tower(y)$ implies $color(y,x)$" though it's not really necessary. –  Apostolos Apr 11 '11 at 22:45
@yoyo Your sentence can't be satisfied in a colorblind universe (where there is nothing which satisfies your color predicate) :( –  matt Apr 12 '11 at 0:32

1 Answer 1

up vote 7 down vote accepted

I'd suggest first rephrasing it in English as a sentence that uses more and more of the formal logic expressions: something like

"For any towers x and y, x and y have the same color"

(Here I'm taking advantage of the fact that it is equivalent to say that a whole class of elements shares a property and to say that every pair of elements in that class shares the property).

then we can further rephrase this as

"For any towers x and y, x has color c if and only if y has color c"

and finally

"For any towers x and y, any c is the color of x if and only if it is the color of y"

Then we need to write that symbolically, remembering that quantifying over certain types of things (towers in our case) can be written as quantification over an implication:

"For all x and y, if x and y are towers, then any c is the color of x if and only if it is the color of y"

$\forall x \forall y \left ( \left ( \operatorname{Tower}(x) \& \operatorname{Tower}(y) \right ) \longrightarrow \forall c \left ( \operatorname{Color}(x,c)\leftrightarrow \operatorname{Color}(y,c) \right ) \right )$

If you want, you can pull the quantification over the $c$ variable out front:

$\forall x \forall y \forall c \left ( \left ( \operatorname{Tower}(x)\& \operatorname{Tower}(y) \right ) \longrightarrow \left ( \operatorname{Color}(x,c)\leftrightarrow \operatorname{Color}(y,c)\right ) \right )$

share|improve this answer
Also, in case you don't like the jump to my first English rephrasing (which I justified in the parenthetical note). I'll add that we could begin by noting that this is also equivalent to "There are no two towers which are of different colors". You might find this leap more intuitive. –  matt Apr 12 '11 at 2:31
You have an extra close-paren after Tower(y) in both formulae. (This caused me some confustion at first!) –  Jeffrey L Whitledge Apr 14 '11 at 13:53
@JeffreyLWhitledge: Those parentheses should match with the 2nd parenthesis of the formula. Matching them all up with subscripts: $$∀x∀y(_1(_2Tower(_3 x)_3\&Tower(_4 y)_4 )_2⟶∀c(_5Color(_6 x,c)_6↔Color(_7 y,c)_7 )_5)_1$$ It's unnecessary if you evaluate conjunction before implication, but I figured I'd throw the extra parentheses in to avoid any ambiguity. –  matt Apr 14 '11 at 17:45
Oh, yes. That makes sense now. Thanks! –  Jeffrey L Whitledge Apr 14 '11 at 17:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.