Help:=proc(): print( ` RandTriple(n) , RandDNF(n,m)`): print(`DNFtoBF1(n,d), DNFtoBF(n,d) , SAT(n,c) `): end: OldHelp:=proc(): print(` BF(n,SLP), VtoS(i,n), BFn(n,SLP),`): print(` RandSLP(n,K) `): end: AncientHelp:=proc(): print(`F(i,x,y), EvalB(SL1,L1), nCube(n) `): 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: