HOME
The Info List - Boolean Function



--- Advertisement ---


In mathematics and logic , a (FINITARY ) BOOLEAN FUNCTION (or switching function) is a function of the form ƒ : Bk → 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 x1, …, xk, and two propositional formulas are logically equivalent if and only if they express the same Boolean function. There are 22k 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
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
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
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
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
Decision problem
* Church–Turing thesis * Computable function * Primitive recursive function

This mathematical logic -related article is a stub . You can help 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 * Disclaimers * Contact * Developers * Cookie statement * Mobile view

* *

Links: ------

.