In mathematics, a finitary boolean function is a 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. Euclid, detail from The School of Athens by Raphael. ... Partial plot of a function f. ... A boolean domain B is a generic 2-element set, say, B = {0, 1}, whose elements are interpreted as logical values, typically 0 = false and 1 = true. ...

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. A boolean-valued function is a function of the type , where is an arbitrary set, where is a generic 2-element set, typically , and where the latter is frequently interpreted for logical applications as . ... In mathematics, a sequence is a list of objects (or events) arranged in a linear fashion, such that the order of the members is well defined and significant. ...

There are 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). Complexity theory can refer to more than one thing: Computational complexity theory: a field in theoretical computer science and mathematics dealing with the resources required during computation to solve a given problem Systems theory (or systemics or general systems theory): an interdisciplinary field including engineering, biology and philosophy that incorporates... ... The German Lorenz cipher machine Cryptography or cryptology is a field of mathematics and computer science concerned with information security and related issues, particularly encryption and authentication. ... Symmetric-key algorithms are a class of algorithms for cryptography that use trivially related cryptographic keys for both decryption and encryption. ... In cryptography, a substitution box (or S-box) is a basic component of symmetric key algorithms. ...

A boolean mask operation on boolean-valued functions combines values point-wise (for example, by XOR, or other boolean operators). Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ... In logical calculus, logical operators or logical connectors serve to connect statements into more complicated compound statements. ...

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). Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ... AND Logic Gate In mathematics, logical conjunction (usual symbol and) is a logical operator that results in false if either of the operands is false. ... In Boolean logic, Algebraic Normal Form (ANF) is a method of standardizing and normalizing logical formulas. ...

The values of the sequence can therefore also uniquely represent a boolean function. The algebraic degree of a boolean function is defined as the highest number of x_i that appear in a product term. Thus f(x₁,x₂,x₃) = x₁ + x₃ has degree 1 (linear), whereas f(x₁,x₂,x₃) = x₁ + x₁x₂x₃ has degree 3 (cubic).

See also

The algebra of sets develops and describes the basic properties and laws of sets, the set-theoretic operations of union, intersection, and complementation and the relations of set equality (mathematics) and set inclusion. ... Wikibooks has more about Boolean logic, under the somewhat misleading title Boolean Algebra For a basic intro to sets, Boolean operations, Venn diagrams, truth tables, and Boolean applications, see Boolean logic. ... A boolean domain B is a generic 2-element set, say, B = {0, 1}, whose elements are interpreted as logical values, typically 0 = false and 1 = true. ... Boolean logic is a system of syllogistic logic invented by 19th-century British mathematician George Boole, which attempts to incorporate the empty set, that is, a class of non-existent entities, such as round squares, without resorting to uncertain truth values. ... In mathematics, a Boolean function is usually a function F(b1, b2, ... , bn) of a number n of Boolean variables bi from the two-element Boolean algebra {0,1}, and such that F also takes values in {0, 1}. A function on a general domain of a function taking values... A boolean-valued function is a function of the type , where is an arbitrary set, where is a generic 2-element set, typically , and where the latter is frequently interpreted for logical applications as . ... Algebra of sets George Boole Boolean algebra Boolean function Boolean logic Boolean homomorphism Boolean Implicant Boolean prime ideal theorem Boolean-valued model Boolean satisfiability problem Booles syllogistic canonical form (Boolean algebra) compactness theorem Complete Boolean algebra connective -- see logical operator de Morgans laws Augustus De Morgan duality (order... In formal logic, logical connectives, also known as logical connectors and sometimes logical constants, serve to connect statements into more complicated compound statements. ... In logic a truth function is a connective for which the truth value is determined systematically by the values of the statements it connects. ... Zeroth-order logic is a term in popular use among practitioners for the subject matter otherwise known as boolean functions, monadic predicate logic, propositional calculus, or sentential calculus. ...

External links

• Boolean Planet — boolean functions in cryptography.