FANDOM


In mathematics, a (finitary) Boolean function is a function of the form ƒ : Bk → B, where B = {0, 1} is a Boolean domain and k is a nonnegative 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 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 applicationsEdit

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, Boolean functions are called simple games (voting games); this notion is applied to solve problems in social choice theory.

See alsoEdit

Template:Portal

Template:Col-breakTemplate:Col-breakTemplate:Col-break

ReferencesEdit

  • Digital Design, Mano. M. Morris

Template:Logicca:Funció booleana de:Boolesche Funktion es:Función booleana fa:تابع بولی fr:Fonction booléenne it:Funzione booleana mk:Булова функција nl:Booleaanse functie ja:ブール関数 ru:Булева функция uk:Булева функція zh:布尔函数

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.