WorksComputer Science
A polynomial-size logical twin for neural networks
Abstract
A logical twin of a neural network is a logical representation that mimics the computation of the network through logical formulas. We revisit two earlier proposals for constructing logical twins of feedforward neural networks in Łukasiewicz logic, both of which are susceptible to exponential blow-up in running time and representation size. Building on ideas from both approaches, we present a new construction that directly yields logical twins in Łukasiewicz logic. We show that this construction can be computed in polynomial time and produces polynomial-size logical twins. Finally, we report an empirical evaluation of the three methods, showing that the new proposal substantially outperforms the other two.
Introduction
A logical twin of a neural network, as we propose to use this term, is a representation of such a network in the formal language of a logical framework. Just as formulas of classical logic represent Boolean functions and formulas of Łukasiewicz logic represent McNaughton functions, formulas of a logical system may represent the functions computed by a neural network. In this way, the computation performed by a neural network, usually represented by a graph circuit together with its associated weights and biases, may be carried out through evaluations of logical formulas comprised in its logical twin.
Neural networks are traditionally associated with the blackbox problem, which may be understood as the difficulty of justifying their learned weights and biases and of explaining their decisions, classifications, and the way they perform tasks [4, 6]. By contrast, logic and symbolic frameworks are usually regarded as being grounded in established laws of reasoning and as having a neatly defined semantics. In this sense, a logical twin may offer a new perspective on the blackbox problem by presenting its neural network twin in a symbolic framework that is often more interpretable, even though we acknowledge that logical formulas are not necessarily amenable to human interpretation, especially when they are large. A more immediate possibility, however, lies in the use of such logical twins for formal verification, which has already proved feasible for some neural networks and some of their properties—namely, reachability and robustness [17, 18].
The architecture of feedforward neural networks with the ReLU activation function is widely used in practice. If such an architecture is considered with input values in the unit interval and with the truncated identity as the activation function in the output layer, then each output value of the network, as a function of its input values, determines a rational McNaughton function [17]. Such functions are continuous piecewise linear, and their linear pieces have rational coefficients. In this work, we refer to neural networks of this kind as ReLU–TId neural networks.
Formulas of Łukasiewicz logic represent McNaughton functions, which are the particular case of rational McNaughton functions whose linear pieces are constrained to have integer coefficients. Thus, direct representations by Łukasiewicz formulas are restricted to McNaughton functions. One approach to circumvent this restriction is representation modulo satisfiability in Łukasiewicz logic, formalized in the system L-MODSAT, a technique for implicitly representing functions by logical formulas proposed by Preto and Finger [15, 16].
In this setting, a function is represented not by a single formula, but by a pair , where is a formula and is a set of formulas. Then, once designated propositional variables are evaluated by a valuation according to the arguments of the function, its value is given by , provided that satisfies the set . Rational McNaughton functions were shown to be representable in L-MODSAT. Moreover, these representations can be constructed in polynomial time when the functions are given in the so-called closed regional format.
A regional format is a natural representation of piecewise linear functions in which the domain is partitioned into regions so that each linear piece coincides with the function over an associated region. Thus, an encoding of a function in regional format consists of pairs , where is a linear piece and is a region. When the regions are polyhedra given by linear inequalities and these pairs satisfy a special property called lattice property, the encoding is said to be in closed regional format. In this case, a lattice representation can be built from it. The construction of representations in L-MODSAT is based on this lattice representation; see Section 3.1.
In order to build a logical twin for a ReLU–TId neural network, one must still extract a regional representation from its graph circuit as an intermediate step. This was the starting point of our earlier workshop paper Regional, Lattice and Logical Representations of Neural Networks, published in the proceedings of the 19th International Workshop on Logical and Semantic Frameworks, with Applications (LSFA 2024) [19], where an algorithm was provided for carrying out this translation. Although the translation produced by that algorithm is not guaranteed to satisfy the lattice property, our experiments indicated that such failures are rare in practice. The present work continues that line of research. However, rather than simply extending the workshop version, this article reframes the problem around a new algorithmic approach that substantially outperforms the previous method.
Beyond the problem that the lattice property is not guaranteed, and therefore that correctness or exactness of the resulting representation is not guaranteed either, that algorithm is exponential in the number of neurons of the ReLU–TId neural network. For this reason, in the present work we propose a new algorithm that abandons the intermediate step of constructing a regional format representation and, inspired by the work of [21], constructs a representation directly by following the architecture of the network.
The algorithm by Zhang and Bö lcskei [21] represents each neuron of a neural network separately by logical formulas and then mimics the compositional, circuit-structured nature of the network through substitutions in logical formulas. It uses both Łukasiewicz logic and rational Łukasiewicz logic, an extension of the former, to represent the neurons individually. However, this technique cannot be applied directly to ReLU–TId neural networks, but only to equivalent neural networks that must first be computed. Unfortunately, these equivalent neural networks generally have more neurons than the original ones, which may cause an exponential blow-up in this intermediate representation.
In this work, we present a polynomial-time algorithm for directly representing a ReLU–TId neural network in the system L-MODSAT, thereby yielding a polynomial-size logical twin. The neural network is first transformed into an equivalent one by operations that we call output and input normalizations. However, this equivalent network has the same number of neurons as the original one. Then, the function computed by each neuron, which is a truncated linear function, is represented in L-MODSAT. These functions are particular cases of rational McNaughton functions whose representations in L-MODSAT are even less complex. Finally, we leverage the representational framework of L-MODSAT to represent the circuit-based compositions by means of interface propositional variables and linking formulas, producing the logical twin.
We also show that the approach of Zhang and Bö lcskei [21] can be adapted so as to use neuron representations in L-MODSAT together with interface propositional variables and linking formulas. Thus, the paper brings together three methods for constructing logical twins of ReLU–TId neural networks in the L-MODSAT setting: a lattice-based method built on regional representations, an architecture-based compositional method, and our new polynomial-time proposal yielding polynomial-size logical twins. Finally, we present an empirical evaluation based on implementations of all three methods on randomly generated ReLU–TId neural networks, showing that the new proposal performs substantially better than the other two.
The rest of this work is organized as follows. Section 2 presents the necessary preliminaries on feedforward neural networks, Łukasiewicz logic, and semantics modulo satisfiability. Section 3 revisits two approaches to the construction of logical twins with exponential blow-up, namely the lattice-based method and the architecture-based compositional method. Section 4 introduces our new polynomial-size logical twin construction. Section 5 describes the implementations of the proposed methods and reports the experimental evaluation. Finally, Section 6 concludes the paper.
Preliminaries
Feedforward neural networks
A feedforward neural network may be given (and represented) by a graph whose nodes are partitioned into an ordered family of ordered sets , where a node is called a neuron and each is a layer. All neurons in layer , for , are linked by an edge to all neurons in layer establishing a computational circuit such that all output values of neurons in are input values to each neuron in . There is a linear function associated to each neuron in layer , for and . In the context of neural networks, the coefficients of are called weights, and the constant term is called the bias. For a tuple of input values to neuron , it has as output the value , where is an activation function. Thus, for as input to layer , it has as outputs the values in the tuple
Input values to in a tuple are neatly associated to the neurons , called input neurons. For uniformity with the the remaining layers, each input neuron may be regarded as receiving the whole input tuple and computing , where is the identity function and is the coordinate projection given by , for . Thus, although its formal input is the whole tuple, effectively depends only on the -th input value.
In this way, from an input tuple , produces the output values in the -tuple
Neurons in are called output neurons. We say that each output neuron in a neural network computes a function for which the value is given in function of the input tuple . Let us denote by the set of all neurons in the neural network , except the ones in the input layer.
The input values of a neural network may be restricted to a subset of . In this work, we focus on ReLU–TId neural networks: they accept input values from and have as activation functions the rectified linear unit , given by , for , and the truncated identity function , given by . Such activation functions are given by piecewise linear definitions as follows.
Example 2.1. Let be a ReLU–TId neural network with , where , and . The graph of depicted in Figure 1 highlights the input values and in layer and the functions in layers and , which are given by:
;
;
.
Figure 1. Graph of the ReLU–TId neural network
For a tuple of inputs to , we have and, thus, .
A rational McNaughton function is a function that satisfies the following:
is continuous with respect to the usual topology of as an interval of the real number line;
There are linear polynomials over with rational coefficients such that, for each point , there is an index with . Polynomials are the linear pieces of .
A neural network whose output neurons exactly compute rational McNaughton functions in function of its input neurons is called a -rational McNaughton neural network (-RMcN); a 1-RMcN is also called rational McNaughton neural network (RMcN).
A useful observation is that ReLU–TId neural networks are -rational McNaughton neural networks [17]. Thus, once logical representations of rational McNaughton functions have been established, they naturally yield logical representations of such neural networks.
Łukasiewicz logic
To obtain logical representations of neural networks, we introduce Łukasiewicz logic () [5]. The basic language of comprehends formulas freely generated from a countable set of propositional variables , a binary disjunction operator and a unary negation operator . For the semantics of , a valuation is a function that obeys, for :
From disjunction and negation one may derive the following operators.
A formula is satisfiable if there exists a valuation such that ; otherwise it is unsatisfiable. A set of formulas is satisfiable if there exists a valuation such that , for all . Note that iff ; similarly, iff . Let be a propositional variable, then , for any ; we define the constant by . We also define , and , times, for ; and .
A well-known result due to McNaughton states that -formulas represent McNaughton functions, which are rational McNaughton functions constrained to allow only integer coefficients in their linear pieces. This means that, given a McNaughton function , there is a formula whose propositional variables are such that
whenever is a valuation for which . Conversely, every McNaughton function is represented by some -formula in this setting [12, 14].
Therefore, McNaughton’s Theorem guarantees that a particular class of -rational McNaughton neural networks—namely, those computing (integer) McNaughton functions—admits logical representations within the framework of Łukasiewicz logic.
Semantics modulo satisfiability
Although -formulas do not represent rational McNaughton functions in general, this issue may be circumvented by adopting different approaches. One possibility is to extend the language of , yielding the rational Łukasiewicz logic, as done by Gerla [10]. The language is extended with unary division operators , for , in such a way that the semantics entails . The analogous of McNaughton’s Theorem for rational Łukasiewicz logic ensures that its formulas represent all rational McNaughton functions and, conversely, any such function may be represented by some formula in this system [12, 14].
Another approach, which we follow in this work, is to represent such functions implicitly in plain using the technique of representation modulo satisfiability [8, 15, 16]. We introduce the latter approach below by means of some particular cases; in Section 3.1 we discuss the general case.
Let denote the -semantics, that is the set of all valuations. Also, let denote the set of valuations that satisfy a set of formulas ; we call such a restricted set of valuations a semantics modulo satisfiability. Given a rational McNaughton function , a formula and a set of formulas , we say that represents modulo -satisfiable or that the pair represents (in the system L-MODSAT) if, for distinguished propositional variables :
For all , there exists some valuation , such that , for ;
For all valuations , such that , for , we have ; and
, for all .
Example 2.2. Constant functions with value , where , may be represented by
where formula is only the propositional variable and set is a singleton comprehending formula , which we denote by . In fact, for any valuation , we have that . Also, functions that take constant value , with and , may be represented by the pair .
Example 2.3. Let be the function given by . It may be represented by
For any valuation , the propositional variable is assigned one third of the value assigned to the propositional variable .
Note that the expressions as , with , have exponential length on the binary representation of . By means of a semantics modulo satisfiability, such an unwanted issue is avoidable: using new propositional variables , replace formula with
where comes from the binary representation of , and let be the set that comprehends the following formulas:
The formulas above define the propositional variables and we have that , for any valuation .
Any rational McNaughton function admits a representation in Ł-MODSAT [15, 16]. In particular, any truncated linear function —that is, a rational McNaughton function of the form , where is a linear function—admits a polynomial representation in Ł-MODSAT. The examples given in this section are truncated linear functions for which . For details on this construction and algorithm, see [16 Section 5.2].
A note on time complexity. In order to better interpret the experimental results in § 5, let us briefly refine the running-time analysis for computing Ł-MODSAT representations of truncated linear functions. A closer inspection of [15, Algorithms 1, 2, and 3; proof of Theorem 5.6] leads us to a more explicit bound for the construction of a representation of , where
and each coefficient is given as a fraction . Let be the length of the binary encoding of the coefficients, where denotes the binary length of an integer . The running time of the construction may be decomposed into the time needed to compute:
The sets of indices and ;
The values ;
The factor ; and
The values .
Once these values have been computed, the remaining formula-construction phase takes
time, where is an upper bound on the length of a propositional variable identifier.
In the exact version of the algorithm, computing requires rational arithmetic, while computing the products may involve arbitrary-precision integer multiplication. In practical implementations, however, the sums defining might be evaluated using fixed-precision floating-point arithmetic, while and the products may be represented using fixed-width machine integers. Moreover, propositional variables might be represented by fixed-size identifiers. Under these assumptions, and provided that formulas are constructed incrementally, the construction procedure runs in time linear in within the computational regime supported by the implementation.
Logical twins with exponential blow-up
Lattice-based logical representations. A possibility to represent rational McNaughton functions (consequently, -rational McNaughton neural networks) is through the regional formats. Let denote the topological interior of and say that, given functions , is above over the set if , for all . A given rational McNaughton function is said to be encoded in the closed regional format if it is given by (not necessarily distinct) linear pieces
where , and , such that each is identical to over a polyhedron , called region. These regions are determined by the finite intersection of half-spaces given by linear inequalities as
and such setting of linear pieces and regions satisfy the following properties:
;
, for ; and
The lattice property: for , there is such that linear piece is above linear piece over region and linear piece is above linear piece over region .
The lattice property yields the possibility to represent rational McNaughton functions and -RMcN by lattice representations—i.e., based on operations of maximum and minimum over functions—as follows. First, let be the function given by
Note that , for all , which is obvious for and follows from the lattice property for where . In this way, we have that
When a rational McNaughton function is given in an encoding that nearly matches the closed regional format, except that satisfaction of the lattice property is not guaranteed, we say that it is in pre-closed regional format. In this case, however, the above construction is not guaranteed to yield a representation; for a counterexample, see [16 Example 5].
Since lattice operations are expressed in L through the minimum and maximum operators, piecewise linear functions may admit lattice representations in L whenever their linear pieces are representable in this system. The same applies when their truncated linear pieces are representable in L, as one may replace (8) by
This construction yields McNaughton’s Theorem, according to which McNaughton functions are represented, in the sense of (4), by formulas of L. Another consequence is that rational McNaughton functions may be represented in the L-MODSAT system. Together with the representation of truncated linear functions (§ 2.3), the lattice representation yields a polynomial-time algorithm for such constructions from closed regional format inputs; for details, see [16 Section 5.3].
To determine whether a linear piece lies above over a region , one can compute the minimum value of over : if , then is above over ; otherwise, it is not. Since regions are given by polyhedra as in (7), this decision problem can be solved by linear programming, which is known to be solvable in polynomial time [2]. Therefore, to construct lattice representations, linear programs must be solved in order to establish expressions (8) or (9).
In view of the above, establishing lattice-based logical representations in L for ReLU–TId neural networks first requires representing them in the regional formats. In the following, we sketch an algorithm for constructing such representations in pre-closed regional format.
Given a ReLU–TId neural network for which , our aim is to translate it into a tuple , where each , , is the codification for a rational McNaughton function in pre-closed regional format, which is the function computed by through the path to its -th output neuron. Each is a set of pairs , where is a linear piece and is its associated region.
Let us begin by analyzing the computation that takes place in each neuron of . Given a tuple of input values to neuron of , where and so , the computation proceeds in two steps: first, the linear function is evaluated for ; second, the activation function is evaluated for . In the second step, one from the two possible values highlighted in the piecewise definition of ReLU in (1) is chosen as the output of . Such choice depends on the position of point in relation to the hyperplane given by equation , since it may be a point lying either in the half-space given by or in the half-space given by . For instance, for as input to the neuron of in Example 2.1, the fact that indicates that lies in one of the half-spaces determined by where, according to , outputs 0. On the other hand, if is given as input to the neuron , as , lies in the half-space determined by where, according to , outputs . Figure 2a depicts the position of in relation to these hyperplanes.
Similarly, in case , we have that and, then, one from three possible values is chosen for depending on the position of in relation to the hyperplanes and . It may be a point lying either in the half-space given by , or in the half-space given by or in the intersection of half-spaces and . Again, for as input to the neural network in Example 2.1, we have . Since and , lies in a position relative to and where, according to , outputs .
Now, still considering Example 2.1, let be any point that, as , satisfies both inequalities
Then, to satisfy inequalities and is equivalent to satisfy inequalities
As the former inequalities (10), the latter inequalities (11) are also linear over tuples from of input values to the neural network . Moreover, for satisfying inequalities (10) and (11), we have that . In this way, we have just devised a region and its associated linear piece for the rational McNaughton function computed by neural network .
Generalizing the observations above, the idea behind the base algorithm for building , for , is to compute each pair beginning by: associating a symbol between and to each neuron , for , alluding to one of the two possible positions of an input to in relation to the hyperplane —i.e., lying in the half-space or in the half-space —; and associating a symbol among , and to the neuron alluding to one of the three possible positions of an input to in relation to the hyperplanes and —i.e., lying in the half-space , or in the half-space or in the intersection of the half-spaces and . These associations of symbols to all the neurons in layers determine a configuration of symbols. Then, the algorithm proceeds by defining as an intersection of half-spaces based on such configuration of symbols and establishing a linear expression for such that , for .
Example 3.1. For the neural network in Example 2.1, in a configuration of symbols where we associate to and to , the consequent region should comprehend the inequalities and (shaded area in Figure 2a). For an input that satisfies these inequalities, we have the outputs and which, composed with , gives us the expression . In this way, in case we complete the configuration of symbols by associating to , should comprehend the inequality and should be given by . In case we associate to , should comprehend the inequality and should be given by . In the last case, if we associate to , should comprehend both inequalities and (shaded area in Figure 2b) and should be given by . Note that the last case is the only one where region would be non-empty.

