Boolean function

From Wikipedia, the free encyclopedia

This article may be too technical for most readers to understand, and needs attention from an expert on its subject. Please expand it to make it accessible to non-experts, without removing the technical details.

A Boolean function describes how to determine a Boolean value output based on some logical calculation from Boolean inputs. These 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 S-box).

A boolean mask operation on boolean-valued functions combines values point-wise (for example, by XOR, or other boolean operators).

1 Algebraic Normal Form
2 Finitary Boolean Function
3 Efficient Representations
4 See also

A boolean function can be written uniquely as a sum (XOR) of products (AND). This is known as the Algebraic Normal Form (ANF).

$f(x_1, x_2, \ldots , x_n) = \!$	$a_0 + \!$
	$a_1x_1 + a_2x_2 + \ldots + a_nx_n + \!$
	$a_{1,2}x_1x_2 + a_{1,3}x_1x_3 + \ldots + a_{n-1,n}x_{n-1}x_n + \!$
	$\ldots + \!$
	$a_{1,2,\ldots,n}x_1x_2\ldots x_n \!$

where $a_0, a_1, \ldots, a_{1,2,\ldots,n} \in \{0,1\}^*$ .

The values of the sequence $a_0,a_1,\ldots,a_{1,2,\ldots,n}$ can therefore also uniquely represent a boolean function. The algebraic degree of a boolean function is defined as the highest number of $x i$ that appear in a product term. Thus $f (x 1, x 2, x 3) = x 1 + x 3$ has degree 1 (linear), whereas $f (x 1, x 2, x 3) = x 1 + x 1 x 2 x 3$ has degree 3 (cubic).

In mathematics, a finitary boolean function is a function of the form f : B^k → B, where B = {0, 1} is a boolean domain and where k is a nonnegative integer. In the case where k = 0, the "function" is simply a constant element of B.

More generally, a function of the form f : X → B, where X is an arbitrary set, is a boolean-valued function. If X = M = {1, 2, 3, …}, then f is a binary sequence, that is, an infinite sequence of 0's and 1's. If X = [k] = {1, 2, 3, …, k}, then f is a binary sequence of length k.

There are $2^{2^k}$ such functions.

Boolean functions are often represented by sentences in propositional logic, but more efficient representations are binary decision diagrams (BDD), negation normal forms, and propositional directed acyclic graphs (PDAG).

Logic Portal

v • d • e

Logic

Main articles

Reason · History of logic · Philosophical logic · Philosophy of logic · Mathematical logic · Metalogic · Logic in computer science

Key concepts
and logics

Reasoning	Deduction · Induction · Abduction
Informal	Proposition · Inference · Argument · Validity · Cogency · Term logic · Critical thinking · Fallacies · Syllogism
Mathematical	Set · Element · Class · Wff · Axiom · Theorem · Interpretation · Consistency · Soundness · Completeness · Decidability · Satisfiability · Formal system · Set theory · Proof theory · Model theory · Recursion theory · Syntax · Semantics · Semantic consequence · Syntactic consequence ·
Zeroth-order	Boolean functions · Monadic predicate calculus · Propositional calculus · Logical connectives · Truth tables
Predicate	First-order · Quantifiers · Second-order
Modal	Deontic · Epistemic · Temporal · Doxastic
Other non-classical	Computability · Fuzzy · Linear · Relevance · Non-monotonic