Simplifying the Boolean expression $\overline{(a+b)\cdot \overline{a(b\oplus c)}}$ to have lowest number of logical gates

Question

I have this boolean expression $$ f(a,b,c)_{Question}=nand(or(a,b) , nand(a, xor(b,c))) = \overline{(a+b)\cdot \overline{a(b\oplus c)}} $$ when I try to simplify the gates using boolean algebra, I get $$ f(a,b,c)_{Question}=or(nor(a,b) , and(a,xor(b,c)))=\overline{a+b}+(a\cdot(b⊕c)) $$

I need to simplify further and get $$ f(a,b,c)_{answer}=a\oplus(b \oplus \overline{a\cdot c}) $$ my function: $f_{answer}$ is justified by the criteria:

• $f_{answer}$ uses lowest number of logical gates,(in our case minimum:3(xor,xor,and))
• there may be n number of possible $f_{answer}$, example we can have another answer with same-minimum number of logical gates: $(a\oplus b) \oplus \overline{a\cdot c}$ is another possible answer,to our function,and it will be accepted,since it has only 3 logical gates,its is accepted

Question: So how can I find $f_{answer}$ when $f_{Question}$ is provided, what are the steps

but don't know what's the steps*,can anyone help?

I found these rules for xor:

from here but they are of no use

Edit:

when I expand** $ f(a,b,c)_{Question}=\overline{a+b}+a\cdot(b⊕c) $
I get $$ f(a,b,c)_{expanded}=\overline{(\overline{\overline{a}\overline{b}})\cdot (\overline{a\cdot\overline{\overline{b}\overline{c}}\cdot \overline{bc}})} $$

*The process to simplify,like "first remove brackets...", "Steps" is the answer I need for this question

**Which I think would be the first step in converting any, $f_{Question}$ to $f_{answer}$

Answer 1

More complex Boolean expression can be calculated using algebraic expressions for each gate.

In this system, we have

• $\operatorname{OR}(a,b) = a+b-ab$
• $\operatorname{AND}(a,b) = ab$
• $\operatorname{NOR}(a,b) = 1-a-b+ab$
• $\operatorname{NAND}(a,b) = 1-ab$
• $\operatorname{XOR}(a,b) = a+b-2ab$

with the usual rule that $a^2=a$.

In this case, $or(nor(a,b) , and(a,xor(b,c)))$ becomes

$$1+ab-a-b+a(b+c-2bc)-(1+ab-a-b)(ab+ac-2abc)$$

$$=1+ab-a-b+ab+ac-2abc-ab-ac+2abc-ab-abc+2abc+ab+ac-2abc+ab+abc-2abc$$

$$=1+2ab-a-b+ac-2abc$$

And similarly, $a\oplus b\oplus\overline{ac}$ is represented by

$$(a+b-2ab)+(1-ac)-2(a+b-2ab)(1-ac)$$

$$=a+b-2ab+1-ac-2a-2b+4ab+2ac+2abc-4abc$$

$$=-a-b+2ab+1+ac-2abc$$

As the two last expressions in each case are the same, we can conclude that $$or(nor(a,b) , and(a,xor(b,c)))=a\oplus b\oplus\overline{ac}$$.

Answer 2

The truth table for your expression is:

$$\begin{array}{c|c|c|c}a&b&c&\overline{(a+b)\cdot\overline{a(b\oplus c)}}\\\hline F&F&F&T\\F&F&T&T\\F&T&F&F\\F&T&T&F\\T&F&F&F\\T&F&T&T\\T&T&F&T\\T&T&T&F\end{array}$$

which means that it should be possible to convert your expression $f_{\text{Question}}$ into the disjunctive normal form corresponding to this truth table, which is:

$$\overline{a}\overline{b}\overline{c}+\overline{a}\overline{b}c+a\overline{b}c+ab\overline{c}$$

And, indeed:

