Jump to content

Integer sequences related to Boolean functions

From Wikiversity
Studies of Boolean functions


number of equivalence classes

[edit | edit source]

See also .../clans.

name equivalent under maximum size sequence 0 1 2 3 4 5
family neg A000231 2 3 7 46 4336 134281216
splinter intersection of family and faction TBA7 2 4 14 184 51564
faction perm A003180 = 2 · A000612 2 4 12 80 3984 37333248
great faction complementary and partner factions A003180(n) / 4 for n > 0 1 1 3 20 996 9333312
clan neg, perm A000616 2 3 6 22 402 1228158
super-family neg, comp (A000231TBA1) / 2 + A001320 1 2 5 30 1973 57805981
super-clan neg, perm, comp (A000616A000721) / 2 + A000610 1 2 4 14 206 533617


by weight

[edit | edit source]

A054724 number of families by weight
A039754 number of clans by weight

balanced

[edit | edit source]
1 2 3 4 5
families balanced TBA1 (central values of A054724) 1 3 14 870 18796230
self-complementary A001320 1 3 14 240 63488
clans balanced A000721 (central values of A039754) 1 2 6 74 169112
self-complementary A000610 1 2 6 42 4094

representatives of equivalence classes

[edit | edit source]

A227722 (families) and A227723 (clans) show smallest values corresponding to truth tables. Which Boolean function an integer represents, depends on the arity.

In the following the representative is always the smallest Zhegalkin index.

self-complementary

[edit | edit source]

Balanced families and clans can contain their own complements.

The sequence for clans is a subsequence of the one for families. All entries are even.

misc.

[edit | edit source]

A211344 is the -ary truth table of

A227724 is the number of balanced n-ary families of size
A227725 is the number of -ary families of size
A051502 is the number of -ary families of maximal size

A000371 is the number of truly -ary functions   (number of nondegenerate Boolean functions of variables)

Monotonic: A000372 (Dedekind numbers) counts functions, A003182 counts clans (which are probably the same as factions)

0 1 2 3 4
male Sloane'sA246418 1 3 13 159 33337
female Sloane'sA246537 1 1 3 97 32199