a. A certain procedure to convert a sentence to CNF contains four steps (1–4 below); each step is based on a logical equivalence. For each step, which of the stated equivalences are valid? 

(i) Step 1: drop biconditionals 

a) (α ⇔ β) ≡ ((α ⇒ β) ∧ (β ⇒ α)) 

b) (α ⇔ β) ≡ ((α ⇒ β) ∨ (β ⇒ α))

c) (α ⇔ β) ≡ (α ∧ β) 

(ii) Step 2: drop implications 

a) (α ⇒ β) ≡ (α ∨ ¬β) 

b) (α ⇒ β) ≡ (¬α ∨ β) 

c) (α ⇒ β) ≡ (¬α ∧ β) 

(iii) Step 3: move not inwards 

a) ¬(α ∨ β) ≡ (¬α ∧ ¬β) 

b) ¬(α ∨ β) ≡ (¬α ∨ ¬β) 

c) ¬(α ∧ β) ≡ (¬α ∨ ¬β) 

(iv) Step 4: move “or” inwards and “and” outwards 

a) (α ∨ (β ∧ γ)) ≡ (α ∨ β ∨ γ) 

b) (α ∨ (β ∧ γ)) ≡ ((α ∨ β) ∧ (α ∨ γ)) 

c) (α ∨ (β ∧ γ)) ≡ ((α ∧ β) ∨ (α ∧ γ)) 

b. The Convert-to-CNF-ish procedure applies the first equivalence (the one labeled “a)”) from each of the four steps in part (a). Show the transformed sentence generated by Convert-to-CNF-ish at each stage, when applied to the input sentence A ⇔ (C ∨ D). 

c. Is the final output of Convert-to-CNF-ish equivalent to the input sentence in part (b)? If not, give a possible world where the input and output sentences have different values.