Properties of truth tables
Studies of Boolean functions |
Studies of Boolean functions |
| ||||
The number of Boolean functions with arity (short for adicity ) is ( A001146).
This article is about properties of finite truth tables of Boolean functions, that change with the arity.
simple
edit- weight: number of true places
- sharpness: weight parity sharp: odd weight dull: even weight
subsets
edit
equivalence classes based on similarity
editsee also: Extended families and clans of Boolean functions
ultra (extension with half-complement)
edit
The two families on the left form a super-family. | ||
Each Boolean function has two half-complements. (The truth table is complemented on the left or on the right side.)
A super-family has a unique half-complement. Merging them gives an ultra-family.
As super-clans consist of super-families, they can be extended in the same way.
(Factions do not have a unique half-complement, so it does not seem useful to define ultra-factions.)
ultra-family (negation, complement, half-complement)
editThe functions in an ultra-family have symmetric positions in a hypercube graph (or the related matrix). See matrices.
This family is a complete ultra-family: 1100 1010 (better seen in its matrix)
ultra-clan (negation, permutation, complement, half-complement)
editAn ultra-clan is the merge of a super-clan and its half-complement.
It can also be seen as a merge of ultra-families, that are permutations of each other.
See here for a table of the 39 ultra-families of 4-ary Boolean functions.
partitions into blocks of equal size
editconsul (binary Walsh spectrum)
editThe Walsh spectrum of a TT is its product with a Walsh matrix.
The binary Walsh spectrum of a TT is its product with a binary Walsh matrix, using F2 operations (mod 2).
It is always a Walsh function, and shall be called consul. The term is also used for the integer denoting the Walsh function.
The consul integer is the Walsh index of the prefect of the twin. The consul is essentially the prefect of the twin, but without the negation.
(One could also define a sign for the consul, by using a negated binary Walsh matrix. But the sign would just be the sharpness.)
3-ary families with Walsh spectra (integers) and consuls (red backgrounds on the right) |
tribe | ||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
The consul weight is the binary weight of the consul integer. (E.g. consul 6 has consul weight 2.)
|
3-ary_Boolean_functions#Walsh spectrum, 4-ary_Boolean_functions#wec
patron
editThe patron of a truth table is the XOR of itself and its twin. It is a noble. (3-ary images)
praetor
editXOR of left and right half of the TT. (3-ary images)
quaestor
editXOR of left and reversed right half of the truth table (i.e. of the coordinates in the Hasse matrix) (3-ary images)
principalities and dominions
edittruth tables | Zhegalkin indices | |
---|---|---|
principality | ||
dominion |
A principality is a set of n-ary truth tables whose (n+1)-ary noble equivalents form a faction.
Dominions are closely related to them. The reversed truth tables of the principalities are the Zhegalkin indices of the dominion.
The following table shows the six members of the red principality, which are also shown in the matrices on the right.
A representative of the 4-ary noble faction can be seen in the bottom left corner of this image.
(It is easily seen, that this tetrahedron can be permuted into six different positions.)
3-ary | 4-ary noble | |||
---|---|---|---|---|
TT | Ж | |||
0001 0000 | 8 | 136 | 0000 0001 0001 0000 | 2176 |
0000 0100 | 32 | 160 | 0000 0001 0000 0100 | 8320 |
0001 0100 | 40 | 40 | 0000 0000 0001 0100 | 10240 |
0000 0010 | 64 | 192 | 0000 0001 0000 0010 | 16512 |
0001 0010 | 72 | 72 | 0000 0000 0001 0010 | 18432 |
0000 0110 | 96 | 96 | 0000 0000 0000 0110 | 24576 |
An overview of all 11 3-ary principalities and dominions can be seen here.
Interesting subsets are those with entries on the diagonal and in the top row of the matrix of Zhegalkin indices.