Boolean function: Difference between revisions

Revision as of 21:42, 12 March 2006

Revision as of 04:38, 13 March 2006

Line 1:

In [[mathematics]], a '''finitary boolean function''' is usually 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''.

:''F''(''b''₁, ''b''₂, ..., ''b''_n)

There are <math>2^{2^n}</math> such functions;. these 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]]).

of a number ''n'' of ''boolean variables'' ''b''_i from the two-element [[boolean algebra]] '''B''' = {0,&nbsp;1}, such that ''F'' also takes values in '''B'''. A function on an arbitrary set ''X'' taking values in '''B''' is called a ''[[boolean-valued function]]'', so that boolean functions are a special case. Such a function with ___domain {1,&nbsp;2,&nbsp;3,&nbsp;…} is commonly called a ''binary sequence'', that is, an [[infinite sequence]] of 0's and 1's. By restricting to {1,&nbsp;2,&nbsp;3,&nbsp;…,&nbsp;''k'' } a boolean function is in a natural way coded by a 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]]).

A '''boolean operation''' on boolean-valued functions combines values point-wise (for example, by [[Exclusive or|XOR]], or other [[boolean operator]]s).