[Math] Translations from English to predicate logic, using quantifiers.

logiclogic-translationpredicate-logicquantifiers

Let "book" be the set of all books and "Author" be the set of all authors. $\in$ denotes set membership.

Consider the following predicates:

short(x) is a predicate indicating x is a short book.
by(x,y) is a predicate indicating that book y was written by x.

Formalize each of the following sentences as a predicate logic formula using the above predicates:

  • i) "Every book has an author"
    My answer : $∀b\in \text{ Books }\land ∃a\in \text{ Authors }$

  • ii) "There is an author who has not written a book"
    My answer: $∃a\in \text{ Authors } \land ∃b\in \text{ Books } \land ¬\text{by}\,(b,a)$

  • iii)"Every author has written a short book"
    My answer: $∀a \in \text{ Authors } \land ∃x\in \text{ Books } \land \text{ short}\,(x) \rightarrow \text{by}\,(x,a)$

Best Answer

You are a bit off on your answers, and one of the reasons is because you haven't delineated the scope of some of the quantified variables; as a result the reappearance of such a variable outside of the scope of its quantifier is then free.

Another more substantive problem is it seems you haven't grasped the general form for a universally quantified statement versus an existentially quantified statement.

For example: "All humans are mortal": This is a universally quantified statement. If we let $H(x)$ represent "x is a human," and let $M(x)$ represent "x is mortal", then what we are essentially saying, in loglish, is "For all x, IF x is human, THEN x is mortal". This translates, symbolically, to the following:

$$\forall x\,(H(x) \rightarrow M(x))\tag{1}$$

Compare the above to the following: suppose we had written:

$$\forall x\, (H(x) \land M(x))\tag{(2) incorrect}$$

What this incorrect translation says is: "For all x, x is human and x is mortal." This states that everything is human and everything is mortal, whereas what we want to say is something regarding all and only those things that are human.

With that in mind, try to rewrite your first statement accordingly.


On the other hand, the general form for an existentially quantified statement uses conjunction to assert "there exists something such that that something is P and that something is Q."

For example, suppose we want to translate: "Some student missed class today." Crudely, we can denote by $S(x)$: "x is a student." And we can denote by $M(x)$: "x missed class today." Then the symbolic translation amounts to:

$$\exists x\, (S(x) \land M(x)).$$


I'll deal with the second statement, in part to make explicit the scope of each quantified variable, and in part to correct the translation for the statement that includes both an existential and universal quantifier.

"There is an author who has not written a book".
$\iff$ "There exists an $a$ such that $a$ is an author AND, for all $b$, IF $b$ is a book, THEN it is NOT the case that book $b$ was written by author $a$."

A full symbolic translation, then, gives us: $$\exists a \Big(a \in \text{ Author }\land \forall b(b\in \;\text{Book}\;\rightarrow \lnot \operatorname{by}(a, b))\Big)$$

Note that we want $\lnot$by$(a, b)$ since we are talking about book $b$ not being written by author $a$, per your definition.

Related Question