TL203F Algorithms, Logic and Complexity

Homework 11

We have looked at the syntax of first-order logic in chapter 9. We considered the logical and nonlogical symbols and used the word Language to mean a set of nonlogical symbols. Formulas of a language get a meaning when we apply and interpretation to a language (9.1). We saw that sentences can have different truth values under different interpretations. We started looking at the proof method Induction on complexity. Next week we will finish with chapter 9 and start on chapter 10.


  1. Translate the following sentences into formulas in first-order logic:
    1. Every dog that is bigger than Snati is bigger than Rover.
    2. Some dogs are happier than any person.
    3. Snati is bigger than any dog that is happier than him.

  2. Problem 9.1 on page 112 in the textbook.

  3. Consider the formulas (9) - (12) on page 102 of the textbook. Show a "reasonable" interpretation that makes formulas (9) and (10) are false, but formulas (11) and (12) are true.

  4. Problem 9.3 on page 113 in the textbook.

  5. [Exam 2013] A counting quantifiern can be added to first-order logic. The meaning of the formula ∃nx F(x) is "there exist at least n elements x such that F(x) holds".
    1. Given the language of arithmetic L* and its standard interpretation, show a formula using counting quantifiers that expresses the sentence "There are at least 25 prime numbers less than 100".
    2. Show that every formula using counting quantifiers can be converted into an equivalent formula that does not use counting quantifiers.

Hand this homework in before 12:00 on friday March 21st.

hh (hja), March 14th, 2014.