Figure 2. Determining a region for neural network
In order to build the entire representative tuple , the algorithm needs to compute all the pairs , each one associated to a different configuration of symbols, for all possible configurations of symbols. Thus, the entire computation of ends up with
pairs .
For a comprehensive presentation of the base algorithm, together with auxiliary methods proposed to mitigate its high complexity, we refer the reader to our earlier LSFA 2024 paper [19]. That paper also reports empirical results showing that exponential blow-up remains unavoidable, even when such auxiliary methods are combined with the base algorithm. Interestingly, among the 1,100 randomly generated ReLU-Tld neural networks considered in those experiments, only one produced a regional representation that failed to satisfy the lattice property and therefore did not yield a representation in the closed regional format.
Architecture-based compositional logical representations.
Another approach to the logical representation of ReLU–TId neural networks, where their compositional structure is exploited, is due to Zhang and Bölcskei [21]. Following the architecture of a neural network, the logical representations of its individual neurons are composed so as to obtain a representation of the entire network. In this way, the logical representation is proportional to the graph representation, thereby avoiding the exponential blow-up associated with regional representations.
However, a generic neuron in a ReLU–TId neural network does not necessarily compute a rational McNaughton function, since hidden-layer neurons do not necessarily have both inputs and output in the unit interval . Therefore, the network is first transformed into an equivalent one whose neurons are suitable for representation in Łukasiewicz logic. Each hidden-layer neuron, which computes a linear function composed with a ReLU activation function, is then replaced by a sequence of neurons computing linear functions composed with TId activation functions.
Such a neuron in the hidden layer computes a function , which is given by
where is a linear function with rational coefficients. The output of lies in the nonnegative real half-line .
As the inputs of a ReLU–TId neural network are constrained to , it follows that the input and output of every neuron in the network, each of which computes a continuous function, are constrained to a closed interval. Let be the maximum output value attained by neuron . Then the computation of may be replaced by the sum of the outputs of neurons
given by
for , where each is still a linear function with rational coefficients. In fact, assuming , we have
Note that, since the output of each is constrained to the unit interval , these neurons compute rational McNaughton functions provided that their inputs are also constrained to . Particularly, with such a constraint, a neuron computes a truncated linear function.
Once each neuron , for , has been replaced in a hidden layer by a sequence of neurons , each neuron in layer must be adapted to this new input configuration. Let be the maximum output value attained by the original neuron , and let
Suppose that computes the function
where and is given by
for . Then is replaced by a neuron , which receives inputs and computes the function
where is given by
for . Originally, the variable in was intended to receive the output of neuron ; now, the variable in is intended to receive the output of neuron . Note that is still a linear function with rational coefficients.
Example 3.2. For the neural network in Example 2.1, the maximum value computed by function is . Therefore, neuron should be replaced by two neurons and , whose associated linear functions are, respectively, given by:
; and
.
Neuron should also be replaced by two neurons—namely, and . Then, neuron should be replaced by a neuron associated to linear function , given by
Therefore, the transformation of a neural network proceeds one layer at a time, starting from layer : each neuron in layer , whose input values lie in , is replaced by a sequence of neurons , whose output values also lie in . Then, before the same procedure is applied to the neurons in layer , they must first be adapted to receive inputs, whereas originally they received only . Note that the neurons in layer do not require any adaptation of their input values, since the inputs to a ReLU–TId neural network already lie in . Likewise, the neurons in the output layer do not need to be replaced by a sequence of neurons , since they already compute the TId activation function.
Let be the neural network obtained from a ReLU–TId neural network by the transformation discussed above. In [21], the function computed by each neuron in , which is a rational McNaughton function, is first represented, in the traditional sense, by a formula of Łukasiewicz logic or rational Łukasiewicz logic, depending on whether the weights are integers or rational numbers. Let be the representations of the functions computed by the neurons in layer . Also, let be the propositional variables corresponding to the variables in the function computed by a neuron in layer . Then the composition of neurons yields a representation by replacing each in with . Performing these substitutions throughout the compositions in yields a formula that is a logical twin of , and hence of .
Going beyond [21], we now show how to adapt these representations to the L-MODSAT setting. Let be a representation in the L-MODSAT system of the function computed by each neuron . In this setting, the propositional variables corresponding to the function variables must be distinct across neurons in different layers. Thus, we write such variables as the interface propositional variables , to indicate their association with Layer . Moreover, let us agree that such propositional variables are the only ones shared among representations . Let be a neuron in layer whose output feeds the function variable of a neuron in layer . Then, instead of composing formulas directly, we may simulate this composition by asserting the linking formulas and , where is a fresh propositional variable associated with neuron . This technique avoids repeating the whole formula , which encodes an input to all neurons in layer , reducing the representation complexity.
Let us write for the propositional variables intended to be evaluated with the inputs to the network; these are evaluated according to the input tuple , whose components correspond to the input neurons in layer . Also, let be an output neuron of . Then, the function computed by with output at is represented in L-MODSAT by the pair , where
In this way, for every L-valuation satisfying and such that , we have
Therefore, the pairs constitute a logical twin of , and hence of . In the next section, we revisit in greater detail the representations given by the pairs .
To conclude this exposition, we note that, while following the architecture of the neural network avoids the exponential blow-up associated with regional representations, there is still no guarantee that replacing each neuron by neurons will not itself result in such a blow-up. Note that, if is encoded in binary, then a quantity proportional to is only pseudo-polynomial: it is polynomial in the numerical value of , but exponential in the length of its binary representation.
A polynomial-size logical twin
Inspired by the logical twins introduced in the previous section, we now present a new architecture-based compositional representation founded on the L-MODSAT framework. As in the previous construction, following the network architecture avoids the exponential blow-up associated with regional formats. The crucial difference, however, is that the present proposal starts from a ReLU–TId neural network and yields an equivalent neural network with the same number of neurons, thus avoiding the possible exponential blow-up arising from the use of a much larger equivalent network.
When establishing an equivalent network in this approach, each neuron may undergo two normalizing transformations: input normalization and output normalization. Recall that, since the inputs to a ReLU–TId neural network lie in and each neuron computes a continuous function, the output of every neuron is constrained to a closed interval.
The output normalization consists in replacing a neuron with a neuron whose output lies in the unit interval . Let be a neuron in a hidden layer computing a function , given by
where is a linear function with rational coefficients. Let be the maximum value attained by , assuming that its inputs are constrained to ; so we have . Then, we define neuron , given by
Neuron computes a rational McNaughton function, particularly a truncated linear function, provided that its inputs are constrained to . Moreover, the outputs of the original neuron can be easily recovered, as stated in the following result.
Lemma 4.1. Let be a neuron in the hidden layer given by (12), and let be the maximum value attained by , assuming that its inputs are constrained to the unit interval . Also, let be the neuron obtained from by output normalization as in (13). Then the output of is guaranteed to lie in , and
for every .
Proof. The output of is in due TId being its activation function. Let . First, let . If , then , since and activation functions are ReLU and TId, respectively. If , then noting that , we have that
The case is obvious.
Note that output normalization is not necessary if . In this case, we already have that , for .
Now, once each neuron , , has been replaced in a hidden layer by its output-normalized version, each neuron in layer must be adapted in order to preserve the coherence of the network. To this end, each neuron is replaced by a neuron through a procedure called input normalization. Let be the maximum output value attained by the original neuron , and suppose that computes the function
where and is given by
for . Then is replaced by a neuron that computes the function
where is given by
for . Again, is a linear function with rational coefficients. Moreover, input normalization ensures that the output normalization performed in layer leaves the outputs of unchanged, as established by the following result.
Lemma 4.2. Let be a neuron in layer with maximum output value on , and let be its output-normalized version, for each . Also, let be the neuron obtained from a neuron in layer , given by (14), through input normalization regarding neurons , as in (15). Then,
for every .
Proof. For each and every , Lemma 4.1 guarantees that
Hence, by the definitions of and in (14) and (15), respectively,
Therefore,
Example 4.3. For the neural network in Example 2.1, the maximum values computed by functions and are and . Therefore, neurons and should be replaced by two neurons and , respectively, whose associated linear functions are, respectively, given by:
; and
.
Then, neuron should be replaced by a neuron associated to linear function , given by
Again in this proposal, the transformation of a neural network proceeds one layer at a time, starting from layer : each neuron in layer , whose input values lie in , is replaced by its output-normalized version , whose output value also lie in . Then, before the same procedure is applied to the neurons in layer , those neurons are first replaced by their input-normalized versions. The neurons in layer do not require input normalization, since the inputs to a ReLU–TId neural network already lie in ; equivalently, they may be normalized using , for . Likewise, the neurons in the output layer do not require output normalization, since they already compute the TId activation function.
Theorem 4.4. Let be a ReLU–TId neural network with , where , and let be a neural network obtained from , one layer at a time starting from layer , in such a way that:
Layer of is obtained from layer of by output normalization of its neurons;
For each , layer of is obtained from layer of by first applying input normalization to its neurons, according to the -values arising from the output normalization of layer , and then applying output normalization to its neurons;
Layer of is obtained from layer of by input normalization of its neurons.
Then and are equivalent, in the sense that , for every .
Proof. Let be an input tuple. For each , let
where is the -th layer of ; note that . Thus, and are the output tuples of the -th layers of and , respectively. Also, let stand for the neuron obtained from after input normalization, and let stand for the neuron obtained from after output normalization. If , let , and if , let .
For each hidden layer , with , write
We claim that, for every and every , there exists a value , namely the maximum value attained by the neuron on , such that
For , the layer is obtained from only by output normalization. Hence, by Lemma 4.1,
for every .
Now assume that (16) holds for some . Fix . Since , Lemma 4.2 yields
On the other hand, for each , by Lemma 4.1 and the induction hypothesis,
Therefore,
Since is the output-normalized version of , Lemma 4.1 yields
Hence,
that is,
This proves (16) for all .
Finally, consider the output layer . By construction, is obtained from only by input normalization. Fix . Since , Lemma 4.2 yields
By Lemma 4.1 and (16) for , for every we have
Therefore,
Hence,
for every .
Let us now proceed to the representation in L-MODSAT of a ReLU–TId neural network by means of its equivalent network , as established by the theorem above, following the same path sketched in Section 3.2. Since each neuron computes a truncated linear function, let be its representation in the L-MODSAT system. Let denote the propositional variable in pairs corresponding to the function variable of the functions computed by the neurons . The propositional variables are intended to be evaluated with the inputs to the network . Also, for each neuron , let be a fresh propositional variable. Then, the function computed by with output at neuron is represented in L-MODSAT by the pair , where
Theorem 4.5. Let be a ReLU–TId neural network with , and let be its equivalent neural network obtained by the output–input normalization procedure discussed in this section. Also, let be the L-MODSAT representations of the neurons , and let , for , be the pairs given by (17). Then, for any -valuation satisfying and such that , we have
for every . Moreover, for every , there exists at least one -valuation satisfying such that .
Proof. Let be a -valuation satisfying such that , and let . For each , let
where is the -th layer of . Also, write
We show by induction on the layers of that, for every neuron , for , one has
For , we have that , and the formulas in (17) ensure that the propositional variables are evaluated by the corresponding inputs . Since satisfies , it follows from the definition of representation modulo satisfiability that
for every neuron . Then, by the linking formulas in , we also have
for every neuron .
Assume now that the claim holds for every neuron in layer , where . By the linking formulas
in , the interface propositional variables are evaluated by the outputs of the neurons , that is, by . Since satisfies for every neuron , the definition of representation modulo satisfiability yields
for every neuron . Again, using the linking formulas , we conclude that
for every neuron . This completes the induction.
In particular, for every ,
By Theorem 4.4, we also have
and hence the first claim follows.
For the second claim, let . Define a partial -assignment by setting
for , and
for every and every , together with
for every . By the definition of representation modulo satisfiability, for each neuron this partial assignment extends to a -valuation satisfying . Since different neuron representations share only the interface propositional variables , and these have been assigned consistently, these local extensions can be combined into a global -valuation satisfying . This proves the existence claim. □
We have just established that the sequence of pairs
constitute a logical twin of , and hence of . We now turn to the algorithmic aspects of this construction.
For complexity purposes, we measure the size of a ReLU–TId neural network by the length of its graph encoding, namely, the total length of the binary representations of its weights and biases—that is, the coefficients of the linear functions computed by its neurons—, together with the information needed to encode the connectivity of the network. Let denote the length of the graph encoding of .
A possible algorithm for building the representation traverses all neurons of the ReLU–TId neural network in order to construct an equivalent neural network , whose neurons are obtained by output–input normalization whenever necessary. These normalization procedures involve only elementary operations on rational numbers, together with the computation of the maximum value attained by a neuron given by (12). More precisely, if
then its maximum value on is
For each neuron, only a bounded number of such elementary operations is performed. Hence, the transformation from to runs in polynomial time in the size of the graph encoding of .
Then, the algorithm proceeds by traversing all neurons and, for each such neuron, computing:
The L-MODSAT representation of the function computed by ;
The linking formula , where is a fresh propositional variable;
The linking formulas connecting to the propositional variables corresponding to the inputs of the neurons in the next layer.
Accordingly, the set comprises all such formulas for all , together with the formulas , for . In addition, the representation includes the formulas , for .
By [16 Theorem 11], the cost of computing a representation for a truncated linear function is polynomial in the total length of the binary representations of its coefficients, written as fractions; we revisit and refine this result in Section 2. Since the coefficients of the neurons of are obtained from those of by polynomial-time normalization procedures, the encoding length of each such truncated linear function is polynomial in . Hence, each local representation has polynomial size in .
Moreover, has the same number of neurons as , and this number is bounded by the length of the graph encoding of . Therefore, the total size of all local representations , for , is polynomial in .
When assembling the global representation , these local representations must be renamed apart at the level of their auxiliary propositional variables, except for the designated interface variables , which are intended to be shared. This can be done by systematically renaming the auxiliary variables in each . Since the total number of propositional variables occurring in all local representations is polynomial in , and since the global construction adds only polynomially many further propositional variables—namely, , for , and , for —the total number of propositional variables occurring in is polynomial in .
Let us agree that propositional variables in are encoded by the concatenation of the symbol X with the binary representation of a natural number, for instance X0, X1, X1010, X1100100, and so on. Under this encoding, the length of the representation of each propositional variable is logarithmic in the total number of propositional variables, and hence polynomial in . It follows that the cost of computing all local representations so that only the designated interface variables are shared is polynomial in .
Moreover, apart from the computation of the local L-MODSAT representations themselves, only a bounded number of formulas containing a constant number of symbols is introduced for each neuron. It follows that the overall construction runs in polynomial time in . We may therefore state the following result.
Theorem 4.6. The construction above yields a layer-by-layer, neuron-by-neuron algorithm for computing a logical twin of a ReLU–TId neural network in the L-MODSAT system. Moreover, this algorithm terminates in polynomial time in the length of the graph encoding of . Hence, the resulting logical twin has polynomial size in the length of the graph encoding of .
Implementation and experimental evaluation
We developed C++ implementations of the three methods described in this work in order to evaluate their performance on randomly generated neural networks. We refer to these methods as Regional–Lattice (Section 3.1), Compositional (§ 3.1), and PolyTwin (§ 4), in the order in which they were presented above. The source code of our implementations, together with a script for the experiments, is publicly available.1
The Regional–Lattice method consists of two steps: first, nn2pwl, which translates a ReLU–TId neural network into the pre-closed regional format; and second, a routine that constructs a lattice representation in L-MODSAT. A routine for constructing L-MODSAT representations of truncated linear functions is also used in Compositional and PolyTwin. For the routines used to construct L-MODSAT representations, we relied on a publicly available C++ implementation.2
Weights and biases of a neural network are represented by fixed-width machine types; so output–input normalizations in PolyTwin are performed via floating-point operations. When such values are required as fractions for truncated linear function representations in L-MODSAT, we approximate them by fractions whose numerators and denominators are bounded by an implementation-defined limit, and then reduce them to lowest terms.
For each randomly generated ReLU–TId neural network , at least one of the three methods constructs a pair . For each such pair, we measure the user CPU running time required by the method used to complete the construction, as well as the total complexity of the formulas in . The complexity of a formula , as usual, is defined inductively by: , if is a propositional variable; ; and , if is a binary operator. The total complexity of a set of formulas is the summation of these formulas individual complexities.
The experiments reported in our earlier LSFA 2024 paper showed that the complexity of the regional representation of ReLU–TId neural networks grows more sharply when the number of neurons per layer is varied while the number of layers is kept fixed than when the number of layers is varied while the number of neurons per layer is kept fixed [19].
For that reason, in the first batch of experiments reported here, we generate ReLU–TId neural networks with 5 hidden layers and a single neuron in the output layer. The numbers of neurons in the input layer and in each hidden layer vary from 1 to 7. For each configuration, 100 ReLU–TId neural networks are generated. The weights and biases of these networks have the form , where and are generated uniformly from and , respectively.
The three considered methods are applied to the neural networks generated in this first batch of experiments. However, it must be noted that, while the pairs constructed by Compositional and PolyTwin are logical twins of , the same is not guaranteed for the pairs constructed by Regional–Lattice. This holds only when the regional format output by NN2PWL satisfies the lattice property.
Therefore, we rerun an enhanced version of the Regional–Lattice method on the instances generated in the first batch. This new version includes a routine that counts the number of ordered pairs of regions generated by NN2PWL that fail to satisfy the lattice property. If this count is 0, then the output of NN2PWL is indeed in closed regional format, and the constructed pair is a logical twin of . For performing such counting, if the regional format has regions, at most linear programs need to be solved.
The results regarding the lattice property in the first batch of experiments reproduce the phenomenon already observed in our earlier LSFA 2024 paper. Among the 700 instances, only three representations in regional format computed by NN2PWL failed to satisfy the lattice property, all of them from instances with 7 neurons per input/hidden layer: in one case, 126 pairs of regions among failed to do so, in another, 387 pairs among , and in the last one, 14 among .
Using the first batch, we compare all three methods with respect to their average running times, shown in Figure 3, and the average complexities of their outputs, shown in Figure 4, for increasing numbers of neurons per layer. It becomes clear that, in terms of running time, Compositional represents a major advance over Regional–Lattice, although the latter performs better in terms of representation complexity. In turn, PolyTwin outperforms Compositional in both respects. Figure 3 also includes the running times of the enhanced Regional–Lattice method. Although counting failures of the lattice property adds only a polynomial overhead, this additional cost may still be significant for larger instances.

Figure 3. Average running time in the first batch of experiments

Figure 4. Average representation complexity in the first batch of experiments
Both Regional–Lattice and Compositional perform a preprocessing step before constructing a representation in L-MODSAT, namely the construction of an intermediate representation: in the former case, a regional format , and in the latter, a neural network equivalent to . From these intermediate representations, the final pair can then be computed in polynomial time. However, an exponential blow-up may already occur at the level of these intermediate constructions. For this reason, for the Regional–Lattice outputs we count the number of regions generated by nn2pwl, while for the Compositional outputs we count the number of neurons in the equivalent neural network . We take these quantities as complexity measures for the corresponding intermediate representations.
Figure 5 shows, for increasing numbers of neurons per layer, the average numbers of regions and neurons in the intermediate representations produced by Regional–Lattice and Compositional, respectively, in the first batch. We observe that the equivalent networks tend to be considerably more complex than the regional formats , which explains why Regional–Lattice outperforms Compositional in terms of representation complexity.

Figure 5. Average complexity of intermediate representations in the first batch of experiments
A possible explanation for the running-time advantage of Compositional over Regional–Lattice is that, although more representations of truncated linear functions must be constructed, these can be produced in linear time at the implementation level, as discussed in § 2.3. By contrast, what appears to dominate the running time of Regional–Lattice is the need to solve linear programs, where is the number of regions, in order to establish expressions such as (9) in the lattice representation. Although linear programming is solvable in polynomial time, it is not a linear-time task, and these routines dominate the cost of constructing the individual truncated linear functions.
In order to compare Compositional and PolyTwin more closely, in the second batch of experiments we generate ReLU–TId neural networks with 5 hidden layers and a single neuron in the output layer. The numbers of neurons in the input layer and in each hidden layer vary from 1 to 20. For each configuration, 100 ReLU–TId neural networks are generated. The weights and biases of these networks have the form , where and are generated uniformly from and , respectively.
In the second batch, the advantage of PolyTwin over Compositional becomes clear. Figure 6 shows the average running time of the two methods on instances with increasing numbers of neurons per layer. Figure 7 shows the average complexities of the logical twins they generate. Moreover, Figure 8 shows a sharp growth in the number of neurons of the equivalent networks constructed from as the intermediate representations computed by Compositional.

