2

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.

GMOterminator
  • 53

1 Answers1

1

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

amI
  • 125
  • 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! – GMOterminator Sep 23 '18 at 06:15
  • Thank you too -- it's been 40 yrs since I learned it and 20 since I used it. – amI Sep 23 '18 at 17:43