21 lines
1.1 KiB
TeX
21 lines
1.1 KiB
TeX
%root: main.tex
|
|
The evaluation of $\abs{\circuit}(1,\ldots, 1)$ can be defined recursively, as follows (where $\circuit_\linput$ and $\circuit_\rinput$ are the `left' and `right' inputs of $\circuit$ if they exist):
|
|
|
|
{\small
|
|
\begin{align}
|
|
\label{eq:T-all-ones}
|
|
\abs{\circuit}(1,\ldots, 1) = \begin{cases}
|
|
\abs{\circuit_\linput}(1,\ldots, 1) \cdot \abs{\circuit_\rinput}(1,\ldots, 1) &\textbf{if }\circuit.\type = \circmult\\
|
|
\abs{\circuit_\linput}(1,\ldots, 1) + \abs{\circuit_\rinput}(1,\ldots, 1) &\textbf{if }\circuit.\type = \circplus \\
|
|
|\circuit.\val| &\textbf{if }\circuit.\type = \tnum\\
|
|
1 &\textbf{if }\circuit.\type = \var.
|
|
\end{cases}
|
|
\end{align}
|
|
}
|
|
|
|
It turns out that for proof of \Cref{lem:sample}, we need to argue that when $\circuit.\type = +$, we indeed have
|
|
\begin{align}
|
|
\label{eq:T-weights}
|
|
\circuit.\lwght &\gets \frac{\abs{\circuit_\linput}(1,\ldots, 1)}{\abs{\circuit_\linput}(1,\ldots, 1) + \abs{\circuit_\rinput}(1,\ldots, 1)};\\
|
|
\circuit.\rwght &\gets \frac{\abs{\circuit_\rinput}(1,\ldots, 1)}{\abs{\circuit_\linput}(1,\ldots, 1)+ \abs{\circuit_\rinput}(1,\ldots, 1)}
|
|
\end{align} |