3-ary Boolean functions

From Wikiversity
Jump to: navigation, search
Created by mate2code.

There are 2^{2^{3}} = 256 3-ary Boolean functions, like set operations or logical connectives.

This Venn diagram 0000 0001, representing the intersection of 3 sets, or the conjunction of 3 statements respectively,
gives an example of a 3-ary Boolean function.

Contents


Actual arity [edit]

Not all of the 256 3-ary functions look really new. The 16 2-ary functions and their rotations are also among them.

218 functions in 32 secs are truly 3-ary:

0000 0001        0001 1001
2*8 = 16     6*8 = 48
ggbec O		 0001 0110        0001 1111
2*8 = 16     6*8 = 48
ggbec O		 0110 1001
1*2 = 2
ggbec E0		 0001 1110
3*8 = 24
ggbec E1		 0101 0011
3*8 = 24
ggbec E2		 0000 1001
6*4 = 24
ggbec E2		 Venn 1000 0001.svg        Venn 0001 0111.svg
2*4 = 8     1*8 = 8
ggbec E3



30 functions in 9 secs are binary:
0110 0110        0001 0001
3*2 = 6     6*4 = 24
ggbec E0        ggbec E1
6 functions in 3 secs are unary:
0000 1111
3*2 = 6
ggbec E0
Contradiction and tautology are nullary:
0000 0000
2*1 = 2
ggbec E0


Equivalence classes [edit]

See: Equivalence classes of Boolean functions

The set of 256 functions can be parted into various equivalence classes.
The most basic way to do that are the 46 small equivalence classes (secs). Functions belong to the same sec, when they can be expressed by each other by negating arguments. There are 3 arguments that can be negated, so there can be up to 2^{3} = 8 different functions in a sec:

A sec with 8 different functions:
1000 0000, 0100 0000, 0010 0000, 0001 0000, 0000 1000, 0000 0100, 0000 0010, 0000 0001
    
A sec with only 2 different functions:
1001 0110, 0110 1001


Big equivalence classes [edit]

Compare: Big equivalence classes of 4-ary Boolean functions

When binarily colored cubes can be transformed into each other by mirroring and rotation, they are essentially the same.
The corresponding Boolean functions are often called equivalent and belong to the same big equivalence class (bec).
There are 1 + 1 + 3 + 3 + 6 + 3 + 3 + 1 + 1 = 22 essentially different cubes and corresponding becs.

The following sortable table (in the collapsed box) shows the 22 becs.
The default order is that of the smallest numerical values of the binary strings. Sorting by column # brings back this default order.
The numbers in column weight are the hamming weights of the functions, i.e. the number of ones in the binary strings.
Column sec tells the number of secs in the bec, which are shown in column SEC.
Column f tells the number of functions in the bec.
The functions are shown in column F, with the numerically smallest one of each sec highlighted.
becs with an entry in column sona are related to subgroups of nimber addition.
The entry in column ggbec denotes the greatest big equivalence class (ggbec) the bec belongs to.
The nonlinearity of all functions in the bec is shown in column nonlin.
To sort by more than one column you can hold the shift-key and than click the other sort buttons. *


The numerical values of all infinite bit strings with a finite non-zero number of ones
can be ordered in an infinite array with the following features:

  • The entries of each row are ordered by size and correspond to functions in the same bec.
  • The entries in the first column are ordered by size.

This array contains all positive integers.
The gray index numbers shown on the left are an enumeration of big equivalence classes of n-ary Boolean functions that is independent of n.

These are the 255 entries of this array that correspond to 3-ary Boolean functions:

 1:         1,   2,   4,   8,  16,  32,  64, 128
 2:         3,   5,  10,  12,  17,  34,  48,  68,  80, 136, 160, 192
 3:         6,   9,  18,  20,  33,  40,  65,  72,  96, 130, 132, 144
 4:         7,  11,  13,  14,  19,  21,  35,  42,  49,  50,  69,  76,  81,  84, 112, 138, 140, 162, 168, 176, 196, 200, 208, 224
 5:        15,  51,  85, 170, 204, 240
 6:        22,  41,  73,  97, 104, 134, 146, 148
 7:        23,  43,  77, 113, 142, 178, 212, 232
 8:        24,  36,  66, 129
 9:        25,  26,  28,  37,  38,  44,  52,  56,  67,  70,  74,  82,  88,  98, 100, 131, 133, 137, 145, 152, 161, 164, 193, 194
10:        27,  29,  39,  46,  53,  58,  71,  78,  83,  92, 114, 116, 139, 141, 163, 172, 177, 184, 197, 202, 209, 216, 226, 228
11:        30,  45,  54,  57,  75,  86,  89,  99, 101, 106, 108, 120, 135, 147, 149, 154, 156, 166, 169, 180, 198, 201, 210, 225
12:        31,  47,  55,  59,  79,  87,  93, 115, 117, 143, 171, 174, 179, 186, 205, 206, 213, 220, 234, 236, 241, 242, 244, 248
13:        60,  90, 102, 153, 165, 195
14:        61,  62,  91,  94, 103, 110, 118, 122, 124, 155, 157, 167, 173, 181, 185, 188, 199, 203, 211, 217, 218, 227, 229, 230
15:        63,  95, 119, 175, 187, 207, 221, 238, 243, 245, 250, 252
16:       105, 150
17:       107, 109, 121, 151, 158, 182, 214, 233
18:       111, 123, 125, 159, 183, 190, 215, 222, 235, 237, 246, 249
19:       126, 189, 219, 231
20:       127, 191, 223, 239, 247, 251, 253, 254
21:       255


Walsh spectrum [edit]

The Boolean function \scriptstyle (1,0,1,0,0,1,1,0)
has the Walsh spectrum \scriptstyle (4,2,0,-2,0,2,0,2)[1]
and the binary Walsh spectrum \scriptstyle (0,1,0,1,0,1,0,1).

The Walsh spectrum of a Boolean function is the product of its binary string (as a row vector) with a Walsh matrix.
The first entry of the Walsh spectrum is the functions digit sum, and all entries have the same parity.
In the expandable boxes in the following chapter the Walsh spectra of the same sec (which differ only in the signs of their entries) are always shown in the same file.

The Walsh spectra of complementary functions sum up to \scriptstyle (8,0,0,0,0,0,0,0,). [2]


Further the binary Walsh spectra are always shown by the red squares in the background. They are always rows of a binary Walsh matrix - or in other terms exclusive disjunctions of unnegated arguments.

The functions with odd digit sum, which make up ggbec O, have each binary Walsh spectrum one time in every sec.

The functions with even digit sum, which make up the other four ggbecs, have always the same binary Walsh spectrum in the same sec:

\scriptstyle \oplus() = 0000 0000 in ggbec E0
\scriptstyle \oplus(A) = 0101 0101     or     \scriptstyle \oplus(B) = 0011 0011     or     \scriptstyle \oplus(C) = 0000 1111        in ggbec E1
\scriptstyle \oplus(A,B) = 0110 0110     or     \scriptstyle \oplus(A,C) = 0101 1010     or     \scriptstyle \oplus(B,C) = 0011 1100        in ggbec E2
\scriptstyle \oplus(A,B,C) = 0110 1001 in ggbec E3


Greatest big equivalence classes [edit]

16x16 matrix like octeract Hasse diagram.svg

This matrix shows the 256 functions arranged in a way similar to the Hasse diagram, which is an octeract graph.
(The respective matrix for 2-ary Boolean functions is this one.)
The colors indicate the five ggbecs, as shown in the following table.
All 3-ary functions in the same ggbec have the same nonlinearity. (Which is not the case e.g. for the 4-ary functions.)


O
nonlinearity 1		   E0  
nonlinearity 0		   E1  
nonlinearity 2		   E2  
nonlinearity 2		   E3  
nonlinearity 2
by bec

Venn 0000 0001.svg        Venn 0001 1001.svg
2*8 = 16     6*8 = 48

Venn 0001 0110.svg        Venn 0001 1111.svg
2*8 = 16     6*8 = 48		 by bec

Venn 0110 0110.svg        Venn 0110 1001.svg
3*2 = 6     1*2 = 2

Venn 0000 1111.svg        Venn 0000 0000.svg
3*2 = 6     2*1 = 2		 by bec

Venn 0001 0001.svg
6*4 = 24

Venn 0001 1110.svg
3*8 = 24		 by bec

Venn 0000 1001.svg
6*4 = 24

Venn 0101 0011.svg
3*8 = 24		 Venn 1000 0001.svg        Venn 0001 0111.svg
2*4 = 8     1*8 = 8
by ggsec by ggsec by ggsec by ggsec



ggbec O with 128 functions


ggbec O ordered according to bec

8 * 8 = 64 functions:

Boolean functions like 1110 0110.svg
Loupe light.svg
 Boolean functions like 1111 1110.svg
Loupe light.svg
Boolean functions like 1100 0010.svg
Loupe light.svg
 Boolean functions like 1101 1010.svg
Loupe light.svg
Boolean functions like 1010 0100.svg
Loupe light.svg
 Boolean functions like 1011 1100.svg
Loupe light.svg
Boolean functions like 1000 0000.svg
Loupe light.svg
 Boolean functions like 1001 1000.svg
Loupe light.svg



8 * 8 = 64 functions:

Boolean functions like 1111 1000.svg
Loupe light.svg
 Boolean functions like 1110 1001.svg
Loupe light.svg
Boolean functions like 1010 1000.svg
Loupe light.svg
 Boolean functions like 1110 1100.svg
Loupe light.svg
Boolean functions like 1100 1000.svg
Loupe light.svg
 Boolean functions like 1110 1010.svg
Loupe light.svg
Boolean functions like 0110 1000.svg
Loupe light.svg
 Boolean functions like 1110 0000.svg
Loupe light.svg





ggbec E0 with 16 functions


ggbec E0 ordered according to bec

3 * 2 = 6 functions:

Boolean functions like 1100 0011.svg
Loupe light.svg
Boolean functions like 1010 0101.svg
Loupe light.svg
Boolean functions like 1001 1001.svg
Loupe light.svg



3 * 2 = 6 functions:

Boolean functions like 1010 1010.svg
Loupe light.svg
Boolean functions like 1100 1100.svg
Loupe light.svg
Boolean functions like 1111 0000.svg
Loupe light.svg



2 functions:

Boolean functions like 1001 0110.svg
Loupe light.svg



2 * 1 = 2 functions:

Boolean function 0000 0000.svg
Loupe light.svg
 Boolean function 1111 1111.svg
Loupe light.svg





ggbec E1 with 48 functions


ggbec E1 ordered according to 'bec'

6 * 4 = 24 functions:

Boolean functions like 1110 1110.svg
Loupe light.svg
Boolean functions like 1100 0000.svg
Loupe light.svg
 Boolean functions like 1111 1010.svg
Loupe light.svg
Boolean functions like 1010 0000.svg
Loupe light.svg
 Boolean functions like 1111 1100.svg
Loupe light.svg
Boolean functions like 1000 1000.svg
Loupe light.svg



3 * 8 = 24 functions:

Boolean functions like 1010 1001.svg
Loupe light.svg
Boolean functions like 1100 1001.svg
Loupe light.svg
Boolean functions like 1110 0001.svg
Loupe light.svg





ggbec E2 with 48 functions


ggbec E2 ordered according to bec

6 * 4 = 24 functions:

Boolean functions like 1111 0110.svg
Loupe light.svg
Boolean functions like 1000 0010.svg
Loupe light.svg
 Boolean functions like 1101 1110.svg
Loupe light.svg
Boolean functions like 1000 0100.svg
Loupe light.svg
 Boolean functions like 1011 1110.svg
Loupe light.svg
Boolean functions like 1001 0000.svg
Loupe light.svg



3 * 8 = 24 functions:

Boolean functions like 1110 0100.svg
Loupe light.svg
Boolean functions like 1011 1000.svg
Loupe light.svg
Boolean functions like 1100 1010.svg
Loupe light.svg





ggbec E3 with 16 functions


Boolean functions like 1000 0001.svg
Loupe light.svg

 Boolean functions like 0111 1110.svg
Loupe light.svg
Boolean functions like 1110 1000.svg
Loupe light.svg





Monotone functions [edit]

The right Hasse diagram in the following file shows the 20 monotonic Boolean functions with 3 variables.
The descriptions show, when the mouse is moved over the diagram:

contradiction A and B and C A and B A and C B and C (A and B) or (A and C) (A and B) or (B and C) (A and C) or (B and C) A B C (A or B) and (A or C) and (B or C) <====> (A and B) or (A and C) or (B and C) (A or B) and (A or C) (A or B) and (B or C) (A or C) and (B or C) A or B A or C B or C A or B or C tautology
In the linked files the monotonic functions are always in the top right position.



Subgroups of nimber addition [edit]

See: Subgroups of nimber addition#Z23

16 secs with in all 8 + 7*4 + 7*2 + 1 = 51 functions are related to subgroups of nimber addition:

These matrices describe equivalence relations.
       
1000 0000 1100 0000 1010 0000 1000 1000 1000 0010 1000 0100 1001 0000 1000 0001 1010 1010 1100 1100 1111 0000 1100 0011 1010 0101 1001 1001 1001 0110 1111 1111
These cubes correspond to the matrices' top lines. In the linked files they are always in the bottom left position.

References [edit]

  1. ↑ Compare Figure 1 in Walsh Spectrum Computations Using Cayley Graphs, by W. J. Townsend and M. A. Thornton
  2. ↑ Compare Property 1 (page 3 of the PDF) in The spectral test of the Boolean function linearity by P. Porwik
Retrieved from "http://en.wikiversity.org/w/index.php?title=3-ary_Boolean_functions&oldid=911618"