Difference between revisions of "Boolean function"

Revision as of 09:28, 21 April 2016

In mathematics and logic, a Boolean function is a mathematicalfunction which describes how to determine a Boolean value output based on some logical calculation from Boolean inputs.

Description

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 function 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.

Applications

Boolean functions play a basic role in:

• Complexity theory
• Design of circuits and chips for digital computers
• Cryptography, particularly in the design of symmetric key algorithms (see substitution box)

Representation

Boolean functions are often represented by sentences in propositional logic, and sometimes as multivariate polynomials over GF(2).

More efficient representations includee:

• binary decision diagrams (BDD)
• negation normal forms
• propositional directed acyclic graphs (PDAG)

Cooperative game theory

In cooperative game theory, monotone Boolean functions are called simple games (voting games)

This notion is applied to solve problems in social choice theory.

Not to be confused with

• Binary function

See also

• Complexity theory
• Cryptography
• Digital computer
• Function (mathematics)
• Logic
• Mathematical logic
• Mathematics
• Propositional logic

External links

• Boolean function @ Wikipedia