Hard properties of Boolean functions

Studies of Boolean functions

**Properties of Boolean functions**
Hard	not dependent on arity
Soft	dependent on arity

Shortcuts

simple

valency: number of relevant arguments (i.e. the number of circles needed to draw an Euler diagram, especially for a blightless BF)
adicity: Atoms are numbered from 0. The adicity of a BF is its biggest atom plus 1. The period length of its truth table $2^{adicity}$ .
weight: quotient of true places and all places of the truth table (0 for the contradiction, 1 for the tautology)

subsets

Belonging to a subset can also be seen as a property.

linear: Walsh functions and their complements
seal: conjunctions of linears

dense: no gaps before or between the atoms, i.e. valency = adicity
balanced: same number of true and false places, i.e. weight = 0.5

monotonic: no true place under false place (when places are arranged in a Hasse diagram) (counted by Dedekind numbers)

equivalence classes based on similarity

basic (negation and permutation)

family (negation)

Functions can be turned into each other by negating inputs.

The 10 (exactly) 2-ary Boolean functions form three families, whose representative functions are AND, OR and XOR. (See this table of 2-ary functions, where equivalents are in the same row.)

The lexicographically smallest truth tables are encoded in A227722 = 0, 1, 3, 5, 6, 7, 15, 17, 18...

family matrix
A family matrix is a symmetric binary $2^{n}\times 2^{n}$ matrix whose rows (and columns) are the truth tables of $n$ -ary functions in the same family.
family of 3-ary functions, at the bottom the 8×8 family matrix	family matrix of a 4-ary function, containing each function twice	A family matrix is a bitwise XOR table with integers replaced by binary values.
See also: Family matrices of Boolean functions (Commons) Each file in 4-ary Boolean functions; BEC (24 × 16×16) contains 24 family matrices.

faction (permutation)

Functions can be turned into each other by permuting inputs.
While families and clans can be self-complementary, factions can not. (Therefore the number of factions is always even.)

clan (negation, permutation)

Functions can be turned into each other by negating and permuting inputs.

The lexicographically smallest truth tables are encoded in A227723 = 0, 1, 3, 6, 7, 15...

super (extension with complement)

super-family, super-faction, super-clan

Each Boolean function has a complement. So have the equivalence classes defined above.
Those defined here are the merge of two complements.

super-family (negation, complement)

Every family has a complement. Together they form a super-family.
This family is a complete super-family: 1110 0001

super-faction (permutation, complement)

Every faction has a complement. Together they form a super-faction. (Every super-faction contains two factions.)

super-clan (negation, permutation, complement)

Every clan has a complement. Together they form a super-clan.
This family is a complete super-clan: 1110 1000

parity and depravity

quadrants
even evil (0)	even odious (2)
odd evil (1)	odd odious (3)

The parity and depravity of a Boolean function are based on the first and last place of its truth table.
It is odd (even), iff the first place is true (false). Its Zhegalkin index is also odd (even).
It is odious (evil), iff the last place is true (false). Its Zhegalkin index has odd (even) binary weight.
It is ugly, iff parity and depravity are different (i.e. iff the quadrant is 1 or 2).
The quadrant is an integer 0...3, and calculated as $parity+2\cdot depravity$ .

images
quandrants	ugly	odd	odious	Ugly, odd and odious are the three foibles not dependent on arity.
compare similar images

prefect

The prefect is a way to assign each BF to a linear BF. A linear is assigned to itself. (3-ary images)

calculating prefect from Zhegalkin index
Ж 123 to prefect 5	Ж 38 to prefect ¬6	Ж 142 to prefect ¬7	The yellow matrix has the pattern of a XAND matrix.
Ж 123 to prefect 5	Ж 38 to prefect ¬6	Ж 142 to prefect ¬7	The possible results are the linear functions.