So hello everyone, I am doing some boolean logic and I have this exercise to convert the following term to DNF (disjunctive normal form), but it is so large that everything I try ends up being mega long! I know the logic rules', but Im just stupefied at how those can be applied to such big big terms Please tell me some steps to simplify this:
(!a AND c) OR ( !b AND !c AND d) OR (!a AND b AND !d) OR (!a AND b AND !c AND !d)
What I don't understand is how to understand and remember the simplification to such things. I tried to simplify it on my own and it just gets larger According to wolfram alpha the answer is: (!a AND b AND !d) OR (!a AND c) OR (!b AND !c AND d)
I shouldn't do this with a truth table
In logic, it is usual to write $\land,\ \lor,\ \lnot$ for the logical connectives 'AND', 'OR', 'NOT', respectively. (That's one way to make formulas a little shorter.)
So, it is about $\varphi\ :=\ (\lnot a\land c)\ \lor\ (\lnot b\land\lnot c\land d)\ \lor\ (\lnot a\land b\land \lnot d)\ \lor\ (\lnot a\land b\land \lnot c\land \lnot d)$.
We can use the same distributivity rule for $\land,\lor$ as we can use for multiplication and addition of numbers: we should apply operation 'OR' for all possible cases when one literal is chosen from each clause.
But before that, observe that the last clause is almost the same as the third one, and use the absorption rule $x\lor(x\land y)=x$ to get rid of it.
Then, we get $$\begin{align} \varphi\ &=\ (\lnot a\land c)\ \lor\ (\lnot b\land\lnot c\land d)\ \lor\ (\lnot a\land b\land \lnot d)\ = \\ &=\ (\lnot a\lor \lnot b\lor\lnot a )\ \land\ (\lnot a\lor\lnot b\lor b)\ \land\ (\lnot a\lor\lnot b\lor\lnot d)\ \land\ \\ &\quad\land (\lnot a\lor \lnot c\lor\lnot a)\ \dots \end{align}$$ which will simplify further, I guess you can take it on from here.