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 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. See also Logic Logic portalAlgebra of sets Boolean algebra 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 functionsReferencesCrama, Y; Hammer, P. L. (2011), Boolean Functions, Cambridge University Press . 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.  Mano, M. M.; Ciletti, M. D. (2013), Digital Design, Pearson .v t eMathematical logicGeneralFormal language Formation rule Formal proof Formal semantics Well-formed formula Set Element Class Classical logic Axiom Rule of inference Relation Theorem Logical consequence Type theory Symbol Syntax TheorySystemsFormal system Deductive system Axiomatic system Hilbert style systems Natural deduction Sequent calculusTraditional logicProposition Inference Argument Validity Cogency Syllogism Square of opposition Venn diagramPropositional calculus Boolean logicBoolean functions Propositional calculus Propositional formula Logical connectives Truth tables Many-valued logicPredicate logicFirst-order Quantifiers Predicate Second-order Monadic predicate calculusNaive set theorySet 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 pairSet theoryFoundations 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 theoryModel theoryModel Interpretation Non-standard model Finite model theory Truth value ValidityProof theoryFormal proof Deductive system Formal system Theorem Logical consequence Rule of inference SyntaxComputability theoryRecursion Recursive set Recursively enumerable set Decision problem Church–Turing thesis Computable function Primitive recursive functionThis mathematical logic-related article is a stub. You can help by expandi

.