Noting that the input of the second-hidden layer of $\Phi^{(1)}$ is contained in the unit cube $[0,1]^{N_1^{(1)}}$,
we can proceed as in the first step and replace each of the $\rho$-neurons in the second hidden layer by $\sigma$-neurons.
The resulting network is given by

\begin{equation*}
\Phi^{(2)} =  W_L \circ  \cdots \circ W_4 \circ \rho \circ W_3^{(2)} \circ  \sigma \circ W_2^{(2)} \circ \sigma  \circ W_1^{(1)},
\end{equation*}

with $W_2^{(2)}(x) = A_2^{(2)}x+b_2^{(2)}, A_2^{(2)}\in \mathbb{Z}^{N_2^{(2)}\times N_1^{(1)}}, b_2^{(2)} \in \mathbb{Q}_{k}^{N_2^{(2)}}$, and $W_3^{(2)}(x) = A_3^{(2)}x+b_3, A_3^{(2)}\in \mathbb{Z}^{N_3\times N_2^{(2)}}$, where $N_2^{(2)}$ is the number of $\sigma$-neurons in the second hidden layer of $\Phi^{(2)}$, and satisfies

\begin{equation*}
\Phi^{(2)}(x) = \Phi(x), \text{ for } x\in [0,1]^n.
\end{equation*}
Continuing in this manner, we eventually get the network $\Phi^{(L-1)}: [0,1]^n\rightarrow[0,1]$ given by

\begin{equation*}
\Phi^{(L-1)} =  W_L^{(L-1)} \circ \sigma \circ  W_{L-1}^{(L-1)} \circ \sigma \circ \cdots  \circ \sigma \circ W_2^{(2)} \circ \sigma  \circ W_1^{(1)},
\end{equation*}
with $W_\ell^{(\ell)}(x) = A_\ell^{(\ell)}x+b_\ell^{(\ell)}, A_\ell^{(\ell)}\in \mathbb{Z}^{N_\ell^{(\ell)}\times N_{\ell-1}^{(\ell-1)}}, b_\ell^{(\ell)} \in \mathbb{Q}_{k}^{N_\ell^{(\ell)}}$, where $N_\ell^{(\ell)}$ is the number of ($\sigma$-)neurons in the $\ell$-th hidden layer of $\Phi^{(L-1)}$, for $\ell\in\{1,\ldots \hspace{-0.02cm}, L-1\}$, and $W_L^{(L-1)}(x)= A_L^{(L-1)}x+b_L, A_L^{(L-1)} \in \mathbb{Z}^{N_L \times N_{L-1}^{(L-1)}}$. The proof is concluded by noting that the resulting $\sigma$-network $\Psi:= \Phi^{(L-1)}$ satisfies $\Psi(x) = \Phi(x)$, for $x\in [0,1]^n$, and has integer weights and biases in $\mathbb{Q}_{k}$.

The reverse transformation from a $\sigma$-network to a $\rho$-network can be effected through lem:sigmatorelu.

Starting from a ReLU nework $\Phi$, transforming it into a $\sigma$-network $\Psi$ according to lem:ConstructSigmaNetwork, and then going back to a ReLU network $\Phi'$ by using lem:sigmatorelu, will recover a network $\Phi'$ that is functionally equivalent to $\Phi$, i.e., $\Phi'(x) = \Phi(x)$, for all $x\in [0,1]^n$, but can be structurally different from $\Phi$. For example, choosing different

$m \in \mathbb{N}$ with $m \geq u-1$ in (<ref>) would lead to such functionally equivalent, but structurally different recovered networks $\Phi'$.

We are now ready to show how DMV terms can be extracted from $\sigma$-networks. Thanks to lem:ConstructSigmaNetwork, we can restrict ourselves to
$\sigma$-networks with integer weights and biases in $\mathbb{Q}_{k}$. We begin by considering a single $\sigma$-neuron, which is of the form

\begin{equation}\label{eq:sigmaneuron}
\sigma(m_1x_1+\cdots+m_nx_n+b), \quad \text{ with } m_1,\ldots \hspace{-0.02cm},m_n\in \mathbb{Z}, b\in \mathbb{Q}_{k}.
\end{equation}
The following lemma provides an inductive way for the extraction of DMV terms from individual $\sigma$-neurons.

Consider the function $f(x_1,\ldots \hspace{-0.02cm}, x_n) = m_1x_1+\cdots+m_nx_n+b,$ defined on $[0,1]^{n}$, with $ m_1,\ldots \hspace{-0.02cm},m_n\in \mathbb{Z}, b\in \mathbb{Q}_{k}.$ Without loss of generality, assume that $\max_{i=1,...,n} |m_i| = m_1$. With $f_{\circ}(x_1,\ldots \hspace{-0.02cm}, x_n) =  (m_1-1)x_1+m_2x_2+\cdots+m_nx_n+b$, we have

\begin{equation}\label{eq:lemma4.4}
\sigma(f) = (\sigma(f_{\circ}) \oplus x_1) \odot \sigma(f_{\circ}+1).
\end{equation}

See Appendix <ref> <cit.>, <cit.>.

We next demonstrate, by way of a simple example, how lem:extractmv can be used to extract DMV terms from individual $\sigma$-neurons.

We extract the DMV term underlying $ \sigma(x-2y+1/2)$ and start by noting that

\begin{align}
\quad \;  & \sigma(x-2y+1/2) \\
& = \; 1- \sigma(-x+2y-1/2+1) \label{eq:neg} \\
& = \; \lnot\sigma(-x+2y+1/2) \label{eq:lnot} \\
& = \; \lnot( (\sigma(-x+y+1/2)\oplus y)\odot \sigma(-x+y+3/2)), \label{eq:ApplyLem}
\end{align}

where in (<ref>) we used $\sigma(x) = 1-\sigma(-x+1)$, for $x\in \mathbb{R}$, and (<ref>) is by $\lnot x=1-x$. In (<ref>)  we applied lem:extractmv with $x_1=y$. We again apply lem:extractmv with $x_1=y$ to remove the $y$-terms inside $\sigma(\cdot)$ as follows:

\begin{equation}\label{eq:Removey}
\begin{aligned}
\sigma(-x+y+1/2) &= (\sigma(-x+1/2)\oplus y)\odot \sigma(-x+3/2) \\
\sigma(-x+y+3/2) &= (\sigma(-x+3/2)\oplus y)\odot \sigma(-x+5/2).
\end{aligned}
\end{equation}
Likewise, we can remove the $x$-terms inside $\sigma(\cdot)$ according to

\begin{equation}\label{eq:Removex}
\begin{aligned}
\sigma(-x+1/2) &= \lnot \sigma(x+1/2) =\lnot( (\sigma(1/2)\oplus x)\odot \sigma(3/2) ) = \lnot (1/2\oplus x)\\
\sigma(-x+3/2) &= \lnot \sigma(x-1/2) =\lnot( (\sigma(-1/2)\oplus x)\odot \sigma(1/2) ) = \lnot (x \odot 1/2) \\
\sigma(-x+5/2) &= \lnot \sigma(x-3/2) =\lnot( (\sigma(-3/2)\oplus x)\odot \sigma(-1/2) ) = 1.
\end{aligned}
\end{equation}

For the constant term $1/2$, by defn:DivisibleMV01, we can write

\begin{equation*}
1/2 = \delta_2 1.
\end{equation*}

Substituting (<ref>) back into (<ref>) and then substituting the results thereof into (<ref>), we obtain the DMV term corresponding to $ \sigma(x-2y+1/2)$ according to

\begin{multline}\label{eq:delta}
\lnot( (((\lnot (\delta_2 1\oplus x)\oplus y)\odot \lnot (x \odot \delta_2 1 ))\oplus y)\odot (\lnot (x \odot \delta_2 1 )\oplus y)).
\end{multline}

We conclude the example by noting that the algebraic expression of the DMV term extracted using this procedure depends on the order in which the variables are eliminated through lem:extractmv; functionally these expressions will, however, all be equivalent.

We are now ready to describe how the DMV term underlying a given ReLU network with integer weights and biases in $\mathbb{Q}_{k}$ mapping $[0,1]^{n}$ to $[0,1]$ can be extracted. The corresponding algorithm starts by
applying lem:ConstructSigmaNetwork to convert the network into a functionally equivalent $\sigma$-network

\begin{equation*}
\Psi^f=  W_L \circ \sigma \circ \cdots \circ W_2 \circ \sigma \circ W_1,
\end{equation*}

where $W_1,\ldots \hspace{-0.02cm}, W_L$ are affine transformations with integer weights and biases in $\mathbb{Q}_{k}$. As the range of $\Psi^f$ is contained in $[0,1]$, we can apply the $\sigma$-activation function to the output layer without changing the mapping, i.e.,

\begin{equation*}
\Psi^f= \sigma \circ W_L \circ \cdots \circ \sigma \circ W_2 \circ \sigma \circ W_1.
\end{equation*}
Next, lem:extractmv is applied to each layer $\sigma \circ W_{\ell}$, $\ell = 1,\ldots \hspace{-0.02cm},L$, as in exmp:Extraction above to extract the DMV terms corresponding to the individual output neurons in layer $\ell$. The resulting DMV formulae are then algebraically composed honoring the compositional structure of $\Psi^f$ to yield the overall DMV term corresponding to the ReLU network we started from. We note that in order to have the compositional structure of ReLU networks correspond to compositions in DMV algebra as just explained, it is crucial to first transform the ReLU network into a (functionally equivalent) $\sigma$-network according to lem:ConstructSigmaNetwork. This is, as mentioned above, to ensure that the outputs of neurons inside the network are guaranteed to be in $[0,1]$ so as to
remain in the set ($[0,1]$) underlying the DMV algebra.

We have automated our extraction algorithm in Python software[Implementation available at <https://www.mins.ee.ethz.ch/research/downloads/NN2MV.html> ]; the algorithm takes a ReLU network as input and outputs a corresponding DMV formula.
Applying this algorithm, for example, to the ReLU network $f_{\text{c}} = \rho(x_{-1}+x_0+x_1)- \rho(x_{-1}+x_0+x_1-1)$ linearly interpolating the transition function in tbl:totalistic, indeed, recovers the MV term $\tau = x_{-1}\oplus x_0 \oplus x_1$ we started from in exmp:2.1.

§.§ delete Simplifying DMV terms

Inspection of the algebraic expression (<ref>) shows that a rather mundane function, namely $\sigma(x-2y+3/4)$, leads to a quite complicated expression in DMV algebra. It is therefore of significant interest to develop a toolset for manipulating DMV terms, with an eye towards reducing their algebraic complexity. For the Boolean case such a theory allowing to rearrange, multiply out, factor and combine terms was developed by Shannon in <cit.>. In the case of MV algebras, concretely here DMV algebras, aside from the axioms (<ref>)-(<ref>) in defn:MV algebra along with
\begin{align*}
x \oplus \lnot x&=1\\
x\odot \lnot x&=0,
\end{align*}
such a general toolset seems to be lacking, to the best of our knowledge. We next take a first step in this direction.

The approach we propose is based on the insight that every DMV term has a neural network counterpart, and hence manipulating DMV terms can equivalently be effected on the level of the corresponding neural networks. To illustrate this approach, we start from the hat function $g:\mathbb{R}\rightarrow[0,1]$,

\begin{equation*}
g(x) = \sigma(2x)-\sigma(2x-1)
\end{equation*}
and let the second-order hat function $g_2$ be the composition of $g$ with itself, i.e.,

\begin{equation*}
g_2:=g\circ g.
\end{equation*}

Upon noting that
\begin{equation}\label{eq:g2*}
g_2(x) = \sigma(4x)-\sigma(4x-1)+\sigma(4x-2)-\sigma(4x-3),
\end{equation}
it follows that $g_2$ can be realized by a two-layer $\sigma$-network according to

\begin{equation}\label{eq:Psi_2}
\Psi_{g}^{2}=  W_2 \circ \sigma \circ W_1
\end{equation}

\begin{equation*}
4 \\ 4 \\ 4 \\4
\end{pmatrix}x+ \begin{pmatrix}
0 \\-1 \\-2 \\-3
\end{pmatrix}, \quad
W_2(x) = \begin{pmatrix}
1 & -1 & 1 & -1
\end{pmatrix} x.
\end{equation*}

On the other hand, $g$ can be realized by a two-layer $\sigma$-network $\Psi_g$, according to $\Psi_g:=  W^g_2\circ \sigma \circ W^g_1=g$ with

\begin{equation*}
2 \\ 2
\end{pmatrix}x+ \begin{pmatrix}
0 \\-1
\end{pmatrix}, \quad
W_2^g(x) = \begin{pmatrix}
1 & -1
\end{pmatrix}
\begin{pmatrix}
x_1 \\x_2
\end{pmatrix}.
\end{equation*}

Therefore, $g_2$ can, in turn, be realized by a three-layer $\sigma$-network according to

\begin{equation*}
\Psi^{2*}_g= \Psi_g \circ  \Psi_g=  W_2^g\circ \sigma \circ W_1^g  \circ W_2^g\circ \sigma \circ W_1^g.
\end{equation*}

We now identify the DMV terms corresponding to these two alternative $\sigma$-network representations of $g_2$. By (<ref>), the DMV terms associated with the $\sigma$-neurons in the first layer of $\Psi_g^2$ are

\begin{align}
\label{eq:1}  \; \sigma(4x) &: x\oplus x \oplus x \oplus x\\
\label{eq:2} \quad     \sigma(4x-1) &: (((( x\odot x)\oplus x)\odot (x\oplus x))\oplus x )\odot (x\oplus x \oplus x) \\
\label{eq:3} \quad  \sigma(4x-2) &: ((x\odot x\odot x)\oplus x)\odot ((( x\odot x)\oplus x)\odot (x\oplus x))\\
\label{eq:4}  \quad  \sigma(4x-3) &: x \odot x\odot x \odot x,
\end{align}

and the second layer

\begin{multline}\label{eq:g2layer2}
\sigma(x_1 -x_2+x_3-x_4): ( (x_3 \odot \lnot (x_2\oplus x_4))\oplus x_1) \odot \\ ( (\lnot (x_2\oplus x_4 ) \oplus x_3) \odot (\lnot x_2 \oplus \lnot x_4)),
\end{multline}

by making use of the identity $\lnot x = 1-x$, for $x\in [0,1]$, and successive application of lem:extractmv. Substitute  (<ref>) for $x_1$, (<ref>) for $x_2$, (<ref>) for $x_3$, and (<ref>) for $x_4$ in (<ref>), we obtain the MV term associated with $\Psi_g^2$, which is too long so we refrain from writing here. Alternatively, the DMV term for the network $\Psi_g$ is given by

\begin{equation}\label{eq:Psi_1}
\Psi_g(x) =  ( x \oplus x) \odot \lnot (x \odot x)
\end{equation}

\begin{align*}
\sigma(2x) &= x \oplus x\\
\sigma(2x-1) &= x \odot x \\
\sigma(x_1 -x_2) &= x_1 \odot \lnot x_2.
\end{align*}

by successive application of lem:extractmv. The DMV term for the network $\Psi^2_g$ can be obtained by composing (<ref>) with itself, i.e., replacing $x$ in (<ref>) by $ ( x \oplus x) \odot \lnot (x \odot x)$. The resulting DMV term is

\begin{multline}\label{eq:deepexpression}
\Psi^{2*}_g(x) =  (  ( x \oplus x) \odot \lnot (x \odot x) \oplus  ( x \oplus x)  \odot \lnot (x \odot x)) \\ \odot \lnot ( ( x \oplus x) \odot \lnot (x \odot x) \odot  ( x \oplus x) \odot \lnot (x \odot x)).
\end{multline}

As $ \Psi_g^{2*} =  \Psi_g^{2}=g_2$, the two alternative DMV terms we obtained must be equivalent. The algebraic expression in (<ref>), which is based on a deeper network exploiting composition, is quite simpler than the expression derived from the shallow representation (<ref>).

The authors are deeply grateful to Prof. Olivia Caramello for drawing their attention to the McNaughton theorem and, more generally, to MV logic.

§ MV TERM CORRESPONDING TO $F_{\TEXT{C}}$ IN (<REF>)

First, expand the domains of the linear pieces of $f_{\text{c}}$ to $[0,1]$ and denote them by $f_1, f_2,f_3$, with

\begin{equation*}
\begin{aligned}
f_1(x) &= 3x,\\
f_2(x) &= 1,\\
f_3(x) &= -3x+3,
\end{aligned}
\end{equation*}

for $x\in [0,1]$. Since $f_{\text{c}}:[0,1]\rightarrow [0,1]$, we can compose each linear piece with $\sigma(\cdot)$, which results in the truncated linear functions $\sigma(f_1), \sigma(f_2),\sigma(f_3)$ depicted in fig:f123. Next, we apply lem:extractmv to extract the MV terms corresponding to $\sigma(f_1), \sigma(f_2),\sigma(f_3)$.
Trivally, $\sigma(f_2) = \lnot 0$ on $[0,1]$. The function $\sigma(f_1)$ can be expressed as

\begin{equation*}
\sigma(f_1)(x) = x\oplus x\oplus x, \text{ for } x\in [0,1].
\end{equation*}

Likewise, we have

\begin{equation*}
\sigma(f_3)(x) = x\odot x\odot x, \text{ for } x\in [0,1].
\end{equation*}

Inspection of fig:f123 and $f_{\text{c}}$ in fig:examplefx allows us to conclude that

\begin{equation*}
f_{\text{c}}(x) = \min\{ \sigma(f_1)(x), \sigma(f_2)(x), \sigma(f_3)(x) \}, \text{ for } x\in [0,1].
\end{equation*}

Finally, it is readily verified that the “min” operation can be realized according to

\begin{equation*}
\min\{x, y\}  = x\wedge y,
\end{equation*}

\[
\min\{x, y,z\} = \min\{ \min \{x,y\},z\}.
\]

Putting the pieces together, we obtain the MV term corresponding to $f_{\text{c}}$ as

\begin{equation*}
(x\oplus x\oplus x) \wedge  \lnot 0 \wedge (x\odot x\odot x).
\end{equation*}

[x=1.5cm, y=1.5cm, >=stealth, scale=1, transform shape]
[->] (0,0) – (0,2.4) node[anchor=west] $\sigma(f_1)$;
[->] (0,0) – (2.4,0) node[anchor= west] $x$;
(-0.02, 2.1) – (0.02, 2.1) node[anchor= east] $1$;
(0.7,-0.02) – (0.7,0.02) node[anchor= north] $1/3$;
(2.1,-0.02) – (2.1,0.02) node[anchor= north] $1$;
at (0.2,-0.3 cm) $0$;
[ultra thick] (0,0) – (0.7,2.1) node[anchor= north] ;
[ultra thick] (0.7,2.1) – (2.1, 2.1) node[anchor= north] ;

[->] (3,0) – (3,2.4) node[anchor=west] $\sigma(f_2)$;
[->] (3,0) – (5.4,0) node[anchor= west] $x$;
(2.98, 2.1) – (3.02, 2.1) node[anchor= east] $1$;
(3.7,-0.02) – (3.7,0.02) node[anchor= north] $1/3$;
(5.1,-0.02) – (5.1,0.02) node[anchor= north] $1$;
at (3.2,-0.3 cm) $0$;
[ultra thick] (3,2.1) – (5.1, 2.1) node[anchor= north] ;

[->] (6,0) – (6,2.4) node[anchor=west] $\sigma(f_3)$;
[->] (6,0) – (8.4,0) node[anchor= west] $x$;
(5.98, 2.1) – (6.02, 2.1) node[anchor= east] $1$;
(7.4,-0.02) – (7.4,0.02) node[anchor= north] $2/3$;
(8.1,-0.02) – (8.1,0.02) node[anchor= north] $1$;
at (6.2,-0.3 cm) $0$;
[ultra thick] (6.0,2.1) – (7.4, 2.1) node[anchor= north] ;
[ultra thick] (8.1, 0) – (7.4, 2.1) node[anchor= north] ;

[x=1.5cm, y=1.5cm, >=stealth, scale=1, transform shape]
[->] (0,0) – (0,2.4) node[anchor=west] $\sigma(f_1)$;
[->] (0,0) – (2.4,0) node[anchor= west] $x$;
(-0.02, 2.1) – (0.02, 2.1) node[anchor= east] $1$;
(0.7,-0.02) – (0.7,0.02) node[anchor= north] $1/3$;
(2.1,-0.02) – (2.1,0.02) node[anchor= north] $1$;
at (0.2,-0.3 cm) $0$;
[ultra thick] (0,0) – (0.7,2.1) node[anchor= north] ;
[ultra thick] (0.7,2.1) – (2.1, 2.1) node[anchor= north] ;

[->] (3,0) – (3,2.4) node[anchor=west] $\sigma(f_2)$;
[->] (3,0) – (5.4,0) node[anchor= west] $x$;
(2.98, 2.1) – (3.02, 2.1) node[anchor= east] $1$;
(3.7,-0.02) – (3.7,0.02) node[anchor= north] $1/3$;
(5.1,-0.02) – (5.1,0.02) node[anchor= north] $1$;
at (3.2,-0.3 cm) $0$;
[ultra thick] (3,2.1) – (5.1, 2.1) node[anchor= north] ;

[->] (6,0) – (6,2.4) node[anchor=west] $\sigma(f_3)$;
[->] (6,0) – (8.4,0) node[anchor= west] $x$;
(5.98, 2.1) – (6.02, 2.1) node[anchor= east] $1$;
(7.4,-0.02) – (7.4,0.02) node[anchor= north] $2/3$;
(8.1,-0.02) – (8.1,0.02) node[anchor= north] $1$;
at (6.2,-0.3 cm) $0$;
[ultra thick] (6.0,2.1) – (7.4, 2.1) node[anchor= north] ;
[ultra thick] (8.1, 0) – (7.4, 2.1) node[anchor= north] ;

The truncated functions $\sigma(f_1), \sigma(f_2), \sigma(f_3)$.

§ TRANSFORMING $\SIGMA$-NETWORKS INTO EQUIVALENT RELU NETWORKS

For $d,d' \in \mathbb{N}$, let $\Psi:\mathbb{R}^d \rightarrow \mathbb{R}^{d'}$ be a $\sigma$-network with integer weights and biases in $\mathbb{Q}_{k}$. There exists a ReLU network $\Phi: \mathbb{R}^d \rightarrow \mathbb{R}^{d'}$, with $\mathcal{L}(\Phi) = \mathcal{L}(\Psi)$, integer weights, and biases in $\mathbb{Q}_{k}$, satisfying

\begin{equation*}
\Phi(x) = \Psi(x), \quad \text{ for all } x\in \mathbb{R}^d.
\end{equation*}

By defn:sigmanetwork, we can write[To keep the exposition simple, we consider the form of $\Psi$ for $L \geq 3$, the cases $L=1,2$ are trivially contained in the discussion.]

\begin{equation*}
\Psi =  W_L \circ \sigma \circ W_{L-1} \circ \sigma \circ \cdots \circ \sigma  \circ W_1,
\end{equation*}
with $W_\ell(x) = A_\ell x+b_\ell, A_\ell\in \mathbb{Z}^{N_\ell\times N_{\ell-1}}, b_\ell \in \mathbb{Q}_{k}^{N_\ell},$ for $\ell\in\{1,\ldots \hspace{-0.02cm}, L\}$, $N_0=d$, and $N_L=d'$. The basic idea of the proof is to use the relationship

\begin{equation}\label{eq:sigm-to-rho}
\sigma(x) = \rho(x)-\rho(x-1), \text{ for all } x \in \mathbb{R},
\end{equation}

to replace every $\sigma$-neuron in $\Psi$ with a pair of $\rho$-neurons. We start with $\sigma \circ W_{1}$
to obtain the equivalent network

\begin{equation*}
\Psi^{(1)} =  W_L  \circ \sigma \circ \cdots \circ \sigma \circ W_2 \circ H_1^{(1)} \circ \rho  \circ W_1^{(1)},
\end{equation*}

\begin{align*}
W_1^{(1)}(x) &:= \begin{pmatrix}
W_1(x) \\
W_1(x) -1_{N_1}
\end{pmatrix}, \quad x\in \mathbb{R}^{N_0},   \\
H_1^{(1)}(x) &:= \begin{pmatrix}
\mathbb{I}_{N_1} & -\mathbb{I}_{N_1}
\end{pmatrix}x, \quad x\in \mathbb{R}^{2N_1},
\end{align*}

with $1_{N_1}$ denoting the $N_1$-dimensional column vector with all entries equal to $1$.

It follows directly that $\Psi^{(1)}$ has integer weights and biases in $\mathbb{Q}_{k}$.

Continuing in this manner, we get

\begin{equation*}
\Psi^{(L-1)} =  W_L  \circ H^{(L-1)}_{L-1} \circ \rho \circ W_{L-1}^{(L-1)} \circ \cdots \circ   W_{2}^{(2)} \circ H_1^{(1)} \circ \rho  \circ W_1^{(1)},
\end{equation*}

\begin{align*}
W_\ell^{(\ell)}(x) &= \begin{pmatrix}
W_\ell(x) \\
W_\ell(x) -1_{N_\ell}
\end{pmatrix}, \quad x\in \mathbb{R}^{N_{\ell-1}},   \\
H_\ell^{(\ell)}(x) &= \begin{pmatrix}
\mathbb{I}_{N_\ell} & -\mathbb{I}_{N_\ell}
\end{pmatrix}x, \quad x\in \mathbb{R}^{2N_\ell},
\end{align*}
for $\ell=1,\ldots \hspace{-0.02cm},L-1,$ satisfying

\begin{equation*}
\Psi^{(L-1)}(x) =\Psi(x), \text{ for all } x\in \mathbb{R}^d.
\end{equation*}

The proof is concluded upon identifying $\Psi^{(L-1)}$ with $\Phi$ and noting that $\Psi^{(L-1)}$ has integer weights and biases in $\mathbb{Q}_{k}$ and
$\mathcal{L}(\Psi^{(L-1)}) = \mathcal{L}(\Psi)$.

§ PROOF OF LEM:EXTRACTMV <CIT.>, <CIT.>

We follow the line of arguments in <cit.> and consider four different cases.

Case 1: $f_{\circ}(x) \geq 1,$ for all $x\in [0,1]^n$. In this case, the LHS of (<ref>) is

\[
\sigma(f)=1.
\]

The RHS becomes

\begin{equation*}
(\sigma(f_{\circ}) \oplus x_1) \odot \sigma(f_{\circ}+1)  =  (1 \oplus x_1)\odot 1 = 1.
\end{equation*}

Case 2: $f_{\circ}(x) \leq -1,$ for all $x\in [0,1]^n$. In this case, the LHS is

\[
\sigma(f)=0.
\]

The RHS is given by

\begin{equation*}
(\sigma(f_{\circ}) \oplus x_1) \odot \sigma(f_{\circ}+1)
=  (0 \oplus x_1)\odot 0=0.
\end{equation*}

Case 3:  $-1 < f_{\circ}(x)\leq 0$, for all $x\in [0,1]^n$. In this case, $f \in (-1,1]$ as $x_1\in [0,1]$. The RHS of (<ref>) becomes

\begin{align*}
& (\sigma(f_{\circ}) \oplus x_1) \odot \sigma(f_{\circ}+1) \\
& =     (0 \oplus x_1)\odot (f_{\circ}+1) \\
& = x_1\odot (f_{\circ}+1)\\
& = \max\{0,x_1+f_{\circ}+1-1\} \\
& = \max\{0,f\}\\
& = \sigma(f).
\end{align*}

Case 4:  $0 < f_{\circ}(x) < 1$, for all $x\in [0,1]^n$. In this case, $f\in (0,2)$. The RHS becomes

\begin{align*}
& (\sigma(f_{\circ}) \oplus x_1) \odot \sigma(f_{\circ}+1)\\
& =    (f_{\circ} \oplus x_1)\odot 1 \\
& = f_{\circ} \oplus x_1\\
& = \min\{1,f_{\circ}+x_1\}\\
& = \min \{1,f\}\\
& = \sigma(f).
\end{align*}

Let $n\in \mathbb{N}$ and let $f_{\text{c}}:[0,1]^n\rightarrow [0,1]$ be a continuous piecewise linear function with linear pieces

\begin{equation}\label{eq:linearpj}
p_j(x_1, \ldots \hspace{-0.02cm}, x_{n}) = m_{j1}x_1+\cdots+m_{jn}x_{n}+b_j, \quad  j = 1,\ldots \hspace{-0.02cm},\ell,
\end{equation}
where $m_{j1},\ldots \hspace{-0.02cm}, m_{jn} \in \mathbb{R}$, $b_j\in \mathbb{R}$.
Let $\Pi$ be the set of all permutations of the index set $\{1,\ldots \hspace{-0.02cm},\ell\}$. There exist a nonempty set of permutations $\Sigma \subset \Pi$ and, for each $\pi \in \Sigma$, an integer $i_\pi$ with $1\leq i_\pi  \leq \ell$, such that

\begin{equation}\label{eq:piecewiseMinMax}
f_{\text{c}}(x) = \max_{\pi\in \Sigma}\min_{i \in \{1,\ldots \hspace{-0.02cm}, i_\pi\}} p_{\pi(i)}(x), \text{ for all } x\in [0,1]^n.
\end{equation}

The proof follows by combining arguments in the proofs of <cit.> and  <cit.>, where the result is established for piecewise linear functions with integer coefficients. For each permutation $\pi=\pi{(1)}\pi{(2)}\cdots \pi{(\ell)} \in \Pi$, let

\begin{equation*}
P_{\pi}:=\{ x\in [0,1]^n: p_{\pi(1)}(x) \geq p_{\pi(2)}(x)\geq \cdots \geq p_{\pi(\ell)}(x)\}
\end{equation*}
be the polyhedron associated with $\pi$. We refer to <cit.>
for a proof of $P_{\pi}$, indeed, constituting a polyhedron. Define the dimension of a polyhedron as the maximum number of affinely independent points it contains minus $1$. Let $\Sigma$ be the collection of permutations whose associated polyhedra are $n$-dimensional, i.e.,

\begin{equation*}
\Sigma := \{\pi \in \Pi: P_\pi \text{ is $n$-dimensional}\}.
\end{equation*}

Note that $\cup_{\pi \in \Sigma}P_\pi = [0,1]^n$ <cit.>.

For every $\pi\in \Sigma$, let $i_{\pi}\in\{1,\ldots \hspace{-0.02cm},\ell\}$ be such that $f_{\text{c}}(x) = p_{\pi(i_{\pi})}(x),$ for $x\in P_\pi$, and let $ g_{\pi}:= \min_{i\in \{1,\ldots \hspace{-0.02cm}, i_\pi\}}p_{\pi(i)}$. For every $\pi \in \Sigma$, $g_\pi(x) = f_{\text{c}}(x) = p_{\pi(i_{\pi})}(x)$, for $x\in P_\pi$. Therefore,

\begin{equation*}
f_{\text{c}}(x) \leq \max_{\pi \in \Sigma} g_\pi(x), \quad \text{ for } x\in [0,1]^n.
\end{equation*}

It hence suffices to prove that $f_{\text{c}}(x)\geq g_\pi(x)$, for $x\in [0,1]^n$, for all $\pi \in \Sigma$, to obtain

\begin{equation*}
f_{\text{c}}(x) = \max_{\pi \in \Sigma} g_\pi(x), \quad \text{ for } x\in [0,1]^n,
\end{equation*}
which establishes the desired result (<ref>). By continuity of $f_{\text{c}}$ and the fact that the min and max of continuous functions are continuous, it suffices to establish $f_{\text{c}} \geq g_\pi$ on the set

\{x \in [0,1]^n: \exists \pi \in \Sigma \, \mid x \,\, \text{is in the interior of $P_\pi$} \}.

Now fix an arbitrary $\pi \in \Sigma$. As already noted above, $g_\pi(x) = f_{\text{c}}(x)$, for $x\in P_\pi$. Take an arbitrary point $y\notin P_\pi$ that
is in the interior of some $P_{\eta}$. There exists

a $k \in \{1,\ldots \hspace{-0.02cm}, \ell\}$ so that $f_{\text{c}}(x) = p_{\pi(k)}(x)$, for $x\in P_\eta$. We treat the cases $k \leq i_\pi$ and $k > i_\pi$ separately. First, if $k \leq i_\pi$, then

\[
f_{\text{c}}(y) = p_{\pi(k)}(y) \geq \min_{i\in \{1,\ldots \hspace{-0.02cm}, i_\pi\}}p_{\pi(i)}(y) = g_\pi(y).
\]

Second, assume that $k > i_\pi$. Let $x $ be a point in the interior of $P_\pi$. Then, $f_{\text{c}}(x) =  p_{\pi(i_\pi)}(x) > p_{\pi(k)}(x)$. Denote by $\mu$ the linear function connecting the points $(x,f_{\text{c}}(x))$ and $(y, f_{\text{c}}(y))$.

Within $\{w = \lambda x + (1-\lambda)y:\mu(w) = f_{\text{c}}(w), 0<  \lambda \leq 1\}$, which is the set of intersection points of $f_{\text{c}}$ and $\mu$ over the interval $[x,y)$, let $w_0$ be the point closest to $y$ (but distinct from $y$).

There exists a $k' \in \{1,\ldots \hspace{-0.02cm}, \ell\}$ such that $f_{\text{c}}(w_0) = p_{\pi(k')}(w_0)$ and $f_{\text{c}}$ coincides with $p_{\pi(k')}$ on a small interval $[w_0,v] \subset [w_0,y]$, with $v \neq w_0$. By continuity of $f_{\text{c}}$, the restriction of the graph of $ p_{\pi(k')}$ to $[w_0,v]$ lies strictly below $\mu$, i.e.,

