MATH 457: Introduction to Mathematical Logic

Homework #2

January 27, 2012

We refer to Chapter 2 of the Mathematical Logic lecture notes.

1. Redo Homework #1.

2. Let C be the sentence in item 3(c) on page 30. I.e., C is the solution of part 3(c) of Exercise 2.2.14. Write C according to each of the following notation systems.

(a) linear notation with full parentheses: i. Every atomic formula is a formula. ii. If A and B are formulas, then (A ∧ B) and (A ∨ B) and (A ⇒ B)

and (A ⇔ B) are formulas. iii. If A is a formula and x is a variable, then (¬ A) and (∀x A) and

(∃x A) are formulas.

(b) modified linear notation with full parentheses: i. Every atomic formula is a formula. ii. If A and B are formulas, then (A) ∧ (B) and (A) ∨ (B) and

(A) ⇒ (B) and (A) ⇔ (B) are formulas. iii. If A is a formula and x is a variable, then ¬ (A) and ∀x (A) and

∃x (A) are formulas.

(c) full tree notation.

(d) abbreviated tree notation.

(e) Polish notation.

(f) reverse Polish notation.

3. Study Exercises 2.2.15 and 2.2.16 and their solutions. Then, using only the predicates P and I, write a sentence C_{4} with the following property. For any group G, G satisfies C_{4} if and only if G is cyclic of order 4.