Problem 703

[albert]

How can S(3) ever be 35?
The total number of function to select from (B^3 -> B) is 16 and 35 is greater than that !
Here goes a full table of all function B^3 -> B
TTT T
TTT F
TTF T
TTF F
TFT T
TFT F
TFF T
TFF F

FTT T
FTT F
FTF T
FTF F
FFT T
FFT F
FFF T
FFF F

Groetjes Albert

[DJohn]

Each function from B^3 to B maps three inputs to one output. There are 8 possibilities for the input, and a function is specified by giving an output independently for each of them. There are 2^8 = 256 ways of doing this, so there are 256 possible functions. In general, there are 2^(2^n) functions from B^n to B.

For two inputs, there are 16 functions. Here they are:

Code: Select all

A  B   out       A  B   out       A  B   out       A  B   out
0  0   0         0  0   0         0  0   0         0  0   0
0  1   0         0  1   0         0  1   0         0  1   0
1  0   0         1  0   0         1  0   1         1  0   1
1  1   0         1  1   1         1  1   0         1  1   1

A  B   out       A  B   out       A  B   out       A  B   out
0  0   0         0  0   0         0  0   0         0  0   0
0  1   1         0  1   1         0  1   1         0  1   1
1  0   0         1  0   0         1  0   1         1  0   1
1  1   0         1  1   1         1  1   0         1  1   1

A  B   out       A  B   out       A  B   out       A  B   out
0  0   1         0  0   1         0  0   1         0  0   1
0  1   0         0  1   0         0  1   0         0  1   0
1  0   0         1  0   0         1  0   1         1  0   1
1  1   0         1  1   1         1  1   0         1  1   1

A  B   out       A  B   out       A  B   out       A  B   out
0  0   1         0  0   1         0  0   1         0  0   1
0  1   1         0  1   1         0  1   1         0  1   1
1  0   0         1  0   0         1  0   1         1  0   1
1  1   0         1  1   1         1  1   0         1  1   1

[kenbrooker]

For those more conversant in Computer Science than Mathematics, the following translation of
Problem 703 may be helpful --

A k-input binary Truth Table is a map from k input bits (0=False; 1=True) to 1 output bit.
For example, the 2-input binary Truth Tables for the logical AND and XOR functions are:

              x y             xANDy            xXORy
              - -            -------          -------
              0 0               0                0
              0 1               0                1
              1 0               0                1
              1 1               1                0

As a further example, we can demonstrate that three 2-input binary Truth Tables, T, satisfy
the formula T(x, y) AND T(y, xANDy) = 0 for all 2-bit inputs (x, y) as follows:

                             Tables(x, y)
 x, y      [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P]

 0, 0      [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
 0, 1      [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]
 1, 0      [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1]
 1, 1      [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

    z = xANDy                Tables(y, z)
 y, z      [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P]

 0, 0      [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
 1, 0      [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1]
 0, 0      [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
 1, 1      [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

            &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&

                          T(x, y) AND T(y, z)
 x, y,(z)  [A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P]

 0, 0, 0   [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
 0, 1, 0   [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1]
 1, 0, 0   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1]
 1, 1, 1   [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

               Tables A, C & E all zero for a Count = 3

Additionally, there are 2118 4-input binary Truth Tables, T, that satisfy
the formula T(a,b,c,d) AND T( (b,c,d,a) AND (bXORc) ) = 0 
for all 4-bit inputs (a,b,c,d).

How many 20-input binary truth tables, T, satisfy the formula
T(a,b,c, ... t) AND T( (b,c,d, ... t,a) AND (bXORc) ) = 0
for all 20-bit inputs (a,b,c, ... t)?

[kenbrooker]

Does not the following statement of Problem 703 represent a...
Headstart on the problem statement immediately above?

Circular Logic II
Problem 703

Given an integer n, n≥3, let B={false,true} and let Bn be the set of sequences of n values from B.
The function f from Bn to Bn is defined by f(b1…bn)=c1…cn where:

ci=bi+1 for 1≤i<n.
cn=b1AND(b2XORb3), where AND and XOR are the logical AND and exclusive OR operations.
Let S(n) be the number of functions T from Bn to B such that for all x in Bn, T(x) AND T(f(x))=false.
You are given that S(3)=35 and S(4)=2118.

Find S(20). Give your answer modulo 1001001011.