0

Consider
$P(x,y)$: $x$ is a citizen of $y$.

$Q(x,y)$: $x$ lives in $y$.

The universe of discourse of x is the set of all people The universe of discourse of y is the set of US states.

Express the following English statement as logical expression using predicates and quantifiers:

"Every state has a citizen who does not live in that state".

Now I am confused between two answers,

$\forall y \exists x(P(x,y)\implies\neg Q(x,y))$

$\forall y \exists x(P(x,y)\wedge\neg Q(x,y))$

Which of these is correct? Or did I miss entirely? The first expression is true even if there is a state having no citizens. But the second one isn't. Truth table of both match only 50%.

Math Attack
  • 1
Harish Patil
  • 11
  • 1
    The second one. See this post – Mauro ALLEGRANZA Nov 16 '23 at 14:58
  • If two logical expressions are not equivalent, then they do not mean the same thing. The first logical expression in English would have an "if $x$ is a citizen of $y$ then $x$ does not live in $y$." I don't see anything that translates directly into "if" or "then" in the English sentence, though. – coiso Nov 16 '23 at 14:59
  • 1
    I would translate the first as saying that, for each state, there is either at least one person who is a citizen but does not live there or there is at least one person who is not a citizen of that state. That is not what you want. – Henry Nov 16 '23 at 15:03
  • To answer the question of the title of your post: Yes! Two logic expressions can be syntactically different (in the sense that they are simply not the same string of symbols), but semantically the same (in the sense that they mean the same thing. For example, $P \land Q$ and $Q \land P$ are different expressions, but both would be true if and only if both $P$ and $Q$ are true. As such we say that they are logically equivalent. And yes, because of that, an English sentence can be symbolized in logic in many different, but equivalent, ways. – Bram28 Nov 16 '23 at 20:35

2 Answers2

1

I think your misunderstanding comes from a misunderstanding of the logical implication. Have you seen the implication as disjunction? $$(A \implies B) \iff (\neg A \lor B)$$ Now your English statement which you had to express in the language of logic was "Every state has a citizen who does not live in this state." Now think about what this means. For this to be true, for every state there must exist a person who is a citizen of that state but who does not live in the state.

I italicized the important phrases here, which have clear logical analogs in this problem. Let us begin translating this into logic.

"For every state" is the universal quantifier on states, "$\forall \mbox{ states } y$". "There exists a person" is the existential quantifier on people, thus we have "$\forall \mbox{ states } y \; \exists \mbox{ a person } x $". "Is a citizen of" is the predicate $P$, thus we have "$\forall \mbox{ states } y \; \exists \mbox{ a person } x \; P(x,y)$". "But" is the logical conjunction, so we have "$\forall \mbox{ states } y \; \exists \mbox{ a person } x \; P(x,y) \land $". "Does not live in" is the predicate $\neg Q$, so finally we have:

$$\forall \mbox{ states } y \; \exists \mbox{ a person } x \; P(x,y) \land \neg Q(x,y) $$

Thus the second answer is right, the first is wrong. Do you understand why this is conjunction, and not implication?

Malady
  • 941
  • 1
  • 10
1

There are indeed multiple ways of translating the same English sentence into the language of FOL. However, only the second formula $\forall y \exists x[ Pxy \wedge \neg Qxy ]$ in your OP is correct.

To see why, you must be acquainted with the concept of ontological commitment, or the assertion that a thing actually exists.

Universal statements make no ontological commitment. In other words, a statement like "all dragons breathe fire" translated as $\forall x [Dx \to Fx]$ makes no claim that dragons actually exist. It merely states that if any thing is a dragon, then that thing breathes fire. There may be no thing that is a dragon and the formula will still hold true, vacuously.

On the other hand, existential statements do make an ontological commitment. In other words, a statement like "there is a dragon that breathes fire" translated as $\exists x [Dx \wedge Fx]$ makes a claim that at least one dragon actually exists and it also breathes fire. In this case, if there are no dragons, then the statement is patently false.

Your English sentence "every state has a citizen who does not live in that state" makes an ontological commitment. I asserts that, in every state, there actually exists at least one person who is a citizen of that state and does not live in that state. Hence, it is not appropriate to translate the sentence in a way that suggests "if such a person existed, then..." within the scope of the existential quantifier, because the English sentence effectively says "there is such a person..."

@Malady offers some great insight into translating keywords, but you definitely want to be aware of whether a particular sentence makes an ontological commitment or not.

RyRy the Fly Guy
  • 5,950
  • 1
  • 11
  • 27