3

So the question I have asks to implement the circuit with $XOR$ gates.

So I am 3/4 through the problem when I am having problems simplifying the Boolean expressions below:

$$A'B'C + A'BC' + ABC + AB'C'$$

According to the professor this can be simplified to $A \,\,XOR \,\,B\,\, XOR \,\,C$.

The next one: $$A'B'C'D + A'B'CD' + A'BC'D' + A'BCD + ABC'D + ABCD' + AB'C'D' + AB'CD $$

Can be simplified to: $A\,\,XOR \,\,B \,\,XOR\,\,C \,\,XOR\,\,D $. Again I have no idea how to simplify it to that.

I have not the slightest clue how to even get to that. I have tried many MANY methods I must be looking at this the wrong way. Can anyone help?

George Nehme
  • 31
  • What is your definition of XOR? If you agree that $A,,XOR,,B$ equals $AB'+A'B$ and if you know that $A,,XOR,,B,,XOR,C$ is independent of the parentheses (order of operations), then you should be able to generalize this.. – Peter Franek Nov 08 '14 at 20:58
  • I thought this was the way to go:

    = A'(B'C + BC') + A(BC + B'C')

    = A'(B XOR C) + A(BC + (B + C)')

    Which is where I ended up getting stuck.

     – George Nehme Nov 08 '14 at 21:00

3 Answers3

5

$$A′B′C+A′BC′+ABC+AB′C′$$ $$=A^{'}(B^{'}C + BC^{'}) + A(BC + B^{'}C^{'})$$

Now

$X \oplus Y = XY^{'} + X^{'}Y$

$(X \oplus Y)^{'}= XY + X^{'}Y^{'}$

Thus

$$=A^{'}(B \oplus C) + A(B \oplus C)^{'}$$ $$=A \oplus B \oplus C$$

Note that $(\oplus)^{'}$ is the logical expression XNOR

Kevin Zakka
  • 1,544
1

This is very easy! If exclusive or is $A\oplus B=\bar AB+A\bar B,~$ then coincidence is $A\odot B$

$=AB+\bar A\bar B.~$ At the same time, the two operations are obviously opposite to one

another; i.e., if A is the same as B, then they coincide, and their XOR yields false;

and vice-versa. In other words, $A\odot B=\overline{A\oplus B}.~$ Now, factoring as you already

have, $~\bar A\Big(B\oplus C\Big)+A\Big(B\odot C\Big)=\bar A\Big(B\oplus C\Big)+A\cdot\overline{B\oplus C}=A\oplus\Big(B\oplus C\Big)=$

$=A\oplus B\oplus C$.

Lucian
  • 48,334
  • 2
  • 83
  • 154
0

Let's denote $\bf{XOR}$ by $\oplus$ as usual. It is in fact addition $\pmod 2$.

You can ask the question: what is the Disjunctive Normal Form of the Boolean function $(A,B,C)\mapsto A \oplus B \oplus C$. We can look at the table of values of the function

$$ \begin{array}{c|c|c|c} A & B & C & A\oplus B\oplus C \\ \hline 0 & 0 & 0 & 0 \\\hline 0 & 0 & 1 & 1 \\\hline 0 & 1 & 0 & 1 \\\hline 0 & 1 & 1 & 0 \\\hline 1 & 0 & 0 & 1 \\\hline 1 & 0 & 1 & 0 \\\hline 1 & 1 & 0 & 0 \\\hline 1 & 1 & 1 & 1 \\\hline \end{array} $$

Now we can build the Disjunctive Normal Form of the function $A\oplus B \oplus C$. Focus on the values $(A,B,C)$ where the functions takes value $1$. For each such value, say $(0,1,0)$, consider the conjunction $A'B C'$. Now take the disjunction ($+$) of all of these conjunctions. You get your formula.

In general, $A_1 \oplus A_2 \oplus \cdots A_n$ takes value $1$ if and only if an odd number of $A_i$ take value $1$. Therefore its disjunctive normal form is

$$\sum_{\epsilon \in \{ \ , '\}^n} \prod_{i=1}^n A_i^{\epsilon_i} $$ where the sum is over all those $\epsilon$ with an odd number of $\epsilon_i = \ $ ( the empty symbol) ( that is, for an odd number of $A_i$ we considered the variable $A_i$ and not its complement $A_i'$).

orangeskid
  • 53,909