Converting to DNF. Demorgans then moved brackets. Correct/incorrect?

132 Views Asked by At

Disjunction normal form (DNF) consists of disjunctions of conjunctions (if I understand correctly). Ex. $(p \land q) \lor (p \land r \land s)$

I am facing this problem: $(t \implies \neg s) \land \neg t$

I have to convert to DNF.

This is my solution:

$\neg t \lor (\neg s \land \neg t)$

What I basically did was get rid of the implication sign using Demorgan's Law. Then, I moved the brackets. That's it.

Is this correct or incorrect?

1

There are 1 best solutions below

1
On

First some corrections to your description / terminology:

Disjunctive normal form. A formula is in DNF if it is a disjunction of conjunctions of literals; here a literal is a propositional atom, or the negation of a propositional atom.

Material implication is the name of the rule that $A\to B$ is equivalent to $\lnot A\lor B$.

De Morgan's laws are the following laws: \begin{align} \lnot(A\land B)\equiv \lnot A\lor\lnot B\\ \lnot(A\lor B)\equiv \lnot A\land\lnot B \end{align} You don't need them in this exercise, but they are very useful in getting to normal forms, since they can bring an "outside" negation to the "inside" of a conjunction / disjunction. They have nothing to do with implications, however.


Now your exercise:

Your formula is equivalent by material implication to: $$(t\to \lnot s)\land \lnot t\quad\equiv\quad(\lnot t\lor\lnot s)\land \lnot t$$ Simply moving the brackets around to get something resembling an answer is not allowed! You could make a truth table to see that the following formulas are not equivalent: $$ p\land (q\lor r)\quad\text{ and }\quad (p\land q)\lor r $$

What you have to do, is use the distributivity laws: \begin{align} (A\lor B)\land C\equiv(A\land C)\lor (B\land C)\\ (A\land B)\lor C\equiv(A\lor C)\land (B\lor C) \end{align}

Using these laws we can see that: $$(\lnot t\lor\lnot s)\land\lnot t\quad\equiv\quad(\lnot t\land\lnot t)\lor(\lnot s\land \lnot t).$$