Boolean functions

In[]:=
CombinatorFixedPoint/@Apply[s[s][k][#1][#2]&]/@Tuples[{s[k],k},2]
Out[]=
{s[k],s[k],s[k],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[]:=
SKTruthTable[expr_]:=Replace[#,{s[k]1,k0}]&/@(CombinatorFixedPoint[#,"MaxSize"100]&/@Apply[expr[#1][#2]&]/@Tuples[{s[k],k},2])
In[]:=
Select[EnumerateCombinators[3],AllTrue[MatchQ[0|1]][SKTruthTable[#]]&]
Out[]=
{s[s][k],k[k][s],k[k][k],k[k[k]]}
In[]:=
SKTruthTable/@%
Out[]=
{{1,1,1,0},{1,1,0,0},{1,1,0,0},{0,0,0,0}}
In[]:=
Select[EnumerateCombinators[4],AllTrue[MatchQ[0|1]][SKTruthTable[#]]&]
Out[]=
{s[s][s[k]],s[s[k]][k],s[k][s][k],s[k[k][s]],s[k][k][k],s[k[k][k]],s[k[k[k]]],k[s][s][k],k[s[k][s]],k[s[k]][s],k[s][k][k],k[s[k][k]],k[s[k]][k],k[k][s[s]],k[k[s[k]]],k[k][s[k]],k[k][k[s]],k[k][k[k]]}
In[]:=
SKTruthTable/@%
Out[]=
{{1,0,1,0},{1,1,0,0},{1,1,0,0},{1,0,1,0},{1,1,0,0},{1,0,1,0},{0,0,0,0},{1,0,1,0},{1,0,1,0},{1,0,1,0},{1,0,1,0},{1,0,1,0},{1,0,1,0},{1,1,0,0},{1,1,1,1},{1,1,0,0},{1,1,0,0},{1,1,0,0}}
In[]:=
Union[%]
Out[]=
{{0,0,0,0},{1,0,1,0},{1,1,0,0},{1,1,1,1}}
In[]:=
Union[Select[EnumerateCombinators[5],AllTrue[MatchQ[0|1]][SKTruthTable[#]]&]]
Out[]=
{k[k[k[k][k]]],k[k[k[k][s]]],k[k[k[k]][k]],k[k[k[k]][s]],k[s[k][k[k]]],k[s[k][k[s]]],k[s[k][s[k]]],k[s[k][s[s]]],k[k[k][k][k]],k[k[k][s][k]],k[s[s][k][k]],k[s[s][s][k]],s[k[k[s[k]]]],s[s[k[k[k]]]],s[k[k][k[k]]],s[k[k][k[s]]],s[k[k][s[k]]],s[k[k][s[s]]],s[s[s[k]][k]],s[s[k][k][k]],s[s[k][s][k]],k[k][k[k[k]]],k[k][k[k[s]]],k[k][k[s[k]]],k[k][k[s[s]]],k[k][s[k[k]]],k[k][s[k[s]]],k[k][s[s[k]]],k[k][s[s[s]]],k[k][k[k][k]],k[k][k[k][s]],k[k][k[s][k]],k[k][k[s][s]],k[k][s[k][k]],k[k][s[k][s]],k[k][s[s][k]],k[k][s[s][s]],k[k[k[k]]][k],k[k[k[k]]][s],k[s[k]][k[k]],k[s[k]][k[s]],k[s[k]][s[k]],k[s[k]][s[s]],k[k[k][k]][k],k[k[k][k]][s],k[k[k][s]][k],k[k[k][s]][s],k[s[s][k]][k],k[s[s][k]][s],s[s][k[k[k]]],s[s][k[k][k]],s[s][k[k][s]],s[s][s[s][k]],s[k[k]][k[k]],s[k[s[k]]][k],s[k[s[k]]][s],s[s[k]][s[k]],s[s[s]][k[k]],s[s[s[k]]][s],s[k[s][k]][k],s[k[s][s]][k],s[s[k][k]][s],s[s[k][s]][s],s[s[s][s]][k],k[k][k][k[k]],k[k][s][k[k]],k[s][k[k]][k],k[s][k[s]][k],k[s][s[k]][k],k[s][s[s]][k],k[k[k]][k][k],k[k[k]][k][s],k[k[k]][s][k],k[k[k]][s][s],k[s[s]][k][k],k[s[s]][s][k],s[k][k][s[k]],s[k][s][s[k]],s[k][k[k]][k],s[k][k[s]][k],s[k][s[k]][k],s[k][s[s]][k],s[s][k[k]][s],s[k[k]][k][k],s[s[k]][s][k],k[k][k][k][k],k[k][k][k][s],k[k][s][k][k],k[k][s][k][s],k[s][k][s][k],k[s][s][s][k],s[k][k][s][k],s[k][s][s][k],s[s][k][k][k],s[s][s][k][k]}
In[]:=
Union[SKTruthTable/@%]
Out[]=
{{0,0,0,0},{0,0,1,0},{1,0,1,0},{1,0,1,1},{1,1,0,0},{1,1,1,0},{1,1,1,1}}
In[]:=
Boole[BooleanTable[#[p,q],{p,q}]&/@{And,Or,Nand,Nor,Xor}]
Out[]=
{{1,0,0,0},{1,1,1,0},{0,1,1,1},{0,0,0,1},{0,1,1,0}}
In[]:=
Union[SKTruthTable/@Select[EnumerateCombinators[6],AllTrue[MatchQ[0|1]][SKTruthTable[#]]&]]
Out[]=
{{0,0,0,0},{0,0,1,0},{1,0,0,0},{1,0,1,0},{1,0,1,1},{1,1,0,0},{1,1,1,0},{1,1,1,1}}
In[]:=
Position[SKTruthTable/@Select[EnumerateCombinators[6],AllTrue[MatchQ[0|1]][SKTruthTable[#]]&],{1,0,0,0}]
Out[]=
{{6},{44},{68},{101}}
In[]:=
EnumerateCombinators[6][[6]]
Out[]=
s[s[s[s][s]][s]]
In[]:=
FromDigits[#,2]&/@%264
Out[]=
{0,2,8,10,11,12,14,15}
In[]:=
TruthTableSearch[n_]:=SortBy[First/@GatherBy[#FromDigits[SKTruthTable[#],2]&/@Pick[EnumerateCombinators[n],ResourceFunction["ParallelMapMonitored"][AllTrue[MatchQ[0|1]][SKTruthTable[#]]&,EnumerateCombinators[n]]],Last],Last]
In[]:=
TruthTableSearch[1]
Out[]=
{}
In[]:=
TruthTableSearch[2]
Out[]=
{s[k]10}
In[]:=
TruthTableSearch[3]
Out[]=
{k[k[k]]0,k[k][s]12,s[s][k]14}
In[]:=
TruthTableSearch[4]
Out[]=
{s[k[k[k]]]0,s[s][s[k]]10,s[s[k]][k]12,k[k[s[k]]]15}
In[]:=
TruthTableSearch[5]
Out[]=
{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}
In[]:=
TruthTableSearch[6]
Out[]=
{s[s[s]][k][k][s]0,s[s][s[k[k[k]]]]2,s[s[s]][s][s[k]]8,s[s[s][s]][s][k]10,s[s[s][s][k]][s]11,s[s][s][s][k][k]12,s[s][s[s[k]][k]]14,s[s[k[k]]][s][k]15}
In[]:=
TruthTableSearch[7]
Out[]=
{s[s[s]][s][s][k][k]0,s[s][s[s[k[k[k]]]]]2,s[s[s[s]]][s][s[k]]8,s[s[s]][s[s]][s[s]]10,s[s[s][s][s][k]][s]11,s[s[s][s][s][s]][k]12,s[s[s[s][s]][s]][k]14,s[s][s[k[s]]][k[k]]15}
In[]:=
TruthTableSearch[8]
Out[]=
{s[s[s[s][s][s]]][k][k]0,s[s[s[s[s]]][s]][k[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]][s][k]]11,s[s[s][s]][s][s][s][k]12,s[s[s[s[s]][s]][s]][k]14,s[s[s][s[k[s]]][k[k]]]15}
In[]:=
TruthTableSearch[9]
Out[]=
{s[s[s[s[s][s][s]]][k][k]]0,s[s[s[s][s][s]][s]][k[k]]2,s[k[s[s[s][k[k[k]]]]]][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][s]][s]]11,s[s[s][s][s][s][s][s]][k]12,s[k[s[s[s[s[k]]][s]]]][k]13,s[s[s[s][s][s][s]][s]][k]14,s[s][s[s[s[s]]]][k[k]][s]15}
In[]:=
Length[%]
Out[]=
11
In[]:=
TruthTableSearch[10]
Out[]=
{s[s[s[s[s[s][s][s]]][k][k]]]0,s[s[k[s[s[s][k[k[k]]]]]]][s]1,s[s[s[s[s[s[s][s]]]][k[k]]]]2,s[s][s[s[s[s[k]]][s]]][k[k]]3,s[k[s[s[s][s[k[k[k]]]]]]][k]4,s[s[s]][s[s[s[k]]]][s][k[k]]5,s[s][k[s[s[s][k[k[k]]]][s]]]6,s[s[s[s[s[s][s][s]][s]]]][k]8,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[k[s[s[s[s][s][k]][s]]]][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[]=
Mon 9 Nov 2020 05:32:40GMT-5
In[]:=
TruthTableSearch[11]
Out[]=
{s[s[s[s][s][s]][s][s]][s][k][k]0,s[s[k[s[s[s][s[k[k[k]]]]]]]][s]1,s[s[s[s][s[s[s[s][s]]]][k[k]]]]2,s[s][s[s][s][s[s[k]]]][s][k[k]]3,s[s[s][k[s[s[s][k[k[k]]]]]]][k]4,s[s[s][s[s[s[s[k]]][s]]][k[k]]]5,s[s][s[k[s[s[s][k[k[k]]]]]][k]]6,s[s[s[s[s][k[k[k[k]]]]]][k[s]]]7,s[s[s[s[s[s][s][s][s][s]]]]][k]8,s[s[s[s[s]][s[s[s[k]]]][s]]][k]9,s[s[s[s][s][s][s][s]][s]][s[s]]10,s[s[s]][s[s[s][s][s][s][s]][s]]11,s[s[s][s][s][s][s][s][s][s]][k]12,s[s[s[k[k]]][s[s[s[k]]]][s]][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[]=
Mon 9 Nov 2020 16:57:42GMT-5
In[]:=
Last/@%390
Out[]=
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
In[]:=
Length[%]
Out[]=
16

Enumerations

In[]:=
Select[allres,CombinatorMatches[Last[#]]=!=<||>&]
Out[]=
{{s[s[s]][s][s][s][s],s[s][s][s[s]][s][s],
⋯105⋯
,s[s[s[s]][s[s[s[s]][s]][s]]][
⋯1⋯
[s[s[s]][s[s[s[s]][s]][s]][s[s[s[s]][s[s[s[s]][s]][s]]]][s[s[s[s]][s[s[s[s]][s]][s]]]][s[s[s[s]][s[s[s[s]][s]][s]][s[s[s[s]][s[s[s[s]][s]][s]]]][s[s[s[s]][s[s[s[s]][s]][s]]]]]][s[s[s[s]][s[s[s[s]][s]][s]][s[s[s[s]][s[s[s[s]][s]][s]]]][s[s[s[s]][s[s[s[s]][s]][s]]]]]]][s[s[s[s]][s[s[s[s]][s]][s]][s[s[s[s]][s[s[s[s]][s]][s]]]][s[s[s[s]][s[s[s[s]][s]][s]]]]][
⋯1⋯
]][s[
⋯1⋯
][
⋯1⋯
]][
⋯1⋯
]],s[s[s[s]][s[s[s[s]][s]][s]]][
⋯1⋯
]},
⋯1⋯
}
large output
show less
show more
show all
set size limit...

Visualizations

DAGs