TÖL203F Algorithms, Logic and Complexity

Homework 12

This week we heard the first student presentations and then finished the proof of the Parenthesis Lemma (in section 9.2). Next week we will hear three more student presentations and then finish off Chapter 9 by looking at four syntactic notations: i) subformulas, ii) free occurrences of variables, iii) instances of formulas, and iv) sentences. We will then start on Chapter 10 and look at what it means for a sentence to be true in an interpretation (10.1).

Homework

  1. Let L be a language with the following nonlogical symbols: a, b are constants, L is a 2-place predicate, and f is a 1-place function. For each of the following sentences construct two interpretations if possible. One where the sentences are true, and one in which they are false.
    1. ~∃x f(x) = x
    2. (∀x ∃y Lxy) → (∃y ∀x Lxy)
    3. ∀x ∀y ∀z ((Lxy & Lyz) → Lxz)

  2. Use induction on complexity to prove that every formula in first-order logic contains at least one atomic formula.

  3. Finish the proof for part c) of Lemma 9.4 by proving the case when functions symbols are present (and we have terms). Do that using induction on complexity for terms and add it into the base case in the proof for c).

  4. Problem 9.4 on page 113 in the textbook. If the formula F is ∃x(Cx & Dx), a formation sequence for it can be [Cx, Dx, (Cx & Dx), ∃x(Cx & Dx)] (however you have to prove this for a general formula F!)

  5. Problem 9.6 on page 113 in the textbook.

Hand this homework in before 12:00 on friday March 28th.

hh (hja) hi.is, March 21st, 2014.