I have some difficulties to derive how one arrives at the RHS by using the common rules for logical equivalences (and yes, the following equivalences are all correct => checked correctness by looking at truth tables)
(A∧(¬B)) ∨ (B∧(¬C)) ≡ (A∨B) ∧ ¬(B∧C)
when distributing the LHS:
(A∨B) ∧ (A∨(¬C)) ∧ ((¬B)∨B) ∧ ((¬B)∨(¬C)) ≡ (A∨B) ∧ ¬(B∧C)
when applying the tautology + de Morgan's law:
(A∨B) ∧ (A∨(¬C)) ∧ ¬(B∧C) ≡ (A∨B) ∧ ¬(B∧C)
Why is the middle part there? It is correct like that as the truth tables are the exact same as in the case of the RHS of the initial formula.
But it shouldn't be there to arrive at the RHS.
I do not know how to get rid of it? I don't see how absorption may apply here.
Does anyone know how to derive it?
Best Answer
Your problem can be solved very easily using the Consensus Theorem, which states that:
$(X \lor Y) \land (\neg Y \lor Z) \land (X \lor Z) \Leftrightarrow (X \lor Y) \land (\neg Y \lor Z)$
(this law is most easily remembered by going from right to left: with the $(X \lor Y)$ term containing a $Y$, and the $(\neg Y \lor Z)$ term containing a $\neg Y$, you can put together the other parts ($X$ and $Z$) into a new term $(X \lor Z)$ and just add that as a third term.
So with that:
$$(A\land\lnot B)\lor(B\land\lnot C)$$
$$\overset{Distribution}{\Leftrightarrow}$$
$$(A\lor B)\land(A\lor\lnot C)\land(\lnot B\lor B)\land(\lnot B\lor\lnot C)$$
$$\overset{Tautology}{\Leftrightarrow}$$
$$(A\lor B)\land(A\lor\lnot C)\land(\lnot B\lor\lnot C)$$
$$\overset{Consensus}{\Leftrightarrow}$$
$$(A\lor B)\land(\lnot B\lor\lnot C)$$
$$\overset{DeMorgan}{\Leftrightarrow}$$
$$(A\lor B)\land \lnot (B\land C)$$
If you are not allowed to use Consensus in one step, please know that it is easily derived as follows:
$$(X \lor Y) \land (\neg Y \lor Z) \land (X \lor Z)$$
$$\overset{Adjacency}{\Leftrightarrow}$$
$$(X \lor Y) \land (\neg Y \lor Z) \land (X \lor Z \lor Y) \land (X \lor Z \lor \neg Y)$$
$$\overset{Absorption \ x \ 2}{\Leftrightarrow}$$
$$(X \lor Y) \land (\neg Y \lor Z)$$