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==============