Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
So, what is your question? My question is whether you can format things to make them a little easier for us to read. –  Gerry Myerson Dec 31 '13 at 22:09
    
My god, my bad.. Don't know why it's formatted out like this... –  user118075 Dec 31 '13 at 22:20
    
doneeeeeeeeeeeee –  user118075 Dec 31 '13 at 22:21
1  
All except for the part about telling us what your question is. Also, I can't make much sense out of the title. –  Gerry Myerson Dec 31 '13 at 22:22
    
(Also this is predicate logic, not propositional logic.) –  Malice Vidrine Dec 31 '13 at 22:37

2 Answers 2

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.

share|improve this answer
1  
$\color{red}{\bf\large \text{Happy New Year 2014}}$ –  Babak S. Jan 1 at 14:18
    
@amWhy: Feliz Ano Nuevo to all! +1 –  Amzoti Jan 1 at 18:01

I'll use the more customary $\in$ for “belongs to”. Your usage of the “and” connective is wrong.

“Every book has an author” should be

$$ \forall b(b\in\mathrm{Books} \to (\exists a(a\in\mathrm{Authors} \land \mathrm{by}(a,b)))) $$

If relativized quantifiers are allowed by the language, it could be $$ \forall b\in\mathrm{Books}(\exists a\in\mathrm{Authors}(\mathrm{by}(a,b))) $$

Your other formulas are similarly wrong.

Let's see how you can build the third formula from the ground up:

Every author has written a short book

Translation: For every author, we can find a book which is short and whose author is the one we're talking about

So the book $b$ is short, $\mathrm{short}(b)$, and its author is $a$, $\mathrm{by}(a,b)$: the bulk of the formula is then $\mathrm{short}(b) \land \mathrm{by}(a,b)$. Now we can add the quantifiers.

$$ \forall a\in\mathrm{Authors}(\exists b\in\mathrm{Books}(\mathrm{short}(b) \land \mathrm{by}(a,b))) $$ Without relativized quantifiers: $$ \forall a(a\in\mathrm{Authors}\to(\exists b(b\in\mathrm{Books}\land (\mathrm{short}(b) \land \mathrm{by}(a,b))))) $$

share|improve this answer
    
Good answer. I would just add that the use of $\Rightarrow$ in the formalization of (iii) is also incorrect. The way he/she uses the truth-functional conditional in this formula is how they should be using the & all along. –  Kevin Halasz Dec 31 '13 at 22:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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