Help:=proc(): print(`Bn(n), N(f,n) , F(i,f,g,n),Xi1(i,n)`): print(`ESL(StraigtLineProgram,NumberofInputs)`): print(`Anc(StraigtLineProgram,NumberofInputs)`): end: #[1,2,3,4,[5,2,1],[1,3,4], [10,6,3]] #Bn(n): inputs a non-negative integer n and ouputs #the set of all 0-1 vectors of length n Bn:=proc(n::nonnegint) local S,i: option remember: if n=0 then RETURN({[]}) fi: S:=Bn(n-1): {seq([op(S[i]),0],i=1..nops(S)), seq([op(S[i]),1],i=1..nops(S))}: end: #not f N:=proc(f,n) Bn(n) minus f: end: #F(i,f,g,n): The i^th non-trivial 2-variable Boolean function #applied to the Boolean functions f and g of n vars #(where Boolean functions are represented but subsets of Bn(n)) # 1<=i <=10 F:=proc(i,f,g,n): if i=1 then f intersect g: elif i=2 then N(f,n) intersect g: elif i=3 then f intersect N(g,n) elif i=4 then N(f,n) intersect N(g,n) elif i=5 then f union g: elif i=6 then N(f,n) union g: elif i=7 then f union N(g,n) elif i=8 then N(f,n) union N(g,n) elif i=9 then (N(f,n) intersect g) union (N(g,n) intersect f) elif i=10 then N((N(f,n) intersect g) union (N(g,n) intersect f),n) else ERROR(`The first argument must be between 1 and 10 (inclusive)`): fi: end: Xi1:=proc(i,n) local S1,S2,i1,i2: S1:=Bn(i-1): S2:=Bn(n-i): {seq(seq([op(S1[i1]),1,op(S2[i2])],i1=1..nops(S1)),i2=1..nops(S2))}: end: #ESL(Li1,n): inputs a straight line program Li1 and a pos. integer #n and outputs the Boolean function computed by Li1 ESL:=proc(Li1,n) local f,g,Lc,Li1l,Li1r: option remember: if nops(Li1)<=n then return Xi1(nops(Li1),n): fi: Lc:=Li1[nops(Li1)]: Li1l:=[op(1..Lc[2],Li1)]: Li1r:=[op(1..Lc[3],Li1)]: F(Lc[1],ESL(Li1l,n),ESL(Li1r,n),n): end: Anc:=proc(Li1,n) local Lc, Li1a,Li1b,Mother,Father: if nops(Li1)<=n then return {nops(Li1)}: fi: Lc:=Li1[nops(Li1)]: Mother:=[op(1..Lc[2],Li1)]: Father:=[op(1..Lc[3],Li1)]: Anc(Mother,n) union Anc(Father,n): end: