Studies of Boolean functions/terminology

• (Boolean) function, BF      usually meant as BF with infinite arity and periodic truth table      similar to Boolean expression

• truth table, TT      usually meant as a truth table of finite length, determined by an arity

• valency ≤ adicity ≤ arity
  • Valency is the number of arguments actually used. It is the number of circles in the Euler diagram.
  • Adicity follows from the biggest atom. 2^adicity is the required TT length, or the period length of the infinite truth table.
  • The term arity is used in two slightly different ways:
    • arity n as an argument (e.g. of a class method) to get a finite truth table of length $2^{n}$   E.g. $B\land C$ can be shown as 3-ary 0000 0011 or as 4-ary 0000 0011 0000 0011.
    • arity n as a shorthand for $adicity\leq n$   (as in: the 16 2-ary Boolean functions)
    • (For a while there may also be a third way, namely the erroneous use instead of valency or adicity.)

• atom      Atoms are also called sets or arguments of a BF.      what is usually shown by a circle and labeled A, B, C...

• atomvals      the vector of atoms of a BF

• root      A root BF has no gaps before or between the atoms. Its valency and adicity are equal.      often called non-degenerate      (The term dense might be more intuitive.)

root and atomvals
A Boolean function is determined by its root and its atomvals. It is a root, iff there are no gaps before or between the atoms. (The atomvals are consecutive integers starting from 0, or they are empty.) Every BF has a root, but there is a small ambiguity: as a BF: its equivalent with gapless atomvals as a TT: binary vector of length 2valency without repeating patterns

• spread      not root

• segment      geometric element of an Euler diagram, e.g. its cells and the walls between them      The number of segments in a Venn diagram is 3^valency.

dimension of a segment

A segment has a dimension, namely the number of zeros in its ternary label. (From the perspective of Euler diagrams the term is counter-intuitive, because it corresponds to the hypercube, rather than to the cross polytope. For the hypersplits it is used in the same way.) The relationships between segments that differ in only one digit are important: Another segment with a 0 in the differing place is a superior. (Points are superior to lines, lines to areas, etc.) Another segment with + or − in the differing place is an inferior. Another segment with the opposite sign in the differing place is a neighbor. 2D example kinide Cell 4 is a gapspot. 3D example medusa

• spot      cell of an Euler diagram      defined as segment with dimension 0      The number of spots in a Venn diagram is 2^valency.

• fullspot      corresponds to true place in TT

• gapspot      corresponds to false place in TT, but necessary for geometrically sound Euler diagram

• link      connection between neighboring spots, i.e. wall between cells      defined as segment with dimension 1

• border      set of links that belong to the same atom, i.e. all walls of the same color

• split      set without the notion of inside and outside      usually the same as a partition into two blocks

• hypersplit      generalization of a split      partitions space into 2ⁿ orthants

• filtrate      reduction of a BF to a subset of its atoms, i.e. what remains when some circles are removed from the Euler diagram

• bundle      part of an Euler diagram that is connected by crossing borders     see e.g. decompose, multi-bundle 3-2-2-1, 4-ary bundles

• blighted      arity can be reduced      bloated or blotted      (blight, blightless)

• bloated      some arguments are equal or complementary to each other      (bloat, bloatless)

• blotted      some arguments are equal or complementary to niverse or empty set      (blot, blotless)

• transformation      signed permutation that turns elements of the same clan into each other

• clan      negation and permutation equivalence class      partitioned into families and factions

• family      negation equivalence class

• faction      permutation equivalence class

• cluster      A cluster contains four or eight factions, that are complements and twins. (category)

• (Zhegalkin) twin      Zhegalkin index interpreted as TT of the same length      (E.g. all bits true and only left bit true are always twins, because the Zhegalkin index of the tautology is 1.)

• Zhegalkin index, Ж      non-negative integer identifying a Boolean function      related to algebraic normal form

• representative      some Boolean function that represents its whole equivalence class      typically the smallest Zhegalkin index of a clan

• junior (senior)      Boolean functions of arity n−1 are junior to those of arity n (and those of arity n+1 are senior)     

• junarity (senarity)      arity − 1 (arity + 1)

• noble      TT is noble, iff identical to its twin

• gentle      set of TTs is gentle, iff identical to set of twins

foibles

• foible      The foibles are seven properties, that correspond to the vertices of a Fano plane. Most important are odd and odious.

• even/odd      foible of a BF, equal to first digit of TT      oddness also called parity

• evil/odious      foible of a BF, equal to last digit of TT      odiousness also called depravity      BF is odious, iff Ж has odd weight

• ugly      foible of a BF, XOR of odd and odious      uglyness

• blunt/sharp      foible of a BF, equal to parity of TT weight      sharpness

• obtuse/acute      foible of a BF, similar to sharpness      acuteness

• rude and rough      foibles of a BF, similar to sharpness and acuteness      rudeness and roughness

• female/male      BF is male, iff its root is sharp.      gender

• quadrant    =    parity + 2 · depravity    ∈ {0, 1, 2, 3}

• reverse    BF with reversed TT

general terms

These words are sometimes used in variable names.

• recto and verso    inside and outside of a set   (see also split)

• powers of two and factorial

$n$	$2^{n}$	$2^{2^{n}}$	$n!$
paltry	plenty	plethora	galore