10 New Results on Reversible Boolean Functions Having Component. . .
229
Namely, it is easy to note that
– The first and the second n-tuples differ only in the 1st bit position,
– The second and the third n-tuples differ only in the 2nd bit position,
– The third and the forth n-tuples differ only in the 3rd bit position.
Thus we observe here a certain periodicity which can be easily extrapolated
leading to the desired infinite sequence of reversible functions as will be seen later.
In this case extrapolating was even simpler than in the previous section.
Definition 10.9 A set of variable assignments over {0, 1} with specified numbers
of m 0s and n 1s is called a block and denoted by b m,n .
Example 10.4 The set of all 8 variable assignments for three variable Boolean
functions can be partitioned into the following four blocks:
b 3,0 = {000} b 2,1 = {001, 010, 100} b 1,2 = {011, 101, 110} b 0,3 = {111} .
Definition 10.10 For any Boolean function f let B 0 (f ) and B 1 (f ) denote the sets of
blocks including all variable assignments for which f is equal 0 and 1, respectively.
Example 10.5 Let us consider the following Boolean projection functions:
f (x 3 , x 2 , x 1 ) = x 3 , g (x 3 , x 2 , x 1 ) = x 2 , h (x 3 , x 2 , x 1 ) = x 1 .
Then
B
0 (f ) = { {000} , {001, 010} , {011} }
B
1 (f ) = { {100} , {101, 110} , {111} }
B
0 (g) = { {000} , {001, 100} {101} }
B
1 (g) = { {010} , {011, 110} , {111} }
B
0 (h) = { {000} , {010, 100} , {110} }
B
1 (h) = { {001} , {011, 101} , {111} }
Notice that for each 3-variable Boolean reversible function k the union of B 0 (k)
and B 1 (k) is equal to the set of all 8 Boolean variable assignments. For each of the
component functions of an arbitrary reversible function cardinalities of unions of
their B i sets are the same.
229
Namely, it is easy to note that
– The first and the second n-tuples differ only in the 1st bit position,
– The second and the third n-tuples differ only in the 2nd bit position,
– The third and the forth n-tuples differ only in the 3rd bit position.
Thus we observe here a certain periodicity which can be easily extrapolated
leading to the desired infinite sequence of reversible functions as will be seen later.
In this case extrapolating was even simpler than in the previous section.
Definition 10.9 A set of variable assignments over {0, 1} with specified numbers
of m 0s and n 1s is called a block and denoted by b m,n .
Example 10.4 The set of all 8 variable assignments for three variable Boolean
functions can be partitioned into the following four blocks:
b 3,0 = {000} b 2,1 = {001, 010, 100} b 1,2 = {011, 101, 110} b 0,3 = {111} .
Definition 10.10 For any Boolean function f let B 0 (f ) and B 1 (f ) denote the sets of
blocks including all variable assignments for which f is equal 0 and 1, respectively.
Example 10.5 Let us consider the following Boolean projection functions:
f (x 3 , x 2 , x 1 ) = x 3 , g (x 3 , x 2 , x 1 ) = x 2 , h (x 3 , x 2 , x 1 ) = x 1 .
Then
B
0 (f ) = { {000} , {001, 010} , {011} }
B
1 (f ) = { {100} , {101, 110} , {111} }
B
0 (g) = { {000} , {001, 100} {101} }
B
1 (g) = { {010} , {011, 110} , {111} }
B
0 (h) = { {000} , {010, 100} , {110} }
B
1 (h) = { {001} , {011, 101} , {111} }
Notice that for each 3-variable Boolean reversible function k the union of B 0 (k)
and B 1 (k) is equal to the set of all 8 Boolean variable assignments. For each of the
component functions of an arbitrary reversible function cardinalities of unions of
their B i sets are the same.