Difference between DNF and CNF

Question

I'm stuck on this particular question:

Let $A$ be the following propositional formula $$(\lnot p \rightarrow q) \leftrightarrow\ (\lnot q \rightarrow \lnot r)$$ Find a propositional formula $B$ in DNF that is logically equivalent to $A$

I don't understand about this DNF, can someone help please?

Answer 1

We say that a formula is in disjunctive normal form if it is a disjunction of conjunctions of literals.

More formally:

Definition: We say that a formula $\varphi$ is in disjunctive normal form if$$\varphi =\bigvee_{i \leq n}\bigwedge_{j \leq m} \varphi_{ij}$$ where $ϕ_{ij}$ is atomic or the negation of an atom (called a literal) and the notation for finite disjunction and conjuction means

\begin{cases} \bigwedge_{i \leq 0} \varphi_i = \varphi_0\\ \bigwedge_{i \leq n+1} \varphi_i = \bigwedge_{i \leq n} \varphi_i \wedge \varphi_{n+1}\\ \end{cases}

\begin{cases} \bigvee_{i \leq 0} \varphi_i = \varphi_0\\ \bigvee_{i \leq n+1} \varphi_i = \bigvee_{i \leq n} \varphi_i \vee \varphi_{n+1}\\ \end{cases}

Now recall that

1. $\alpha \rightarrow \beta \equiv \neg \alpha \lor \beta$
2. $\alpha \leftrightarrow \beta \equiv (\alpha \rightarrow \beta)\land(\beta \rightarrow \alpha)$.

Now why don't you try to apply those equivalences above? Distributivity may also be helpful to get rid of the outermost conjuction.