Formed in 2009, the Archive Team (not to be confused with the archive.org Archive-It Team) is a rogue archivist collective dedicated to saving copies of rapidly dying or deleted websites for the sake of history and digital heritage. The group is 100% composed of volunteers and interested parties, and has expanded into a large amount of related projects for saving online and digital history.
Boolean function
 | This article needs additional citations for verification. (February 2020) (Learn how and when to remove this template message) |
A Boolean function is a function in mathematics and logic whose arguments, as well as the function itself, assume values from a finitary two-element set (usually {0,1}).[1] As a result, it is sometimes referred to as a "switching function".
A Boolean function takes 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[edit]
A function that can be utilized to evaluate any Boolean output in relation to its Boolean input by logical type of calculations. 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.
In order to optimize electronic circuits, Boolean functions can be minimized using the Quine–McCluskey algorithm or Karnaugh map.
See also[edit]
- Algebra of sets
- Boolean algebra
- Boolean algebra topics
- Boolean domain
- Boolean differential calculus
- 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
- Pseudo-Boolean function
3-ary Boolean functions
References[edit]
Further reading[edit]
- Crama, Y; Hammer, P. L. (2011), Boolean Functions : Theory, Algorithms, and Applications, Cambridge University Press, doi:10.1017/CBO9780511852008, ISBN 9780511852008.
- Hazewinkel, Michiel, ed. (2001) [1994], "Boolean function", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, 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.
- Bradford Henry Arnold (1 January 2011). Logic and Boolean Algebra. Courier Corporation. ISBN 978-0-486-48385-6.
- Mano, M. M.; Ciletti, M. D. (2013), Digital Design, Pearson.
