I am trying to define a Odd Parity Function that takes three 1 bit inputs and will output a 1 if the 3 bits are odd as a Boolean function.

1 1 0 = 0
1 0 0 = 1
0 0 0 = 0
1 1 1 = 1

I understand this has a relationship to XOR as I can define this with 2 parameter as

X xor Y = (XY')+(X'Y)

My assumption is the function will look like this

(X xor Y) xor Z = (((XY')+(X'Y))Z')+(((XY')+(X'Y))'Z)

Can this function be simplifed?

  • 1
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$ – David Richerby Apr 22 '14 at 12:50
  • 1
    $\begingroup$ @DavidRicherby We could still provide a proof that it is the simplest or provide a simpler solution. It might be interesting to consider other notions of simplicity, then reference relevant materials to such. It isn't explicitly asked for, but it still might be useful both to OP and others. $\endgroup$ – mdxn Apr 22 '14 at 16:48
  • $\begingroup$ If you want to determine whether this is minimal, I suggest that you do a brute-force enumeration of all such functions (the number is small enough that exhaustive enumeration is feasible). I encourage you to give it a try yourself. $\endgroup$ – D.W. Apr 22 '14 at 19:23
  • $\begingroup$ Yes aplogies if the question looked like a footnote but I was wanting to find the minimal form. @D.W. is there a method to enumerate possible solutions or is it just a matter of trail and error given the simlicity of the problem? $\endgroup$ – ojhawkins Apr 23 '14 at 0:25
  • $\begingroup$ ojhawkins, What is your definition of minimal? What metric are you trying to minimize? What counts as a function? Is it a truth table, or an expression in boolean algebra with only certain boolean operators (AND and OR) allowed? Please edit the question to give a clear specification of that. Once we know over what space you are trying to enumerate, we can give you suggestions how to enumerate all elements of that space. $\endgroup$ – D.W. Apr 23 '14 at 0:27

Your question is addressed (for the parity of $n$ bits) by Troy Lee, who shows in his paper The formula size of PARITY that the (optimal) formula size (number of literals) of parity on $n = 2^\ell + k$ bits (where $0 \leq k < 2^\ell$) is $2^\ell (2^\ell + 3k)$. In your particular case, $\ell = k = 1$ and so the formula size is $10$, matching your formula, and showing that it is tight under this complexity measure.

| cite | improve this answer | |

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