\[
p_{\pi(k')}(x) < \mu(x), \quad \text{ for } x \in [w_0,v], \,\, x \neq w_0.
\]

Moving from $w_0$ to $y$ along $p_{\pi(k')}$, we get $p_{\pi(k')}(y) < f_{\text{c}}(y)$. On the other hand, moving from $w_0$ to $x$, we obtain $p_{\pi(k')}(x) \geq f_{\text{c}}(x) = p_{\pi(i_\pi)}(x)$, thus $k' \leq i_\pi$. Hence $g_\pi(z)\leq p_{\pi(k')}(z) $, for $z\in [0,1]^n$, and in particular $g_\pi(y)\leq p_{\pi(k')}(y) < f_{\text{c}}(y)$.

As $\pi$ and $y$ above were arbitrary, we can conclude that $f_{\text{c}}(x) \geq g_\pi(x)$, for all $ x\in [0,1]^n$, for all $\pi \in \Sigma$. The proof is complete.

A. Adamatzky  Identification of Cellular Automata, 1 ed., CRC Press,1994.
adamatzky  a    1994    identification of cellular automata

Automatic programming of cellular automata: Identification approach, Kybernetes, vol.26(1997), no.2, pp.126–135.
adamatzky  a    1997    automatic programming of cellular automata identification approach

Identification of cellular automata, Encyclopedia of Complexity and Systems Science,(2009), pp.4739–4751.
adamatzky  a    2009    identification of cellular automata

A. Adamatzky (editor)  Game of Life Cellular Automata, 1 ed., Springer,2010.
adamatzky  a    2010    game of life cellular automata

S. Aguzzoli  Geometrical and Proof Theoretical Issues in Propositional Logics, PhD thesis, University of Siena, Italy,1998.
aguzzoli  s    1998    geometrical and proof theoretical issues in luka propositional logics

P.P.Amato, A.A.Di Nola, and B.B.Gerla

P. Amato, A. Di Nola,  B. Gerla  Neural networks and rational logic, Proceedings of the Annual Meeting of the North American Fuzzy Information Processing Society,2002, pp.506–510.
amato  p   di nola  a   gerla  b    2002    neural networks and rational luka logic

P.P.Amato, A.A.Di Nola, and B.B.Gerla

Neural networks and rational McNaughton functions, Journal of Multiple-Valued Logic and Soft Computing, vol.11(2005), no.1-2, pp.95–110.
amato  p   di nola  a   gerla  b    2005    neural networks and rational uppercasemcuppercasenaughton functions

E. R.E. R.Berlekamp, J. H.J. H.Conway, and R. K.R. K.Guy

E. R. Berlekamp, J. H. Conway,  R. K. Guy  Winning Ways for Your Mathematical Plays, Academic Press, New York,1982.
berlekamp  e r   conway  j h   guy  r k    1982    winning ways for your mathematical plays

A. W.A. W.Burks

A. W. Burks  Von Neumann's self-reproducing automata, Technical Report 08226-11-T, University of Michigan,1969.
burks  a w    1969    von neumanns self reproducing automata

C. C.C. C.Chang

C. C. Chang  Algebraic analysis of many-valued logics, Transactions of the American Mathematical Society, vol.88(1958), no.2, pp.467–490.
chang  c c    1958    algebraic analysis of many valued logics

C. C.C. C.Chang

A new proof of the completeness of the Łukasiewicz axioms, Transactions of the American Mathematical Society, vol.93(1959), no.1, pp.74–80.
chang  c c    1959    a new proof of the completeness of the lukasiewicz axioms

R. L.R. L.Cignoli, I. M.I. M.d'Ottaviano, and D.D.Mundici

R. L. Cignoli, I. M. d'Ottaviano,  D. Mundici  Algebraic Foundations of Many-Valued Reasoning, Springer,2000.
cignoli  r l   dottaviano  i m   mundici  d    2000    algebraic foundations of many valued reasoning

M. Cook  Universality in elementary cellular automata, Complex Systems, vol.15(2004), no.1, pp.1–40.
cook  m    2004    universality in elementary cellular automata

S.S.Das and M. K.M. K.Chakraborty

S. Das  M. K. Chakraborty  Formal logic of cellular automata, Complex Systems, vol.30(2021), no.2, pp.187–203.
das  s   chakraborty  m k    2021    formal logic of cellular automata

A.A.Di Nola, B.B.Gerla, and I.I.Leuştean

A. Di Nola, B. Gerla,  I. Leuştean  Adding real coefficients to Łukasiewicz logic: An application to neural networks, Fuzzy Logic and Applications: 10th International Workshop,(2013), pp.77–85.
di nola  a   gerla  b   leucstean  i    2013    adding real coefficients to lukasiewicz logic an application to neural networks

D.D.Elbrächter, D.D.Perekrestenko, P.P.Grohs, and H.H.Bölcskei

D. Elbrächter, D. Perekrestenko, P. Grohs,  H. Bölcskei  Deep neural network approximation theory, IEEE Transactions on Information Theory, vol.67(2021), no.5, pp.2581–2623.
elbrachter  d   perekrestenko  d   grohs  p   bolcskei  h    2021    deep neural network approximation theory

J. L.J. L.Elman

J. L. Elman  Finding structure in time, Cognitive Science, vol.14(1990), no.2, pp.179–211.
elman  j l    1990    finding structure in time

M. Gardner  The fantastic combinations of John Conway's new solitaire game “life”, Scientific American, vol.223(1970), pp.120–123.
gardner  m    1970    the fantastic combinations of john conways new solitaire game life

B. Gerla  Rational logic and DMV-algebras, Neural Network Worlds, vol.25(2001), pp.1–13.
gerla  b    2001    rational luka logic and uppercasedmv algebras

W. Gilpin  Cellular automata as convolutional neural networks, Physical Review E, vol.100(2019), p.032402.
gilpin  w    2019    cellular automata as convolutional neural networks

A.A.Graves and J.J.Schmidhuber

A. Graves  J. Schmidhuber  Offline handwriting recognition with multidimensional recurrent neural networks, Proceedings of the 21st International Conference on Neural Information Processing Systems,2008.
graves  a   schmidhuber  j    2008    offline handwriting recognition with multidimensional recurrent neural networks

A. Hatcher  Algebraic Topology, Cambridge University Press,2002.
hatcher  a    2002    algebraic topology

I.I.Hubara  et al.

I. Hubara   Quantized neural networks: Training neural networks with low precision weights and activations, Journal of Machine Learning Research, vol.18(2017), no.1, p.6869–6898.
hubara  i   et al    2017    quantized neural networks training neural networks with low precision weights and activations

C.C.Hutter, R.R.Gül, and H.H.Bölcskei

C. Hutter, R. Gül,  H. Bölcskei  Metric entropy limits on recurrent neural network learning of linear dynamical systems, Applied and Computational Harmonic Analysis, vol.59(2022), pp.198–223.
hutter  c   gul  r   bolcskei  h    2022    metric entropy limits on recurrent neural network learning of linear dynamical systems

T.T.Ishida, S.S.Inokuchi, and Y.Y.Kawahara

T. Ishida, S. Inokuchi,  Y. Kawahara  Cellular automata and formulae on monoids, Proceedings of the 11th International Conference on Cellular Automata for Research and Industry,2014, pp.55–64.
ishida  t   inokuchi  s   kawahara  y    2014    cellular automata and formulae on monoids

J.J.Jumper  et al.

J. Jumper   Highly accurate protein structure prediction with AlphaFold, Nature, vol.596(2021), no.7873, pp.583–589.
jumper  j   et al    2021    highly accurate protein structure prediction with alphafold

J. Kari  Theory of cellular automata: A survey, Theoretical Computer Science, vol.334(2005), no.1-3, pp.3–33.
kari  j    2005    theory of cellular automata a survey

S. B.S. B.Kotsiantis

S. B. Kotsiantis  Supervised machine learning: A review of classification techniques, Informatica, vol.31(2007), pp.249–268.
kotsiantis  s b    2007    supervised machine learning a review of classification techniques

G.G.Leifert  et al.

G. Leifert   Cells in multidimensional recurrent neural networks, Journal of Machine Learning Research, vol.17(2016), no.1, p.3313–3349.
leifert  g   et al    2016    cells in multidimensional recurrent neural networks

M.M.Liang and X.X.Hu

M. Liang  X. Hu  Recurrent convolutional neural network for object recognition, 2015 IEEE Conference on Computer Vision and Pattern Recognition,2015, pp.3367–3375.
liang  m   hu  x    2015    recurrent convolutional neural network for object recognition

W. S.W. S.McCulloch and W.W.Pitts

W. S. McCulloch  W. Pitts  A logical calculus of the ideas immanent in nervous activity, Bulletin of Mathematical Biophysics, vol.5(1943), pp.115–133.
mcculloch  w s   pitts  w    1943    logical calculus of the ideas immanent in nervous activity

R. McNaughton  A theorem about infinite-valued sentential logic, , vol.16(1951), no.1, pp.1–13.
mcnaughton  r    1951    theorem about infinite valued sentential logic

D. Mundici  A constructive proof of McNaughton's theorem in infinite-valued logic, , vol.59(1994), no.2, pp.596–602.
mundici  d    1994    a constructive proof of mcnaughtons theorem in infinite valued logic

A.A.Radford, L.L.Metz, and S.S.Chintala

A. Radford, L. Metz,  S. Chintala  Unsupervised representation learning with deep convolutional generative adversarial networks, Proceedings of the International Conference on Learning Representations,2016.
radford  a   metz  l   chintala  s    2016    unsupervised representation learning with deep convolutional generative adversarial networks

P. Rendell  Turing universality of the Game of Life, Collision-Based Computing (A. Adamatzky, editor), Springer,2002, pp.513–539.
rendell  p    2002    turing universality of the game of life

F. C.F. C.Richards, T. P.T. P.Meyer, and N. H.N. H.Packard

F. C. Richards, T. P. Meyer,  N. H. Packard  Extracting cellular automaton rules directly from experimental data, Physica D: Nonlinear Phenomena, vol.45(1990), no.1, pp.189–202.
richards  f c   meyer  t p   packard  n h    1990    extracting cellular automaton rules directly from experimental data

A.A.Rose and J. B.J. B.Rosser

A. Rose  J. B. Rosser  Fragments of many-valued statement calculi, Transactions of the American Mathematical Society, vol.87(1958), no.1, pp.1–53.
rose  a   rosser  j b    1958    fragments of many valued statement calculi

K. H.K. H.Rosen

K. H. Rosen  Discrete Mathematics and Its Applications, 7 ed., New York: McGraw-Hill,2012.
rosen  k h    2012    discrete mathematics and its applications

R.R.Rovatti, M.M.Borgatti, and R.R.Guerrieri

R. Rovatti, M. Borgatti,  R. Guerrieri  A geometric approach to maximum-speed n-dimensional continuous linear interpolation in rectangular grids, IEEE Transactions on Computers, vol.47(1998), no.8, pp.894–899.
rovatti  r   borgatti  m   guerrieri  r    1998    geometric approach to maximum speed n dimensional continuous linear interpolation in rectangular grids

D.D.Silver  et al.

D. Silver   Mastering the game of Go with deep neural networks and tree search, Nature, vol.529(2016), pp.484–489.
silver  d   et al    2016    mastering the game of go with deep neural networks and tree search

L. Smith  Linear Algebra, Springer,1998.
smith  l    1998    linear algebra

A. Tarski  Logic, semantics, metamathematics: Papers from 1923 to 1938, Hackett Publishing,1983.
tarski  a    1983    logic semantics metamathematics papers from 1923 to 1938

S. Ulam  Random processes and transformations, Proceedings of the International Congress on Mathematics, vol. 2,1950, pp.264–275.
ulam  s    1950    random processes and transformations

P. P.P. P.Vaidyanathan

P. P. Vaidyanathan  Multirate systems and filter banks, Pearson Education India,2006.
vaidyanathan  p p    2006    multirate systems and filter banks

J.J.Von Neumann

J. Von Neumann  The general and logical theory of automata, Systems Research for Behavioral Science, Routledge,1968, pp.97–107.
von neumann  j    1968    general and logical theory of automata

B. H.B. H.Voorhees

B. H. Voorhees  Computational analysis of one-dimensional cellular automata, vol. 15, World Scientific,1996.
voorhees  b h    1996    computational analysis of one dimensional cellular automata

R. T.R. T.Wainwright

R. T. Wainwright  Life is universal!, Proceedings of the 7th Conference on Winter Simulation-Volume 2,1974, pp.449–459.
wainwright  r t    1974    life is universal

A.A.Weiser and S. E.S. E.Zarantonello

A. Weiser  S. E. Zarantonello  A note on piecewise linear and multilinear table interpolation in many dimensions, Mathematics of Computation, vol.50(1988), no.181, pp.189–196.
weiser  a   zarantonello  s e    1988    note on piecewise linear and multilinear table interpolation in many dimensions

S. Wolfram  Statistical mechanics of cellular automata, Reviews of Modern Physics, vol.55(1983), pp.601–644.
wolfram  s    1983    statistical mechanics of cellular automata

A New Kind of Science, Wolfram Media,2002.
wolfram  s    2002    a new kind of science

S.S.Wu, G.G.Li, F.F.Chen, and L.L.Shi

S. Wu, G. Li, F. Chen,  L. Shi  Training and inference with integers in deep neural networks, Proceedings of the 6th International Conference on Learning Representations,2018.
wu  s   li  g   chen  f   shi  l    2018    training and inference with integers in deep neural networks

N.N.Wulff and J. A.J. A.Hertz

N. Wulff  J. A. Hertz  Learning cellular automaton dynamics with neural networks, Proceedings of the 5th International Conference on Neural Information Processing Systems, vol. 5,1992, pp.631–638.
wulff  n   hertz  j a    1992    learning cellular automaton dynamics with neural networks

Y.Y.Zhao and S.S.Billings

Y. Zhao  S. Billings  Neighborhood detection using mutual information for the identification of cellular automata, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol.36(2006), no.2, pp.473–479.
zhao  y   billings  s    2006    neighborhood detection using mutual information for the identification of cellular automata

§ PRIVATE APPENDIX (NOT INCLUDED IN SUBMITTED VERSION)

§.§ Proof of lem:ReLUConcatenating

The proof is based on the identity $x = \rho(x) - \rho(-x)$. First, note that by defn:ReLU, we can write
\begin{equation*}
\Phi_1 = W_{L_1}^1 \circ \rho \circ  W_{L_1-1}^1 \circ \cdots \circ \rho  \circ  W_{1}^1
\end{equation*}
\begin{equation*}
\Phi_2 = W_{L_2}^2 \circ \rho \circ  W_{L_2-1}^2 \circ \cdots \circ \rho \circ  W_{1}^2.
\end{equation*}
Next, let $N_{L_1-1}^1$ denote the width of layer $L_1-1$ in $\Phi_1$ and let $N_1^2$ denote the width of layer $1$ in $\Phi_2$. We define the affine transformations $\widetilde{W}_{L_1}^1: \mathbb{R}^{N_{L_1-1}^1} \rightarrow \mathbb{R}^{2d_2} $ and $\widetilde{W}_{1}^2:\mathbb{R}^{2d_2} \rightarrow \mathbb{R}^{N_{1}^2}  $ according to

\begin{align*}
\widetilde{W}_{L_1}^1(x) :&= \begin{pmatrix} \mathbb{I}_{d_2} \\  -\mathbb{I}_{d_2} \end{pmatrix} W_{L_1}^1(x) \\
\widetilde{W}_{1}^2(x) :&= W_1^2 \left( \begin{pmatrix} \mathbb{I}_{d_2} &  -\mathbb{I}_{d_2} \end{pmatrix} x \right).
\end{align*}
The proof is completed by noting that the network

\begin{equation*}
\Psi:=  W_{L_2}^2 \circ \cdots \circ W_2^2 \circ \rho \circ \widetilde{W}_{1}^2 \circ \rho \circ \widetilde{W}_{L_1}^1(x) \circ \rho \circ W_{L_1-1}^1 \circ \cdots \circ W_1^1
\end{equation*}
satisfies the claimed properties.

§.§ Proof of lma:augmenting

Let $\widetilde{W}_j(x):= \text{diag}\left(\mathbb{I}_{d_2}, \mathbb{I}_{d_2}\right)x$, for $j\in\{ \mathcal{L}(\Phi)+1,\ldots \hspace{-0.02cm}, L-1\}$, $\widetilde{W}_L(x):=\left(\mathbb{I}_{d_2} -\mathbb{I}_{d_2}\right)x$, and note that with
\begin{equation*}
\Phi = W_{\mathcal{L}(\Phi)}\circ \rho \circ  W_{\mathcal{L}(\Phi)-1}\circ \rho \circ \cdots \circ \rho \circ W_1,
\end{equation*}

the network
\begin{multline*}
\Psi := \widetilde{W}_L \circ \rho \circ \widetilde{W}_{L-1} \circ \cdots \circ  \widetilde{W}_{\mathcal{L}(\Phi)+1}W_{\mathcal{L}(\Phi)} \circ \begin{pmatrix}
W_{\mathcal{L}(\Phi)} \\ -W_{\mathcal{L}(\Phi)-1}
\end{pmatrix}\\ \circ \rho\circ W_{\mathcal{L}(\Phi)-1}\circ \rho \circ \cdots \circ \rho \circ W_1
\end{multline*}

satisfies the claimed properties.

§.§ Proof of lem:parallelizing

We write the network $\Phi_i$ as

\begin{equation*}
\Phi_i = W_{L}^i \circ \rho \circ W_{L-1}^i \circ  \cdots \circ \rho \circ W_1^i,
\end{equation*}

with $W_\ell^i(x) = A_\ell^ix+b_\ell^i$. Furthermore, we denote the layer dimensions of $\Phi_i$ by $N_0,N_1^i,\ldots \hspace{-0.02cm}, N_L^i$ and set $N_\ell:= \sum_{i=1}^n N_\ell^i$, for $\ell \in \{ 1,\ldots \hspace{-0.02cm}, L\}$. Next, let

\begin{equation*}
W_1(x)  := \begin{pmatrix}
\vdots \\
\end{pmatrix}
\end{equation*}

and define, for $\ell \in \{2,\ldots \hspace{-0.02cm}, L\}$, the block-diagonal matrix $A_\ell := \text{diag} (A_\ell^1, A_\ell^2,$ $\ldots \hspace{-0.02cm},A_\ell^n)$, the vectors $b_\ell := (b_\ell^1,b_\ell^2,\ldots \hspace{-0.02cm}, b_\ell^n)$, and the affine transformations $W_\ell(x):=A_\ell x+b_\ell$. The proof is concluded by noting that
\begin{equation*}
\Psi := W_L \circ \rho \circ W_{L-1} \circ \rho \circ \cdots \circ \rho \circ W_1
\end{equation*}
satisfies the claimed properties.

The basic packages loaded by amsart are amsmath.sty
and amsthm.sty, and the document guides for them are
amsldoc and amsthdoc; these (and the  book)
are also the basic guides for asl.sty.[These files
can be picked up from the CTAN sites where  resources are
distributed, and, for convenience, they are also posted in the
ASL Typesetting Office site.] The -nically ambitious will
surely want to read them, but for most authors of papers in logic
who know  and article, this
brief document together with the briefer amsthdoc will
serve the purpose, perhaps supplemented by occasional excursions
into the more complex amsldoc when some very special effect
is required.

In fact, asl.sty loads several packages in
addition to amsmath.sty and amsthm.sty, and so all
macros and symbols in them are available for ASL-typesetting.
Here is a complete list of all the packages loaded by

amsmath Defines extra environments for multline displayed
equations, as well as a number of other enhancements for math.

amsthm Provides a proof environment and
extensions for the newtheorem command.

amstext Provides a text command for
typesetting a fragment of text inside a display.

amsbsy Defines boldsymbol and pmb `poor man's
bold' commands.

amsopn Provides DeclareMathOperator for defining new
`operator names' like sin and lim.

amssymb Makes all the symbols in the AMS fonts available.
(Names for them are defined in amssymb.sty and also in

latexsym Makes all the  symbols available. (These
are defined in the  book.)