Help:=proc(): print(` DNFtoSLP(n,S), Join(s1,s2) `): print(` OneStepQM(S), RandBF(n,K) , Implicants(n,S) `): end: OldHelp:=proc(): print( ` RandTriple(n) , RandDNF(n,m)`): print(`DNFtoBF1(n,d), DNFtoBF(n,d) , SAT(n,c) `): print(` BF(n,SLP), VtoS(i,n), BFn(n,SLP),`): print(` RandSLP(n,K) `): print(`F(i,x,y), EvalB(SL1,L1), nCube(n), `): print(`BFtoDNF1(s), BFtoDNF(S)`): print(`DNFtoSLP1(n,s) `): print(`RenumberTriple(n,T1,c), Marry(n,L1,L2)`): end: with(combinat): t:=true: f:=false: SL1:=[1,2,3,4,[5,1,2],[6,3,4],[10,5,6]]: #F(i,x,y): inputs an integer i, 1<=i<=10 and #logical constants (i.e. true or false) and #outputs the value of the #i-GENUINE 2-variable #Boolean function F:=proc(i,x,y) : if i=1 then x or y: elif i=2 then not x or y : elif i=3 then x or not y : elif i=4 then not x or not y: elif i=5 then x and y: elif i=6 then not x and y : elif i=7 then x and not y : elif i=8 then not x and not y: elif i=9 then (not x and y) or (x and not y): elif i=10 then (not x and not y) or (x and y): else ERROR(`i has to be an integer between 1 and 10 `): fi: end: #EvalB(n,SLP,L1): Inputs a pos. integer n #a "straight line program" SLP and a list #L1 of length n of true and false's (t and f) #outputs the values of the function computed #by this SLP for each of the gates #For example, #EvalB(SL1,[t,f,f,t]); EvalB:=proc(SLP,L1) local n,L2,i,inst: n:=nops(L1): L2:=L1: for i from n+1 to nops(SLP) do inst:=SLP[i]: L2:=[ op(L2), F(inst[1], L2[inst[2]],L2[inst[3]]) ]: od: L2: end: #nCube(n): The set of all n-vectors of t's and f's nCube:=proc(n) local S,s: option remember: if n=0 then RETURN({ [] }): fi: S:=nCube(n-1): { seq( [op(s),t], s in S), seq( [op(s),f], s in S) }: end: #====================================================== #Work from January 27th 2011 #====================================================== #BF(n,SLP): inputs a straight-line program SLP of #n input variables and outputs the Boolean function #(as a set of vectors that yield true) that it computes BF:=proc(n,SLP) local C,S,s: C:=nCube(n): S:={}: for s in C do if EvalB(SLP,s)[-1]=t then S:={op(S),s}: fi: od: S: end: #VtoS(i,n): inputs positive integers i and n # 1<=i<=n and outputs the Boolean function #expressed as a set of n-vectors of {t,f}'s #corresponding to x[i] VtoS:=proc(i,n) local CK,v: CK:=nCube(n-1): #v=[v1, ..., v(n-1)] {seq([op(1..i-1,v),t,op(i..n-1,v)], v in CK )}: end: #BFn(n,SLP): another way to do BF(n,SLP) BFn:=proc(n,SLP) local L,i,inst,nf,a,b,c,C: C:=nCube(n): L:=[ seq(VtoS(i,n),i=1..n) ]: for i from n+1 to nops(SLP) do inst:=SLP[i]: #a is the 2-Boolean function-name (from 1 to 10 using F) #b is the first argument #c is the second argument a:=inst[1]: b:=inst[2]: c:=inst[3]: if a=1 then nf:=L[b] union L[c]: elif a=2 then nf:=(C minus L[b]) union L[c]: elif a=3 then nf:=L[b] union (C minus L[c]): elif a=4 then nf:=(C minus L[b]) union (C minus L[c]): elif a=5 then nf:=L[b] intersect L[c]: elif a=6 then nf:=(C minus L[b]) intersect L[c]: elif a=7 then nf:=L[b] intersect (C minus L[c]): elif a=8 then nf:=(C minus L[b]) intersect (C minus L[c]): elif a=9 then nf:=((C minus L[b]) intersect L[c]) union (L[b] intersect (C minus L[c])): elif a=10 then nf:=((C minus L[b]) intersect (C minus L[c])) union (L[b] intersect L[c]): else ERROR(`i has to be an integer between 1 and 10 `): fi: L:=[op(L),nf]: od: L[nops(L)]: end: RandSLP:=proc(n,K) local L,i,inst: L:=[seq(i,i=1..n)]: for i from n+1 to n+K do inst:=[rand(1..10)(),rand(1..i-1)(),rand(1..i-1)()]: L:=[op(L),inst]: od: L: end: #EH:=(x1,x2,x3,x4)-> (x1 or (not x2) or x3) and #((not x1) or (not x2) or x4); #RandTriple(n): a random 3-element subset of {-n, ,,, ,-1} #union {1, .. n} RandTriple:=proc(n) local ra,S,co,i: co:=rand(0..1): ra:=rand(1..n): S:={seq(ra(),i=1..3)}: {seq(s*(-1)^co(),s in S)}: end: #RandDNF(n,m): inputs pos. integers n and m #and outputs a DNF with n variables (1, ..,n ) #and m clauses, with each clause having three #literal. -i denotes not x[i], and #written as a set of triplets #e.g. {{ 1,-3, 4}, {5,7,-8}} stands for #(x1 AND (not x3) AND x4) OR (x5 and x7 and not x8) RandDNF:=proc(n,m) local i: {seq(RandTriple(n),i=1..m)}: end: #DNFtoBF1(n,d): inputs a pos. integer n and #a clause d (a set of integers) #and evaluates DNFtoBF1:=proc(n,d) local C, i,S,d1: C:=nCube(n): S:=C: for d1 in d do if d1>0 then S:= VtoS(d1,n) intersect S: elif d1<0 then S:=(C minus VtoS(-d1,n)) intersect S: else ERROR(`bad input `): fi: od: S: end: #DNFtoBF(n,d): inputs a pos. integer n and #a DNF d in n variables (in the above format as #a set of triplets) and outputs the Boolean function #it evaluates DNFtoBF:=proc(n,d) local d1,S: S:={}: for d1 in d do S:=S union DNFtoBF1(n,d1): od: S: end: #CNFtoBF1(n,d): inputs a pos. integer n and #a clause d (a set of integers) #and evaluates CNFtoBF1:=proc(n,d) local C, i,S,d1: C:=nCube(n): S:={}: for d1 in d do if d1>0 then S:= VtoS(d1,n) union S: elif d1<0 then S:=(C minus VtoS(-d1,n)) union S: else ERROR(`bad input `): fi: od: S: end: #CNFtoBF(n,d): inputs a pos. integer n and #a CNF d in n variables (in the above format as #a set of triplets) and outputs the Boolean function #it evaluates CNFtoBF:=proc(n,d) local d1,S: S:=nCube(n): for d1 in d do S:=S intersect CNFtoBF1(n,d1): od: S: end: #SAT(n,c): A program to solve a million dollar problem #(unfortunately not poly time) SAT:=proc(n,c) evalb(CNFtoBF(n,c) <>{}): end: #10^(n^100)*(n)^(100*n^100)< < 2^(2^n) #BFtoDNF1(s): inputs a pos. integer #and a Boolean function with a single member # given as the set #of n-tuples that evalue true, and outputs #the subset of {1,2,...,n) union {-1, ..., -n) BFtoDNF1:=proc(s) local tb, i: tb:={}: for i from 1 to nops(s) do if s[i] then tb:=tb union {i}: elif not s[i] then tb:=tb union {-i}: else ERROR(`Input should be a list of true-false`): fi: od: tb: end: #BFtoDNF(S): inputs a pos. integer #and a Boolean function S given as the set #of n-tuples that evalue true, and outputs #a disjunctive normal form for it BFtoDNF:=proc(S) local s: {seq(BFtoDNF1(s) , s in S) }: end: #y1 AND y2 AND y3= (y1 AND y2) AND y3 #DNFtoSLP1(n,s): inputs a single conjunction #written as a set of integres from -n to n #and outputs an SLP just for that DNFtoSLP1:=proc(n,s) local L,i,s1: s1:=convert(s,list): L:=[seq(i,i=1..n)]: if nops(s)<1 then RETURN(FAIL): fi: if nops(s)=1 then if s[1]>0 then RETURN([op(L),[5,s[1],s[1]]]): else RETURN([op(L),[8,-s[1],-s[1]]]): fi: fi: if s1[1]>0 and s1[2]>0 then L:=[op(L), [5,s1[1],s1[2]]]: elif s1[1]<0 and s1[2]>0 then L:=[op(L), [6,-s1[1],s1[2]]]: elif s1[1]>0 and s1[2]<0 then L:=[op(L), [7,s1[1],-s1[2]]]: elif s1[1]<0 and s1[2]<0 then L:=[op(L), [8,-s1[1],-s1[2]]]: else ERROR(`Something is wrong`): fi: for i from 3 to nops(s1) do if s1[i]>0 then L:=[op(L), [5, nops(L),s1[i]] ]: elif s1[i]<0 then L:=[op(L), [7, nops(L),-s1[i]] ]: else ERROR(`Bad input!`): fi: od: L: end: #RenumberTriple(n,T1,c): inputs a single gate #T1 a triple [FunctionNumber,PreviousGate1,PreviousGate2]: #and renames the non-input arguments by adding c to them RenumberTriple:=proc(n,T1,c) local T11: T11:=[T1[1]]: if T1[2]<=n then T11:=[op(T11),T1[2]]: else T11:=[op(T11),T1[2]+c]: fi: if T1[3]<=n then T11:=[op(T11),T1[3]]: else T11:=[op(T11),T1[3]+c]: fi: T11: end: #Marry(n,L1,L2) #Marries SLPs L1 and L2 with n inputs gates #and constructs a new SLP that computes the #OR of their respective outputs Marry:=proc(n,L1,L2) local L,i: L:=L1: for i from n+1 to nops(L2) do L:=[op(L),RenumberTriple(n,L2[i],nops(L1)-n)]: od: [op(L),[1,nops(L1),nops(L)]]: end: #DNFtoSLP(n,S): inputs a DNF in n variables #S and putputs an SLP that computes it: DNFtoSLP:=proc(n,S) local L,i: if S={} then ERROR(`S should be non-empty`): fi: L:=DNFtoSLP1(n,S[1]): for i from 2 to nops(S) do L:=Marry(n,L,DNFtoSLP1(n,S[i])): od: L: end: #Join(s1,s2): determines whether s1 and s2 #two clauses in a DNF can be combined to make #a lower-dimensional clause and either returns #FAIL of finds the union Join:=proc(s1,s2) local a: if nops(s1)<>nops(s2) then RETURN(FAIL): fi: a:=s1 intersect s2: if nops(a)=nops(s1)-1 then if (s1 minus a)[1] + (s2 minus a)[1]=0 then RETURN(a): fi: fi: RETURN(FAIL): end: #OneStepQM(S): Given a set of implicants with the same #size outputs all those implied by them with one #of lower size OneStepQM:=proc(S) local i,j, S1,s1: S1:={}: for i from 1 to nops(S) do for j from i+1 to nops(S) do s1:=Join(S[i],S[j]): if s1<>FAIL then S1:=S1 union {s1}: fi: od: od: S1: end: #RandBF(n,K): a random Boolean function with n variables #and K truth vectors: RandBF:=proc(n,K): randcomb(nCube(n), K): end: #Implicants(n,f): inputs a positive integer n #and a Boolean function f in n variables #(expressed as the set of its truth vectors) #outputs a list whose i-th component are #the i-1 dimensional implicants (and hence having #n-i+1 elements Implicants:=proc(n,S) local L,S1: S1:=S: L:=[S1]: while S1<>{} do S1:=OneStepQM(S1): L:=[op(L),S1]: od: L: end: