Properties of truth tables

Studies of Boolean functions
Studies of Boolean functions
not dependent on arity: Properties of Boolean functions
dependent on arity: Properties of truth tables

The number of Boolean functions with arity (short for adicity ) is (Sloane'sA001146).

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

edit

see also: Extended families and clans of Boolean functions

ultra (extension with half-complement)

edit

The two families on the left form a super-family.
The family on the right is a super-family on its own.
Together these two super-families form an ultra-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)

edit

The 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)

edit

An 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

edit

consul (binary Walsh spectrum)

edit

The 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.)

 
sharp family with consuls 0...7
 
dull family with consul 2
(compare 4-ary family with consul 6)
3-ary families with Walsh spectra (integers) and consuls (red backgrounds on the right)

3-ary_Boolean_functions#Walsh spectrum, 4-ary_Boolean_functions#wec

patron

edit

The patron of a truth table is the XOR of itself and its twin. It is a noble.    (3-ary images)

praetor

edit

XOR of left and right half of the TT.    (3-ary images)

quaestor

edit

XOR 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

edit
truth 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.