$$\begin{array}{rcll}\overline{(a+b)\cdot\overline{a(b\oplus c)}}&=&\overline{(a+b)\cdot\overline{a(b\overline{c}+\overline{b}c)}}&\text{definition of }\oplus\\&=&\overline{(a+b)\cdot\overline{ab\overline{c}+a\overline{b}c}}&\text{distributivity}\\&=&\overline{(a+b)\cdot((\overline{a}+\overline{b}+c)\cdot(\overline{a}+b+\overline{c})})&\text{de Morgan's law}\\&=&\overline{a}\overline{b}+ab\overline{c}+a\overline{b}c&\text{de Morgan's law}\\&=&\overline{a}\overline{b}(\overline{c}+c)+ab\overline{c}+a\overline{b}c&\text{as }c+\overline{c}\text{ is true}\\&=&\overline{a}\overline{b}\overline{c}+\overline{a}\overline{b}c+ab\overline{c}+a\overline{b}c&\text{distributivity}\\&=&\overline{a}\overline{b}\overline{c}+\overline{a}\overline{b}c+a\overline{b}c+ab\overline{c}&\text{commutativity}\end{array}$$

Now, if $f_\text{Answer}$ is really an equivalent formula, it should result in the same truth table. This means that, similarly, you can convert $f_\text{Answer}$ to the same disjunctive normal form:

$$\begin{array}{rcll}a\oplus(b\oplus(\overline{ac}))&=&a\oplus(b\oplus(\overline{a}+\overline{c}))&\text{de Morgan's law}\\&=&a\oplus(b\oplus(\overline{a}+\overline{c}))&\text{de Morgan's law}\\&=&b\oplus(a\oplus(\overline{a}+\overline{c}))&\text{commutativity and associativity of }\oplus\\&=&b\oplus(a\cdot\overline{\overline{a}+\overline{c}}+\overline{a}(\overline{a}+\overline{c}))&\text{definition of }\oplus\\&=&b\oplus(aac+\overline{a}\overline{a}+\overline{a}\overline{c}))&\text{de Morgan's laws, distributivity}\\&=&b\oplus(\overline{a}+c)&\text{tidy up}\\&=&b\overline{\overline{a}+c}+\overline{b}(\overline{a}+c)&\text{definition of }\oplus\\&=&ba\overline{c}+\overline{b}\overline{a}+\overline{b}c&\text{de Morgan's law}\\&=&ab\overline{c}+\overline{a}\overline{b}(\overline{c}+c)+(\overline{a}+a)\overline{b}c&\overline{a}+a,\overline{c}+c\text{ are true}\\&=&ab\overline{c}+\overline{a}\overline{b}\overline{c}+\overline{a}\overline{b}c+\overline{a}\overline{b}c+a\overline{b}c&\text{distributivity}\\&=&\overline{a}\overline{b}\overline{c}+\overline{a}\overline{b}c+a\overline{b}c+ab\overline{c}&\text{remove duplicates, commutativity}\end{array}$$

Phew! We've successfully transformed $f_\text{Question}$ and $f_\text{Answer}$ into their (common) disjunctive normal form, which means that we can now transform $f_\text{Question}$ into $f_\text{Answer}$ by first following the first transformation until reaching the disjunctive normal form, and then following the second transformation in reverse.

Of course, in the answer above, I mostly just applied the definition of $\oplus$ and well-known rules for $+$ and $\cdot$ (idempotency, commutativity, associativity, absorption, de Morgan's laws). Someone could come up with a longer or shorter proof. (In particular, a negation of a disjunctive normal form is a conjunctive normal form and it takes quite a bit of work to convert it back to a disjunctive normal form. We were lucky to have two negations above!) However, the idea is the same:

• Either two expressions have the same truth table, in which case they have the same disjunctive normal form, and you can convert both to it - and therefore to each other,
• Or they don't have the same truth table, and obviously, being not equivalent, they cannot be converted to each other.

See also: How to convert formula to disjunctive normal form?