Evasive Boolean function: Difference between revisions

Revision as of 19:37, 4 February 2010

Revision as of 05:25, 1 July 2010

Line 3:

== Examples ==

=== An example for a non-evasive boolean function ===

The following is a Boolean function on the three variblesvariables ''x'', ''y'', ''z'':

: <math>f(x,y,z) = (x \wedge y) \vee (\urcorner x \wedge z) \, </math>

(where <math> \wedge</math> is the bitwise "and", <math>\vee</math> is the bitwise "or", and <math>\urcorner </math> is the bitwise "not").

This function is not evasive, because there is a decision tree that solves it by checking exactly two variables: The algorithm first checks the value of&nbsp;''x''. If ''x'' is true, the algorithm checks the value of ''y'' and returns it.