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?


  • 3
    $\begingroup$ Just note that this is about the predicate calculus, not the propositional calculus. Also, in general $\forall x \phi(x)$ is equivalent to $\neg \exists x \neg \phi(x)$, which may give you some clue about it. $\endgroup$ – Nagase Feb 10 '15 at 19:40

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$


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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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