View source for Boolean function

[[File:LogicGates.jpg|thumb|Chart of fundamental Boolean functions.]]In [[Boolean algebra]], a '''Boolean function''' is a [[Function (mathematics)|mathematical function]] which describes how to determine a Boolean value [[output]] based on some logical calculation from Boolean [[Input|inputs]].

== Description ==

A (finitary) '''Boolean function''' (or '''switching function''') is a [[Function (mathematics)|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]]
* [[Logic gates]] and the design of circuits and chips for [[Digital computer|digital computers]]
* [[Cryptography]], particularly in the design of [[Symmetric key algorithm|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 diagram|binary decision diagrams]] (BDD)
* [[Negation normal form|negation normal forms]]
* [[Propositional directed acyclic graph|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 ==

* [[3-ary Boolean functions]]
* [[Algebra of sets]]
* [[Balanced boolean function]]
* [[Boolean algebra]]
* [[Boolean algebra topics]]
* [[Boolean domain]]
* [[Boolean-valued function]]
* [[Complexity theory]]
* [[Cryptography]]
* [[Decision tree model]]
* [[Digital computer]]
* [[Evasive Boolean function]]
* [[Function (mathematics)]]
* [[Indicator function]]
* [[Logic]]
* [[Logical connective]]
* [[Mathematical logic]]
* [[Mathematics]]
* [[Propositional logic]]
* [[Read-once function]]
* [[Symmetric Boolean function]]
* [[Truth function]]
* [[Truth table]]

==  External links ==

* [https://en.wikipedia.org/wiki/Boolean_function Boolean function] @ Wikipedia

[[Category:Functions]]
[[Category:Logic]]
[[Category:Mathematics]]