Figure 6. Average running time in the second batch of experiments

Figure 7. Average representation complexity in the second batch of experiments

Figure 8. Average complexity of intermediate representations in the second batch of experiments
Finally, to test the scalability of PolyTwin, we consider only this method in the third and fourth batches of experiments. In both batches, the randomly generated ReLU–TId neural networks have 10 hidden layers and a single output neuron. The numbers of neurons in the input and hidden layers vary from 1 to 50. For each configuration, 100 ReLU–TId neural networks are generated. The weights and biases of these networks have the form , where is generated uniformly from . In the third batch, is generated uniformly from ; in the fourth batch, it is generated uniformly from .
Figure 9 shows that the integer part of the weights and biases does not influence either the running time or the representation complexity of the PolyTwin method. More importantly, the third and fourth batches of experiments make it clear that PolyTwin is highly scalable: even for the largest instances in these batches, in which the ReLU–TId neural networks have 500 neurons, the average running time of the method does not exceed 5 seconds.

Figure 9. Running time and representation complexity in the third and fourth batches
Final remarks and conclusions
In this work, we proposed a new algorithm for constructing logical twins for ReLU–TId neural networks through formulas of Łukasiewicz logic, namely as representations in the system Ł-MODSAT of the functions computed by these networks.
To this end, we first revisited two earlier approaches. The first is based on lattice representations of rational McNaughton functions built from encodings in regional format, and ultimately yields representations in Ł-MODSAT [15, 16, 19]. The second is an architecture-based compositional approach introduced by Zhang and Bölcskei [21] that constructs logical twins by formulas of Łukasiewicz logic or rational Łukasiewicz logic. We also showed how to adapt this second approach so as to construct logical twins in the system Ł-MODSAT. The main drawback of both approaches is that they are susceptible to exponential blow-up in running time and/or representation size.
Inspired by both of them, we then proposed a new polynomial-time, architecture-based compositional algorithm that constructs logical twins for ReLU–TId neural networks in the system Ł-MODSAT. More precisely, the new construction yields polynomial-size logical twins. In addition to establishing these complexity bounds, we submitted all three approaches to empirical evaluation on randomly generated ReLU–TId neural networks, showing a clear superiority of the new algorithm.
A feature of representations in Ł-MODSAT is that they avoid restricting the class of ReLU–TId neural networks that can be represented, since they allow plain Łukasiewicz logic to represent rational McNaughton functions, whose linear pieces have rational coefficients. Importantly, Łukasiewicz logic provides a well-studied logical setting whose main computational problems have reasonable complexity: satisfiability is NP-complete and validity is coNP-complete [13]. Moreover, there is extensive literature on algorithms for solving these problems, including implementations in which the phase-transition phenomenon has been detected [1, 3, 7].
An important application of such logical twins in Łukasiewicz logic lies in the formal verification of neural-network properties. Properties such as reachability and robustness for ReLU–TId neural networks have already been encoded in the language of Łukasiewicz logic by means of logical twins in L-MODSAT [17, 18]. However, the practical scalability of these verification techniques for large networks still depended on more compact logical twins. In this sense, the contribution of the present work is a significant step forward for the use of such verification methods in practice.
As directions for future work, one may consider neural networks with architectures other than ReLU–TId neural networks. Networks computing non-piecewise linear functions might be addressed by approximate logical twins in L-MODSAT; an initial study on approximate representations was carried out by Lobo et al. [11].
In this context, the computational problems of Łukasiewicz logic themselves, such as satisfiability and validity, may also be revisited. Although there is already substantial literature on these problems and on algorithms for solving them, such methods may now be further tested and improved on instances arising from neural network properties encoded through the polynomial-size logical twins introduced in this work. Some work in this direction has already been done by testing existing algorithms and tools on instances using lattice-based twins in L-MODSAT [20]. One may also investigate how polynomial approximations to reasoning in Łukasiewicz logic, such as the one proposed by Finger and Preto [9], could be used for incomplete or approximate formal verification methods.
On another front, one may also investigate more deeply the regional and lattice representations of ReLU–TId neural networks. Although such representations are computationally harder to construct and are not necessarily compact, precisely because they provide representations that differ from the original network architecture, they may support alternative forms of interpretation based on their regional or lattice structure. In particular, for regional representations, one may pursue a better understanding of the rare cases in which the lattice property fails, a correction procedure for such cases, or even the extent to which these representations may still approximate the original network despite lacking the lattice property.
To conclude, this work strengthens the connection between neural networks and symbolic methods in many-valued logic, and opens new perspectives for their formal analysis and verification.
Acknowledgements
This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001. This study was financed by the São Paulo Research Foundation (FAPESP), Brasil, process #2024/19144-7 (SPRINT). Preto was financed by the São Paulo Research Foundation (FAPESP), Brasil, process #2025/15917-4 (Learning to Prove). Finger was partly supported by CNPq grant PQ 302963/2022-7 and by the São Paulo Research Foundation (FAPESP), Brasil, process #2023/00488-5 (SPIRA).
Center for Mathematics, Computing and Cognition, Federal University of ABC, Santo André, Brazil
Email address: [email protected]
Institute of Mathematics, Statistics and Computer Science, University of São Paulo, São Paulo, Brazil
Email address: [email protected]
References
- [1]C. Ansótegui, M. Bofill, F. Manyà, and M. Villaret, Building automated theorem provers for infinitely-valued logics with satisfiability modulo theory solvers, 2012 IEEE 42nd International Symposium on Multiple-Valued Logic, 2012, pp. 25–30.DOI
- [2]Dimitris Bertsimas and John N. Tsitsiklis, Introduction to linear optimization, Athena scientific series in optimization and neural computation, Athena Scientific, 1997.
- [3]Miquel Bofill, Felip Manyà, Amanda Vidal, and Mateu Villaret, Finding hard instances of satisfiability in Łukasiewicz logics, Multiple-Valued Logic (ISMVL), 2015 IEEE International Symposium on, IEEE, 2015, pp. 30–35.
- [4]Davide Castelvecchi, Can we open the black box of AI?, Nature 538 (2016), no. 7623, 20–23.DOI
- [5]Roberto L.O. Cignoli, Itala M.L. D’Ottaviano, and Daniele Mundici, Algebraic foundations of many-valued reasoning, Trends in Logic, Springer Netherlands, 2000.DOI
- [6]Marcelo Finger, Logic in times of big data, A True Polymath: A Tribute to Francisco Antonio Doria (J. Acacio de Barros and Décio Krause, eds.), College Publications, 2020, pp. 184–198.
- [7]Marcelo Finger and Sandro Preto, Probably half true: Probabilistic satisfiability over Łukasiewicz infinitely-valued logic, Automated Reasoning (Cham) (Didier Galmiche, Stephan Schulz, and Roberto Sebastiani, eds.), Springer International Publishing, 2018, pp. 194–210.DOI
- [8]———, Probably partially true: Satisfiability for Łukasiewicz infinitely-valued probabilistic logic and related topics, Journal of Automated Reasoning 64 (2020), no. 7, 1269–1286.DOI
- [9]———, Polyhedral semantics and the tractable approximation of Łukasiewicz infinitely-valued logic, Journal of Logic and Computation 35 (2025), no. 5, exad059.
- [10]Brunella Gerla, Rational Łukasiewicz logic and DMV-algebras, Neural Network World 11 (2001), no. 6, 579–594.
- [11]João Lobo, Marcelo Finger, and Sandro Preto, Logical approximation and formal verification of neural networks, Anais do V Workshop Brasileiro de Lógica (Porto Alegre, RS, Brasil), SBC, 2024, pp. 1–8.
- [12]R. McNaughton, A theorem about infinite-valued sentential logic, Journal of Symbolic Logic 16 (1951), 1–13.DOI
- [13]Daniele Mundici, Satisfiability in many-valued sentential logic is NP-complete, Theoretical Computer Science 52 (1987), no. 1-2, 145–153.DOI
- [14]———, A constructive proof of McNaughton’s theorem in infinite-valued logic, The Journal of Symbolic Logic 59 (1994), no. 2, 596–602.DOI
- [15]Sandro Preto and Marcelo Finger, An efficient algorithm for representing piecewise linear functions into logic, Electronic Notes in Theoretical Computer Science 351 (2020), 167–186, Proceedings of LSFA 2020, the 15th International Workshop on Logical and Semantic Frameworks, with Applications (LSFA 2020).
- [16]———, Efficient representation of piecewise linear functions into Łukasiewicz logic modulo satisfiability, Mathematical Structures in Computer Science 32 (2022), no. 9, 1119–1144.
- [17]———, Effective reasoning over neural networks using Łukasiewicz logic, Compendium of Neurosymbolic Artificial Intelligence (Pascal Hitzler, Md Kamruzzaman Sarker, and Aaron Eberhart, eds.), Frontiers in Artificial Intelligence and Applications, vol. 369, IOS Press, 2023, pp. 609–630.
- [18]———, Proving properties of binary classification neural networks via Łukasiewicz logic, Logic Journal of the IGPL 31 (2023), no. 5, 805–821.DOI
- [19]______, Regional, lattice and logical representations of neural networks, Proceedings of the 19th International Workshop on Logical and Semantic Frameworks, with Applications, Goiânia, Brazil, 18th-20th September 2024 (Cynthia Kop and Helida Salles Santos, eds.), Electronic Proceedings in Theoretical Computer Science, vol. 421, Open Publishing Association, 2025, pp. 64–79.DOI
- [20]Sandro Preto, Felip Manyà, and Marcelo Finger, Benchmarking Łukasiewicz logic solvers with properties of neural networks, 2023 IEEE 53rd International Symposium on Multiple-Valued Logic (ISMVL), 2023, pp. 158–163.
- [21]Yani Zhang and Helmut Bölcskei, Extracting formulae in many-valued logic from deep neural networks, IEEE Transactions on Signal Processing 74 (2026), 1–12.
