fun conv([])=[] |
	conv((l,v)::l1)=if v=0 then conv(l1) else l::conv(l1);
fun el(x,[])=false |
	el(x,l::l1)=if (x=l) then true else el(x,l1);
fun add([],l1)=l1 |
	add(x::l,l1)=if el(x,l1) then add(l,l1) else x::add(l,l1);
fun del1(x,[])=[] |
	del1(x,l::l2)=if x=l then del1(x,l2) else l::del1(x,l2);
fun del([],a)=a |
	del(x::l,a)=del1(x,del(l,a));
fun d([],[])=[] |
	d(v1::l1,v2::l2)=if (v1=v2) then v1::d(l1,l2) else 2::d(l1,l2);
fun dif([],[])=0 |
	dif(v1::l1,v2::l2)=if (v1=v2) then dif(l1,l2) else 1+dif(l1,l2);
fun dif1(l1,l2)=if dif(l1,l2)=1 then d(l1,l2) else [];
fun check(m,[])=[] |
	check(m,m1::l1)=let val c=dif1(m,m1)in if c=[] then check(m,l1) else 
    				 c::check(m,l1) end; 
fun fr([])=([]) |
	fr(m::l)=let val b=check(m,l)in if b=[]
               then fr(l) 
               else( add(b,fr(l))) end;
fun s(x,[])=false |
	s(x,m::l)=(dif(x,m)=1) orelse s(x,l);
fun fr2([],m2)=[] |
	fr2(x::l,m2)=if s(x,m2) then fr2(l,m2) else x::fr2(l,m2);
fun QMC1([],p)=p |
	QMC1(m,p)=let val a=fr(m) in QMC1(a,p@fr2(m,a)) end;
fun eval([],[])= 1 |
	eval(v::l1,m::l2)=if (((v=0) andalso (m=1)) orelse ((v=1) andalso (m=0))) then 0 else eval(l1,l2);
fun zero([],m)=true |
	zero(p::l,m)= eval(p,m)=0 andalso zero(l,m);
fun del2(x,a::b)=if (x=a) then b else a::del2(x,b);
fun ness1(x,p,[])=true |
	ness1(x,p,m::l)= if (eval(x,m)=0) then ness1(x,p,l) else (zero(del2(x,p),m)=false) andalso ness1(x,p,l);
fun ness([],p,m)= [] |
	ness(x::l,p,m)=if ness1(x,p,m) then x else ness(l,p,m);
fun QMC2(p,m)=let val x=ness(p,p,m) in if x=[] then p else QMC2(del2(x,p),m) end;
fun QMCt(x)=let val a=conv(x) in QMC2(QMC1(a,[]),a) end;
fun cs([],n)="" |
	cs(x::y,n)=if x=1 then "x"^Int.toString(n)^cs(y,n+1) else if x=0 then "(-x"^Int.toString(n)^")"^cs(y,n+1) else cs(y,n+1);
fun st([])="0"|
	st(x::[])=cs(x,1) |
	st(x::y)=cs(x,1)^"+"^st(y);
fun QMC(x)=let val a=st(QMCt(x)) in if a="" then "1" else a end;
use "C:\\Program Files\\sml\\src\\smlnj-lib\\Util\\lib-base-sig.sml";
use "C:\\Program Files\\sml\\src\\smlnj-lib\\Util\\lib-base.sml";
use "C:\\Program Files\\sml\\src\\smlnj-lib\\Util\\random-sig.sml";
use "C:\\Program Files\\sml\\src\\smlnj-lib\\Util\\random.sml";
fun add1([])=[] |
	add1(x::l)=[x@[0]]@[x@[1]]@add1(l);
fun gen(0)=[] |
	gen(1)=[[0],[1]] |
    gen(n)=add1(gen(n-1));
fun atv([],n)=[] |
	atv(l::l1,n)=((l, 0)::atv(l1,n+1);
fun grbf(n)=atv(gen(n),0);   (*random boolean function generator*)