DNF form ( $ \neg ((p \wedge q) \equiv (r \vee s)) $ )

Question

I need your help bringing $ \neg ((p \wedge q) \equiv (r \vee s)) $ into DNF form (Disjunctive normal form). I have tried many times but appear to get slightly different answers each time.

Wolfram alpha gives an answer but unfortunately no steps on how to reach this answer. I have not been able to reach this answer in my attempts. Here is a link to wolfram alpha's solution: https://www.wolframalpha.com/input/?i=~(+(((p+%26%26+q)+%3C--%3E+(r+%7C%7C+s)))+)

Thank you very much! :)

Answer 1

The truth table of $p\land q$ is: $$ \begin{array}{c|c|c} p&q&p\land q\\\hline 0&0&0\\\hline 0&1&0\\\hline 1&0&0\\\hline 1&1&1\\\hline \end{array} $$

The truth table of $r\lor s$ is: $$ \begin{array}{c|c|c} r&s&r\lor s\\\hline 0&0&0\\\hline 0&1&1\\\hline 1&0&1\\\hline 1&1&1\\\hline \end{array} $$

The truth table of $t\equiv u$ is: $$ \begin{array}{c|c|c} t&u&t\equiv u\\\hline 0&0&1\\\hline 0&1&0\\\hline 1&0&0\\\hline 1&1&1\\\hline \end{array} $$

Putting all together, the truth table of $\neg((p\land q)\equiv (r\lor s))$ is:

$$ \begin{array}{l|c|c|c|c|} {}_{\Large{rs}}~~{}^{\Large{pq}}&00&01&11&10\\\hline 00&0&0&1&0\\\hline 01&1&1&0&1\\\hline 11&1&1&0&1\\\hline 10&1&1&0&1\\\hline \end{array} $$

You can now see all the minterms that must be OR'ed in order to give the DNF:

The minterm associated to the isolated $1$ under $(p,q,r,s)=(1,1,0,0)$ that is thus given by $p\land q\land \neg r\land\neg s$

The minterm associated to: $$ \begin{array}{l|c|c|c|c|} {}_{\Large{rs}}~~{}^{\Large{pq}}&00&01\\\hline 01&1&1\\\hline 11&1&1\\\hline \end{array} $$

is given by $\neg p\land s$.

The minterm associated to: $$ \begin{array}{l|c|c|c|c|} {}_{\Large{rs}}~~{}^{\Large{pq}}&00&01\\\hline 11&1&1\\\hline 10&1&1\\\hline \end{array} $$ is given by $\neg p\land r$

The minterm associated to:

$$ \begin{array}{l|c|c|c|c|} {}_{\Large{rs}}~~{}^{\Large{pq}}&00&10\\\hline 01&1&1\\\hline 11&1&1\\\hline \end{array} $$

is given by $\neg q\land s$

The minterm associated to: $$ \begin{array}{l|c|c|c|c|} {}_{\Large{rs}}~~{}^{\Large{pq}}&00&10\\\hline 11&1&1\\\hline 10&1&1\\\hline \end{array} $$ is given by $\neg q\land r$.

The OR of all of them gives: $$\neg((p\land q)\equiv (r\lor s))=(p\land q\land \neg r\land\neg s)\lor(\neg p\land s)\lor(\neg p\land r)\lor(\neg q\land s)\lor(\neg q\land r)$$

Answer 2

You can do all of this algebraicaly using the following algorithm:

$$ \neg ((p \wedge q) \equiv (r \vee s))$$

Rewrite all $\leftrightarrow$'s ($\equiv$'s) using $P \leftrightarrow Q \Leftrightarrow ((P \rightarrow Q) \land (Q \rightarrow P))$

$$\neg (((p \land q) \rightarrow (r \lor s)) \land ((r \lor s) \rightarrow (p \land q)))$$

Rewrite all $\rightarrow$'s using $P \rightarrow Q \Leftrightarrow \neg P \lor Q$:

$$\neg ((\neg (p \land q) \lor (r \lor s)) \land (\neg (r \lor s) \lor (p \land q)))$$

Keep applying DeMorgan until all negations are 'inside', removing any double negations as they may appear:

$$\neg (\neg (p \land q) \lor (r \lor s)) \lor \neg (\neg (r \lor s) \lor (p \land q))$$

$$ (\neg \neg (p \land q) \land \neg (r \lor s)) \lor (\neg \neg (r \lor s) \land \neg (p \land q))$$

$$ ((p \land q) \land (\neg r \land \neg s)) \lor ((r \lor s) \land (\neg p \lor \neg q))$$

Keep distributing any $\land$'s over $\lor$'s until it is in DNF:

$$ ((p \land q) \land (\neg r \land \neg s)) \lor (((r \lor s) \land \neg p) \lor ((r \lor s) \land \neg q))$$

$$ ((p \land q) \land (\neg r \land \neg s)) \lor ((r \land \neg p) \lor (s \land \neg p)) \lor ((r \land \neg q) \lor (s \land \neg q))$$

(Drop unnecessary parentheses:)

$$ (p \land q \land \neg r \land \neg s) \lor (r \land \neg p) \lor (s \land \neg p) \lor (r \land \neg q) \lor (s \land \neg q)$$