I am currently learning about propositions and logical equivalences in a mathematics course I'm taking at university. I'm having trouble understanding how to simplify DNF Formulas. I was given a truth table, and was asked to write a DNF formula without simplifying. I think I successfully managed to do that, but now the question is asking to simplify and I've been stuck for hours. Can someone help me? I'm not really looking for an answer, but at least an explanation.
the formula is
$$P = (\neg m \wedge n \wedge o) \vee (\neg m \wedge \neg n \wedge o) \vee (\neg m \wedge \neg n \wedge \neg o)$$
thank you!
Best Answer
Notice that $\neg m$ is in every clause, so let's temporarily separate it from the rest of the expression:
$$\neg m \wedge \big[(n \wedge o) \vee (\neg n \wedge o) \vee (\neg n \wedge \neg o)\big]$$
You should verify yourself that this is an equivalent form.
Now let's just look at the sub-expression in brackets. Notice that of the 4 possible valuations of $n,o$, only one of them results in this sub-expression being false: $n = T, o = F$ (check with a truth table). So that means it is equivalent to $\neg(n \wedge \neg o)$ (again, check!). Substituting it back, we get
$$\neg m \wedge \neg(n \wedge \neg o)$$
There are two remaining steps to get this back into DNF, which I will leave to you. But I'll give you a hint that one of those steps is doing the reverse of what I did with $\neg m$.