Simplifying propositional formula

Question

[a ^ ¬(b^c^d)] V [a^b^ ¬(c^d)] V [¬a^b^¬(c^d)] V [a^b^¬c^d] V [a^b^c^¬d]

=[a^¬(b^c^d)] V [b^¬(c^d)] V [a^b^¬c^d] V [a^b^c^¬d]

=[a^¬(b^c^d)] V [b^¬c] V [b^¬d] V [a^b^¬c^d] V [a^b^c^¬d]

=[a^¬b] V [a^¬c] V [a^¬d] V [b^¬c] V [b^¬d] V [a^b^¬c^d] V [a^b^c^¬d]

=[a^¬b] V [a^¬c] V [a^¬d] V [b^¬c] V [b^¬d] V [a^¬c] V [b^¬d]

= [a^¬b] V [a^¬c] V [a^¬d] V [b^¬c] V [b^¬d{ ( the answer is supposed to be [b^¬c] V [b^¬d] V [a^¬c] + [a^¬d]

Answer 1

$[a \wedge ¬(b\wedge c \wedge d)] \vee [a\wedge b \wedge ¬(c\wedge d)] \vee [¬a\wedge b \wedge ¬(c\wedge d)] \vee [a\wedge b\wedge ¬c\wedge d] \vee [a\wedge b\wedge c\wedge ¬d]$

I will be taking a CS approach. Assume $\wedge$ as AND $\vee $ as OR and $¬ $ as NOT. Rewriting,

$a (bcd)'+ ab(cd)'+a'b(cd)'+abc'd +abcd'$

$a(b'+c'+d')+ab(c'+d')+abc'd+abcd'$ (Demorgan's Law)

$ab'+ac'+ad'+abc'+abd'+abc'd+abcd'$

$ab'+ac'+ad'+abd'+abc'(1+d)+abcd'$

$ab'+ac'+ad'(1+b)+abc'(1+d)+abcd'$

$ab'+ac'+ad'+abc'+abcd'$

$ab'+ac'+ad'(1+bc)+abc'$

$ab'+ac'+ad'+abc'$

$ab'+ac'(1+b)+ad'$

$ab'+ac'+ad'$

$a(b'+c'+d')$ (Demorgan's Law)

$a(bcd)'$

$\boxed{a\wedge ¬(b \wedge c \wedge d)}$

Hope I didn't commited any mistake.

Answer 2

Like Vineet, I'll take the starting expression as:

$a(bcd)'+ ab(cd)'+a'b(cd)'+abc'd +abcd'$

Now, assuming you copied the starting expression correctly from the book, the 'supposed' answer $bc'+bd'+ac'+ad'$ is incorrect:

Take $A=C=D=T$, and $B=F$

Then the original expression evaluates to $T$ (since $a(bcd)'$ is True)

but the supposed answer evaluates to False

Now, your answer of $ab'+ac'+ad'+bc'+bc'$ is equivalent to the starting expression (good job!) ... but it can be simplified a little further:

$ab'+ac'+ad'+bc'+bd'=$ ($ad'=abd'+ab'd'$)

$ab'+ac'+abd'+ab'd'+bc'+bd'=$ ($abd'$ gets absorbed by $bd'$, and $ab'd'$ by $ab'$)

$ab'+ac'+bc'+bd'=$ ($ac'=abc'+ab'c'$)

$ab'+abc'+ab'c'+bc'+bd'=$ ($abc'$ gets absorbed by $bc'$, and $ab'c'$ by $ab'$)

$ab'+bc'+bd'$

These last few steps can actually be done immediately using the Consensus Theorem:

$xy+x'z+yz=xy+x'z$

That is, from

$ab'+ac'+ad'+bc'+bd'$

we can eliminate $ad'$ as the consensus of $ab'$ and $bd'$, as well as $ac'$ as the consensus of $ab'$ and $bc'$

Another useful principle is:

Generalized Reduction

$pq+pq'r=pq+pr$

So, starting at the very beginning:

$a(bcd)'+ ab(cd)'+a'b(cd)'+abc'd +abcd'\overset{DeMorgan}{=}$

$a(b'+c'+d')+ ab(c'+d')+a'b(c'+d')+abc'd +abcd'\overset{Distribution}{=}$

$ab'+ac'+ad'+abc'+abd'+a'bc'+a'bd'+abc'd+abcd'\overset{Absorption}{=}$

$ab'+ac'+ad'+a'bc'+a'bd'\overset{Reduction}{=}$

$ab'+ac'+ad'+bc'+bd'\overset{Consensus}{=}$

$ab'+bc'+bd'$