#C10.txt, Feb. 24, 2025
Help10:=proc(): print(`NAND(x,y),NOT(x), AND(x,y),  OR(x,y) , RSLP(n,k), TF(n), EvalSP1(P,IN) `):
print(`EvalSP(P,n)`):
end:
#NAND(x,y): not (x and y)
NAND:=proc(x,y): not (x and y): end:
NOT:=proc(x): NAND(x,x):end:

AND:=proc(x,y): NAND(NAND(x,y),NAND(x,y)):end:

#x OR y= NOT (NOT x AND NOT y)
OR:=proc(x,y)
NAND(NAND(x,x) , NAND(y,y)):
end:

#Def. Straight-Line NAND porgram has n input gates labeled [1, ...n], and
#k (say) non-input gates of the form [i,j] where 1<=i<=j<=k-1 are previous gates
#[1,2,3,[1,1],[3,4],[1,3],[4,4]]
#The compute such a program you evaluate each gate in turn, and the last gate is the
#value of the Boolean function

RSLP:=proc(n,k) local P,i,i1,j1:
P:=[seq(i,i=1..n)]:

for i from n+1 to k+n do
 i1:=rand(1..nops(P))():
 j1:=rand(1..nops(P))():
 P:=[op(P),[i1,j1]]:
od:
P:
end:

#TF(n): the set of all true-false vectors of length n
TF:=proc(n) local V,v:
option remember:
if n=0 then
  RETURN({[]}):
fi:
V:=TF(n-1):
{seq([op(v),false],v in V),seq([op(v),true],v in V)}:
end:

#EvalSP1(P,IN): inputs a straight-line NAND program and an input true-false vector
#outputs the value of the last gate
EvalSP1:=proc(P,IN) local n,P1,i,i1,j1:
P1:=IN:
n:=nops(IN):
for i from n+1 to nops(P) do
 i1:=P[i][1]:
 j1:=P[i][2]:
  P1:=[op(P1),NAND(P1[i1],P1[j1])]:
od:

P1[-1]:
end:

#EvalSP(P,n): inputs a NAND SLP and outouts the set of vectors of length n that yields true 
EvalSP:=proc(P,n) local V,v,T:
V:=TF(n):
T:={}:
for v in V do
 if EvalSP1(P,v) then
   T:=T union {v}:
 fi:
od:
T:
end: