Boolean function

Boolean function

In mathematics, a (finitary) Boolean function is a function of the form f : B"k" → 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 "x"1,…,"x"k, 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).

ee also

* Algebra of sets
* Boolean algebra (logic)
* Boolean algebra topics
* Boolean domain
* Boolean logic
* Boolean-valued function
* Logical connective
* Truth function


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Boolean function — Boolean funkcija statusas T sritis automatika atitikmenys: angl. Boolean connective; Boolean function vok. Boolesche Funktion, f; logische Funktion, f rus. булева связка, f; булева функция, f pranc. fonction booléenne, f; fonction de Boole, f… …   Automatikos terminų žodynas

  • Boolean function — loginė funkcija statusas T sritis informatika apibrėžtis ↑Funkcija, kurios rezultatas – ↑loginė reikšmė: ↑tiesa arba ↑netiesa. Logines funkcijas galima rašyti programose, jų būna ↑kompiliatorių ir ↑taikomųjų programų bibliotekose. atitikmenys:… …   Enciklopedinis kompiuterijos žodynas

  • Boolean function — noun Any function based on the operations AND, OR and NOT, and whose elements are from the domain of Boolean algebra …   Wiktionary

  • Boolean algebras canonically defined — Boolean algebras have been formally defined variously as a kind of lattice and as a kind of ring. This article presents them more neutrally but equally formally as simply the models of the equational theory of two values, and observes the… …   Wikipedia

  • Boolean logic — is a complete system for logical operations. It was named after George Boole, who first defined an algebraic system of logic in the mid 19th century. Boolean logic has many applications in electronics, computer hardware and software, and is the… …   Wikipedia

  • Boolean — (after George Boole), as a noun or an adjective, may refer to: * Boolean algebra (logic), a logical calculus of truth values or set membership * Boolean algebra (structure), a set with operations resembling logical ones * Boolean datatype, a… …   Wikipedia

  • Boolean operation — may refer to one of the following related meanings.*Boolean function *an operation in a Boolean algebra; in particular: **operations over the algebra of sets: union (set theory), intersection (set theory), etc. **Boolean operations on polygons… …   Wikipedia

  • Boolean connective — Boolean funkcija statusas T sritis automatika atitikmenys: angl. Boolean connective; Boolean function vok. Boolesche Funktion, f; logische Funktion, f rus. булева связка, f; булева функция, f pranc. fonction booléenne, f; fonction de Boole, f… …   Automatikos terminų žodynas

  • Boolean funkcija — statusas T sritis automatika atitikmenys: angl. Boolean connective; Boolean function vok. Boolesche Funktion, f; logische Funktion, f rus. булева связка, f; булева функция, f pranc. fonction booléenne, f; fonction de Boole, f ryšiai: sinonimas –… …   Automatikos terminų žodynas

  • Boolean algebra (structure) — For an introduction to the subject, see Boolean algebra#Boolean algebras. For the elementary syntax and axiomatics of the subject, see Boolean algebra (logic). For an alternative presentation, see Boolean algebras canonically defined. In abstract …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”