Boolean function: Difference between revisions

Revision as of 22:19, 23 November 2004

Revision as of 22:21, 23 November 2004

Line 5:

of a number ''n'' of '''Boolean variables''' ''b''_i from the two-element [[Boolean algebra]] {0,1}, and such that ''F'' also takes values in {0, 1}. A function on a general [[___domain (mathematics)|___domain of a function]] taking values in {0, 1} would be called a '''''Boolean-valued function''''', so that Boolean functions are a special case. Such a function with ___domain {1, 2, 3, ... } is commonly called a '''binary sequence''', i.e. an [[infinite sequence]] of 0's and 1's; by restricting to { 1, 2, 3, ..., ''n'' } a Boolean function is in a natural way coded by a sequence of length ''n''.

There are 2^{2^''n''} 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]]).

==See also==