Studies of Boolean functions/terminology
(Redirected from Studies of Euler diagrams/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. 2adicity is the required TT length, or the period length of the infinite truth table.
The term arity is used where a finite truth table is needed. E.g. can be shown as 3-ary0000 0011
or as 4-ary0000 0011 0000 0011
.
(But the term arity may linger for a while, where valency or adicity shold be used.)
- atom Atoms are also called sets or arguments of a BF. what is usually shown by a circle and labeled A, B, C...
- dense There are no gaps before or between the atoms. Valency and adicity are equal. often called non-degenerate
- spread not dense
- 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 3valency.
A segment has a dimension, namely the number of zeros in its ternary label. The relationships between segments that differ in only one digit are important:
|
- spot cell of an Euler diagram defined as segment with dimension 0 The number of spots in a Venn diagram is 2valency.
- 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 2n 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
- (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)
- gentle set of TTs is gentle iff identical to set of twins
- foible The foibles are seven properties, that correspond to the vertices of a Fano plane. Most important are odd and odious.
- evil/odious foible of a BF, equal to last digit of TT odiousness also called depravity BF is evil/odious iff Ж has even/odd weight