Information about Boolean Function

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).

Algebraic Normal Form

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



where .

The values of the sequence can therefore also uniquely represent a boolean function. The algebraic degree of a boolean function is defined as the highest number of that appear in a product term. Thus has degree 1 (linear), whereas has degree 3 (cubic).

Finitary Boolean Function

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 such functions.

Efficient Representations

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).

See also

Algebra of sets Boolean algebra (logic) Boolean algebra topics

Boolean domain Boolean logic

Boolean-valued function Logical connective Truth function Zeroth order logic

•  • [ e] Logic
Navigation:	WikiProject Cleanup Noticeboard
Main Articles:	Reason History of Logic Philosophical Logic Philosophy of logic Mathematical Logic Metalogic Logic in computer science
Key Concepts	Reasoning: Deduction Induction Abduction Informal Logic: Proposition Inference Argument Validity Cogency Term logic Critical Thinking Fallacies Syllogism Mathematical logic: Set Syntax Semantics Wff Axiom Theorem Consistency Soundness Completeness Decidability Formal system Set theory Proof theory Model theory Recursion theory Zeroth-Order Logic: Boolean functions Monadic predicate calculus Propositional calculus Logical connectives Truth Tables Predicate Logic: First-Order LogicQuantifiers Second-order logic Modal Logic: Deontic logic Epistemic logic Temporal logic Doxastic logic Other non-classical logics: Computability logic Fuzzy logic Linear logic Relevance logic Non-monotonic logic
Controversies	Paraconsistent Logic Dialetheism Intuitionistic logic Paradoxes Antinomies Is logic empirical?
Key Figures	Aristotle Boole Cantor Carnap Church Frege Gentzen Gdel Hilbert Kripke Peano Peirce Putnam Quine Russell Skolem Tarski Turing Whitehead
Lists	Basic Topics in Logic Topics in Logic Logicians Rules of Inference Mathematical Logic Topics Basic Discrete Mathematics Topics Set theory topics Paradoxes Fallacies Logical Symbols