Properties of Boolean functions
Studies of Boolean functions |
| ||||
simple
edit- 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 .
- weight: quotient of true places and all places of the truth table (0 for the contradiction, 1 for the tautology)
subsets
editBelonging to a subset can also be seen as a property.
- 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
editsee also:
- sequences
- examples of extended families and clans
- smallest Zhegalkin index of families, factions and clans
basic (negation and permutation)
editfamily (negation)
editFunctions 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 matrix whose rows (and columns) are the truth tables of -ary functions in the same family. | ||
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)
editFunctions 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)
editFunctions 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)
editsuper-family, super-faction, super-clan |
---|
Each Boolean function has a complement. So have the equivalence classes defined above. super-family (negation, complement)editEvery family has a complement. Together they form a super-family. super-faction (permutation, complement)editEvery faction has a complement. Together they form a super-faction. (Every super-faction contains two factions.) super-clan (negation, permutation, complement)editEvery clan has a complement. Together they form a super-clan. |
partitions into blocks of equal size
editparity, depravity, quadrant
editeven 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 .
images | ||||
---|---|---|---|---|
compare similar images |
prefect
editThe prefect is a way to assign each BF to a linear BF. A linear is assigned to itself. The resulting equivalence class may be called prefecture. (3-ary images)
calculating prefect from Zhegalkin index | |||
---|---|---|---|
|
other
editgender
editGender is based on parity. For any positive arity there are slightly more males than females. See Gender of Boolean functions.