Stuck with boolean expression simplification

98 Views Asked by At

I have the expression $\lnot A \land B \land C \lor A \land \lnot B \land C \lor A \land B \land \lnot C \lor A \land B \land C$. This simplifies to $A \land B \lor B \land C \lor C \land A$.

This is what I tried:
1. $\lnot A \land B \land C \lor A \land \lnot B \land C \lor A \land B \land \lnot C \lor A \land B \land C$
2. $A \land (\lnot B \land C \lor B \land \lnot C \lor B \land C) \lor \lnot A \land B \land C$
3. $A \land (B \land (C \lor \lnot C) \lor \lnot B \land C) \lor \lnot A \land B \land C$
4. $A \land (B \lor \lnot B \land C) \lor \lnot A \land B \land C$
5. $A \land B \lor A \land \lnot B \land C \lor \lnot A \land B \land C$
6. $C \land (A \land \lnot B \lor \lnot A \land B) \lor A \land B$

And I don't know what to do next. Maybe there is error in my calculation? If someones spots an error and/or knows what should be my next step, please help.

2

There are 2 best solutions below

0
On BEST ANSWER

Here is a useful principle:

Adjacency:

$$(P \land Q) \lor (P \land \neg Q) \Leftrightarrow P$$ If you don't have Adjacency, you can derive it from more basic equivalences:

$$(P \land Q) \lor (P \land \neg Q) \Leftrightarrow \text{Distribution}$$

$$P \land (Q \lor \neg Q) \Leftrightarrow \text{Complement}$$

$$P \land \top \Leftrightarrow \text{Identity}$$

$$P$$

You can use Adjacency at various times, e.g. right from the start you can combine $\neg A \land B \land C$ and $A \land B \land C$ to get $B \land C$

Or, from your line two you can combine $B \land \neg C$ and $B \land C$ to just $B$.

Another useful principle is:

Reduction

$$P \lor (\neg P \land Q) \Leftrightarrow P \lor Q$$

Its proof:

$$P \lor (\neg P \land Q) \Leftrightarrow \text{Distribution}$$

$$(P \lor \neg P) \land (P \lor Q) \Leftrightarrow \text{Complement}$$

$$\top \land (P \lor Q) \Leftrightarrow \text{Identity}$$

$$P \lor Q$$

This one you could use on line 4 to reduce $B \lor (\neg B \land C)$ to $B \lor C$

The reduction principle generalizes to:

Generalized Reduction

$$(P \land R) \lor (\neg P \land Q \land R) \Leftrightarrow (P \land R) \lor (Q \land R)$$

Its proof:

$$(P \land R) \lor (\neg P \land Q \land R) \Leftrightarrow \text{Distribution}$$

$$(P \lor (\neg P \land Q)) \land R \Leftrightarrow \text{Reduction}$$

$$(P \lor Q) \land R \Leftrightarrow \text{Distribution}$$

$$(P \land R) \lor (Q \land R)$$

And this one you could use on line $5$ to reduce $A \land \neg B \land C$ to $A \land C$ in the context of $A \land B$, and to also reduce $\neg A \land B \land C$ to $B \land C$, also in the context of $A \land B$, and that immediately gives you your desired answer.

Putting it all together:

$$(\lnot A \land B \land C) \lor (A \land \lnot B \land C) \lor (A \land B \land \lnot C) \lor (A \land B \land C) \Leftrightarrow \text{Adjacency}$$

$$(B \land C) \lor (A \land \lnot B \land C) \lor (A \land B \land \lnot C) \Leftrightarrow \text{Generalized Reduction x 2}$$

$$(B \land C) \lor (A \land C) \lor (A \land B) \Leftrightarrow \text{Commutation}$$

$$(A \land B) \lor (B \land C) \lor (C \land A)$$

0
On

Note that $a \lor a=a$.

Thus $\bar A B C \lor A \bar B C \lor A B \bar C \lor A B C=\bar A B C \lor A B C \lor A \bar B C \lor A B C \lor A B \bar C \lor A B C $. Applying distributive law and using $\bar a \lor a = T$ we get what we need