[Solved]: Odd Parity Function

Problem Detail: 

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?

Asked By : ojhawkins

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24025