[Math] Simplify a Boolean Algebra expression with don’t cares


In my homework assignment, I'm asked to simplify an expression of Q'RS'T' + Q'R'S'T + RS'T with don't-cares of m3, m12, and m14.

I know how I would achieve this result with a K-map, however the instructions of the question explicitly forbid the use of a K-map and only allow the use of boolean properties.

This means (or so I guess) that when the input (QRST) = (0011, 1100, 1110), the output can be anything. I don't see any identifying features of these that I could use to simplify it, again, without using a k-map.

How do I simplify an expression like this, while factoring in the don't-cares, without a k-map?

Best Answer

The don't cares are $Q'R'ST, QRS'T', QRST'$. The expression to be simplified is $Q'RS'T' + Q'R'S'T + RS'T$.

$$\begin{array}{r|c|c|c|c|} QR\backslash ST&00&01&11&10\\\hline 00&&1&X\\\hline 01&1&1\\\hline 11&X&1&&X\\\hline 10\\\hline \end{array}$$

Adding $QRS'T'$ and $Q'R'ST$ to the expression,

$$\begin{align*} f(Q,R,S,T) &= Q'RS'T' + Q'R'S'T + RS'T + QRS'T' + Q'R'ST\\ &=(Q'+Q)RS'T' + RS'T + Q'R'(S+S')T\\ &=RS'T' + RS'T + Q'R'T\\ &= RS' + Q'R'T \end{align*}$$

From the comment expression,

$$\begin{align*} g(Q,R,S,T) &= (QR')'S'T + Q'R'ST + RS'T'\\ &= (Q'+R)S'T + Q'R'ST + RS'T'\\ &= Q'S'T + RS'T + Q'R'ST + RS'T'\\ &= Q'(R+R')S'T + RS'T + Q'R'ST + RS'T'\\ &= Q'RS'T + Q'R'S'T + RS'T + Q'R'ST + RS'T'\\ &= Q'R'(S'+S)T + (Q'+1)RS'T + RS'T'\\ &= Q'R'T + RS' \end{align*}$$


$$\begin{align*} h(Q,R,S,T) &= Q'RS'T' + Q'R'S'T + RS'T + QRS'T'\\ &=RS'+ Q'R'S'T'\\ &= S'(R+Q'R'T')\\ &= S'(R+R')(R+Q')(R+T')\\ &= S'(R+Q')(R+T') \end{align*}$$

Related Question