Out[]=
S[S]
Clear[]
In[]:=
SKTruthTable[expr_,{t_,f_}]:=Replace[#,{t1,f0}]&/@(ResourceFunction["CombinatorFixedPoint"][#,"MaxSize"100,"SKGlyphs"{s,k}]&/@Apply[expr[#1][#2]&]/@Tuples[{t,f},2])
In[]:=
TruthTableSearch[n_,{t_,f_}]:=SortBy[First/@GatherBy[#FromDigits[SKTruthTable[#,{t,f}],2]&/@Pick[ResourceFunction["EnumerateCombinators"][n,{s,k}],ParallelMap[AllTrue[MatchQ[0|1]][SKTruthTable[#,{t,f}]]&,ResourceFunction["EnumerateCombinators"][n,{s,k}]]],Last],Last]
In[]:=
ResourceFunction["CombinatorMatches"]
Out[]=
[◼]
CombinatorMatches
Version (latest): 1.0.1
Documentation »
In[]:=
TruthTableSearch[4,{k,s[k]}]
Out[]=
{k[k[s[k]]]0,s[s][s[k]]10,s[s[k]][k]12,s[k[k[k]]]15}
In[]:=
TruthTableSearch[3,{k,s[k]}]
Out[]=
{s[s][k]8,k[k][s]12,k[k[k]]15}
In[]:=
TruthTableSearch[3,{s[k],k}]
Out[]=
{k[k[k]]0,k[k][s]12,s[s][k]14}
TruthTableSearch[3,{s,s[s]}]
Out[]=
{k[k][s]12,k[k[s]]15}
In[]:=
Monitor[Table[TruthTableSearch[n,{s,s[s]}],{n,2,5}],n]
Out[]=
{{s[k]10},{k[k][s]12,k[k[s]]15},{k[k[s[s]]]0,s[k[k][s]]10,s[s[k]][k]12,s[k[k[s]]]15},{s[k[k[s[s]]]]0,s[s[s[k]][k]]10,s[s][s][k][k]12,s[s[k[k[s]]]]15}}
In[]:=
Monitor[Table[TruthTableSearch[n,{s,s[s]}],{n,2,7}],n]
Out[]=
{{s[k]10},{k[k][s]12,k[k[s]]15},{k[k[s[s]]]0,s[k[k][s]]10,s[s[k]][k]12,s[k[k[s]]]15},{s[k[k[s[s]]]]0,s[s[s[k]][k]]10,s[s][s][k][k]12,s[s[k[k[s]]]]15},{s[s[k[k[s[s]]]]]0,s[s[s][s]][s][k]10,s[s][s][s][k][k]12,s[s[s[k[k[s]]]]]15},{s[s[s[k[k[s[s]]]]]]0,s[s[s][s][s]][s][k]10,s[s][s][s][s][k][k]12,s[s[s[s[k[k[s]]]]]]15}}
In[]:=
Monitor[Table[TruthTableSearch[n,{k,k[k]}],{n,2,5}],n]
Out[]=
{{s[k]10},{k[k][s]12,k[k[k]]15},{k[k[k[k]]]0,s[k[k][s]]10,s[s[k]][k]12,s[k[k[k]]]15},{s[s[s]][k][k]0,s[s][s[s[k]]]8,s[s[s[k]][k]]10,s[s][s][k][k]12,s[s[s[s]]][k]14,s[s[k[k[k]]]]15}}
In[]:=
Monitor[Table[TruthTableSearch[n,{k[k],k}],{n,2,5}],n]
Out[]=
{{s[k]10},{k[k[k]]0,k[k][s]12},{s[k[k[k]]]0,s[k[k][s]]10,s[s[k]][k]12,k[k[k[k]]]15},{s[s[k[k[k]]]]0,s[s[s[s]]][k]8,s[s[s[k]][k]]10,s[s][s][k][k]12,s[s][s[s[k]]]14,s[s[s]][k][k]15}}
In[]:=
With[{ttresults=%46},Text[Grid[Table[{{True,Nand,Implies,Not,"",Not,Equal,Nor,Or,Xor,Last,"",First,"",And,False}[[i+1]],Extract[ttresults,Position[ttresults,i][[1,;;2]]][[1]]/.{sCombinatorS,kCombinatorK}},{i,{14,8,2,1,6}}],FrameAll]]]
In[]:=
LeafCount[s[s[s[s][s][s][s][s][s]][s]][k]]
Out[]=
11
In[]:=
Table[Echo@TruthTableSearch[n,{k[k],k}],{n,2,11}]
»
{s[k]10}
»
{k[k[k]]0,k[k][s]12}
»
{s[k[k[k]]]0,s[k[k][s]]10,s[s[k]][k]12,k[k[k[k]]]15}
»
{s[s[k[k[k]]]]0,s[s[s[s]]][k]8,s[s[s[k]][k]]10,s[s][s][k][k]12,s[s][s[s[k]]]14,s[s[s]][k][k]15}
»
{s[s[s]][k][k][s]0,s[s[k[s]][k]][k]3,s[s[s][s]][s][k]10,s[s[s][s[s[k]]]]11,s[s][s][s][k][k]12,s[s][s[s][s][k]]14,s[s[s[s]][k][k]]15}
»
{s[s[s]][s][s][k][k]0,s[s][s][s[s][k]][s]2,s[s[s[s[s][k]][k]]]3,s[s[s[s][s[s[k]]]]]5,s[s[s[s]]][k[k][s]]8,s[s[s][s][s]][s][k]10,s[s[s][s[s[s][s]]]]11,s[s][s][s][s][k][k]12,s[s[s[s[s]]][s]][k]14,s[s[s[s[s]][k][k]]]15}
»
{s[s[s][s[s[s][s]]]][k]0,s[s[s][s][s[s][k]][s]]1,s[s[s[s][s]]][s[s][k]]2,s[s[s[s[s[s]]][s]]][k]3,s[s[s[s][s[s[s][s]]]]]5,s[s[s[s[s][k]][s[k]]]]7,s[s[s[s[s[s[s]]]]]][k]8,s[s][s][k[s[s][s[k]]]]9,s[s[s][s][s][s]][s][k]10,s[s[s][s[s[s][s][s]]]]11,s[s][s][s][s][s][k][k]12,s[s[k[s]][s[s][k]]][k]13,s[s[s[s[s]]][s][s]][k]14,s[s[s[s[s[s]][k][k]]]]15}
»
{s[s[s[s[s][s]][s][s]]][k]0,s[s[s[s[s][s]]][s[s][k]]]1,s[s[s[s]][s[s[s]][s]]][k]2,s[s[s[s][s][s[s[s]]]]][k]3,s[s[s[s][s[s[s][s][s]]]]]5,s[s[s[s][s][s][s[s][k]]]]7,s[s[s[s[s[s][s]][s]]]][k]8,s[s[s[s][s]][s[s]][s[s]]]9,s[s[s[s[s[s][s]][s]]]][s]10,s[s[s][s[s[s][s][s][s]]]]11,s[s[s][s[s[s[s][s]]]]][k]12,s[s[s[s[s[s]]]]][s[s][k]]13,s[s[s[s[s][s[s[s][s]]]]]]14,s[s[s[s[s[s]]][s][s]]][k]15}
»
{s[s[s[s[s][s][s]]][s][s]][k]0,s[s[s[s[s]][s[s[s]][s]]][k]]1,s[s[s]][s[s]][s[s[s[s][s]]]]2,s[s[s[s[s][s][s]][s][s]]][k]3,s[s[s[s[s][s]][s[s]][s[s]]]]4,s[s[s[s[s]][s[s[s[s]]]][s]]]5,s[s[s[s[s]][s[s]][s[s[k]]]]]6,s[s[s[s][s[s[s][k]]][s[k]]]]7,s[s[s[s[s[s][s][s]][s]]]][k]8,s[s[s[s[s]][s]][s[s][s]][s]]9,s[s[s[s[s[s][s][s]][s]]]][s]10,s[s[s[s[s[s][s[s[s][s]]]]]]]11,s[s[s[s[s][s][s]][s]][s]][k]12,s[s[s[s[s[s]]]]][s[s][k[k]]]13,s[s[s[s[s][s[s[s][s][s]]]]]]14,s[s[s[s[s[s[s]]][s][s]]][k]]15}
In[]:=
Out[]=
In[]:=
SKTruthTable[expr_,{t_,f_}]:=Replace[#,{t1,f0}]&/@(ResourceFunction["CombinatorFixedPoint"][#,"MaxSize"100,"SKGlyphs"{s,k}]&/@Apply[expr[#1][#2]&]/@Tuples[{t,f},2])
In[]:=
TruthTableSearch[n_,{t_,f_}]:=SortBy[First/@GatherBy[#FromDigits[SKTruthTable[#,{t,f}],2]&/@Pick[ResourceFunction["EnumerateCombinators"][n,{s,k}],ParallelMap[AllTrue[MatchQ[0|1]][SKTruthTable[#,{t,f}]]&,ResourceFunction["EnumerateCombinators"][n,{s,k}]]],Last],Last]
In[]:=
Table[Echo@TruthTableSearch[n,{k,s[k]}],{n,5}]
»
{k12}
»
{s[k]10}
»
{s[s][k]8,k[k][s]12,k[k[k]]15}
»
{k[k[s[k]]]0,s[s][s[k]]10,s[s[k]][k]12,s[k[k[k]]]15}
»
{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}
Out[]=
{{k12},{s[k]10},{s[s][k]8,k[k][s]12,k[k[k]]15},{k[k[s[k]]]0,s[s][s[k]]10,s[s[k]][k]12,s[k[k[k]]]15},{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}}
In[]:=
In[]:=
Tuples[{1,0},2]
Out[]=
{{1,1},{1,0},{0,1},{0,0}}
In[]:=
Tuples[{0,1},2]
Out[]=
{{0,0},{0,1},{1,0},{1,1}}
In[]:=
{{k12},{s[k]10},{k[k[k]]0,k[k][s]12,s[s][k]14},{s[k[k[k]]]0,s[s][s[k]]10,s[s[k]][k]12,k[k[s[k]]]15},{s[s[k[k[k]]]]0,s[s][k[k[k]]]2,s[s[s[k]][k]]10,s[s[s[k]]][s]11,s[s[s][s]][k]12,s[s][s[s][k]]14,s[k[k[s[k]]]]15}}/.n_Integer:>FromDigits[Reverse[IntegerDigits[#,2,4]]/.{1->0,0->1},2]&[n]
Out[]=
{{k12},{s[k]10},{k[k[k]]15,k[k][s]12,s[s][k]8},{s[k[k[k]]]15,s[s][s[k]]10,s[s[k]][k]12,k[k[s[k]]]0},{s[s[k[k[k]]]]15,s[s][k[k[k]]]11,s[s[s[k]][k]]10,s[s[s[k]]][s]2,s[s[s][s]][k]12,s[s][s[s][k]]8,s[k[k[s[k]]]]0}}
In[]:=
Sort/@%
Out[]=
{{k12},{s[k]10},{k[k[k]]15,k[k][s]12,s[s][k]8},{k[k[s[k]]]0,s[k[k[k]]]15,s[s][s[k]]10,s[s[k]][k]12},{s[k[k[s[k]]]]0,s[s[k[k[k]]]]15,s[s[s[k]][k]]10,s[s][k[k[k]]]11,s[s][s[s][k]]8,s[s[s[k]]][s]2,s[s[s][s]][k]12}}
In[]:=
%33===Sort/@{{k12},{s[k]10},{s[s][k]8,k[k][s]12,k[k[k]]15},{k[k[s[k]]]0,s[s][s[k]]10,s[s[k]][k]12,s[k[k[k]]]15},{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}}
Out[]=
True
{ff,}
{{}}
In[]:=
FromDigits[Reverse[IntegerDigits[#,2,4]]/.{1->0,0->1},2]&[12]
Out[]=
12
In[]:=
ttresults/.n_Integer:>FromDigits[Reverse[IntegerDigits[#,2,4]]/.{1->0,0->1},2]&[n]
In[]:=
In[]:=
Grid[Table[{i,ArrayPlot[{IntegerDigits[i,2,4]},ColorRules{1GrayLevel[.35],0White},MeshTrue,ImageSize50],{False,Nor,"",Not,"",Not,Xor,Nand,And,Equal,Last,Implies,First,"",Or,True}[[i+1]],Extract[ttresults,Position[ttresults,i][[1,;;2]]][[1]]/.{sStyle[s,Black,FontWeight->"SemiBold"],kStyle[k,Black,FontWeight->"SemiBold"]},ResourceFunction["CombinatorTraditionalForm"][Extract[ttresults,Position[ttresults,i][[1,;;2]]][[1]]]},{i,15,0,-1}],FrameAll]