Dictionary
Thesaurus
Reference
Translate
Web
Related Searches
on Ask.com
Boolean Function
2 reference results for: Boolean function
Wikipedia
In mathematics, a (finitary) Boolean function is a function of the form f : 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 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, but more efficient representations are binary decision diagrams (BDD), negation normal forms, and propositional directed acyclic graphs (PDAG).

See also

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)
This article is licensed under the GNU Free Documentation License.
Last updated on Thursday July 10, 2008 at 16:54:50 PDT (GMT -0700)
View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

CITE THIS SOURCE|PRINT
Wikipedia
In mathematics, a (finitary) Boolean function is a function of the form f : 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 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, but more efficient representations are binary decision diagrams (BDD), negation normal forms, and propositional directed acyclic graphs (PDAG).

See also

CITE THIS SOURCE|PRINT
Share This:Share This: digg.comShare This: ma.gnolia.comShare This: www.stumbleupon.comShare This: del.icio.usShare This: FacebookShare This: favorites.live.comShare This: www.technorati.comShare This: furl.netShare This: myweb2.search.yahoo.comShare This: www.google.com