# OK to post homework # Aurora Hiveley, 2/24/25, Assignment 10 Help := proc(): print(`SimulateNAND(n,k,K), Monotone(n,k,p), SimulateMonotone(n,k,p,K), EvalSPM(P,n), EvalSPM1(n,P)`): end: with(combinat): with(linalg): # SimulateNAND(n,k,K): estimates the average number of vectors of length n in a random NAND SLP with n input gates and k other gates, # by running it K times and computing the average of this sample SimulateNAND := proc(n,k,K) local i: add( nops(EvalSP(RSLP(n,k),n)), i=1..K )/K: end: # What did you get for # SimulateNAND(10,5, 1000) # SimulateNAND(10,10, 1000) # SimulateNAND(10,20, 1000) # SimulateNAND(10,50, 1000) # Monotone(n,k,p): adapted from RSLP(n,k). Has no NOT, i.e. only using AND and OR, and a typical member is [i,j,AND] or [i,j,OR] # for each non-input gate, the probability of AND is p and the probability of OR is 1-p) Monotone := proc(n,k,p) 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))(): if LD(p) then P:=[op(P),[i1,j1,AND]]: else P:=[op(P),[i1,j1,OR]]: fi: od: P: end: # loaded die: returns true with probabality p (where p is a rational number between 0 and 1) LD:=proc(p):evalb(rand(1..denom(p))()<=numer(p)):end: # SimulateMonotone(n,k,p,K): adapted from SimulateNAND(n,k,K), but uses AND/OR instead of NAND SLP SimulateMonotone := proc(n,k,p,K) local i: add( nops(EvalSPM(Monotone(n,k,p),n)), i=1..K )/K: end: ## example computations: # kList := [5,10,20,50]: # [seq( SimulateMonotone(10,k,1/2,1000), k in kList )]: # output: [63904/125, 64272/125, 131233/250, 64196/125] # [seq( SimulateMonotone(10,k,3/4,1000), k in kList )]: # output: [46684/125, 8731/25, 36301/125, 32409/125] # [seq( SimulateMonotone(10,k,1,1000), k in kList )]: # output: [27498/125, 21088/125, 27951/250, 27129/500] # needed helpers #EvalSP1M(P,IN): inputs a straight-line AND/OR program and an input true-false vector #outputs the value of the last gate EvalSP1M:=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]: if P[i][3] = AND then P1:=[op(P1),AND(P1[i1],P1[j1])]: else P1:=[op(P1),OR(P1[i1],P1[j1])]: fi: od: P1[-1]: end: #EvalSPM(P,n): inputs a AND/OR SLP and outouts the set of vectors of length n that yields true EvalSPM:=proc(P,n) local V,v,T: V:=TF(n): T:={}: for v in V do if EvalSP1M(P,v) then T:=T union {v}: fi: od: T: end: ### copied form C10.txt #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: