Hard properties of Boolean functions

Studies of Boolean functions

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

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

see also:

• sequences
• examples of extended families and clans
• smallest Zhegalkin index of families, factions and clans

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.
			The possible results are the linear functions.

legion and cohort

examples for 1001 0000
	3-ary	4-ary	result
legion			{0, 4}
cohort			{0, 3, 4, 7}

gender and honesty

These binary properties seem to be related. Apparently there are no dishonest male BF.

gender

Gender is based on parity. For any positive arity there are slightly more males than females. See Gender of Boolean functions.

honesty

The XOR of all members of a family is either the tautology or the contradiction. Where it is the tautology, the BF is honest. Most BF are.