Evasive Boolean function: Difference between revisions

Revision as of 16:08, 24 May 2017

Revision as of 21:33, 14 November 2018

Line 11:

|<math>~f(x,y,z)~</math>

|<math>~=~</math>

|<math>~(x \andland y)~</math>

|<math>~\orlor~</math>

|<math>~(\neg x \andland z)~</math>

|-

|[[File:Venn 0001 1011.svg|50px]]

|<math>~=~</math>

|[[File:Venn 0001 0001.svg|50px]]

|<math>~\orlor~</math>

|[[File:Venn 0000 1010.svg|50px]]

|}

(where <math>\andland</math> is the bitwise "and", <math>\orlor</math> is the bitwise "or", and <math>\neg </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.

:( &nbsp;&nbsp;&nbsp;&nbsp;<math>(\neg x = \text{false}) ~~\Rightarrow~~ ((\neg x \andland z) = \text{false})</math>&nbsp;&nbsp;&nbsp;&nbsp; )

If ''x'' is false, the algorithm checks the value of ''z'' and returns it.