The Full Wiki

Boolean function: Wikis

  

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

From Wikipedia, the free encyclopedia

In mathematics, a (finitary) Boolean function is a function of the form f : BkB, 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, 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).

See also

References

  • Digital Design, Mano. M. Morris

Wiktionary

Up to date as of January 15, 2010

Definition from Wiktionary, a free dictionary

English

Noun

Wikipedia-logo.png
Wikipedia has an article on:

Wikipedia

Boolean function (plural Boolean functions)

  1. (algebra, logic, computing) Any function based on the operations AND, OR and NOT, and whose elements are from the domain of Boolean algebra

Translations








Got something to say? Make a comment.
Your name
Your email address
Message