1. Consider the set of propositional formulas: U = {p q, (p q) r, p r}

Provide an example of

(i) a non-satisfying interpretation

(ii) a satisfying interpretation

2. Provide an example of a formula A such that U A, where U is the set of formulas given in the Question 1.

3. Is the set of formulas of Question 1, {p q, (p q) r, p r}, closed under logical consequence?

4. Analyze the proof of the theorem and mention one rule of inference used in the proof.

Theorem Let n . If 7n + 6 is odd then n is odd.

Proof

Let us assume that n is not odd, that is, n is even. Then we have that n = 2k for some k . So

7n + 6 = 7(2k) + 6

= 2(7k) + 6

= 2(7k + 3)

From here we conclude that 7n + 6 is even in contradiction with the premise of the theorem. Therefore, if 7n + 6 is odd then n must be odd.

5.The proof in the Hilbert deductive system of a theorem known as conjunction elimination is provided. Write to the right of each step the number of the axiom or the name of the inference rule used. Note that the justification of the last step is already given.

Theorem conjunction elimination

Let A and B be arbitrary formulas of propositional logic. Then A B A

Proof

1. A (B A)

2. (B A) A

3. (B A) A

4. A B A 3, definition of operator ((B A) A B)

6. Prove in the Hilbert deductive system the expression given in Problem 3.8 of the textbook:

{A} (B A) B

The first two steps of the proof, as well as the inference rule to be used in the third step, are given. You are required to complete the third step and give the subsequent steps of the proof.

1. {A, B A} A Assumption

2. {A, B A} B A Assumption

3. 2, contrapositive rule (2)