Studies of Euler diagrams/NP tables

From Wikiversity
Jump to navigation Jump to search

dummy

These tables are in category Studies of Euler diagrams; templates; NP tables.

The natural subdivisions of an NP equivalence class are permutation and negation equivalence classes.

These tables show all functions of an NP-EC (hereafter just EC) with the P-ECs as rows and the N-ECs as groups of columns.

The functions are represented by their Zhegalkin indices, and the order of the rows and columns is based on these numbers.
The chosen representative is highlighted in violet, and its name is shown in the header.
The transformations, denoted by number icons, refer to this representative. (Otherwise it has no influence on the table.)

The following table shows the EC of takate (Ж 30) and its complement gilera (Ж 31).
It has three N-ECs, each with 8 functions.
Its six P-ECs contain 3 functions if the Venn diagrams are symmetric, or 6 functions if they are not.

EC 6   takate
W C
24

36

66
2 3 24 &3_3
3

24
(0, 1, 2)
(1, 0, 2)

36
(0, 2, 1)
(2, 0, 1)

66
(1, 2, 0)
(2, 1, 0)
3 3 25 &2_2
2

25
(0, 1, 2)
(1, 0, 2)

37
(0, 2, 1)
(2, 0, 1)

67
(1, 2, 0)
(2, 1, 0)
3 6 26 &2_2
2

26
(0, 1, 2)
(1, 0, 2)

28
(1, 0, 2)
(0, 1, 2)

38
(0, 2, 1)
(2, 0, 1)

52
(2, 0, 1)
(0, 2, 1)

70
(1, 2, 0)
(2, 1, 0)

82
(2, 1, 0)
(1, 2, 0)
4 6 27 &1_1
1

27
(0, 1, 2)
(1, 0, 2)

29
(1, 0, 2)
(0, 1, 2)

39
(0, 2, 1)
(2, 0, 1)

53
(2, 0, 1)
(0, 2, 1)

71
(1, 2, 0)
(2, 1, 0)

83
(2, 1, 0)
(1, 2, 0)
4 3 30 &0_0
0

30
(0, 1, 2)
(1, 0, 2)

54
(0, 2, 1)
(2, 0, 1)

86
(1, 2, 0)
(2, 1, 0)
5 3 31 &1_1
1

31
(0, 1, 2)
(1, 0, 2)

55
(0, 2, 1)
(2, 0, 1)

87
(1, 2, 0)
(2, 1, 0)


mouseovers of Zhegalkin indices

Hovering over the numbers will show a mouseover.
Its first line is the Zhegalkin index in little-endian binary (which corresponds to the algebraic normal form).
The second line is the truth table of the Boolean function.
The screenshot on the right shows a mouseover in the table above.
(The diagram to its right shows how the second line is derived from the first.)


The number icons denote the transformations from the representative to each particular function.
A transformation is a signed permutation, i.e. a negator pattern paired with a permutation — both of which can be represented by a natural number.
While the permutation index numbers are unambiguous, there is some potential confusion about numbering the negator patterns.
Generally it is more useful to refer to which values are negated. (See this 8×6 matrix.)
But functions in the same P-EC have the same negated places in common — which are thus used as row labels in these tables.
To avoid confusion, the icons referring to negated values are round, and those referring to negated places are square.

So each function corresponds to a set of transformations.
To such a set corresponds a set of keyneg indices, a set of valneg indices and a set of perm indices.
P-ECs (rows) have the same set of keyneg indices, and N-ECs (column groups) have the same set of perm indices in common.
The sets of perm indices are cosets of The symmetric group , where is the arity. (See Subgroups of S4.)
The valneg set is shown under each Zhegalkin index. Hovering over it will show a table with the whole set of transformations.

transformations from takate (Ж 30) to tabora (Ж 38)

The representative function of the table above is takate (Ж 30). The hover table is shown for tabora (Ж 38).
Below is shown how the two transformations turn the Euler diagram of the former into (mirrored) Euler diagrams of the latter.

takate
tabora
tabora
hover table

 

 


Often the set of valneg indices of a function contains only a single element.
Two are also common:

There is only one 3-ary EC with three:

Eight are an extreme case. This is very rare:

(This table is wider than most screens. The hover tables on the right can be seen by keeping the mouse on them, and pressing the right arrow key.)