print(`This is PIE, a Maple package written by the`); print(`Experimental Math class taught by Dr. Z during`); print(`Spring 2011.`); with(combinat): #==================================================================== Help := proc() if nargs=0 then print(`contains the following procedures:`); print(`AND1(C1,C2,n), AND(L,n) , PIE(L), PIEdnf(L,n) `); print(`PIEdnfF(L,n) `): elif nargs=1 and args[1]=PIE then print(`PIE(L):`); print(`Inputs a list of sets, L, and outputs the number`); print(`of elements in their union `); print(`For example, try:`); print(`PIE([{1,3},{2,3}])`); elif nargs=1 and args[1]=PIEdnf then print(`PIEdnf(L,n): inputs a DNF (with our format as a set`): print(`of sets) and a pos. integer n, and outputs the`): print(`the number of truth vectors (in the truth table`): print(`divided by 2^n (if the ans. 1 it is a tautology)`): print(`For example, try:`): print(`PIEdnf({{1,2},{-3}},3);`): elif nargs=1 and args[1]=PIEdnfF then print(`PIEdnfF(L,n): faster version of PIEdnf(L,n)`): print(`inputs a DNF (with our format as a set`): print(`of sets) and a pos. integer n, and outputs the`): print(`the number of truth vectors (in the truth table`): print(`divided by 2^n (if the ans. 1 it is a tautology)`): print(`For example, try:`): print(`PIEdnf({{1,2},{-3}},3);`): elif nargs=1 and args[1]=AND1 then print(`AND1(C1,C2,n):`); print(`Inputs two clauses, C1 and C2, in n variables (expressed`); print(`as sets of integers from the set {-n,...,-1,1,...,n}) finds`); print(`their AND`); elif nargs=1 and args[1]=AND then print(`AND(L,n): inputs a set of clauses and`): print(`finds their AND`): print(`For example, try:`): print(`AND({{1,3},{2,3},{-1,4}},4);`): fi; end: #==================================================================== PIE := proc(L) local co,i,S,s,m; m := nops(L); co := add(nops(L[i]),i=1..m); for i from 2 to m do S := choose(L,i); #print(S); co := co + (-1)^(i-1)*add(nops(`intersect`(op(s))),s in S); od; RETURN(co); end: #==================================================================== AND1 := proc(C1,C2,n) local C,i; C := C1 union C2; for i from 1 to n do if member(i,C) and member(-i,C) then RETURN(0); fi; od; RETURN(C); end: #====================start stuff done on Monday, Feb. 21, 2011============== #AND(L,n): inputs a set of clauses and #finds their AND AND:=proc(L,n) local i,L1: if nops(L)=1 then RETURN(L[1]): fi: L1:=L[1]: for i from 2 to nops(L) do L1:=AND1(L1,L[i],n): if L1=0 then RETURN(0): fi: od: L1: end: #PIEdnf(L,n): A fast version of PIEdnf(L,n) #quits as soon as it is obvious one way or the #other #inputs a DNF (with our format as a set #of sets) and a pos. integer n, and outputs the #the number of truth vectors (in the truth table) #divided by 2^n (if the ans. 1 it is a tautology) #For example, try: #PIEdnf({{1,2},{-3}},3); PIEdnf := proc(L,n) local co,i,S,s,m,co1,tim; m := nops(L); co := add(2^(-nops(L[i])),i=1..m); for i from 2 to m do S := choose(L,i); co1:=0: for s in S do tim:=AND(s,n): if tim<>0 then co1:=co1+(1/2)^(nops(tim)): fi: od: co:=co+(-1)^(i+1)*co1: od: evalb(co=1): end: #PIEdnfF(L,n): A fast version of PIEdnf(L,n) #quits as soon as it is obvious one way or the #other #inputs a DNF (with our format as a set #of sets) and a pos. integer n, and outputs the #the number of truth vectors (in the truth table) #divided by 2^n (if the ans. 1 it is a tautology) #For example, try: #PIEdnf({{1,2},{-3}},3); PIEdnfF := proc(L,n) local co,i,S,s,m,co1,tim; m := nops(L); co := add(2^(-nops(L[i])),i=1..m); if co<1 then RETURN(false): fi: for i from 2 to m do S := choose(L,i); co1:=0: for s in S do tim:=AND(s,n): if tim<>0 then co1:=co1+(1/2)^(nops(tim)): fi: od: co:=co+(-1)^(i+1)*co1: if type(i,odd) then if co<1 then RETURN(false): fi: else if co>=1 then RETURN(true): fi: fi: od; evalb(co=1): end: #====================end stuff done on Monday, Feb. 21, 2011==============