######################################################################
#BoolFns.txt Save this file as BoolFns.txt                           #
#To use it, stay in the                                              #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read BoolFns.txt : <Enter>                         #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Blair Seidler, Rutgers University ,                     #
#blair at math dot rutgers dot edu                                   #
######################################################################
 
#Created: Aug. 2021
 
print(`Created: Aug. 2021`):
print(`This is BoolFns `):
print(`to explore boolean functions and their`):
print(`associated disjunctive normal forms.`):
print(`One of the main procedures is an implementation`):
print(`of the Quine-McCluskey algorithm for simplification`):
print(`of DNF's`):
print(``):
print(`In this package, we will represent a Boolean function as `):
print(`a set of vectors (lists) in {-1,0,1}^n, where -1 is false, `):
print(`1 is true, and 0 is don't care.`):
print(`{[-1,0,1]} can be interpreted as "not x[1] and x[3]"`):
print(`{[-1,0,0],[0,0,1]} can be interpreted as "not x[1] or x[3]"`):
print(``):
print(`written by Blair Seidler.`):
print(``):
print(`Please report bugs to blair at math dot rutgers dot edu`):
print(``):
print(`For a list of the procedures type Help();, for help with`):
print(`a specific procedure, type Help(procedure_name);   .`):
print(``):

with(combinat):

Help:=proc():

if args=NULL then
print(`The main procedures are: `):
print(`BoolToFn,BoolToDNF,VecToClause`):
print(`EvalBoolOnVec,IntegerToVec,VecToInteger`):
print(`RandBool,FindPrimeImplicants,QuineMcC`):
print(` `):


elif nops([args])=1 and op(1,[args])=IntegerToVec then
print(`IntegerToVec(k,n): inputs an integer k in [0,2^n-1]`):
print(`and the number of boolean variables n`):
print(`and outputs the vector (in list form) of length n`):
print(`that corresponds to the binary representation of k`):
print(``):
print(`For example, IntegerToVec(3,4); will output [-1,-1,1,1].`):

elif nops([args])=1 and op(1,[args])=VecToInteger then
print(`VecToInteger(v): inputs a vector in {-1,1}^n`):
print(`and outputs the integer in [0,2^n-1]`):
print(`that corresponds to the vector`):
print(``):
print(`For example, IntegerToVec([-1,-1,1,1]); will output 3,`):
print(`the decimal equivalent of 0011.`):

elif nops([args])=1 and op(1,[args])=RandBool then
print(`RandBool(n [,ptrue [,pdontcare]]): inputs`):
print(`the number of boolean variables n, and optionally`):
print(`the probability that f(vector)=true and the probabilty`):
print(`that we don't care about the value of f(vector).`):
print(``):
print(`If called with one argument, RandBool uses .5 for ptrue`):
print(`and 0 for pdontcare.`):
print(``):
print(`If called with 1 or 2 arguments, RandBool returns a set`):
print(`containing all vectors for which the function is true.`):
print(`If called with 3 arguments, RandBool returns a list of two`):
print(`sets. The first set is vectors for which f is true, the`):
print(`second set is vectors for which we don't care if f is true.`):
print(``):
print(`Examples: RandBool(4), RandBool(4,.7), RandBool(4,.6,.2)`):

elif nops([args])=1 and op(1,[args])=VecToClause then
print(`VecToClause(v): inputs v as a vector in {-1,0,1}^n`):
print(`and returns the string for the DNF clause`):
print(`respresenting that vector.`):
print(``):
print(`For example, VecToClause([1,1,-1,1]); will output`):
print(`"x[1] and x[2] and not([3]) and x[4]"`):

elif nops([args])=1 and op(1,[args])=EvalBoolOnVec then
print(`EvalBoolOnVec(f,v): inputs a Boolean function f and`):
print(`v as a vector in {-1,0,1}^n`):
print(`and returns the value of f(v) - true or false.`):
print(``):
print(`Example: EvalBoolOnVec({[-1, -1] , [1, 1]}, [1, 1]) returns true`):
print(`Example: EvalBoolOnVec({[-1, -1] , [1, 1]}, [-1, 1]) returns false`):


elif nops([args])=1 and op(1,[args])=FindPrimeImplicants then
print(`FindPrimeImplicants(f): inputs a Boolean function f,`):
print(`a subset of {-1,1}^n, and returns the set of prime`):
print(`implicants (a la Quine-McCluskey) in {-1,0,1}^n.`):
print(``):
print(`Note that this function returns a LIST of vectors instead`):
print(`of a SET of vectors. This is done to guarantee that the`):
print(`largest prime implicants are at the beginning of the list.`):
print(`Here largest means containing the greatest number of 0's.`):
print(``):
print(`Example: FindPrimeImplicants({[-1, -1, 1], [1, 1, -1], [1, 1, 1]})`):
print(`returns [[1, 1, 0], [-1, -1, 1]]`):


