View source for Studies of Euler diagrams/clans

{{EuDi}}

Functions in the same [[Equivalence classes of Boolean functions#NP|NP equivalence class]] (clan) have Euler diagrams with the same shape.

The functions in it can be turned into each other with [[Studies of Euler diagrams/transformations|transformations]].<br>
They negate and permute the arguments, i.e. they are signed permutations.

A diagram's symmetry determines the cardinality of the clan, i.e. the number of functions in it.

Let any function have <math>k</math> transformations to itself. Then the diagram's symmetry group has <math>k</math> elements, and the cardinality of the clan is <math>\frac{2^n \cdot n!}{k}</math>.

So the clans with the hightest possible cardinality of <math>2^n \cdot n!</math> are those whose diagrams have no symmetry.<br>
For arity <math>n = 3</math> that would be <math>8 \cdot 6 = 48</math>, but no such clan exists. (The hightest cardinality is 24.)<br>
For arity <math>n = 4</math> that is <math>16 \cdot 24 = 384</math>. 
<small>An example is the clan of {{boolfname|dakota}}. See [[Template:Studies of Euler diagrams/dakota NP table|table]].</small>

<small>Apart from constants, multigrade XOR has the highest symmetry, and thus corresponds to the lowest cardinality of 2.
An example is the that of {{boolflink|selera}}. See [[Template:Studies of Euler diagrams/selera NP table|table]].</small>


==[[Studies of Euler diagrams/dukeli NP|clan of {{boolfname|dukeli}}]]==
{{multiple image
 | align = right | perrow = 2 | total_width = 500
 | image1 = EuDi; dukeli NP 00 00 (0, 1, 2, 3).svg
 | image2 = EuDi; dukeli NP 03 10 (~1, 3, ~0, 2).svg
 | footer = diagrams of {{boolfname|dukeli}} and another function in the same clan
}}

The diagrams are mirror symmetric, so the cardinality is 192. <small>(All 382 diagrams are shown, i.e. both mirror images for each function.)</small>

Compare the transformations between [[Studies of Euler diagrams/transformations#dukeli_pamina|{{boolfname|dukeli}} and {{boolfname|pamina}}]].


==[[Studies of Euler diagrams/NP tables|tables]]==

Each clan can be partitioned into smaller equivalence classes based only on [[Boolf-EC#P|permutation]] (factions) or [[Boolf-EC#N|negation]] (families).<br>
<small>Within the conventions of this project, the factions are rows, while families partition the table in vertical stripes. (They shall be called columns.)</small>

The following table shows the clan of {{boolfname|takate}} {{zhe|30}} and its complement {{boolflink|gilera}} {{zhe|31}}.
&nbsp;&nbsp; <small style="opacity: .5;">(The complements make it an [[Equivalence classes of Boolean functions#NPN|NPN-EC]].)</small><br>

Its contains 24 functions. The columns partition it into 3 families, each with 8 functions.
The rows partition it into 6 factions.<br>
The four rows with mirror symmetric Venn diagrams contain 3, and the other two rows contain 6 functions.<br>
The families always have the same size, while that of the factions can vary.

{{Studies of Euler diagrams/takate NP table}}


The following tables show clans with only one family. 
They contain the 2-ary OR {{zhe|14}} and the 3-ary OR {{zhe|254}}:

{| style="border-collapse: collapse;"
|style="border: 5px solid #efdcce; padding: 15px 30px;"| {{Studies of Euler diagrams/vinona NP table}}
|style="border: 5px solid #efdcce; padding: 15px 30px;"| {{Studies of Euler diagrams/bunese NP table}}
|}


The number of factions is at least 2.
These contain the multigrade XOR {{zhe|22}} and the complement of equality {{zhe|126}}:

{| style="border-collapse: collapse;"
|style="border: 5px solid #efdcce; padding: 15px 30px;"| {{Studies of Euler diagrams/selera NP table}}
|style="border: 5px solid #efdcce; padding: 15px 30px;"| {{Studies of Euler diagrams/foravo NP table}}
|}