0
\$\begingroup\$

If we have an OR function with two terms, like $$a \vee b$$ it can be written with only XOR like $$a \oplus b \oplus ab$$

RULE: $$a \vee b = a \oplus b \oplus ab$$

But what if we have three terms, like $$a \vee b \vee c$$ How can that be written with only XOR?

What is the equivalent of the RULE above for three terms?

What about four or more terms?

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

You can just add more terms the same. Starting with: $$ a \vee b = a \oplus b \oplus a{\cdot}b $$ Which has a truth table of: $$ \begin{matrix} a & b & & Q \\ \hline 0 & 0 & & 0 \\ 1 & 0 & & 1 \\ 0 & 1 & & 1 \\ 1 & 1 & & 1 \\ \end{matrix} $$ When you add c to it the truth table ends up as: $$ \begin{matrix} a & b & c & & Q \\ \hline 0 & 0 & 0 && 0\\ 1 & 0 & 0 && 1\\ 0 & 1 & 0 && 1\\ 1 & 1 & 0 && 1\\ 0 & 0 & 1 && 1\\ 1 & 0 & 1 && 1\\ 0 & 1 & 1 && 1\\ 1 & 1 & 1 && 1\\ \end{matrix} $$ Taking the entries where Q is 1 yields 7 terms. Taking just the values that are 1 the permutations equate to a, b, c, ab, ac, bc and finally abc. XOR them all together and you end up with: $$ a \vee b \vee c = a \oplus b \oplus c \oplus a{\cdot}b \oplus a{\cdot}c \oplus b{\cdot}c \oplus a{\cdot}b{\cdot}c $$ "or" is "any combination of...", so it can exclusively be one of all possible combinations or permutations.

The more terms you add the more complex and long winded the expression gets.

For OR made from XOR the number of valid permutations will always be \$2^n-1\$ where \$n\$ is the number of input values.

\$\endgroup\$
5
  • \$\begingroup\$ Great answer to my question. I see the expression gets complicated very fast if the number of terms increase. I wonder, if one has an expression like B'C'D' ∨ A'B' ∨ A'D' ∨ A'B' and is supposed to write it in XOR form, how would one go about it an easier way? \$\endgroup\$
    – Data
    Jan 2, 2015 at 15:24
  • \$\begingroup\$ You have 4 terms there: a = x′2x′3x′4, b = x′1x′3, c = x′1x′4 and d = x′1x′2. So you have 15 terms as combinations of a/b/c/d. a v b v c v d v ab v ac v ad ... abcd. Then replace a b c and d with x'2x'3x'4 etc. \$\endgroup\$
    – Majenko
    Jan 2, 2015 at 15:30
  • \$\begingroup\$ Sorry I edited my post a bit to make it easier to read. I wonder since the above method creates very complicated expressions, is there another way to do this easier? \$\endgroup\$
    – Data
    Jan 2, 2015 at 15:31
  • \$\begingroup\$ The expression is what it needs to be to satisfy the requirements. There may be simplifications after creation, but OR to XOR always results in increased complexity. \$\endgroup\$
    – Majenko
    Jan 2, 2015 at 15:35
  • \$\begingroup\$ But is there any way to make the calculations easier? Maybe using another method? \$\endgroup\$
    – Data
    Jan 2, 2015 at 19:41
5
\$\begingroup\$

The OR operation is associative:

$$ (a \vee b) \vee c $$

Apply your rule to \$(a \vee b)\$:

$$ (a \oplus b \oplus ab) \vee c $$

We can then apply your rule again, but one of the terms is the expression \$ (a \oplus b \oplus ab) \$:

$$ (a \oplus b \oplus ab) \oplus c \oplus (a \oplus b \oplus ab)c $$

Now it's just a matter of simplification. AND distributes over XOR, so we can distribute the \$c\$ in the final \$ (a \oplus b \oplus ab)c \$ and get:

$$ (a \oplus b \oplus ab) \oplus c \oplus (ac \oplus bc \oplus abc) $$

Because XOR is also associative we can drop all the parenthesis and reorder however we want:

$$ a \vee b = a \oplus b \oplus c \oplus ab \oplus ac \oplus bc \oplus abc$$

As Majenko's answer explains, this is every possible combination of one or more of the terms. This pattern extends to as many terms as you want, although it gets very long, very fast. If we want to tack on a \$\vee d\$, then following the same steps, we get:

$$ (a \oplus b \oplus c \oplus ab \oplus ac \oplus bc \oplus abc) \vee d \\ (a \oplus b \oplus c \oplus ab \oplus ac \oplus bc \oplus abc) \oplus d \oplus (a \oplus b \oplus c \oplus ab \oplus ac \oplus bc \oplus abc)d \\ (a \oplus b \oplus c \oplus ab \oplus ac \oplus bc \oplus abc) \oplus d \oplus (ad \oplus bd \oplus cd \oplus abd \oplus acd \oplus bcd \oplus abcd) \\ a \oplus b \oplus c \oplus d \oplus ab \oplus ac \oplus ad \oplus bc \oplus bd \oplus cd \oplus abc \oplus abd \oplus acd \oplus bcd \oplus abcd $$

You can keep doing this, but at some point you won't be able to cross your eyes far enough.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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