Math 2510 Spring 2010 -- Homework Problem Set #2

Due: Friday, February 5th
  1. Let \( \underline{c} \) be a constant, \( f(x) \) be a function, and \( P(x,y), Q(x) \) be predicates.
    1. Consider the sentence "\( \forall x \; (P(x,\underline{c}) \to Q(f(x)) \)". Show that this sentence is satisfiable (find a model for the sentence).
    2. Is this sentence logically valid? Prove your answer.
    3. Write a sentence (i.e. no free variables) involving \( \underline{c}, f(x), P(x,y), \) and \( Q(x) \) which is unsatisfiable. Explain why your sentence is unsatisfiable.
    4. Write a sentence (i.e. no free variables) involving \( \underline{c}, f(x), P(x,y), \) and \( Q(x) \) which is satisfiable but not logically valid. Construct models showing that your sentence is satisfiable but not logically valid.
    5. Write a sentence (i.e. no free variables) involving \( \underline{c}, f(x), P(x,y), \) and \( Q(x) \) which is logically valid. Prove that your sentence is logically valid.

    Note: For parts c, d, and e, don't reuse the sentence from part a.

  2. Prove Theorems K9, K10, K19, K25, K30, and K35