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
