2
$\begingroup$

I'm having trouble trying to simplify the following Boolean expressions and will appreciate it very much if anyone can point me in the right direction.

Question 1: Show that $\lnot (\lnot a \lor b) \land (\lnot b \lor c) \equiv a \land \lnot b$

For this one, I used an online Boolean calculator to test their equivalency. However, I have no idea how its able to get rid of the term $c$ in the left hand expression:

$\lnot (\lnot a \lor b) \land (\lnot b \lor c) \equiv (a \land \lnot b) \land (\lnot b \lor c) $ I used DeMorgan's law to arrive at this step, but I don't know how to proceed after it in order to get to $a \land \lnot b$. I mean if there was a $\lnot c$ in here, it's able to turn the $c$ into a tautology... with $c \lor \lnot c$

Question 2: Show that $\lnot ((a \rightarrow c) \land \lnot (c \rightarrow b)) \equiv b \lor \lnot c$

My attempt:

Since the right hand side is in terms of $\lor $, I should change the implication to $\lor$ :

$\lnot ((a \rightarrow c) \land \lnot (c \rightarrow b)) \equiv \lnot(a \rightarrow c) \lor (c \rightarrow b) \equiv \lnot(\lnot a \lor c) \lor (\lnot c \lor b) \equiv (a \land \lnot c) \lor(\lnot c \lor b)$

I think this one is similar to the above question, where it's hard to get rid of the $a$ in this case.

Could someone please show me the rules to eliminate the $c$ and $a$.

Thank you.

$\endgroup$
1
$\begingroup$

To eliminate a redundant term:

note that disjunction is commutative:
(a v b) v c == a v (b v c)

note that (a ^ b) v b = b

therefore (a ^ b) v (b v c) == ((a ^ b) v b) v c == b v c

substitute your variables (as in Question #2):

(a ^ ~c) v (~c v b) == ~c v b

$\endgroup$
2
  • $\begingroup$ Thank you so much!! I googled the equation that you gave in your reply, and I think it's called the absorption law: p v (p ^ q) = p, and p ^ (p v q) = p. I got it now! $\endgroup$ Sep 23 '18 at 6:15
  • $\begingroup$ Thank you too -- it's been 40 yrs since I learned it and 20 since I used it. $\endgroup$
    – amI
    Sep 23 '18 at 17:43

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.