Jump to content

Families of Boolean functions

From Wikiversity
Studies of Boolean functions

Boolean functions belong to the same family, when they can be transformed into each other by negating arguments.
The size of a family is always a power of two. The maximal size is 2adicity, i.e. the period length of the truth table.
(While the size of faction and clan increases with the chosen arity, the size of a family is fixed.)

The simplest property of a family is its weight, i.e. the number of true entries in each truth table.
An important property is the parity of the weight. Those with odd weight shall be called sharp, those with even weight dull.
(It is the same as the parity of the quaestor weight.)

Sharp families always have the maximal size.
Each member of sharp family has a unique consul, while all members of a dull family have the same consul.
This makes it easy to calculate a family representative for sharp Boolean functions. (For males to be precise.)

A family belongs to a clan (where the arguments are not just negated, but also permuted).
Together with its complement, it forms a super-family. Adding a half-complement forms an ultra-family.
Clans belong to a tribe. Sharp BF form a tribe on their own. The tribe of a dull BF is the binary weight of the consul.

sequences

[edit | edit source]

A227725 is the number of -ary families of size .
A227724 is the number of balanced -ary families of size .
A054724 is the number of -ary families with weight .

super-clans

[edit | edit source]

The following table shows the 46 3-ary families within the 14 super clans. That means, each family is shown in its clan, and together with its complement.
In each matrix a family has a distinct color. Complements have the same base color (RGB or beige). Clans have the same shade (light or dark).
(The number of families in a super-clan is 1, 2, 3 or 6.)

misc.

[edit | edit source]

3-ary partitions: family (46), reverse family (46), super family (30), ultra family (18), family size (4), quaestor weight (5), tribe (5), is sharp (2)