Boolean function

Not to be confused with Binary function.

In mathematics and logic, a (finitary) Boolean function (or switching function) is a function of the form ƒ : B^k → 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₁, …, x_k, and two propositional formulas are logically equivalent if and only if they express the same Boolean function. There are 2^{2^k} 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.

References

Hazewinkel, Michiel, ed. (2001), "Boolean function", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
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

Mathematical logic

General	Formal language Formation rule Formal system Deductive system Formal proof Formal semantics Well-formed formula Set Element Class Classical logic Axiom Natural deduction Rule of inference Relation Theorem Logical consequence Axiomatic system Type theory Symbol Syntax Theory

Traditional logic	Proposition Inference Argument Validity Cogency Syllogism Square of opposition Venn diagram

Propositional calculus Boolean logic	Boolean functions Propositional calculus Propositional formula Logical connectives Truth tables

Predicate logic	First-order Quantifiers Predicate Second-order Monadic predicate calculus

Naive set theory	Set Empty set Enumeration Extensionality Finite set Infinite set Subset Power set Countable set Uncountable set Recursive set Domain Range Map Function Relation Ordered pair

Set theory	Foundations of mathematics Zermelo–Fraenkel set theory Axiom of choice General set theory Kripke–Platek set theory Von Neumann–Bernays–Gödel set theory Morse–Kelley set theory Tarski–Grothendieck set theory

Model theory	Model Interpretation Non-standard model Finite model theory Truth value Validity

Proof theory	Formal proof Deductive system Formal system Theorem Logical consequence Rule of inference Syntax

Computability theory	Recursion Recursive set Recursively enumerable set Decision problem Church–Turing thesis Computable function Primitive recursive function

Boolean function

Boolean functions in applications

See also

References