Jump to content

Studies of Euler diagrams/dukeli NP

Add links
From Wikiversity

dummy


    (0, 1, 2, 3)
    (3, 2, 1, 0)
    (~0, ~2, ~1, ~3)
    (~3, ~1, ~2, ~0)
above the mirrored diagrams of dukeli (Ж 11809)   (all circles point to inside)
below those of its complement (Ж 11808)   (all circles point to outside)

The NP equivalence class of dukeli contains Boolean functions.
It contains the complement of each function, which makes it a complete NPN equivalence class.

There are 16 · 24 = 384 Euler diagrams. As they are mirror symmetric, each function is described by two of them.

Each Euler diagram is denoted by a signed permutation of four elements. They are abbreviated by pairs .

The truth table corresponding to diagram (m, n) can be found in row m of matrix n in this file.

The obvious way to show them in a 16×24 matrix can be seen in valneg.
Functions in the same column are in the same negation equivalence class

    (~1, 2, 3, ~0)   (Ж 2766)
    (3, ~1, 2, ~0)   (Ж 11278)
values 0 and 1 negated
(red and green circle point to outside, blue and yellow to inside)

A more intuitive arrangement is shown in keyneg, where the rows have negated places (instead of negated values) in common.
This adds the feature, that functions in the same row are in same permutation equivalence class.

hover table showing the two transformations from dukeli to netuno (Ж 3971)
      (~1, ~2, 3, 0)   (Ж 3971)
      (~3, ~1, 2, 0)   (Ж 14387)
places 0 and 1 negated
(two cirles on the left point to outside, those on the right to inside)

But in the last arrangement the rows and columns forming the same equivalence class are not next to each other.
This problem is solved in ordered.

That arrangement still contains duplicates, because it shows all possible Euler diagrams.
A similar one without duplicates is the following, where the functions are represented by their Zhegalkin indices:

W C
2290
2291
8398
8399
11278
11279
16558
16559
18958
18959
25138
25139
6 24 2290 &2_2
2
 2290
(0, 3, 2, 1)
(1, 2, 3, 0)
 3972
(1, 2, 3, 0)
(0, 3, 2, 1)
 2292
(1, 3, 2, 0)
(0, 2, 3, 1)
 3970
(0, 2, 3, 1)
(1, 3, 2, 0)
 8398
(0, 3, 1, 2)
(2, 1, 3, 0)
 13200
(2, 1, 3, 0)
(0, 3, 1, 2)
 8412
(2, 3, 1, 0)
(0, 1, 3, 2)
 13186
(0, 1, 3, 2)
(2, 3, 1, 0)
 11278
(0, 2, 1, 3)
(3, 1, 2, 0)
 14640
(3, 1, 2, 0)
(0, 2, 1, 3)
 11532
(3, 2, 1, 0)
(0, 1, 2, 3)
 14386
(0, 1, 2, 3)
(3, 2, 1, 0)
 16558
(1, 3, 0, 2)
(2, 0, 3, 1)
 21904
(2, 0, 3, 1)
(1, 3, 0, 2)
 16570
(2, 3, 0, 1)
(1, 0, 3, 2)
 21892
(1, 0, 3, 2)
(2, 3, 0, 1)
 18958
(1, 2, 0, 3)
(3, 0, 2, 1)
 22864
(3, 0, 2, 1)
(1, 2, 0, 3)
 19210
(3, 2, 0, 1)
(1, 0, 2, 3)
 22612
(1, 0, 2, 3)
(3, 2, 0, 1)
 25138
(2, 1, 0, 3)
(3, 0, 1, 2)
 25924
(3, 0, 1, 2)
(2, 1, 0, 3)
 25378
(3, 1, 0, 2)
(2, 0, 1, 3)
 25684
(2, 0, 1, 3)
(3, 1, 0, 2)
7 24 2291 &2_2
2
 2293
(0, 3, 2, 1)
(1, 2, 3, 0)
 3971
(1, 2, 3, 0)
(0, 3, 2, 1)
 2291
(1, 3, 2, 0)
(0, 2, 3, 1)
 3973
(0, 2, 3, 1)
(1, 3, 2, 0)
 8413
(0, 3, 1, 2)
(2, 1, 3, 0)
 13187
