1

I have this expression (which represents $C_{out}$ of a full adder):

$$a \neg b \neg c + \neg a b \neg c + \neg a \neg b c + abc$$

which is generated by some program I wrote that converts a truth table into a list of expressions that represent each of the outputs. Ultimately, I have another program that takes these expressions and turns them into logical circuits.

Since the expressions are not simplified or reduced, the resulting circuits are often extremely inefficient. I'd thought I'd sit down and try to figure out the math myself first, and here's how I would reduce this expression, starting with factoring $a$ out:

$a(\neg b\neg c+bc) + \neg a b \neg c + \neg a \neg b c$

Then $\neg a$:

$a(\neg b\neg c+bc) + \neg a (b \neg c + \neg b c)$

I recognize that the terms inside parentheses are XNOR and XOR operations:

$a (b \odot c) + \neg a(b \oplus c)$

but now I don't really know the steps between the above expression and this one (which is the simplest form):

$a \oplus b \oplus c$

What am I missing? How would you get to the two XOR's from here?

mochaccino
  • 135
  • 6
  • Hi vera, you may find Karnaugh maps a worthwhile topic. They are very good human ways to find efficient AND, OR, and NOT gates. Wikipedia: https://en.wikipedia.org/wiki/Karnaugh_map – Matt Groff Dec 18 '22 at 22:48
  • Thanks, but I'm only working this out myself to figure out how a computer could do it. Currently, it simply does a BFS and returns the steps it took to reach the "most simplified" version of the original expression. I don't think Karnaugh maps work as well for computers :p – mochaccino Dec 15 '23 at 21:56
  • Unfortunately, it is thought that computers will have a hard time with this. But I will give you some encouraging words below. You may want to consider the Boolean Satisfiability Problem. If you have a general formula, computer scientists often transform this formula into a "3-SAT" formula with $3 n$ symbols, and it often seems to take $2^{c n}$ time just to tell if the formula can be true or if it must always be false. However, like calculus, there are certain types of formulas, such a XOR-SAT, that are easy to work with. – Matt Groff Jan 04 '24 at 21:29
  • By the way, can you tell us what type of "goal" you're looking for? Like I said, if you're just trying to see if the formula can ever be true, or if it is ever false, your best best is to study the Boolean Satisfiability Problem. But if you actually need the formula, this is more complicated. You may also be able to use math software to do the work for you, without having to rewrite what someone has already done. I forgot to mention that XOR-SAT can be solved to give you exactly how many inputs are true in $O(n)$ time. – Matt Groff Jan 04 '24 at 21:37
  • @MattGroff Thanks, I had already looked into SAT solvers but wanted to try something different. I needed to reduce expressions into a simplified form to produce more efficient "circuits". I'm not actively working on the project, but I'll look into what you said. – mochaccino Jan 05 '24 at 07:55

1 Answers1

1

In general, $x \oplus y = x\neg y + \neg x y$

Now, you already recognized that:

$$a \neg b \neg c + \neg a b \neg c + \neg a \neg b c + abc = a (b \odot c) + \neg a(b \oplus c)$$

where $b \odot c$ is the XNOR ... i.e. $b \odot c = \neg (b \oplus c)$

So just use that:

$$a (b \odot c) + \neg a(b \oplus c) = a \neg(b \oplus c) + \neg a(b \oplus c) = a \oplus (b \oplus c)$$

And you can drop the parentheses, since the XOR is associative.

Note that it is easy to see that the output bit of a full adder is the XOR on the three inputs: the XOR is a $1$ iff an odd number of its arguments are a $1$ ... and that's exactly what we want for the output bit.

Bram28
  • 100,612
  • 6
  • 70
  • 118