Answer to Question #144937 in Discrete Mathematics for RamyaaSai

Question

Obtain DNF for ~(p → (q ^ r)) and also obtain PCNF for (p → q) ^ (qr) without using truth tables.

Answer 1

We shall use $\overline{x}$ for negation of $x$. Let us obtain DNF for $\overline{p → (q \land r)}$ :

$\overline{p → (q \land r)}=\overline{\overline{p} \lor (q \land r)}= \overline{(\overline{p} \lor q) \land(\overline{p}\lor r)}= \overline{(\overline{p} \lor q)} \lor\overline{(\overline{p}\lor r)}= (p \land \overline{q}) \lor(p\land \overline{r})$

Therefore, $(p \land \overline{q}) \lor(p\land \overline{r})$ is DNF for $\overline{p → (q \land r)}$ .

Let us obtain PCNF for $(p → q) \land (q\lor r)$:

$(p → q) \land (q\lor r)= (\overline{p}\lor q) \land (q\lor r)= (\overline{p}\lor q\lor (r\land\overline{r})) \land ((p\land\overline{p})\lor q\lor r)=$

$=(\overline{p}\lor q\lor r)\land (\overline{p}\lor q\lor\overline{r}) \land (p\lor q\lor r)\land (\overline{p}\lor q\lor r)=$

$=(\overline{p}\lor q\lor r)\land (\overline{p}\lor q\lor\overline{r}) \land (p\lor q\lor r)$

Consequently, $(\overline{p}\lor q\lor r)\land (\overline{p}\lor q\lor\overline{r}) \land (p\lor q\lor r)$ is  PCNF for $(p → q) \land (q\lor r).$