Ed's Big Plans

Computing for Science and Awesome

Searching for a Continuous Bit Parity function

with 2 comments

Update: The function being sought is better described as “continuous bit-parity” rather than “Fuzzy XOR”, the title of the post has been changed from Fuzzy Exclusive OR (XOR)” to reflect that.

About two weeks ago, I was working on a project wherein I needed to define a continuous XOR function. The only stipulations are that (1) the function must either be binary and commutative, or it must be variadic; and (2) the function must be continuous.

In my first attempt, I used the classic arrangement of four binary NAND gates to make an XOR where each NAND gate was replaced with the expression { λ: p, q → 1.0 – pq }. The algebraic product T-norm { λ: p, q → pq } is used instead of the standard fuzzy T-norm { λ: p, q → min(p, q) } in order to keep it continuous. Unfortunately, this attempt does not preserve commutativity, so the search continued.

At this point, Dr. Kremer suggested I consider a shifted sine curve. I eventually chose the equation
{ λ: p[1..n] → 0.5 – 0.5cos(π Σi=1npi) }.
This is shown graphically in the below figure …

Variadic Fuzzy XOR -- 0.5 - 0.5 cos( pi sum p over i )

# gnuplot source ...
set xrange[-2*pi:2*pi]
set output "a.eps"
set terminal postscript eps size 2.0, 1.5
plot 0.5 - 0.5 * cos(pi * x)

This can be considered a variadic function because it takes the sum of all fuzzy bits pi in a given string and treats the arguments the same no matter the number of bits n.

Whenever the sum of all bits is equal to an even number, the function returns a zero — whenever the sum is an odd number, the function returns a one. This function offers a continuous (although potentially meaningless) value between integer values of the domain and can handle bitstrings of any length.

If you’re aware of a purely binary Fuzzy XOR (instead of variadic) that is a legal extension of classic XOR, continuous, and commutative — please let me know for future reference 😀

Eddie Ma

June 1st, 2011 at 9:42 pm

Andre Masella says...

Ugh. You can’t do that because it won’t be an XOR any more and it won’t hold for the definitions of triangular norms. XOR is defined to be x·¬y+y·¬x. So, in fuzzy logic, it should be (xT(Cy))S(yT(Cx)) where T is the triangular norm and S is the matching conorm. If you’re using the Gödel T-norm (min), then that’s max(min(x, 1-y), min(y, 1-x)).

If your concern is commutativity, then well, it depends entirely on the norms you choose. In general, it doesn’t hold because there is no requirement that the norms work that way. This is obvious in the case of the Łukasiewicz t-norm. T-norms are not require to be distributive, so, you can’t generalise an XOR. In the case of the Gödel t-norm, it just so happens to be distributive, so you can make such an XOR. For three variables: x⊗y⊗z = x·¬(y⊗z)+¬x·(y⊗z) = x·¬(y·¬z+¬y·z)+¬x·(y·¬z+¬y·z) = x·(¬y+z)·(y+¬z)+¬x·(¬y+z)·(y+¬z) = (x·¬y+x·z)·(y+¬z)+(¬x·¬y+¬x·z)·(y+¬z) = x·¬y·y+x·z·y+¬z·x·¬y+¬z·x·z+¬x·¬y·y+¬x·z·y+¬x·¬y·¬z

Which is much uglier than the regular Boolean version because x·¬x is normally 0, but min(x, 1-x) is not necessarily 0.

Eddie Ma says...

Good idea — so in reality, if I just find a T-norm and S-norm that satisfies { pT(Cq))S(qT(Cp) } for the XOR table and all of those properties I need, then I’m set.

Alternatively, I may have misidentified the problem afterall — maybe I got hung up on Fuzzy Logic, and forgot the overarching goal — continuous bit parity for any number of values in [0, 1] — not necessarily fuzzy bits. Maybe the transformed sine curve is as good as I really needed for my purposes.

It’s been a while since I’ve thought about the project that this problem belonged to … hmm … I’ll leave this thought to run in the background since I don’t need it right away. I’ll let you know if I bump into a relevant function 😀