3
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ there exists x st x is a color and for all y tower(y) implies color(y,x) $\endgroup$
    – yoyo
    Commented Apr 11, 2011 at 22:11
  • $\begingroup$ 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? $\endgroup$
    – stressed_geek
    Commented Apr 11, 2011 at 22:19
  • $\begingroup$ 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. $\endgroup$
    – Apostolos
    Commented Apr 11, 2011 at 22:45
  • 1
    $\begingroup$ @yoyo Your sentence can't be satisfied in a colorblind universe (where there is nothing which satisfies your color predicate) :( $\endgroup$
    – matt
    Commented Apr 12, 2011 at 0:32

1 Answer 1

Reset to default
9
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – matt
    Commented Apr 12, 2011 at 2:31
  • $\begingroup$ You have an extra close-paren after Tower(y) in both formulae. (This caused me some confustion at first!) $\endgroup$
    – Jeffrey L Whitledge
    Commented Apr 14, 2011 at 13:53
  • $\begingroup$ @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. $\endgroup$
    – matt
    Commented Apr 14, 2011 at 17:45
  • $\begingroup$ Oh, yes. That makes sense now. Thanks! $\endgroup$
    – Jeffrey L Whitledge
    Commented Apr 14, 2011 at 17:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .