1.  Prove the following by formal deduction using only

•  the 11 rules of formal deduction,

•  membership ( ∈),

•  negation introduction (¬+),

•  double negation (¬¬),

•  transitivity (Tr.),

•  hypothetical syllogism (Hyp.), and

• replaceability of equivalent formulas (Repl.).

[2]                     (a) A → ¬B ⊢ ¬(A ∧ B)

[3]                     (b) Lemma 1: A → B, B → A ⊢ A ↔ B

[2]                       (c) Lemma 2: A → B, B → C, C → A ⊢ A ↔ C.

You may also use Lemma 1 in the proof.

[2]                      (d) A → B, B → C, C → A ⊢ (A ↔ B) ∧ (B ↔ C) ∧ (C ↔ A)

You may also use Lemma 2 in the proof.

[3]                     (e) Lemma 3: A ↔ B ⊢ (A → B) ∧ (B → A)

[3]                       (f) A ↔ B, B ↔ C, C ↔ A ⊢ (A → B) ∧ (B → C) ∧ (C → A)

You may also use Lemma 3 in the proof.

2. Show the following. You may use the soundness and completeness of formal deduc-

tion.

(a)  ¬(¬(A ∧ B) ∧ ¬(C ∧ D)) ⊢⊣ (A ∧ B) ∨ (C ∧ D).

Note that ¬(A ∧ B) is tautologically equivalent to the Sheffer stroke, A | B.

[5]                     (b) A → (B → C) ⊬ (A → B) → C

3. For the following, is it possible to construct an inconsistent formula using only log- ical variables and only the connectives from the given set, Ki?  Prove your answer either by showing that all formulas constructed using only the given connectives are satisfiable, or by showing that a specific formula is not satisfiable.

(a) K1 = {∧, ∨}. (Use structural induction.)

[2]                     (b) K2 = {¬, ↔}

[2]                     (c) K3 = {¬, ∨}

4. Infinite-valued Łukasiewicz logic is a “fuzzy logic” in which “truth valuations” as- sign propositional variables real number values in the interval [0, 1]. The connectives {→ , ↔ , ¬ , ∧ , ∨ , ⊗ , ⊕} are defined to have the following truth valuations:

Equivalence:           (p ↔ q)t : = 1 − |pt − qt |

Weak conjunction:   (p ∧ q)t  : = min {pt, qt}

Weak disjunction:    (p ∨ q)t  : = max {pt, qt}

Strong conjunction: (p ⊗ q)t  : = max {0,pt + qt − 1}

Strong disjunction:  (p ⊕ q)t  : = min {1,pt + qt}

Note that in this question all connectives refer to those of the Łukasiewicz logic, not those of the propositional logic that we have studied. For this reason, we write them in blue as a reminder, but this is not essential.

In this logic, a formula is a tautology if it evaluates to 1 under any valuation of the propositional variables.

Which of the following are tautologies? Prove your claim by an informal argument (i.e. a proof using real number arithmetic, not by formal deduction).

(a) p ∨ ¬p“Weak excluded middle”

[2]                     (b) p ⊕ ¬ p“Strong excluded middle”

[2]                     (c) p ∧(p → q) ↔ q“Weak modus ponens”.

[2]                    (d) p ⊗(p → q) ↔ q“Strong modus ponens”

[2]                     (e) p ⊗(q ⊕ r) ↔(p ⊗ q) ⊕(p ⊗ r)“Strong distributivity 1”

5. The study of a class of substances has led to the following results:

(i) If A and B appear, then so does precisely one of C or D.

(ii) If B and C appear, then both or neither of A, D appears.

(iii) If neither of A, B appears, then neither of C, D appears.

(iv) If neither of C, D appears, then neither of A, B appears.

In this question, you will use the Davis-Putnam Procedure (DPP) to show that not all three of A, B, C can occur, and if A, B are both missing then so is C.

We translate the above argument into propositional logic using proposition symbols A, B, C and D as follows.

Premises:

(A ∧ B) → (C ↔ ¬D),

(B ∧ C) → (A ↔ D),

(¬A ∧ ¬B) → (¬C ∧ ¬D),

(¬C ∧ ¬D) → (¬A ∧ ¬B)

Conclusion:

(¬(A ∧ B ∧ C)) ∧ ((¬A ∧ ¬B) → ¬C)

Now carry out the following steps:

[5]                       (a) Use the laws of propositional calculus to transform the formulas above (or their

negations, as appropriate) into conjunctive normal form (CNF). Explicitly state each law of propositional calculus that you use in any of your transformations. Finally, convert your set of formulas into a set of clauses.