(2, 1, 3, 0)
(0, 3, 1, 2)
 8399
(2, 3, 1, 0)
(0, 1, 3, 2)
 13201
(0, 1, 3, 2)
(2, 3, 1, 0)
 11533
(0, 2, 1, 3)
(3, 1, 2, 0)
 14387
(3, 1, 2, 0)
(0, 2, 1, 3)
 11279
(3, 2, 1, 0)
(0, 1, 2, 3)
 14641
(0, 1, 2, 3)
(3, 2, 1, 0)
 16571
(1, 3, 0, 2)
(2, 0, 3, 1)
 21893
(2, 0, 3, 1)
(1, 3, 0, 2)
 16559
(2, 3, 0, 1)
(1, 0, 3, 2)
 21905
(1, 0, 3, 2)
(2, 3, 0, 1)
 19211
(1, 2, 0, 3)
(3, 0, 2, 1)
 22613
(3, 0, 2, 1)
(1, 2, 0, 3)
 18959
(3, 2, 0, 1)
(1, 0, 2, 3)
 22865
(1, 0, 2, 3)
(3, 2, 0, 1)
 25379
(2, 1, 0, 3)
(3, 0, 1, 2)
 25685
(3, 0, 1, 2)
(2, 1, 0, 3)
 25139
(3, 1, 0, 2)
(2, 0, 1, 3)
 25925
(2, 0, 1, 3)
(3, 1, 0, 2)
7 24 2298 &3_3
3
 2298
(0, 3, 2, 1)
(1, 2, 3, 0)
 3980
(1, 2, 3, 0)
(0, 3, 2, 1)
 2300
(1, 3, 2, 0)
(0, 2, 3, 1)
 3978
(0, 2, 3, 1)
(1, 3, 2, 0)
 8430
(0, 3, 1, 2)
(2, 1, 3, 0)
 13232
(2, 1, 3, 0)
(0, 3, 1, 2)
 8444
(2, 3, 1, 0)
(0, 1, 3, 2)
 13218
(0, 1, 3, 2)
(2, 3, 1, 0)
 11790
(0, 2, 1, 3)
(3, 1, 2, 0)
 15152
(3, 1, 2, 0)
(0, 2, 1, 3)
 12044
(3, 2, 1, 0)
(0, 1, 2, 3)
 14898
(0, 1, 2, 3)
(3, 2, 1, 0)
 16622
(1, 3, 0, 2)
(2, 0, 3, 1)
 21968
(2, 0, 3, 1)
(1, 3, 0, 2)
 16634
(2, 3, 0, 1)
(1, 0, 3, 2)
 21956
(1, 0, 3, 2)
(2, 3, 0, 1)
 19982
(1, 2, 0, 3)
(3, 0, 2, 1)
 23888
(3, 0, 2, 1)
(1, 2, 0, 3)
 20234
(3, 2, 0, 1)
(1, 0, 2, 3)
 23636
(1, 0, 2, 3)
(3, 2, 0, 1)
 29234
(2, 1, 0, 3)
(3, 0, 1, 2)
 30020
(3, 0, 1, 2)
(2, 1, 0, 3)
 29474
(3, 1, 0, 2)
(2, 0, 1, 3)
 29780
(2, 0, 1, 3)
(3, 1, 0, 2)
8 24 2299 &1_1
1
 2301
(0, 3, 2, 1)
(1, 2, 3, 0)
 3979
(1, 2, 3, 0)
(0, 3, 2, 1)
 2299
(1, 3, 2, 0)
(0, 2, 3, 1)
 3981
(0, 2, 3, 1)
(1, 3, 2, 0)
 8445
(0, 3, 1, 2)
(2, 1, 3, 0)
 13219
(2, 1, 3, 0)
(0, 3, 1, 2)
 8431
(2, 3, 1, 0)
(0, 1, 3, 2)
 13233
(0, 1, 3, 2)
(2, 3, 1, 0)
 12045
(0, 2, 1, 3)
(3, 1, 2, 0)
 14899
(3, 1, 2, 0)
(0, 2, 1, 3)
 11791
(3, 2, 1, 0)
(0, 1, 2, 3)
 15153
(0, 1, 2, 3)
(3, 2, 1, 0)
 16635
