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_1, …, _x__k_, and two propositional
formulas are logically equivalent if and only if they express the same
Boolean function. There are 22_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 .

SEE ALSO

*
**Logic** portal

*
**Algebra of sets**
*
**Boolean algebra**
*
**Boolean algebra** topics
*
**Boolean domain**
*
**Boolean-valued function**
*
**Logical connective**
*
**Truth function**
*
**Truth table**
*
**Symmetric Boolean function**
*
**Decision tree model**
*
**Evasive Boolean function**
*
**Indicator function**
*
**Balanced boolean function**
*
**Read-once function**
* 3-ary Boolean functions

REFERENCES

* Crama, Y; Hammer, P. L. (2011), _Boolean Functions_, Cambridge
University Press .
* Hazewinkel, Michiel, ed. (2001), "Boolean function", _Encyclopedia
of
**Mathematics** _, Springer, ISBN 978-1-55608-010-4
* 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). Archived from the original (PDF) on 2016-03-05.
Retrieved 2015-06-07.
* Mano, M. M.; Ciletti, M. D. (2013), _Digital Design_, Pearson .

* v
* t
* e

**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
*
**Many-valued logic**

PREDICATE LOGIC

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

NAIVE SET THEORY

* Set
*
**Empty set**
* Element
*
**Enumeration**
*
**Extensionality**
*
**Finite set**
*
**Infinite set**
*
**Subset**
*
**Power set**
*
**Countable set**
*
**Uncountable set**
*
**Recursive set**
* Domain
*
**Codomain**
* Image
* 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**

_
This mathematical logic -related article is a stub . You can help
**Wikipedia** by expanding it ._

* v
* t
* e

Retrieved from
"https://en.wikipedia.org/w/index.php?title=Boolean_function
additional terms may apply. By using this site, you agree to the Terms
of Use and Privacy Policy .® is a registered trademark of
the Wikimedia Foundation, Inc. , a non-profit organization.

* Privacy policy
* About
**Wikipedia**
* Disclaimers
* Contact
**Wikipedia**
* Developers
* Cookie statement
* Mobile view

*
*

Links:
------