Iterated nand

From Boolean Zoo
Jump to: navigation, search


Let [math]n = 2^k[/math]. The iterated NAND function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] is recursively-defined as follows:

[math] f(x) = \begin{cases} \textrm{NAND}(x_1, x_2), & \textrm{if}~ n = 2 \\ \textrm{NAND}(f(x^{(1)}),f(x^{(2)})) & \textrm{otherwise}, \end{cases}[/math]

where [math]x^{(1)} = (x_1,x_2\ldots x_{n/2})[/math], [math]x^{(2)} = (x_{n/2+1},\ldots x_{n})[/math], and [math]\mathrm{NAND}(x,y)[/math] is [math]-1[/math] if [math]x = y = 1[/math] and [math]1[/math] otherwise.



  1. M. Saks and A. Wigderson, "Probabilistic Boolean decision trees and the complexity of evaluating game trees," 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), Toronto, ON, Canada, 1986, pp. 29-38.