elif nops([args])=1 and op(1,[args])=QuineMcC then
print(`QuineMcC(f, [dontcare]): inputs a Boolean function f as`):
print(`a subset of {-1,1}^n. The optional second argument is another`):
print(`subset of {-1,1}^n for which we don't care about the value`):
print(`of f. The function returns a subset of {-1,0,1}^n representing`):
print(`the same Boolean function as f.`):
print(``):
print(`This function uses FindPrimeImplicants but then uses a greedy`):
print(`algorithm to find a covering set of prime implicants. Each`):
print(`prime implicant is inspected in descending order of size, and`):
print(`added to the output if it covers a previously uncovered vector.`):
print(``):
print(`Example: QuineMcC({[-1, -1], [-1, 1], [1, -1]}) returns`):
print(`{[-1, 0], [0, -1]}.`):
print(`Example: QuineMcC({[-1, -1], [-1, 1], [1, -1]},{[1,1]}) returns`):
print(`{[0,0]}.`):

elif nops([args])=1 and op(1,[args])=BoolToDNF then
print(`BoolToDNF(x,f): inputs a variable name x`):
print(`and a Boolean function f`):
print(`and outputs the (human-readable) DNF for f`):
print(``):
print(`For example, BoolToDNF(b, {[-1, -1, 0], [1, 0, -1]});`):
print(`will output "((not(b[1]) and not(b[2])) or (b[1] and not(b[3])))".`):

elif nops([args])=1 and op(1,[args])=BoolToFn then
print(`BoolToFn(x,f): inputs a Boolean function f`):
print(`and outputs a truth table for f`):
print(``):
print(`Example: BoolToFn({[-1, -1], [1, 1]}) prints`):
print(`f([-1, -1]) = true`):
print(`f([-1, 1]) = false`):
print(`f([1, -1]) = false`):
print(`f([1, 1]) = true`):
else
print(`There is no Help for`,args):
fi:
 
end:


#IntegerToVec(k,n): inputs an integer k in [0,2^n-1] (and n) and outputs the vector of
#length n that corresponds to the binary representation of k (written as a list)
#(with -1's padded at the front to make it of length n, if necessary)
IntegerToVec:=proc(k,n) local i,rem,r,L:
option remember:
rem:=k:
L:=[0$n]:
for i from n to 1 by -1 do
  r:=rem mod 2:
  rem:=trunc(rem/2):
  if r=1 then
    L[i]:=1:
  else
    L[i]:=-1:
  fi:
od:
L:
end:

#VecToInteger(v): inverse of IntegerToVec(k,n)
VecToInteger:=proc(v) local n,i,s:
n:=nops(v): s:=0:
for i from 1 to n do
  if v[i]=1 then s:=s+2^(n-i): fi:
od:
s:
end:


#BoolToFn(S): takes the set of vectors S (presumed to be a subset of {-1,0,1}^n where n is the
#length of the vectors.

BoolToFn:=proc(S) local n,s,k,i,istrue:
if nops(S)=0 then
  print(`Input is empty`): RETURN():
fi:
n:=nops(S[1]):
for i from 0 to 2^n-1 do
  istrue:=false:
  s:=IntegerToVec(i,n):
  for k in S do
    if VecsMatch(s,k) then
      istrue:=true:
      break:
    fi:
  od:
  if istrue then
    print(cat(`f(`,convert(s,string),`) = true`)):
  else
    print(cat(`f(`,convert(s,string),`) = false`)):
  fi:
od:
RETURN():
end:

BoolToInt:=proc(n,f):
add(2^((2^n-1)-VecToInteger(v)),v in f):
end:

IntToBool:=proc(n,fn) local f,i,rem:
rem:=fn:
f:={}:
for i from 2^n-1 to 0 by -1 while rem>0 do
  if rem mod 2=1 then
    f:=f union {IntegerToVec(i,n)}:
  fi:
  rem:=floor(rem/2):
od:
f:
end:

BoolToDNF:=proc(x,S) local n,i,DNF:
if nops(S)=0 then RETURN(""): fi:
DNF:=cat("((",VecToClause(x,S[1],n),")"):
for i from 2 to nops(S) do
  DNF:=cat(DNF," or (",VecToClause(x,S[i],n),")"):
od:
cat(DNF,")"):
end:

#VecToClause(x,v): takes v as a vector in {-1,0,1}^n, and returns the string for the
#clause respresenting that vector
#Example: {1,1,-1,1} as a subset of [4] returns "x[1] and x[2] and not([3]) and x[4]"
VecToClause:=proc(x,v) local n,cl,i,j:
n:=nops(v):
if n<=0 then RETURN("false"): fi:
if {op(v)}={0} then RETURN("true"): fi:
for i from 1 to n do
if v[i]=1 then
  cl:=cat(x,"[",i,"]"): break:
elif v[i]=-1 then
  cl:=cat("not(",x,"[",i,"])"): break:
fi:
od:
for j from i+1 to n do
if v[j]=1 then
  cl:=cat(cl," and ",x,"[",j,"]"):
elif v[j]=-1 then
  cl:=cat(cl," and not(",x,"[",j,"])"):
fi:
od:
cl:
end:


RandBool:=proc() local n,ptrue,pdc,r,S,f,s,D,i:
if nargs<1 or nargs>3 then
  print("Usage: RandBool(n [,ptrue [,pdontcare]])"):
  RETURN(FAIL):
elif nargs=1 then
  n:=args[1]:
  ptrue:=.5:
  pdc:=0:
elif nargs=2 then
  n:=args[1]:
  ptrue:=args[2]:
  pdc:=0:
else
  n:=args[1]:
  ptrue:=args[2]:
  pdc:=args[3]:
fi:
S:={}:
D:={}:
for i from 0 to 2^n-1 do
  r:=rand(0..1.0)():
  if r<ptrue then
    S:=S union {i}:
  elif r<(ptrue+pdc) then
    D:=D union {i}:
  fi:
od:
if nargs<3 then RETURN({seq(IntegerToVec(s,n),s in S)}): fi:
[{seq(IntegerToVec(s,n),s in S)},{seq(IntegerToVec(s,n),s in D)}]:
end:


EvalBoolOnVec:=proc(f,v) local w,i,s:
for w in f do
  if not -1 in {seq(v[i]*w[i],i=1..nops(v))} then
    RETURN(true):
  fi:
od:
RETURN(false):
end:

VecsMatch:=proc(w,v):
if -1 in {seq(v[i]*w[i],i=1..nops(v))} then
  RETURN(false):
else
  RETURN(true):
fi:
end:

VecsOffByOne:=proc(v,w) local d:
  d:=[seq(abs(v[i]-w[i]),i=1..nops(v))]:
  if (add(d)=2) and (convert(d,set) subset {0,2}) then
    RETURN(true):
  else
    RETURN(false):
  fi:
end:

NextLevel:=proc(f) local n,u,i,j,k,l:
n:={}:
u:={}:
  for i in f do
    for j in f minus {i} do
      if VecsOffByOne(i,j) then
        k:=[seq((i[l]+j[l])/2,l=1..nops(i))]:
        n:=n union {k}:
        u:=u union {i,j}:
      fi:
    od:
  od:
[n,u]:
end:

FindPrimeImplicants:=proc(f) local p,ff,l,nl:
if not ({seq(op(p),p in f)} subset {-1,1}) then
  print(`FindPrimeImplicants: All vectors in f must be in {-1,1}^n`):
  RETURN(FAIL):
fi:
if nops({seq(nops(p),p in f)})<>1 then
  print(`FindPrimeImplicants: All vectors in f must be of same length`):
  RETURN(FAIL):
fi:
l:=f:
p:=[]:
while true do
  nl:=NextLevel(l):
  p:=[op(l minus nl[2]),op(p)]:
  if(nops(nl[1])=0) then break: fi:
  l:=nl[1]:
od:
p:
end:

QuineMcC:=proc() local f,dc,v,ff,F,p,P:
if nargs<1 or nargs>2 then
  print("Usage: QuineMcC(f, [dontcare]"):
  RETURN(FAIL):
elif nargs=1 then
  f:=args[1]:
  dc:={}:
elif nargs=2 then
  f:=args[1]:
  dc:=args[2]:
fi:
if not ({seq(op(p),p in (f union dc))} subset {-1,1}) then
  print(`QuineMcC: All vectors in f (and dc) must be in {-1,1}^n`):
  RETURN(FAIL):
fi:
if nops({seq(nops(p),p in (f union dc))})<>1 then
  print(`QuineMcC: All vectors in f (and dc) must be of same length`):
  RETURN(FAIL):
fi:
P:=FindPrimeImplicants(f union dc):
ff:=f:
F:={}:
for p in P do
  for v in ff do
    if VecsMatch(p,v) then
      F:=F union {p}:
      ff:=ff minus {v}:
    fi:
  od:
od:
F:
end:

ExpandVec:=proc(v) local i:
option remember:
for i from 1 to nops(v) do
  if v[i]=0 then
    RETURN(`union`(ExpandVec([op(1..i-1,v),-1,op(i+1..nops(v),v)]),ExpandVec([op(1..i-1,v),1,op(i+1..nops(v),v)]))):
  fi:
od:
{v}:
end:

ExpandBool:=proc(f):
`union`(seq(ExpandVec(v),v in f)):
end:

VarSetToVec:=proc(n,s) local v,i:
v:=[0$n]:
for i in s do v[i]:=1: od:
v:
end: