“Flipped” Boolean functions
“Flipped” Boolean functions
In[]:=
CombinatorFixedPoint/@Apply[s[s][k][#1][#2]&]/@Tuples[{k,s[k]},2]
Out[]=
{k,s[k],s[k],s[k]}
In[]:=
EnumerateCombinators[3]
Out[]=
{s[s][s],s[s[s]],s[s][k],s[s[k]],s[k][s],s[k[s]],s[k][k],s[k[k]],k[s][s],k[s[s]],k[s][k],k[s[k]],k[k][s],k[k[s]],k[k][k],k[k[k]]}
In[]:=
SKTruthTableFlipped[expr_]:=Replace[#,{s[k]0,k1}]&/@(CombinatorFixedPoint[#,"MaxSize"100]&/@Apply[expr[#1][#2]&]/@Tuples[{k,s[k]},2])
In[]:=
TruthTableSearchFlipped[n_]:=SortBy[First/@GatherBy[#FromDigits[SKTruthTableFlipped[#],2]&/@Pick[EnumerateCombinators[n],ResourceFunction["ParallelMapMonitored"][AllTrue[MatchQ[0|1]][SKTruthTableFlipped[#]]&,EnumerateCombinators[n]]],Last],Last]
In[]:=
TruthTableSearchFlipped[1]
Out[]=
{k12}
In[]:=
TruthTableSearchFlipped[2]
Out[]=
{s[k]10}
In[]:=
TruthTableSearchFlipped[3]
Out[]=
{s[s][k]8,k[k][s]12,k[k[k]]15}
In[]:=
TruthTableSearchFlipped[4]
Out[]=
{k[k[s[k]]]0,s[s][s[k]]10,s[s[k]][k]12,s[k[k[k]]]15}
In[]:=
TruthTableSearchFlipped[5]
Out[]=
{s[k[k[s[k]]]]0,s[s[s[k]]][s]2,s[s][s[s][k]]8,s[s[s[k]][k]]10,s[s][k[k[k]]]11,s[s[s][s]][k]12,s[s[k[k[k]]]]15}
Note that standard variable elimination gives 6 for And
In[]:=
TruthTableSearchFlipped[6]
Out[]=
{s[s[k[k]]][s][k]0,s[s[s][s][k]][s]2,s[s][s[s[k]][k]]8,s[s[s][s]][s][k]10,s[s][s[k[k[k]]]]11,s[s][s][s][k][k]12,s[s[s]][s][s[k]]14,s[s[s]][k][k][s]15}
In[]:=
TruthTableSearchFlipped[7]
Out[]=
{s[s][s[k[s]]][k[k]]0,s[s[s][s][s][k]][s]2,s[s[s[s][s]][s]][k]8,s[s[s]][s[s]][s[s]]10,s[s][s[s[k[k[k]]]]]11,s[s[s][s][s][s]][k]12,s[s[s[s]]][s][s[k]]14,s[s[s]][s][s][k][k]15}
In[]:=
TruthTableSearchFlipped[8]
Out[]=
{s[s[s][s[k[s]]][k[k]]]0,s[s[s]][s[s[s]][s][k]]2,k[s[s[s][k[k[k]]]][s]]5,s[s[s[s[s]][s]][s]][k]8,s[s[s][s]][s[s]][s][s]10,s[s[s[s[s]]][s]][k[k]]11,s[s[s][s]][s][s][s][k]12,s[s[s][s[s[s][s]]]][k]14,s[s[s[s][s][s]]][k][k]15}
In[]:=
Now
Out[]=
In[]:=
TruthTableSearchFlipped[9]
Out[]=
{s[s][s[s[s[s]]]][k[k]][s]0,s[s[s]][s[s[s][s][s]][s]]2,s[k[s[s[s[s[k]]][s]]]][k]4,k[s[s[s[s]][s]][k[k[k]]]]5,s[s[s[s][s][s][s]][s]][k]8,s[s[s[s][s][s]][s]][s[s]]10,s[s[s[s][s][s]][s]][k[k]]11,s[s[s][s][s][s][s][s]][k]12,s[k[s[s[s][k[k[k]]]]]][k]13,s[s[s[s[s[s][s][s]]]]][k]14,s[s[s[s[s][s][s]]][k][k]]15}
In[]:=
Now
Out[]=
In[]:=
TruthTableSearchFlipped[10]
Out[]=
{s[s][s[s[s[s[s]][s]]]][k[k]]0,s[s[s]][s[s[s][s[s[s]]]][s]]2,s[s][s[s[s[s[k]]][s]]][k[k]]3,s[k[s[s[s[s][s][k]][s]]]][k]4,s[s[s]][s[s[s[k]]]][s][k[k]]5,s[s[k[s[s[s][k[k[k]]]]]]][s]7,s[s[s[s[s[s][s]]][s]][s]][k]8,s[s][k[s[s[s][k[k[k]]]][s]]]9,s[s][s[s[s][s]][s[s]]][s][s]10,s[s[s[s[s[s[s][s]]]][k[k]]]]11,s[s[s[s[s][s][s]][s]][s]][k]12,s[k[s[s[s][s[k[k[k]]]]]]][k]13,s[s[s[s[s[s][s][s]][s]]]][k]14,s[s[s[s[s[s][s][s]]][k][k]]]15}
In[]:=
Now
Out[]=
In[]:=
TruthTableSearchFlipped[11]
Out[]=
{s[s[s][s[s[s[s[s]][s]]]][k[k]]]0,s[s[s[s[s][k[k[k[k]]]]]][k[s]]]1,s[s[s]][s[s[s][s][s][s][s]][s]]2,s[s][s[s][s][s[s[k]]]][s][k[k]]3,s[s[s[k[k]]][s[s[s[k]]]][s]][k]4,s[s[s][s[s[s[s[k]]][s]]][k[k]]]5,s[s[s[s[s]][s[s[s[k]]]][s]]][k]6,s[s[k[s[s[s][s[k[k[k]]]]]]]][s]7,s[s[s[s][s][s][s][s][s]][s]][k]8,s[s][s[k[s[s[s][k[k[k]]]]]][k]]9,s[s[s[s][s][s][s][s]][s]][s[s]]10,s[s[s[s][s[s[s[s][s]]]][k[k]]]]11,s[s[s][s][s][s][s][s][s][s]][k]12,s[s[s][k[s[s[s][k[k[k]]]]]]][k]13,s[s[s[s[s[s][s][s][s][s]]]]][k]14,s[s[s[s][s][s]][s][s]][s][k][k]15}
In[]:=
Now
Out[]=
In[]:=
TruthTableSearchFlipped[12]
Out[]=
$Aborted
Now
In[]:=
In[]:=
SortBy[First/@GatherBy[Flatten[allcases],Last],Last]
Out[]=
{k[k[s[k]]]0,s[s[s[s[s][k[k[k[k]]]]]][k[s]]]1,s[s[s[k]]][s]2,s[s][s[s[s[s[k]]][s]]][k[k]]3,s[k[s[s[s[s[k]]][s]]]][k]4,k[s[s[s][k[k[k]]]][s]]5,s[s[s[s[s]][s[s[s[k]]]][s]]][k]6,s[s[k[s[s[s][k[k[k]]]]]]][s]7,s[s][k]8,s[s][k[s[s[s][k[k[k]]]][s]]]9,s[k]10,s[s][k[k[k]]]11,k12,s[k[s[s[s][k[k[k]]]]]][k]13,s[s[s]][s][s[k]]14,k[k[k]]15}
Searching for Z
Searching for Z
In[]:=
CombinatorFixedPoint[s[k[s]][k][f][g][x]]
Out[]=
f[g[x]]
In[]:=
Select[EnumerateCombinators[3],CombinatorFixedPoint[#[f][g][x],"MaxSize"100]===f[g[x]]&]
Out[]=
{}
In[]:=
Select[EnumerateCombinators[4],CombinatorFixedPoint[#[f][g][x],"MaxSize"100]===f[g[x]]&]
Out[]=
{s[k[s]][k]}
In[]:=
Select[EnumerateCombinators[5],CombinatorFixedPoint[#[f][g][x],"MaxSize"100]===f[g[x]]&]
Out[]=
{}
In[]:=
Select[EnumerateCombinators[6],CombinatorFixedPoint[#[f][g][x],"MaxSize"100]===f[g[x]]&]
Out[]=
{s[s][k[k]][k[s]],s[k[s]][k][s][k],s[k[s]][k[k][s]],s[k[s]][k[k][k]],s[k[k][s][s]][k],s[k[k[s][s]]][k],s[k[k[s]][s]][k],s[k[k[s][k]]][k],s[k[k[s]][k]][k],s[k[k][k][s]][k],k[s][s][k[s]][k],k[s[k[s]]][s][k],k[s[k[s]][k]][s],k[s[k[s]][k]][k],k[s[k[s]]][k][k],k[s][k][k[s]][k]}
Searching for T
Searching for T
In[]:=
With[{z=s[k[s]][k]},s[z[z][s]][k[k]]]
Out[]=
s[s[k[s]][k][s[k[s]][k]][s]][k[k]]
In[]:=
LeafCount[%]
Out[]=
12
In[]:=
CombinatorFixedPoint[With[{z=s[k[s]][k]},s[z[z][s]][k[k]]][f][y][x]]
Out[]=
f[x][y]
In[]:=
Select[EnumerateCombinators[3],CombinatorFixedPoint[#[f][y][x],"MaxSize"100]===f[x][y]&]
Out[]=
{}
In[]:=
Select[EnumerateCombinators[4],CombinatorFixedPoint[#[f][y][x],"MaxSize"100]===f[x][y]&]
Out[]=
{}
In[]:=
Select[EnumerateCombinators[5],CombinatorFixedPoint[#[f][y][x],"MaxSize"100]===f[x][y]&]
Out[]=
{}
In[]:=
Select[EnumerateCombinators[6],CombinatorFixedPoint[#[f][y][x],"MaxSize"100]===f[x][y]&]
Out[]=
{}
Searching for Z
Searching for Z
Z[f][g][x] = f[g[x]]
Z[f][g][x] = f[g[x]]
Parallel Innermost ? Is it /. ?
Parallel Innermost ? Is it /. ?
Is /. parallel outermost ?