2
$\begingroup$

I have the question on:

$$f(a,b,c) = (\neg a \wedge \neg b \wedge c) \vee (\neg a \wedge \neg c)$$

I got to the point : $$\neg a \wedge (\neg c \vee (\neg b \wedge c))$$

But on our book, it states it is: $$\neg a \wedge (\neg b \vee \neg c)$$ or $$\neg a \wedge \neg(b \wedge c)$$

What did I do wrong? Thanks!

$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

For any $P$ and $Q$, you have $P \vee (\neg P \wedge Q) = P \vee Q$. This is called Reduction. If you don't have Reduction, you can get it as follows:

$P \vee (\neg P \wedge Q) = (P \vee \neg P) \wedge (P \vee Q) = True \wedge (P \vee Q) = P \vee Q$.

So, from where you got to, you can proceed as follows:

$\neg a \wedge (\neg c \vee (\neg b \wedge c)) =$ (Reduction)

$\neg a \wedge (\neg c \vee \neg b)) =$ (DeMorgan)

$\neg a \wedge \neg (c \wedge b)$

So, you weren't doing anything wrong .. you just needed a few more steps.

$\endgroup$
0
0
$\begingroup$

You're on a good path. Here is the identity obtained algebraically:

$$\begin{align} \lnot c \lor \lnot b c & = \lnot c \lor \lnot c \lor \lnot b c \\ & = \lnot c \lor \lnot c 1 \lor \lnot b c \\ & = \lnot c \lor \lnot c (b \lor \lnot b) \lor \lnot b c \\ & = \lnot c \lor \lnot c b \lor \lnot c \lnot b \lor \lnot b c \\ & = \lnot c (1 \lor b) \lor (\lnot c \lor c)\lnot b \\ & = \lnot c 1 \lor 1 \lnot b \\ & = \lnot c \lor \lnot b \end{align}$$

You can see the same result for a standard two-valued Boolean algebra on a Venn diagram:

A Venn diagram for 'not C or (C and not B)'

or in a Karnaugh map:

$$\begin{array}{c|c|c|l} & B=0 & B=1 \\ \hline C=0 & \bbox[2pt, gold]1 & \bbox[2pt, gold]1 & \ \lnot C\\ \hline C=1 & \bbox[2pt, cyan]1 & 0 & \ \lnot BC \end{array}$$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .