|
A Boolean function describes how to determine a Boolean value output based on some logical calculation from Boolean inputs. These 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 S-box). The adjective Boolean [], coined in honour of George Boole, is used in many contexts: An evaluation that results in either of the truth values true or false. A Boolean value is a truth value, either true or false, often coded 1 and 0, respectively. ...
In mathematics, a Boolean function is usually a function F(b1, b2, ... , bn) of a number n of Boolean variables bi from the two-element Boolean algebra {0,1}, and such that F also takes values in {0, 1}. A function on a general domain of a function taking values...
Mathematical logic is a subfield of mathematics that is concerned with formal systems in relation to the way that they encode intuitive concepts of mathematical objects such as sets and numbers, proofs, and computation. ...
Complexity theory can refer to more than one thing: Computational complexity theory: a field in theoretical computer science and mathematics dealing with the resources required during computation to solve a given problem Systems theory (or systemics or general systems theory): an interdisciplinary field including engineering, biology and philosophy that incorporates...
...
The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κÏυπτός kryptós hidden, and the verb γÏάφω gráfo write or λεγειν legein to speak) is the study of message secrecy. ...
Symmetric-key algorithms are a class of algorithms for cryptography that use trivially related cryptographic keys for both decryption and encryption. ...
In cryptography, a substitution box (or S-box) is a basic component of symmetric key algorithms. ...
A boolean mask operation on boolean-valued functions combines values point-wise (for example, by XOR, or other boolean operators). Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ...
In logical calculus, logical operators or logical connectors serve to connect statements into more complicated compound statements. ...
Algebraic Normal Form
A boolean function can be written uniquely as a sum (OR) of products (AND). This is known as the Algebraic Normal Form (ANF). OR logic gate. ...
AND Logic Gate In logic and mathematics, logical conjunction (usual symbol and) is a two-place logical operation that results in a value of true if both of its operands are true, otherwise a value of false. ...
In Boolean logic, Algebraic Normal Form (ANF) is a method of standardizing and normalizing logical formulas. ...
where  .
The values of the sequence  can therefore also uniquely represent a boolean function. The algebraic degree of a boolean function is defined as the highest number of xi that appear in a product term. Thus f(x1,x2,x3) = x1 + x3 has degree 1 (linear), whereas f(x1,x2,x3) = x1 + x1x2x3 has degree 3 (cubic).
Finitary Boolean Function In mathematics, a finitary boolean function is a function of the form f : Bk → B, where B = {0, 1} is a boolean domain and where k is a nonnegative integer. In the case where k = 0, the "function" is simply a constant element of B. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ...
Graph of example function, The mathematical concept of a function expresses the intuitive idea of deterministic dependence between two quantities, one of which is viewed as primary (the independent variable, argument of the function, or its input) and the other as secondary (the value of the function, or output). A...
A boolean domain B is a generic 2-element set, say, B = {0, 1}, whose elements are interpreted as logical values, typically 0 = false and 1 = true. ...
More generally, a function of the form f : X → B, where X is an arbitrary set, is a boolean-valued function. If X = M = {1, 2, 3, …}, then f is a binary sequence, that is, an infinite sequence of 0's and 1's. If X = [k] = {1, 2, 3, …, k}, then f is a binary sequence of length k. A boolean-valued function, in some usages a predicate or a proposition, is a function of the type f : X → B, where X is an arbitrary set and where B is a boolean domain. ...
In mathematics, a sequence is a list of objects (or events) arranged in a linear fashion, such that the order of the members is well defined and significant. ...
There are  such functions.
Efficient Representations Boolean functions are often represented by sentences in propositional logic, but more efficient representations are binary decision diagrams (BDD), negation normal forms, or more generally by propositional directed acyclic graphs (PDAG). Propositional logic or sentential logic is the logic of propositions, sentences, or clauses. ...
A binary decision diagram (BDD), like a negation normal form (NNF) or a propositional directed acyclic graph (PDAG), is a data structure that is used to represent a Boolean function. ...
A logical formula is in negation normal form if negation occurs only immediately above elementary propositions. ...
A propositional directed acyclic graph (PDAG) is a data structure that is used to represent a Boolean function. ...
See also The algebra of sets develops and describes the basic properties and laws of sets, the set-theoretic operations of union, intersection, and complementation and the relations of set equality (mathematics) and set inclusion. ...
Boolean algebra is the finitary algebra of two values. ...
Algebra of sets George Boole Boolean algebra Boolean function Boolean logic Boolean homomorphism Boolean Implicant Boolean prime ideal theorem Boolean-valued model Boolean satisfiability problem Booles syllogistic canonical form (Boolean algebra) compactness theorem Complete Boolean algebra connective -- see logical operator de Morgans laws Augustus De Morgan duality (order...
A boolean domain B is a generic 2-element set, say, B = {0, 1}, whose elements are interpreted as logical values, typically 0 = false and 1 = true. ...
Boolean logic is a complete system for logical operations. ...
A boolean-valued function, in some usages a predicate or a proposition, is a function of the type f : X → B, where X is an arbitrary set and where B is a boolean domain. ...
In logic, a logical connective is a syntactic operation on sentences, or the symbol for such an operation, that corresponds to a logical operation on the logical values of those sentences. ...
In logic a truth function is a connective for which the truth value is determined systematically by the values of the statements it connects. ...
Zeroth-order logic is a term in popular use among practitioners for the subject matter otherwise known as boolean functions, monadic predicate logic, propositional calculus, or sentential calculus. ...
External links - Boolean Planet — boolean functions in cryptography.
|
Feeds |
Contact