Boolean function: Difference between revisions

Revision as of 04:38, 13 March 2006

Revision as of 04:44, 13 March 2006

Line 1:

In [[mathematics]], a '''finitary boolean function''' is a [[function (mathematics)|function]] of the form f : '''B'''^''k'' → '''B''', where '''B''' = {0, 1} is a ''[[boolean ___domain]]'' and where ''k'' is a nonnegative integer. In the case where ''k'' = 0, the "function" is simply a constant element of '''B'''.

More generally, a function of the form ''f'' : ''X'' → '''B''', where ''X'' is an arbitrary set, is a ''[[boolean-valued function]]''. If ''X'' = '''M''' = {1, 2, 3, …}, then ''f'' is a ''binary sequence'', that is, an [[infinite [[sequence]] of 0's and 1's. If ''X'' = [''k''] = {1, 2, 3, …, ''k''}, then ''f'' is ''binary sequence'' of length ''k''.

There are <math>2^{2^n}</math> such functions. These play a basic role in questions of [[complexity theory]] as well as the design of circuits and chips for [[digital computer]]s. The properties of boolean functions play a critical role in [[cryptography]], particularly in the design of [[symmetric key algorithm]]s (see [[S-box]]).