Boolean function
Encyclopedia
In mathematics
, a (finitary
) Boolean function (or switching function) is a function
of the form ƒ : Bk → B, where B = {0, 1} is a Boolean domain
and k is a non-negative integer called the arity
of the function. In the case where k = 0, the "function" is essentially a constant element of B.
Every k-ary Boolean formula can be expressed as a propositional formula
in k variables x1, …, xk, and two propositional formulas are logically equivalent
if and only if they express the same Boolean function. There are 22k k-ary functions for every k.
value output based on some logical
calculation from Boolean inputs. Such functions 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 substitution box
).
Boolean functions are often represented by sentences in propositional logic, and sometimes as multivariate polynomial
s over GF
(2), but more efficient representations are binary decision diagram
s (BDD), negation normal forms, and propositional directed acyclic graph
s (PDAG).
In cooperative game
theory, Boolean functions are called simple games (voting games); this notion is applied to solve problems in social choice theory
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a (finitary
Finitary
In mathematics or logic, a finitary operation is one, like those of arithmetic, that takes a finite number of input values to produce an output. An operation such as taking an integral of a function, in calculus, is defined in such a way as to depend on all the values of the function , and is so...
) Boolean function (or switching function) is a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
of the form ƒ : Bk → B, where B = {0, 1} is a Boolean domain
Boolean domain
In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include false and true...
and k is a non-negative integer called the arity
Arity
In logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...
of the function. In the case where k = 0, the "function" is essentially a constant element of B.
Every k-ary Boolean formula can be expressed as a propositional formula
Propositional formula
In propositional logic, a propositional formula is a type of syntactic formula which is well formed and has a truth value. If the values of all variables in a propositional formula are given, it determines a unique truth value...
in k variables x1, …, xk, and two propositional formulas are logically equivalent
Logical equivalence
In logic, statements p and q are logically equivalent if they have the same logical content.Syntactically, p and q are equivalent if each can be proved from the other...
if and only if they express the same Boolean function. There are 22k k-ary functions for every k.
Boolean functions in applications
A Boolean function describes how to determine a BooleanBoolean datatype
In computer science, the Boolean or logical data type is a data type, having two values , intended to represent the truth values of logic and Boolean algebra...
value output based on some logical
Boolean logic
Boolean algebra is a logical calculus of truth values, developed by George Boole in the 1840s. It resembles the algebra of real numbers, but with the numeric operations of multiplication xy, addition x + y, and negation −x replaced by the respective logical operations of...
calculation from Boolean inputs. Such functions play a basic role in questions of complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
as well as the design of circuits and chips for digital computers. The properties of Boolean functions play a critical role in cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, particularly in the design of symmetric key algorithms (see substitution box
Substitution box
In cryptography, an S-Box is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext — Shannon's property of confusion...
).
Boolean functions are often represented by sentences in propositional logic, and sometimes as multivariate polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
s over GF
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
(2), but more efficient representations are binary decision diagram
Binary decision diagram
In the field of computer science, a binary decision diagram or branching program, like a negation normal form or a propositional directed acyclic graph , is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed...
s (BDD), negation normal forms, and propositional directed acyclic graph
Propositional directed acyclic graph
A propositional directed acyclic graph is a data structure that is used to represent a Boolean function. A Boolean function can be represented as a rooted, directed acyclic graph of the following form:...
s (PDAG).
In cooperative game
Cooperative game
In game theory, a cooperative game is a game where groups of players may enforce cooperative behaviour, hence the game is a competition between coalitions of players, rather than between individual players...
theory, Boolean functions are called simple games (voting games); this notion is applied to solve problems in social choice theory
Social choice theory
Social choice theory is a theoretical framework for measuring individual interests, values, or welfares as an aggregate towards collective decision. A non-theoretical example of a collective decision is passing a set of laws under a constitution. Social choice theory dates from Condorcet's...
.
See also
- Algebra of setsAlgebra of setsThe 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 and set inclusion...
- Boolean algebra (logic)
- Boolean algebra topics
- Boolean domainBoolean domainIn mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include false and true...
- Boolean logicBoolean logicBoolean algebra is a logical calculus of truth values, developed by George Boole in the 1840s. It resembles the algebra of real numbers, but with the numeric operations of multiplication xy, addition x + y, and negation −x replaced by the respective logical operations of...
- Boolean-valued functionBoolean-valued functionA boolean-valued function, in some usages is a predicate or a proposition, is a function of the type f : X → B, where X is an arbitrary set and where B is a boolean domain....
- Logical connectiveLogical connectiveIn logic, a logical connective is a symbol or word used to connect two or more sentences in a grammatically valid way, such that the compound sentence produced has a truth value dependent on the respective truth values of the original sentences.Each logical connective can be expressed as a...
- Truth function
- Truth tableTruth tableA truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
- Symmetric Boolean functionSymmetric Boolean functionIn mathematics, a symmetric Boolean function is a Boolean function whose value does not depend on the permutation of its input bits, i.e., it depends only on the number of ones in the input....
- Decision tree modelDecision tree modelIn computational complexity and communication complexity theories the decision tree model is the model of computation or communication in which an algorithm or communication process is considered to be basically a decision tree, i.e., a sequence of branching operations based on comparisons of some...
- Evasive Boolean functionEvasive Boolean functionIn mathematics, an evasive Boolean function ƒ is a Boolean function for which every decision tree algorithm has running time of exactly n...
- Indicator function
- 3-ary Boolean functions