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

  • $\begingroup$ Because in this example give a question "Italians are happy if the Italian National team wins the world cup." an explanation why this formula are wrong. I mean that i need to proof in some way, and i think to costruct an equivalent formula from the original one, by a trasformation (so CNF)...but i m not sure this is right way for proof. thanks so much for answear, finally i got the point! $\endgroup$ – theantomc Dec 11 '18 at 11:06
  • $\begingroup$ i think my correct answear to this question is . ∀x [(italian(x) ∧ winWC(National))⇒happy(x)] $\endgroup$ – theantomc Dec 11 '18 at 11:56
  • $\begingroup$ I believe I understand know. So what you are trying to prove is that the statement "Italians are happy if the Italian national team wins the World Cup" is not (logically) equivalent to what is specified by the given formula (i.e., $\forall x \forall y ((\text{italian}(x) \to (\text{winWC}(y) \to \text{happy}(x)))$)? $\endgroup$ – dkaeae Dec 11 '18 at 12:23
  • $\begingroup$ i think is right @dkaeae $\endgroup$ – theantomc Dec 11 '18 at 12:57

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.

  • $\begingroup$ So, for the proof i can say that can be exist an $italian$ that is happy for $winWC$ of other country? this is valid case, that give my question invalid... right? $\endgroup$ – theantomc Dec 11 '18 at 15:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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