Midterm Exam #1 – MATH 457 Stephen G. Simpson February 24, 2012

This is a 50-minute exam. While taking this exam, you may not consult any books, notes, or electronic devices.

1. Let L be the language consisting of one 2-place predicate, R. Write an L-sentence A with the following properties.

(a) There exists at least one L-structure which satisfies A and contains exactly 5 elements.

(b) There is no L-structure which satisfies A and contains less than 5 elements.

Which of the following sentences are logically valid? In each case, use a structure or a tableau to justify your answer.

2. (∀x ∃y Rxy) ⇒ (∃x ∀y Rxy).

3. (∀x (Hx ⇒ Mx)) ⇔ ¬ ∃x (Hx ∧ ¬ Mx).

4. ((P ⇒ Q) ⇒ P) ⇒ P.

5. ((P ⇒ Q) ⇒ R) ⇔ (P ⇒ (Q ⇒ R)).

6. (∃x (A ⇒ B)) ⇔ ((∀x A) ⇒ B) where x does not occur in B.