0
$\begingroup$

Using logical laws, I would like to simplify the following expression:

$\neg a \lor \neg b \lor (a \wedge b \wedge \neg c)$

1) Distribution law:

$(\neg a \lor a) \land (\neg a \lor b) \land (\neg a \lor \neg c) \land (\neg b \lor a) \land (\neg b \lor b) \land (\neg b \lor \neg c)$

2) Inverse law:

$(T) \land (\neg a \lor b) \land (\neg a \lor \neg c) \land (\lnot b \lor a) \land (T) \land (\neg b \lor \neg c)$

3) Identity law:

$(\neg a \lor b) \land (\neg a \lor \neg c) \land (\lnot b \lor a) \land (\neg b \lor \neg c)$ from here I'm not sure what to do next.

$\endgroup$
2
$\begingroup$

Try distributing like this:

\begin{align*} &\neg a \vee \neg b \vee (a\wedge b\wedge \neg c) & \\ &\equiv \left[\neg a \vee \neg b\right] \vee (a\wedge b\wedge \neg c) &\text{(Associativity)}\\ &\equiv (\left[\neg a \vee \neg b\right]\vee a) \wedge (\left[\neg a \vee \neg b\right]\vee b) \wedge (\left[\neg a \vee \neg b\right]\vee \neg c) &\text{(Distribution law)}\\ &\equiv ([\neg a \vee a] \vee \neg b)\wedge ([\neg b \vee b] \vee \neg a) \wedge (\neg a \vee \neg b\vee \neg c) &\text{(Assoc. and commut.)}\\ &\equiv (T\vee \neg b)\wedge (T\vee \neg a)\wedge (\neg a \vee \neg b\vee \neg c)&\text{(Identity laws)}\\ &\equiv (T)\wedge (T)\wedge (\neg a \vee \neg b\vee \neg c) &\text{(Identity laws)}\\ &\equiv (\neg a \vee \neg b\vee \neg c) &\text{(Identity laws)} \end{align*}

$\endgroup$
  • $\begingroup$ Steps 4, 5 and 6 are they identity laws or domination laws? $\endgroup$ – direprobs May 30 '16 at 18:13
  • $\begingroup$ Probably they are domination laws. It has been a long time and I don't remember very well the names of the rules. $\endgroup$ – Darío G May 30 '16 at 20:48
2
$\begingroup$

Wore’s answer is good, but a slightly different approach may be a little more intuitive. If you’re familiar enough with the De Morgan laws to notice that $\neg a\lor\neg b$ is just the negation of $a\land b$, which is the first part of the conjunction in parentheses, you might be led immediately to this:

$$\begin{align*} \neg a\lor\neg b\lor(a\land b\land\neg c)&\equiv\color{red}{\neg(a\land b)}\lor(\color{red}{a\land b}\land\neg c)\\ &\equiv\big(\neg(a\land b)\lor(a\land b)\big)\land\big(\neg(a\land b)\lor\neg c\big)\\ &\equiv\top\land\big(\neg(a\land b)\lor\neg c\big)\\ &\equiv\neg(a\land b)\lor\neg c\\ &\equiv\neg a\lor\neg b\lor\neg c\;. \end{align*}$$

The first step is De Morgan, the second is distributivity, the third is inverse, the fourth is identity, and the last is De Morgan again. As an aside, it’s worth mentioning that for some purposes it might be more useful to apply De Morgan again to get $\neg(a\land b\land c)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.