The serrations of a Boolean function refine the concept of sharpness, i.e. the parity of the weight of a truth table.
Serration separates the truth table into smaller parts of length .
is the sharpness of part .
For an -ary BF is essentially the sharpness, may be called half sharpness, quarter sharpness, etc.
Illustrations for 3-ary BF: sharpness, half sharpness, quarter sharpness
A BF with adicity has a truth table with period length .
It has meaningful serrations for .
is the BF itself. (Part length is 1.)
is the tautology/contradiction, iff the BF is sharp/blunt. (Part length is the period length of the truth table.)
for is the contradiction. (Part length is at least twice the period length, so each part has even weight.)
The XOR of all serrations of a BF shall be called its serrator. Each BF has a unique serrator, i.e. they form a permutation.
The following images show the initial BF in red, its serrations in yellow, and its serrator in green.
Yellow truth tables in the same row show the same pattern, but on the left the entries have length .
Left: Dark yellow rectangles contain an odd number of red circles. Right: Dark green squares have an odd number of dark yellow squares above them.
0101 0110 1100 0100 (sharp)
0101 1110 1100 0100 (blunt)
1000 0000 (sharp)
0001 0111 (blunt)
1100 0000 (blunt)
The serrator is equal to the initial BF, iff all pairs in the truth table are equal.
0110 1001 (blunt)
The serrator is the complement of the initial BF, iff all pairs in the truth table are unequal.
Serrator permutation
The serrator is a hard property of a BF, i.e. it does not depend on the arity.
The permutation from Zhegalkin indices to those of the serrators is an infinite Walsh permutation.
Its vector is the sequence 1, 3, 4, 11, 16, 36, 64, 139, 256, 528, 1024, 2084, 4096, 8256, 16384, 32907, 65536... = A127804.
The corresponding matrix is upper triangular, with entries on diagonals with different angles. (See this illustration of the transposed matrix.)
The vector of the inverse Walsh permutation is the sequence 1, 3, 4, 10, 16, 36, 64, 136, 256, 528, 1024, 2080, 4096, 8256, 16384, 32896, 65536... = A051437
The following tables show the invertible matrices corresponding to these Walsh permutations.
relationships between the four compression matrices
These images explain relationships between the four compression matrices for Walsh permutations of BF in general.
The matrices used as examples are those of the serrator permutation.
four related matrices
relationships between adjacent rows and columns
matrices corresponding to Sierpinski and Zhegalkin permutation
serrator permutation
compression matrices for arities 1 to 8
arities 1 and 2
arity 1
from T
from Z
to T
to Z
arity 2
from T
from Z
to T
to Z
arities 3 and 4
arity 3
from T
from Z
to T
to Z
arity 4
from T
from Z
to T
to Z
arities 5 and 6
arity 5
from T
from Z
to T
to Z
arity 6
from T
from Z
to T
to Z
arities 7 and 8
arity 7
from T
from Z
to T
to Z
arity 8
from T
from Z
to T
to Z
full permutations for arity 3
from T to T
from T to Z
from Z to T
from Z to Z
inverse of the serrator permutation
compression matrices for arities 1 to 8
arities 1 and 2
arity 1
from T
from Z
to T
to Z
arity 2
from T
from Z
to T
to Z
arities 3 and 4
arity 3
from T
from Z
to T
to Z
arity 4
from T
from Z
to T
to Z
arities 5 and 6
arity 5
from T
from Z
to T
to Z
arity 6
from T
from Z
to T
to Z
arities 7 and 8
arity 7
from T
from Z
to T
to Z
arity 8
from T
from Z
to T
to Z
full permutations for arity 3
from T to T
from T to Z
from Z to T
from Z to Z
The BF that are their own serrator are those with truth tables streched by 2. Their Zhegalkin indices form the Moser–de Bruijn sequenceA000695.
