10 New Results on Reversible Boolean Functions Having Component. . .
219
Definition 10.1 A Boolean function f : {0, 1} n → {0, 1} is called balanced if it takes
value 1 the same number of times as value 0.
In the case of Boolean functions, depending on the operations allowed in
a particular classification, the P-equivalent, NP-equivalent, and NPN-equivalent
functions are distinguished. In some applications, equivalence classes defined with
respect to a restricted set of operations are of a particular interest, as for example, in
[11, 12]. In the present paper, we are particularly interested in P-equivalent functions
when studying properties of component functions.
Definition 10.2 Two Boolean functions are
1. P-equivalent if they can be converted to each other by the permutation of
variables,
2. NP-equivalent if they can be converted to each other by the negation and/or
permutation of variables,
3. NPN-equivalent if they can be converted to each other by negation of variables,
permutation of variables, and negation of the function.
Definition 10.3 A Boolean function f is self-complementary (SC) if f and f ’ are
NP-equivalent, where f ’ denotes negation of f.
Definition 10.4 A Boolean function f is self-dual (SD) if
f (x 1 , x 2 , . . . , x n ) = f
x 1
, x 2
, . . . , x n
.
Definition 10.5 A Boolean function f is linear with respect to a variable x i if the
function f can be expressed in the form f = x i ⊕ g, where g is a function independent
of x i (then the variable x i is called linear in f ). A function f is called linear (L) if all
its variables are linear in f. Otherwise it is called nonlinear. A function has property
LV if it contains at least one linear variable.
Example 10.1 f 1 (x, y, z) = x ⊕ y ⊕ yz is linear with respect to x as then g = y ⊕
yz is independent of x, but f 1 is not linear with respect to y as then g = x ⊕ yz is
dependent of y. Similarly, f 2 (x, y) = x ⊕ y ⊕ xy is linear with respect to neither x
nor y.
The following results are well known:
Lemma 10.1
1. All self-complementary functions are balanced,
2. All self-dual functions are self-complementary,
3. All functions having property LV are self-complementary,
4. If a Boolean function f is linear with respect to a variable x i, then
f (x i = 1) = f
(x i = 0) .
219
Definition 10.1 A Boolean function f : {0, 1} n → {0, 1} is called balanced if it takes
value 1 the same number of times as value 0.
In the case of Boolean functions, depending on the operations allowed in
a particular classification, the P-equivalent, NP-equivalent, and NPN-equivalent
functions are distinguished. In some applications, equivalence classes defined with
respect to a restricted set of operations are of a particular interest, as for example, in
[11, 12]. In the present paper, we are particularly interested in P-equivalent functions
when studying properties of component functions.
Definition 10.2 Two Boolean functions are
1. P-equivalent if they can be converted to each other by the permutation of
variables,
2. NP-equivalent if they can be converted to each other by the negation and/or
permutation of variables,
3. NPN-equivalent if they can be converted to each other by negation of variables,
permutation of variables, and negation of the function.
Definition 10.3 A Boolean function f is self-complementary (SC) if f and f ’ are
NP-equivalent, where f ’ denotes negation of f.
Definition 10.4 A Boolean function f is self-dual (SD) if
f (x 1 , x 2 , . . . , x n ) = f
x 1
, x 2
, . . . , x n
.
Definition 10.5 A Boolean function f is linear with respect to a variable x i if the
function f can be expressed in the form f = x i ⊕ g, where g is a function independent
of x i (then the variable x i is called linear in f ). A function f is called linear (L) if all
its variables are linear in f. Otherwise it is called nonlinear. A function has property
LV if it contains at least one linear variable.
Example 10.1 f 1 (x, y, z) = x ⊕ y ⊕ yz is linear with respect to x as then g = y ⊕
yz is independent of x, but f 1 is not linear with respect to y as then g = x ⊕ yz is
dependent of y. Similarly, f 2 (x, y) = x ⊕ y ⊕ xy is linear with respect to neither x
nor y.
The following results are well known:
Lemma 10.1
1. All self-complementary functions are balanced,
2. All self-dual functions are self-complementary,
3. All functions having property LV are self-complementary,
4. If a Boolean function f is linear with respect to a variable x i, then
f (x i = 1) = f
(x i = 0) .