2
\$\begingroup\$

I want to simplify the following boolean function:

$$Z=A\bar B \bar{C_i} + \bar A B \bar{C_i} + \bar A\bar B {C_i} + A B {C_i}$$

Here's my attempt:

\begin{align} Z &= A\bar B \bar{C_i} + \bar A B \bar{C_i} + \bar A\bar B {C_i} + A B {C_i} \\ & = \bar{C_i}(A \bar B + \bar A B) + C_i(\bar A \bar B + AB) \\ & = \bar C_i(A \oplus B) + C_i(A \equiv B) \end{align}

I thought this was the end of it but in my textbook it continues and has: \begin{align} Z &= A\bar B \bar{C_i} + \bar A B \bar{C_i} + \bar A\bar B {C_i} + A B {C_i} \\ & = \bar{C_i}(A \bar B + \bar A B) + C_i(\bar A \bar B + AB) \\ & = \bar C_i(A \oplus B) + C_i(A \equiv B) \\ & = A \oplus B \oplus C_i \\ & = A \equiv B \equiv C_i \end{align}

I'm confused about what happened between the third and fourth step. What boolean algebra rules are being used here?

\$\endgroup\$
  • \$\begingroup\$ You need a double dollar sign for your title. \$\endgroup\$ – DKNguyen Sep 2 '20 at 19:34
  • 2
    \$\begingroup\$ $$A \equiv B$$ is the same as NOT $${(A \oplus B)}$$ (sorry not very good at formulas) \$\endgroup\$ – jcaron Sep 2 '20 at 21:05
  • 1
    \$\begingroup\$ @jcaron Yes but I'm trying to figure out why $$\bar C_i(A \oplus B) + C_i(A \equiv B)=A \oplus B \oplus C_i$$. \$\endgroup\$ – Ski Mask Sep 3 '20 at 12:02
  • 3
    \$\begingroup\$ By \$X\equiv Y \$, what do you mean exactly? I've never seen this notation so far. \$\endgroup\$ – edmz Sep 4 '20 at 19:10
  • 2
    \$\begingroup\$ Seems like $$A\equiv B$$ is the same as $$\overline{(A\oplus B)}$$. In that case, $$\begin{align} Z&=\overline{C_i} (A \oplus B) + C_i (A\equiv B)\\ &=\overline{C_i} (A \oplus B) + C_i\overline{(A \oplus B)} \\ &= C_i \oplus (A\oplus B)\\ &=A\oplus B\oplus C_i \end{align}$$ \$\endgroup\$ – cjferes Sep 4 '20 at 21:50
4
+50
\$\begingroup\$

When in doubt about booleans, just build a truth table.

Truth tables for XOR (\$\oplus\$):

   | 0 | 1
---+---+---
 0 | 0 | 1
---+---+---
 1 | 1 | 0

For "is equal to" (\$\equiv\$):

   | 0 | 1
---+---+---
 0 | 1 | 0
---+---+---
 1 | 0 | 1

As you can see \$A \equiv B\$ gives just the opposite result of \$A \oplus B\$ (the result is 1 for the first when it is 0 for the second, and vice-versa). This means that:

$$A \equiv B = \overline{A \oplus B}$$

You used several times the identity $$X\overline{Y} + \overline{X}Y = X \oplus Y$$

This means: If (X is true AND Y is false) OR (if X is false and Y is true) is the same as either X or Y is true, but not both, which is quite straightforward.

So now you get to this equation:

$$\overline{C_i}(A \oplus B) + C_i(A \equiv B) \\$$

Since \$A \equiv B\$ can be written as \$\overline{A \oplus B}\$, you can rewrite it to:

$$\overline{C_i}(A \oplus B) + C_i(\overline{A \oplus B}) \\$$

Which is a form of \$X\overline{Y} + \overline{X}Y\$, with \$X = C_i\$ and \$Y = A \oplus B\$.

So it can then be rewritten to:

$$C_i \oplus (A \oplus B)$$

As all these boolean operators are commutative, this be be rewritten as:

$$A \oplus B \oplus C_i$$

\$\endgroup\$
5
\$\begingroup\$

Observe that
\begin{align}\overline{\overline{A} \cdot\overline{B} + A\cdot B} = \overline{(\overline{A}\cdot\overline{B})}\cdot\overline{(A \cdot B)} = (A + B)\cdot(\overline{A}+\overline{B}) = A \cdot\overline{B} + \overline{A}\cdot B \end{align}

Hence

\begin{align} Z&=\overline{C_i} (A \oplus B) + C_i (A\equiv B)\\ &=\overline{C_i} (A \oplus B) + C_i\overline{(A \oplus B)} \\ &= C_i \oplus (A\oplus B)\\ &=A\oplus B\oplus C_i \end{align}

\$\endgroup\$
  • 1
    \$\begingroup\$ Ah I see. I made the mistake of taking $$A \equiv B = A \oplus B$$ and not $$\lnot{(A \oplus B)}$$ \$\endgroup\$ – Ski Mask Sep 7 '20 at 11:18
-1
\$\begingroup\$

First, plus is an unusual operator for bool equations Wikipedia. I assumed you referencing a OR

formula

With this assumtion I came to the result: no further reduction possible. For This I used a Karnaugh map

enter image description here

https://en.wikipedia.org/wiki/Karnaugh_map

\$\endgroup\$
  • 1
    \$\begingroup\$ Leibniz used + for inclusive OR and Boole used it too, so it's been around for over 300 years. Nowadays, it's more usual to use + for OR and ⊕ for XOR because it's far more readable. See discussion here. Plus, there's far more to reduction than Karnaugh Maps, e.g. De Morgan's Laws. Don't believe everything you read on Wikipedia. \$\endgroup\$ – tim Sep 7 '20 at 12:30
  • \$\begingroup\$ I only quote wikipedia if it states things I know to be correct an are also in my books... I work in electronics for 25 years now, and never saw a plus for OR from any professional... \$\endgroup\$ – schnedan Sep 7 '20 at 12:38
  • \$\begingroup\$ also as you can see in the formula als well as in the Karnaugh_map there are always 2 of 3 elements different in any case and there is no 2 Element term which can be reused without modification (like invert) in an other therm. So if there is a further reduction I like to learn how, but I don't see any \$\endgroup\$ – schnedan Sep 7 '20 at 12:47
  • \$\begingroup\$ Things like De Morgan's Laws, to my knowledge are good for 5 or more variables where Karnaugh_maps start to be of no use. But if you can apply a simple scheme like Karnaugh_map its a valid measure to do so. \$\endgroup\$ – schnedan Sep 7 '20 at 12:54
  • \$\begingroup\$ As you can see, a 4-input OR gate with 3 NOT gates had been reduced to a 3-input XOR gate. The + and ⊕ signs are standard teaching in schools, colleges and universities around the world. Are you trolling? \$\endgroup\$ – tim Sep 7 '20 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.