Studies of Boolean functions/terminology

Shortcut

Boolf-term

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

weight The weight of a BF is a fraction between 0 and 1. The weight of a TT is a non-negative integer.

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

dense A dense BF has no gaps before or between the atoms. Its valency and adicity are equal. often called non-degenerate

spread not dense

root The root of a BF is its dense equivalent. The term is also used for the TT of the root BF. It is a binary vector of length 2^valency without repeating patterns.

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

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

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

reverse BF with reversed TT

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

noble TT is noble, iff identical to its twin

patron XOR of twins, a noble TT

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

properties

see Properties of Boolean functions and of truth tables

clan negation and permutation equivalence class partitioned into families and factions

family negation EC

faction permutation EC

splinter intersection of family and faction

tribe Dull TT form tribes, denoted by their consul weight.

super Prefix used for EC of BF extended by complement.

ultra Prefix used for EC of TT extended by half-complement.

foibles

foible The foibles are seven properties, that correspond to the vertices of a Fano plane. (see here for an overview)

- 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

- pretty/ugly foible of a BF, XOR of odd and odious uglyness

- dull/sharp foible of a TT, equal to parity of TT weight sharpness

- obtuse/acute foible of a TT, similar to sharpness acuteness

- polite/rude and smooth/rough foibles of a TT, similar to sharpness and acuteness rudeness and roughness

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

prefect BF ↦ linear BF

sub-prefect BF ↦ senior linear BF (category)

consul TT ↦ linear TT (basically twin prefect)

praetor XOR of left and right half of TT

quaestor XOR of left and reversed right half of TT

principality and dominion juniors corresponding to noble factions

provisional

cluster A cluster contains four or eight factions, that are complements and twins.

federation abandoned term related to clusters

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