Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Given the following predicate formula $F$:
$$\forall x \forall y [(\text{italian}(x) \Rightarrow (\text{winWC}(y) \Rightarrow \text{happy}(x))]$$
I am having trouble understanding whether $x$ and $y$ must be different elements.
Also, I have been given the following statement:
"Italians are happy if the Italian National team wins the world cup."
How can I prove that this is not equivalent to what is expressed by $F$? Should I bring both in CNF and then somehow argue they cannot be equivalent?
For any formula $\varphi$ in which $x$ and $y$ are free variables, $\forall x \> \forall y \> \varphi$ quantifies over all possible values for $x$ and $y$. As a result, $x$ and $y$ may be different objects or they may be equal; for the statement to hold, $\varphi$ must hold in both cases.
Following this reasoning, a valid interpretation for your formula would be "an Italian is happy regardless of who wins the World Cup" (assuming "WC" stands for "World Cup"), with "Italian" standing for $x$ and "who" for $y$. Thus, $x$ is happy if they win the World Cup ($x = y$) but also happy if someone else does ($x \neq y$); hence "regardless".
The other statement can be expressed in predicate logic as follows: $$\forall x (\text{italian}(x) \to (\text{winWC}(x) \to \text{happy}(x)))$$
In fact, this evaluates to the same truth value as the first formula precisely when you pick the same values for $x$ and $y$.
Assuming the most reasonable domain (i.e., persons in the world) and interpretation in this setting, you could argue there is an Italian which is happy only if the Italian national team wins the World Cup and is unhappy otherwise. Pick this person as your value for $x$ and an arbitrary non-Italian (e.g., German) person for $y$; then the second formula evaluates to true under this variable assignment (since $\text{italian}(x)$ is true and $x$ is happy if $\text{winWC}(x)$, that is, the Italian national team wins), but the first evaluates to false (since $x$ is unhappy if $y$'s team, that is, the German national team wins).
For all means for all. If you want to say that "for all distinct $x$ and $y$ property $P$ holds", your formula needs to include a formula that enforces distinctness. $$\forall x\,\forall y\,(x\neq y\rightarrow P(x,y))\,.$$ (Note: not $\forall x\,\forall y\,(x\neq y\land P(x,y))$, which is false because it's not true that $x=y$ for all $x$ and $y$ unless there's only one element in the domain.)
However, in your example, distinctness is probably implied by the intended semantics. I assume that $\mathrm{italian}(x)$ is true only if $x$ is an Italian person, and $\mathrm{winWC}(y)$ is true only if $y$ is a country that has won the World Cup. Since people and countries are different things, it will never be the case that $x=y$ when $\mathrm{italian}(x)$ and $\mathrm{winWC}(y)$ are both true.
