Boolean function : definition of Boolean function and synonyms of Boolean function (English)

Not to be confused with Binary function.

In mathematics, 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 formula 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

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). http://www.journal.tfc.kg.ac.rs/Vol_1-1/05-Jankovic.pdf. 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

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

Logic

Overview

Academic areas	Argumentation theory Axiology Critical thinking Computability theory Formal semantics History of logic Informal logic Logic in computer science Mathematical logic Mathematics Metalogic Metamathematics Model theory Philosophical logic Philosophy Philosophy of logic Philosophy of mathematics Proof theory Set theory

Foundational concepts	Abduction Analytic truth Antinomy A priori Deduction Definition Description Entailment Induction Inference Logical consequence Logical form Logical implication Logical truth Name Necessity Meaning Paradox Possible world Presupposition Probability Reason Reasoning Reference Semantics Statement Strict implication Substitution Syntax Truth Truth value Validity

Philosophical logic

Critical thinking and Informal logic	Analysis Ambiguity Argument Belief Bias Credibility Evidence Explanation Explanatory power Fact Fallacy Inquiry Opinion Parsimony Premise Propaganda Prudence Reasoning Relevance Rhetoric Rigor Vagueness

Theories of deduction	Constructivism Dialetheism Fictionalism Finitism Formalism Intuitionism Logical atomism Logicism Nominalism Platonic realism Pragmatism Realism

Metalogic and metamathematics

Cantor's theorem Church's theorem Church's thesis Consistency Effective method Foundations of mathematics Gödel's completeness theorem Gödel's incompleteness theorems Soundness Completeness Decidability Interpretation Löwenheim–Skolem theorem Metatheorem Satisfiability Independence Type–token distinction Use–mention distinction

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 and Boolean logic	Boolean functions Propositional calculus Propositional formula Logical connectives Truth tables

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

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

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

Non-classical logic

Modal logic	Alethic Axiologic Deontic Doxastic Epistemic Temporal

Intuitionism	Intuitionistic logic Constructive analysis Heyting arithmetic Intuitionistic type theory Constructive set theory

Fuzzy logic	Degree of truth Fuzzy rule Fuzzy set Fuzzy finite element Fuzzy set operations

Substructural logic	Structural rule Relevance logic Linear logic

Paraconsistent logic	Dialetheism

Description logic	Ontology Ontology language

Logicians

Anderson Aristotle Averroes Avicenna Bain Barwise Bernays Boole Boolos Cantor Carnap Church Chrysippus Curry De Morgan Frege Geach Gentzen Gödel Hilbert Kleene Kripke Leibniz Löwenheim Peano Peirce Putnam Quine Russell Schröder Scotus Skolem Smullyan Tarski Turing Whitehead William of Ockham Wittgenstein Zermelo

Lists

Topics	Outline of logic Index of logic articles Mathematical logic Boolean algebra Set theory

Other	Logicians Rules of inference Paradoxes Fallacies Logic symbols

Arabic	Bulgarian	Chinese	Czech
Danish	Dutch	English	Estonian
Finnish	French	German	Greek
Hungarian	Italian	Japanese	Korean
Norwegian	Polish	Portuguese	Romanian
Russian	Serbian	Slovenian	Spanish
Swedish	Turkish	Latvian	Persian
Lithuanian	Icelandic	Slovak	Croatian
Hindi	Vietnamese	Hebrew	Thai
Indonesian

Arabic	Bulgarian	Chinese	Czech
Danish	Dutch	English	Estonian
Finnish	French	German	Greek
Hungarian	Italian	Japanese	Korean
Norwegian	Polish	Portuguese	Romanian
Russian	Serbian	Slovenian	Spanish
Swedish	Turkish	Latvian	Persian
Lithuanian	Icelandic	Slovak	Croatian
Hindi	Vietnamese	Hebrew	Thai
Indonesian

Wikipedia

Boolean function

Boolean functions in applications

See also

References