Boolean function
From Textop Wiki
| The article below may contain errors of fact, bias, grammar, etc. The Citizendium Foundation and the participants in the Citizendium project make no representations about the reliability of this article or, generally, its suitability for any purpose. We make this disclaimer of all Citizendium article versions that have not been specifically approved. |
In mathematics, a finitary boolean function is a function of the form f : Bk → 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^k}</math> such functions. These play a basic role in questions of complexity theory as well as the design of circuits and chips for digital computers. The properties of boolean functions play a critical role in cryptography, particularly in the design of symmetric key algorithms (see S-box).
A boolean mask operation on boolean-valued functions combines values point-wise (for example, by XOR, or other boolean operators).
Algebraic Normal Form
A boolean function can be written uniquely as a sum (XOR) of products (AND). This is known as the Algebraic Normal Form (ANF).
| <math>f(x_1, x_2, \ldots , x_n) = \!</math> | <math>a_0 + \!</math> |
| <math>a_1x_1 + a_2x_2 + \ldots + a_nx_n + \!</math> | |
| <math>a_{1,2}x_1x_2 + a_{n-1,n}x_{n-1}x_n + \!</math> | |
| <math>\ldots + \!</math> | |
| <math>a_{1,2,\ldots,n}x_1x_2\ldots x_n \!</math> |
The values of the sequence <math>a_0,a_1,\ldots,a_{1,2,\ldots,n}</math> can therefore also uniquely represent a boolean function. The algebraic degree of a boolean function is defined as the highest number of <math>x_i</math> that appear in a product term. Thus <math>f(x_1,x_2,x_3) = x_1 + x_3</math> has degree 1 (linear), whereas <math>f(x_1,x_2,x_3) = x_1 + x_1x_2x_3</math> has degree 3 (cubic).
See also
Template:Col-begin Template:Col-break
External links
- Boolean Planet — boolean functions in cryptography.
- Portions of the above article are adapted from an earlier version of the Wikinfo article, "Boolean function", used under the GNU Free Documentation License.
- Portions of the above article are adapted from an earlier version of the Wikipedia article, "Boolean function", used under the GNU Free Documentation License.
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section titled GNU FDL text.
