Boolean function: Difference between revisions
m fixed reference |
corrected number of k-ary Boolean functions |
||
| Line 3: | Line 3: | ||
In [[mathematics]], a '''([[finitary]]) Boolean function''' (or switching function) is a [[function (mathematics)|function]] of the form ''ƒ'' : '''B'''<sup>''k''</sup> → '''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'''. |
In [[mathematics]], a '''([[finitary]]) Boolean function''' (or switching function) is a [[function (mathematics)|function]] of the form ''ƒ'' : '''B'''<sup>''k''</sup> → '''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 ''x''<sub>1</sub>, …, ''x''<sub>''k''</sub>, and two propositional formulas are [[logical equivalence|logically equivalent]] if and only if they express the same Boolean function. There are |
Every ''k''-ary Boolean function can be expressed as a [[propositional formula]] in ''k'' variables ''x''<sub>1</sub>, …, ''x''<sub>''k''</sub>, and two propositional formulas are [[logical equivalence|logically equivalent]] if and only if they express the same Boolean function. There are 2<sup>''k+1''</sup> ''k''-ary functions for every ''k''. |
||
==Boolean functions in applications== |
==Boolean functions in applications== |
||
Revision as of 17:16, 15 December 2013
 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (October 2012) |
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 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 2k+1 k-ary functions for every k.
Boolean functions in applications
A Boolean function describes how to determine a Boolean 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 polynomials over GF(2), but more efficient representations are binary decision diagrams (BDD), negation normal forms, and propositional directed acyclic graphs (PDAG).
In cooperative game theory, monotone Boolean functions are called simple games (voting games); this notion is applied to solve problems in social choice theory.
See also
References
- "Boolean function", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
- Digital Design, Mano. M. Morris
- Janković, Dragan; Stanković, Radomir S.; Moraga, Claudio (November 2003). "Arithmetic Expressions Optimisation Using Dual Polarity Property" (PDF). Serbian journal of electrical engineering. 1 (71–80, number 1). Retrieved 2010-04-06.
- http://www.answers.com/topic/switching-function?cat=technology
- http://www-cse.uta.edu/~carroll/cse2341/summer99/powerpoint%20files/chapter_2.ppt
| Major fields |
| ||||
|---|---|---|---|---|---|
| Foundations | |||||
| Lists |
| ||||
 | This mathematical logic-related article is a stub. You can help Wikipedia by expanding it. |