1

I have been attempting to prove the following proposition is a tautology, without the use of truth tables (i.e.: using logical equivalences):

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

The initial approach that occurred to me was to show that $(((a \land\lnot b) \lor\lnot c) \land (a \lor b))$ was equivalent to the negation of $(c \lor \lnot b)$.

However, I have tried for a while and cannot seem to eliminate the '$a$' which does not appear in $(c \lor \lnot b)$. I was wondering if there was a way to approach this, or whether I have just done the overall approach incorrectly.

user400188
  • 1,936
Ryan
  • 13
  • 2

1 Answers1

0

Your initial approach was on the right track. However it was not required that $(((a \land \lnot b) \lor \lnot c) \land (a \lor b))$ was equal to the negation of $(c\lor\lnot b)$, only that it was equal to something which contained $\lnot(c\lor\lnot b)$ in a disjunction.

\begin{align}&(((a \land \lnot b) \lor \lnot c) \land (a \lor b)) \lor (c \lor \lnot b)\\ &(\color{blue}{a} \land \lnot b\land \color{blue}{a})\lor(a \land \color{red}{\lnot b\land b})\lor(\lnot c\land a)\lor(\lnot c\land b)\lor(c\lor\lnot b)\\ &(a \land \lnot b)\lor(\lnot c\land a)\lor\underbrace{\color{green}{(\lnot c\land b)}}_{=\lnot(c\lor \lnot b)}\lor\color{green}{(c\lor\lnot b)}\\ &\lnot(c\lor\lnot b)\lor(c\lor\lnot b) \end{align}

user400188
  • 1,936