Reducing a boolean expression to XOR gates.

757 Views Asked by At

Is there any method or recommendation to reduce a boolean AND, OR expression to a XOR expression? For example I can reduce the following expression like this: $$\bar{A} \bar{C}+\bar{A}B+BC = \overline{(A \oplus C)(B \oplus C)}$$

Requires moderate work to reach this result so I'd like to know if there's any algorithm or shortcut to solve it. The idea is to get a minimum number of logic gates.

Thank you.

1

There are 1 best solutions below

0
On

$((\lnot A\land\lnot C)\lor(\lnot A\land B)\lor(B\land C)\equiv\lnot((A\not\equiv C)\land(B\not\equiv C)))$

$\begin{array}{l|l|l} D:\lnot A&H:F\lor G&L:B\not\equiv C\\ E:\lnot C&I:B\land C&M:K\land L\\ F:D\land E&J:H\lor I&N:\lnot M\\ G:D\land B&K:A\not\equiv C&X:J\equiv N \end{array}$

$\begin{array}{c|c|c} \mathtt{ABC}&\mathtt{DEFGHIJKLMN}&\mathtt{X}\\ \hline \mathtt{000}&\mathtt{11101010001}&\mathtt{1}\\ \mathtt{001}&\mathtt{10000001110}&\mathtt{1}\\ \mathtt{010}&\mathtt{11111010101}&\mathtt{1}\\ \mathtt{011}&\mathtt{10011111001}&\mathtt{1}\\ \mathtt{100}&\mathtt{01000001001}&\mathtt{0}\\ \mathtt{101}&\mathtt{00000000101}&\mathtt{0}\\ \mathtt{110}&\mathtt{01000001110}&\mathtt{1}\\ \mathtt{111}&\mathtt{00000110001}&\mathtt{1} \end{array}$

Your equivalence does not hold when A is true and B is false.