Translating a sentence to predicate logic

Question

I have the following sentence:

"Everyone who has a tail is a dog"

and its translation to predicate logic is:

$$\neg\exists x \, ( \neg\text{dog}(x) \land \text{hasTail}(x))$$

I don't understand this? How did they get this answer? Can someone help me by explaining how the translation was made?

Thanks.

Answer 1

In words: "There is no one who is not a dog and has a tail".

The obvious translation is $\forall{x}:\text{hasTail}(x)\implies\text{dog}(x)$.

---

The translation was probably made as follows:

$[\text{hasTail}(x)\implies\text{dog}(x)]$ is equivalent to

$[\neg\text{hasTail}(x)\vee\text{dog}(x)]$ is equivalent to

$\neg[\text{hasTail}(x)\wedge\neg\text{dog}(x)]$ is equivalent to

$\neg[\neg\text{dog}(x)\wedge\text{hasTail}(x)]$

Answer 2

Perhaps it would make more sense if it were written as follows:

$$\forall x(hasTail(x) \rightarrow dog(x))$$

Your statement is equivalent to the above statement: $$\begin{align} \lnot \lnot \forall x(hasTail(x) \rightarrow dog(x))&\equiv \lnot \exists x( \lnot(hasTail(x) \rightarrow dog(x)))\tag{1}\\ \\ & \equiv \lnot \exists x (\lnot(\lnot hasTail(x) \lor dog(x)))\tag{2}\\ \\ &\equiv \lnot \exists x(hasTail(x) \land \lnot dog(x))\tag{3}\\ \\ &\equiv \lnot \exists x (\lnot dog(x) \land hasTail(x))\tag{4} \end{align}$$

$(1)$ follows from the equivalence $\lnot \forall x P(x) \equiv \exists x (\lnot P(x))$

$(2)$ follows from the equivalence $p \rightarrow q\equiv \lnot p \lor q$

$(3)$ follows from DeMorgan's Law

$(4)$ because of the commutativity of $\land$