TÖL203F Algorithms, Logic and Complexity

Homework 13

This week we started on Chapter 10. On monday March 31st there will only be one student presentation, so we will continue with Chapter 10 and look at some metalogical notation from section 10.2.

Homework

  1. Argue that we could make do with having only ~ (negation), & (conjunction), and ∀ (universal quantification) in first-order logic. How about having only & (conjunction), ∨ (disjunction), and ∃ (existential quantification)?

  2. Let L be the language {a, b, R, f} and let M be an interpretation with the domain |M| being the natural numbers, aM = 0, bM = 2, RM(m, n) is the relation that m divides n evenly (e.g. 3 divides 12 evenly, but 3 does not divide 13 evenly), and fM(n) = n+1 (i.e. the successor function). What are the truth values of the following sentences under the interpretation M:
    1. R(f(a), f(b))
    2. ∀x(R(b,x) ∨ R(b,f(x)))
    3. ∃x∀y(~(x = f(a)) & R(x, y))

  3. Problem 10.2 on page 123 in the textbook. To do this problem (and the next ones) you have to read the beginning of section 10.2, bottom of page 119 and top of page 120. It will be covered in mondays lecture.

  4. Problem 10.3 on page 123 in the textbook.

  5. Problem 10.4 on page 123 in the textbook.

Hand this homework in before 12:00 on friday April 4th.

hh (hja) hi.is, March 28th, 2014.