![BinaryDecisionTree](https://upload.wikimedia.org/wikipedia/commons/e/eb/BinaryDecisionTree.svg)
In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a Boolean function is a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
whose
arguments
An argument is a statement or group of statements called premises intended to determine the degree of truth or acceptability of another statement called conclusion. Arguments can be studied from three main perspectives: the logical, the dialectic ...
and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
literature, and
truth function
In logic, a truth function is a function that accepts truth values as input and produces a unique truth value as output. In other words: The input and output of a truth function are all truth values; a truth function will always output exactly one ...
(or logical function), used in
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
. Boolean functions are the subject of
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in e ...
and
switching theory
Switching circuit theory is the mathematical study of the properties of networks of idealized switches. Such networks may be strictly combinational logic, in which their output state is only a function of the present state of their inputs; or may ...
.
A Boolean function takes the form
, where
is known as the
Boolean domain
In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include ''false'' and ''true''. In logic, mathematics and theoretical computer science, a Boolean domain is usually written as ...
and
is a non-negative integer called the
arity
Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. In ...
of the function. In the case where
, the function is a constant element of
. A Boolean function with multiple outputs,
with
is a ''vectorial'' or ''vector-valued'' Boolean function (an
S-box
In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Sha ...
in symmetric
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
).
There are
different Boolean functions with
arguments; equal to the number of different
truth tables
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
with
entries.
Every
-ary Boolean function can be expressed as a
propositional formula
In propositional logic, a propositional formula is a type of syntactic formula which is well formed and has a truth value. If the values of all variables in a propositional formula are given, it determines a unique truth value. A propositional fo ...
in
variables
, and two propositional formulas are
logically equivalent
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
if and only if they express the same Boolean function.
Examples
![Logical connectives Hasse diagram](https://upload.wikimedia.org/wikipedia/commons/3/3e/Logical_connectives_Hasse_diagram.svg)
The rudimentary symmetric Boolean functions (
logical connectives
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary c ...
or
logic gates
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate ...
) are:
*
NOT,
negation
In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and false ...
or
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-class ...
- which receives one input and returns true when that input is false ("not")
*
AND
or AND may refer to:
Logic, grammar, and computing
* Conjunction (grammar), connecting two words, phrases, or clauses
* Logical conjunction in mathematical logic, notated as "∧", "⋅", "&", or simple juxtaposition
* Bitwise AND, a boole ...
or
conjunction
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy), in which two astronomical bodies ...
- true when all inputs are true ("both")
*
OR or
disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
- true when any input is true ("either")
*
XOR
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
or
exclusive disjunction
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , , ...
- true when one of its inputs is true and the other is false ("not equal")
*
NAND or
Sheffer stroke
In Boolean functions and propositional calculus, the Sheffer stroke denotes a logical operation that is equivalent to the logical negation, negation of the logical conjunction, conjunction operation, expressed in ordinary language as "not both". ...
- true when it is not the case that all inputs are true ("not both")
*
NOR or
logical nor - true when none of the inputs are true ("neither")
*
XNOR
The XNOR gate (sometimes XORN'T, ENOR, EXNOR or NXOR and pronounced as Exclusive NOR. Alternatively XAND, pronounced Exclusive AND) is a digital logic gate whose function is the logical complement of the Exclusive OR (XOR) gate. It is equivalen ...
or
logical equality
Logical equality is a logical operator that corresponds to equality in Boolean algebra and to the logical biconditional in propositional calculus. It gives the functional value ''true'' if both functional arguments have the same logical value, ...
- true when both inputs are the same ("equal")
An example of a more complicated function is the
majority function In Boolean logic, the majority function (also called the median operator) is the Boolean function that evaluates to false when half or more arguments are false and true otherwise, i.e. the value of the function equals the value of the majority of t ...
(of an odd number of inputs).
Representation
A Boolean function may be specified in a variety of ways:
*
Truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
: explicitly listing its value for all possible values of the arguments
**Marquand diagram: truth table values arranged in a two-dimensional grid (used in a
Karnaugh map
The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logica ...
)
**
Binary decision diagram
In computer science, a binary decision diagram (BDD) or branching program is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. Un ...
, listing the truth table values at the bottom of a binary tree
**
Venn diagram
A Venn diagram is a widely used diagram style that shows the logical relation between set (mathematics), sets, popularized by John Venn (1834–1923) in the 1880s. The diagrams are used to teach elementary set theory, and to illustrate simple ...
, depicting the truth table values as a colouring of regions of the plane
Algebraically, as a
propositional formula
In propositional logic, a propositional formula is a type of syntactic formula which is well formed and has a truth value. If the values of all variables in a propositional formula are given, it determines a unique truth value. A propositional fo ...
using rudimentary boolean functions:
*
Negation normal form In mathematical logic, a formula is in negation normal form (NNF) if the negation operator (\lnot, ) is only applied to variables and the only other allowed Boolean operators are conjunction (\land, ) and disjunction (\lor, ).
Negation normal for ...
, an arbitrary mix of AND and ORs of the arguments and their complements
*
Disjunctive normal form
In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or (in philosophical logic) a ''cluster c ...
, as an OR of ANDs of the arguments and their complements
*
Conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a can ...
, as an AND of ORs of the arguments and their complements
*
Canonical normal form
In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form ( CDNF) or minterm canonical form and its dual canonical conjunctive normal form ( CCNF) or maxterm canonical form. Other canonical forms include ...
, a standardized formula which uniquely identifies the function:
**
Algebraic normal form
In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), '' Zhegalkin normal form'', or '' Reed–Muller expansion'' is a way of writing logical formulas in one of three subforms:
* The entire formula is purely tr ...
or
Zhegalkin polynomial
Zhegalkin (also Žegalkin, Gégalkine or Shegalkin) polynomials (russian: полиномы Жегалкина), also known as algebraic normal form, are a representation of functions in Boolean algebra. Introduced by the Russian mathematician Iva ...
, as a XOR of ANDs of the arguments (no complements allowed)
**''Full'' (canonical)
disjunctive normal form
In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or (in philosophical logic) a ''cluster c ...
, an OR of ANDs each containing every argument or complement (
minterms
In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form ( CDNF) or minterm canonical form and its dual canonical conjunctive normal form ( CCNF) or maxterm canonical form. Other canonical forms include ...
)
**''Full'' (canonical)
conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a can ...
, an AND of ORs each containing every argument or complement (
maxterms
In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form ( CDNF) or minterm canonical form and its dual canonical conjunctive normal form ( CCNF) or maxterm canonical form. Other canonical forms include ...
)
**
Blake canonical form
In Boolean logic, a formula for a Boolean function ''f'' is in Blake canonical form (BCF), also called the complete sum of prime implicants, the complete sum, or the disjunctive prime form, when it is a disjunction of all the prime implicants of ...
, the OR of all the
prime implicants of the function
Boolean formulas can also be displayed as a graph:
*
Propositional directed acyclic graph A propositional directed acyclic graph (PDAG) is a data structure that is used to represent a Boolean function. A Boolean function can be represented as a rooted, directed acyclic graph of the following form:
* Leaves are labeled with \top (true), ...
**
Digital circuit In theoretical computer science, a circuit is a model of computation in which input values proceed through a sequence of gates, each of which computes a function. Circuits of this kind provide a generalization of Boolean circuits and a mathematical ...
diagram of
logic gates
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate ...
, a
Boolean circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input ...
**
And-inverter graph
An and-inverter graph (AIG) is a directed, acyclic Graph (discrete mathematics), graph that represents a structural implementation of the logical functionality of a digital circuit, circuit or network. An AIG consists of two-input nodes represent ...
, using only AND and NOT
In order to optimize electronic circuits, Boolean formulas can be
minimized using the
Quine–McCluskey algorithm
The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952 and extended by Edward J. McCluskey in 1956. As a genera ...
or
Karnaugh map
The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logica ...
.
Analysis
Properties
A Boolean function can have a variety of properties:
*
Constant: Is always true or always false regardless of its arguments.
*
Monotone
Monotone refers to a sound, for example music or speech, that has a single unvaried tone. See: monophony.
Monotone or monotonicity may also refer to:
In economics
*Monotone preferences, a property of a consumer's preference ordering.
*Monotonic ...
: for every combination of argument values, changing an argument from false to true can only cause the output to switch from false to true and not from true to false. A function is said to be
unate in a certain variable if it is monotone with respect to changes in that variable.
*
Linear
Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
: for each variable, flipping the value of the variable either always makes a difference in the truth value or never makes a difference (a
parity function In Boolean algebra, a parity function is a Boolean function whose value is one if and only if the input vector has an odd number of ones. The parity function of two inputs is also known as the XOR function.
The parity function is notable for its ...
).
*
Symmetric
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
: the value does not depend on the order of its arguments.
*
Read-once: Can be expressed with
conjunction
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy), in which two astronomical bodies ...
,
disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
, and
negation
In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and false ...
with a single instance of each variable.
*
Balanced
In telecommunications and professional audio, a balanced line or balanced signal pair is a circuit consisting of two conductors of the same type, both of which have equal impedances along their lengths and equal impedances to ground and to other ...
: if its
truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
contains an equal amount of zeros and ones. The
Hamming weight
The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string o ...
of the function is the number of ones in the truth table.
*
Bent: its derivatives are all balanced (the autocorrelation spectrum is zero)
*
Correlation immune to ''m''th order: if the output is uncorrelated with all (linear) combinations of at most ''m'' arguments
*
Evasive: if evaluation of the function always requires the value of all arguments
*A Boolean function is a ''Sheffer function'' if it can be used to create (by composition) any arbitrary Boolean function (see
functional completeness In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression.. ("Complete set of logical connectives").. (" ...
)
*The ''algebraic degree'' of a function is the order of the highest order monomial in its
algebraic normal form
In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), '' Zhegalkin normal form'', or '' Reed–Muller expansion'' is a way of writing logical formulas in one of three subforms:
* The entire formula is purely tr ...
Circuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...
attempts to classify Boolean functions with respect to the size or depth of circuits that can compute them.
Derived functions
A Boolean function may be decomposed using
Boole's expansion theorem in positive and negative ''Shannon'' ''cofactors'' (
Shannon expansion
Boole's expansion theorem, often referred to as the Shannon expansion or decomposition, is the identity: F = x \cdot F_x + x' \cdot F_, where F is any Boolean function, x is a variable, x' is the complement of x, and F_xand F_ are F with the argum ...
), which are the (k-1)-ary functions resulting from fixing one of the arguments (to zero or one). The general (k-ary) functions obtained by imposing a linear constraint on a set of inputs (a linear subspace) are known as ''subfunctions''.
The ''
Boolean derivative'' of the function to one of the arguments is a (k-1)-ary function that is true when the output of the function is sensitive to the chosen input variable; it is the XOR of the two corresponding cofactors. A derivative and a cofactor are used in a
Reed–Muller expansion
In Boolean logic, a Reed–Muller expansion (or Davio expansion) is a decomposition of a Boolean function.
For a Boolean function f(x_1,\ldots,x_n) : \mathbb^n \to \mathbb we call
:
\begin
f_(x) & = f(x_1,\ldots,x_,1,x_,\ldots,x_n) \\
f_(x)& = ...
. The concept can be generalized as a k-ary derivative in the direction dx, obtained as the difference (XOR) of the function at x and x + dx.
The ''
Möbius transform
Moebius, Möbius or Mobius may refer to:
People
* August Ferdinand Möbius (1790–1868), German mathematician and astronomer
* Theodor Möbius (1821–1890), German philologist
* Karl Möbius (1825–1908), German zoologist and ecologist
* Paul ...
'' (or ''Boole-Möbius transform'') of a Boolean function is the set of coefficients of its
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
(
algebraic normal form
In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), '' Zhegalkin normal form'', or '' Reed–Muller expansion'' is a way of writing logical formulas in one of three subforms:
* The entire formula is purely tr ...
), as a function of the monomial exponent vectors. It is a
self-inverse transform. It can be calculated efficiently using a
butterfly algorithm ("''Fast Möbius Transform''"), analogous to the
Fast Fourier Transform
A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in th ...
. ''Coincident'' Boolean functions are equal to their Möbius transform, i.e. their truth table (minterm) values equal their algebraic (monomial) coefficients. There are 2^2^(''k''−1) coincident functions of ''k'' arguments.
Cryptographic analysis
The ''
Walsh transform
The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal ...
'' of a Boolean function is a k-ary integer-valued function giving the coefficients of a decomposition into
linear functions
Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
(
Walsh functions), analogous to the decomposition of real-valued functions into
harmonics
A harmonic is a wave with a frequency that is a positive integer multiple of the ''fundamental frequency'', the frequency of the original periodic signal, such as a sinusoidal wave. The original signal is also called the ''1st harmonic'', the ...
by the
Fourier transform
A Fourier transform (FT) is a mathematical transform that decomposes functions into frequency components, which are represented by the output of the transform as a function of frequency. Most commonly functions of time or space are transformed, ...
. Its square is the ''power spectrum'' or ''Walsh spectrum''. The Walsh coefficient of a single bit vector is a measure for the correlation of that bit with the output of the Boolean function. The maximum (in absolute value) Walsh coefficient is known as the ''linearity'' of the function.
The highest number of bits (order) for which all Walsh coefficients are 0 (i.e. the subfunctions are balanced) is known as ''resiliency'', and the function is said to be
correlation immune to that order.
The Walsh coefficients play a key role in
linear cryptanalysis
In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers. Linear cryptanalysis is one of the two most ...
.
The ''
autocorrelation
Autocorrelation, sometimes known as serial correlation in the discrete time case, is the correlation of a signal with a delayed copy of itself as a function of delay. Informally, it is the similarity between observations of a random variable ...
'' of a Boolean function is a k-ary integer-valued function giving the correlation between a certain set of changes in the inputs and the function ouput. For a given bit vector it is related to the Hamming weight of the derivative in that direction. The maximal autocorrelation coefficient (in absolute value) is known as the ''absolute indicator''.
If all autocorrelation coefficients are 0 (i.e. the derivatives are balanced) for a certain number of bits then the function is said to satisfy the ''propagation criterion'' to that order; if they are all zero then the function is a
bent function
In the mathematics, mathematical field of combinatorics, a bent function is a special type of Boolean function which is maximally non-linear; it is as different as possible from the set of all linear map, linear and affine functions when measure ...
. The autocorrelation coefficients play a key role in
differential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can aff ...
.
The Walsh coefficients of a Boolean function and its autocorrelation coefficients are related by the equivalent of the
Wiener–Khinchin theorem
In applied mathematics, the Wiener–Khinchin theorem or Wiener–Khintchine theorem, also known as the Wiener–Khinchin–Einstein theorem or the Khinchin–Kolmogorov theorem, states that the autocorrelation function of a wide-sense-stationary r ...
, which states that the autocorrelation and the power spectrum are a Walsh transform pair.
These concepts can be extended naturally to ''vectorial'' Boolean functions by considering their output bits (''coordinates'') individually, or more thoroughly, by looking at the set of all linear functions of output bits, known as its ''components''.
The set of Walsh transforms of the components is known as a ''Linear Approximation Table'' (LAT)
or ''correlation matrix''; it describes the correlation between different linear combinations of input and output bits. The set of autocorrelation coefficients of the components is the ''autocorrelation table'',
related by a Walsh transform of the components
to the more widely used ''Difference Distribution Table'' (DDT)
which lists the correlations between differences in input and output bits (see also:
S-box
In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Sha ...
).
Real polynomial form
On the unit hypercube
Any Boolean function
can be uniquely extended (interpolated) to the
real domain by a
multilinear polynomial In algebra, a multilinear polynomial is a multivariate polynomial that is linear (meaning affine) in each of its variables separately, but not necessarily simultaneously. It is a polynomial in which no variable occurs to a power of 2 or higher; tha ...
in
, constructed by summing the truth table values multiplied by
indicator polynomials:
For example, the extension of the binary XOR function
is
which equals
Some other examples are negation (
), AND (
) and OR (
). When all operands are independent (share no variables) a function's polynomial form can be found by repeatedly applying the polynomials of the operators in a Boolean formula. When the coefficients are calculated
modulo 2 one obtains the
algebraic normal form
In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), '' Zhegalkin normal form'', or '' Reed–Muller expansion'' is a way of writing logical formulas in one of three subforms:
* The entire formula is purely tr ...
(
Zhegalkin polynomial
Zhegalkin (also Žegalkin, Gégalkine or Shegalkin) polynomials (russian: полиномы Жегалкина), also known as algebraic normal form, are a representation of functions in Boolean algebra. Introduced by the Russian mathematician Iva ...
).
Direct expressions for the coefficients of the polynomial can be derived by taking an appropriate derivative:
this generalizes as the
Möbius inversion
Moebius, Möbius or Mobius may refer to:
People
* August Ferdinand Möbius (1790–1868), German mathematician and astronomer
* Theodor Möbius (1821–1890), German philologist
* Karl Möbius (1825–1908), German zoologist and ecologist
* Paul ...
of the
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
of bit vectors:
where
denotes the weight of the bit vector
. Taken modulo 2, this is the
Boolean ''Möbius transform'', giving the
algebraic normal form
In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), '' Zhegalkin normal form'', or '' Reed–Muller expansion'' is a way of writing logical formulas in one of three subforms:
* The entire formula is purely tr ...
coefficients:
In both cases, the sum is taken over all bit-vectors ''a'' covered by ''m'', i.e. the "one" bits of ''a'' form a subset of the one bits of ''m''.
When the domain is restricted to the n-dimensional
hypercube
In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, ...
, the polynomial