(1, 3, 0, 2)
(2, 0, 3, 1)
 21957
(2, 0, 3, 1)
(1, 3, 0, 2)
 16623
(2, 3, 0, 1)
(1, 0, 3, 2)
 21969
(1, 0, 3, 2)
(2, 3, 0, 1)
 20235
(1, 2, 0, 3)
(3, 0, 2, 1)
 23637
(3, 0, 2, 1)
(1, 2, 0, 3)
 19983
(3, 2, 0, 1)
(1, 0, 2, 3)
 23889
(1, 0, 2, 3)
(3, 2, 0, 1)
 29475
(2, 1, 0, 3)
(3, 0, 1, 2)
 29781
(3, 0, 1, 2)
(2, 1, 0, 3)
 29235
(3, 1, 0, 2)
(2, 0, 1, 3)
 30021
(2, 0, 1, 3)
(3, 1, 0, 2)
5 24 2754 &3_3
3
 2754
(1, 2, 3, 0)
(0, 3, 2, 1)
 2756
(0, 3, 2, 1)
(1, 2, 3, 0)
 3234
(1, 3, 2, 0)
(0, 2, 3, 1)
 3236
(0, 2, 3, 1)
(1, 3, 2, 0)
 8898
(2, 1, 3, 0)
(0, 3, 1, 2)
 8912
(0, 3, 1, 2)
(2, 1, 3, 0)
 12426
(2, 3, 1, 0)
(0, 1, 3, 2)
 12440
(0, 1, 3, 2)
(2, 3, 1, 0)
 11298
(3, 1, 2, 0)
(0, 2, 1, 3)
 11552
(0, 2, 1, 3)
(3, 1, 2, 0)
 14346
(3, 2, 1, 0)
(0, 1, 2, 3)
 14600
(0, 1, 2, 3)
(3, 2, 1, 0)
 17572
(2, 0, 3, 1)
(1, 3, 0, 2)
 17584
(1, 3, 0, 2)
(2, 0, 3, 1)
 20620
(2, 3, 0, 1)
(1, 0, 3, 2)
 20632
(1, 0, 3, 2)
(2, 3, 0, 1)
 19012
(3, 0, 2, 1)
(1, 2, 0, 3)
 19264
(1, 2, 0, 3)
(3, 0, 2, 1)
 22540
(3, 2, 0, 1)
(1, 0, 2, 3)
 22792
(1, 0, 2, 3)
(3, 2, 0, 1)
 25168
(3, 0, 1, 2)
(2, 1, 0, 3)
 25408
(2, 1, 0, 3)
(3, 0, 1, 2)
 25648
(3, 1, 0, 2)
(2, 0, 1, 3)
 25888
(2, 0, 1, 3)
(3, 1, 0, 2)
6 24 2755 &1_1
1
 3235
(1, 2, 3, 0)
(0, 3, 2, 1)
 3237
(0, 3, 2, 1)
(1, 2, 3, 0)
 2755
(1, 3, 2, 0)
(0, 2, 3, 1)
 2757
(0, 2, 3, 1)
(1, 3, 2, 0)
 12427
(2, 1, 3, 0)
(0, 3, 1, 2)
 12441
(0, 3, 1, 2)
(2, 1, 3, 0)
 8899
(2, 3, 1, 0)
(0, 1, 3, 2)
 8913
(0, 1, 3, 2)
(2, 3, 1, 0)
 14347
(3, 1, 2, 0)
(0, 2, 1, 3)
 14601
(0, 2, 1, 3)
(3, 1, 2, 0)
 11299
(3, 2, 1, 0)
(0, 1, 2, 3)
 11553
(0, 1, 2, 3)
(3, 2, 1, 0)
 20621
(2, 0, 3, 1)
(1, 3, 0, 2)
 20633
(1, 3, 0, 2)
(2, 0, 3, 1)
 17573
(2, 3, 0, 1)
(1, 0, 3, 2)
 17585
(1, 0, 3, 2)
(2, 3, 0, 1)
 22541
(3, 0, 2, 1)
(1, 2, 0, 3)
 22793
(1, 2, 0, 3)
(3, 0, 2, 1)
 19013
(3, 2, 0, 1)
(1, 0, 2, 3)
 19265
(1, 0, 2, 3)
(3, 2, 0, 1)
 25649
