Solutions to Chapter 45 Normal forms

A. Consider the following sentences:

1. 1.
   ​

   $(A\to \neg B)$

2. 2.
   ​

   $\neg (A\leftrightarrow B)$

3. 3.
   ​

   $(\neg A\vee \neg (A\wedge B))$

4. 4.
   ​

   $(\neg (A\to B)\wedge (A\to C))$

5. 5.
   ​

   $(\neg (A\vee B)\leftrightarrow ((\neg C\wedge \neg A)\to \neg B))$

6. 6.
   ​

   $((\neg (A\wedge \neg B)\to C)\wedge \neg (A\wedge D))$

For each sentence, find an equivalent sentence in DNF and one in CNF. We give a solution for (2). The truth table for $\neg (A\leftrightarrow B)$ is:

A sentence in DNF can be read off from lines 2 and 3:

and one in CNF from lines 1 and 4: