Boolean Function
Safiur Rahman Ansari
Boolean Algebra
Boolean algebra provides the operations and the rules for
working with the set {0, 1}.
The three operations in Boolean algebra that we will use most
are complementation, the Boolean sum, and the Boolean
product.
The complement of an element, denoted with a bar, is defined
by
0’ = 1 and 1’ = 0
Boolean Algebra
The Boolean sum, denoted by + or by OR, has the following values:
1+1=1 1+0=1
0+1=1 0+0=0
The Boolean product, denoted by ⋅ or by AND, has the following
values:
1⋅1=1 1⋅0=0
0⋅1=0 0⋅0=0
Boolean Functions
Let B = {0, 1}. Then Bn = {(x1 , x2 , … , xn ) ∣ xi ∈ B for 1 ≤ i ≤ n}
is the set of all possible n-tuples of 0s and 1s.
The variable x is called a Boolean variable if it assumes values
only from B, that is, if its only possible values are 0 and 1.
A function from Bn to B is called a Boolean function of degree n
Boolean Function
Boolean functions can be represented using expressions made
up from variables and Boolean operations.
Each Boolean expression represents a Boolean function. The
values of this function are obtained by substituting 0 and 1 for
the variables in the expression.
Boolean Function Representation
Truth table
explicitly listing its value for all possible values of the arguments
Algebraically
as a propositional formula using rudimentary Boolean functions:
Negation normal form, an arbitrary mix of AND and ORs of the
arguments and their complements
Disjunctive normal form, as an OR of ANDs of the arguments
and their complements
Conjunctive normal form, as an AND of ORs of the arguments
and their complements
Properties of Boolean Function
Constant: Is always true or always false regardless of its
arguments.
Monotone: 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: 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).
Properties of Boolean Function
Symmetric: the value does not depend on the order of its
arguments.
Read-once: Can be expressed with conjunction, disjunction,
and negation with a single instance of each variable.
Balanced: if its truth table contains an equal number of zeros
and ones. The Hamming weight of the function is the number of
ones in the truth table.
Bent: its derivatives are all balanced (the autocorrelation
spectrum is zero)
Properties of Boolean Function
Correlation immune to mth 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)
The algebraic degree of a function is the order of the highest order
monomial in its algebraic normal form
Application of Boolean Function
Boolean functions play a basic role in questions of complexity theory
as well as the design of processors for digital computers, where they
are implemented in electronic circuits using logic gates.
The properties of Boolean functions are critical in cryptography,
particularly in the design of symmetric key algorithms (see
substitution box).
In cooperative game theory, monotone Boolean functions are called
simple games (voting games); this notion is applied to solve problems
in social choice theory.
Thank you