(3, 0, 1, 2)
(2, 1, 0, 3)
 25889
(2, 1, 0, 3)
(3, 0, 1, 2)
 25169
(3, 1, 0, 2)
(2, 0, 1, 3)
 25409
(2, 0, 1, 3)
(3, 1, 0, 2)
5 12 2760 &4_4
4
 2760
(0, 3, 2, 1)
(1, 2, 3, 0)
 3240
(0, 2, 3, 1)
(1, 3, 2, 0)
 8928
(0, 3, 1, 2)
(2, 1, 3, 0)
 12456
(0, 1, 3, 2)
(2, 3, 1, 0)
 11808
(0, 2, 1, 3)
(3, 1, 2, 0)
 14856
(0, 1, 2, 3)
(3, 2, 1, 0)
 17632
(1, 3, 0, 2)
(2, 0, 3, 1)
 20680
(1, 0, 3, 2)
(2, 3, 0, 1)
 20032
(1, 2, 0, 3)
(3, 0, 2, 1)
 23560
(1, 0, 2, 3)
(3, 2, 0, 1)
 29248
(2, 1, 0, 3)
(3, 0, 1, 2)
 29728
(2, 0, 1, 3)
(3, 1, 0, 2)
6 12 2761 &0_0
0
 3241
(0, 3, 2, 1)
(1, 2, 3, 0)
 2761
(0, 2, 3, 1)
(1, 3, 2, 0)
 12457
(0, 3, 1, 2)
(2, 1, 3, 0)
 8929
(0, 1, 3, 2)
(2, 3, 1, 0)
 14857
(0, 2, 1, 3)
(3, 1, 2, 0)
 11809
(0, 1, 2, 3)
(3, 2, 1, 0)
 20681
(1, 3, 0, 2)
(2, 0, 3, 1)
 17633
(1, 0, 3, 2)
(2, 3, 0, 1)
 23561
(1, 2, 0, 3)
(3, 0, 2, 1)
 20033
(1, 0, 2, 3)
(3, 2, 0, 1)
 29729
(2, 1, 0, 3)
(3, 0, 1, 2)
 29249
(2, 0, 1, 3)
(3, 1, 0, 2)
7 12 2766 &2_2
2
 2766
(0, 3, 2, 1)
(1, 2, 3, 0)
 3246
(0, 2, 3, 1)
(1, 3, 2, 0)
 8946
(0, 3, 1, 2)
(2, 1, 3, 0)
 12474
(0, 1, 3, 2)
(2, 3, 1, 0)
 12066
(0, 2, 1, 3)
(3, 1, 2, 0)
 15114
(0, 1, 2, 3)
(3, 2, 1, 0)
 17652
(1, 3, 0, 2)
(2, 0, 3, 1)
 20700
(1, 0, 3, 2)
(2, 3, 0, 1)
 20292
(1, 2, 0, 3)
(3, 0, 2, 1)
 23820
(1, 0, 2, 3)
(3, 2, 0, 1)
 29520
(2, 1, 0, 3)
(3, 0, 1, 2)
 30000
(2, 0, 1, 3)
(3, 1, 0, 2)
8 12 2767 &2_2
2
 3247
(0, 3, 2, 1)
(1, 2, 3, 0)
 2767
(0, 2, 3, 1)
(1, 3, 2, 0)
 12475
(0, 3, 1, 2)
(2, 1, 3, 0)
 8947
(0, 1, 3, 2)
(2, 3, 1, 0)
 15115
(0, 2, 1, 3)
(3, 1, 2, 0)
 12067
(0, 1, 2, 3)
(3, 2, 1, 0)
 20701
(1, 3, 0, 2)
(2, 0, 3, 1)
 17653
(1, 0, 3, 2)
(2, 3, 0, 1)
 23821
(1, 2, 0, 3)
(3, 0, 2, 1)
 20293
(1, 0, 2, 3)
(3, 2, 0, 1)
 30001
(2, 1, 0, 3)
(3, 0, 1, 2)
 29521
(2, 0, 1, 3)
(3, 1, 0, 2)
Retrieved from "https://en.wikiversity.org/w/index.php?title=Studies_of_Euler_diagrams/dukeli_NP&oldid=2474398"