Łukasiewicz Neural Networks Extended: Residual Architectures and Crystallization Strategies for Interpretable Rule Extraction

Carlos Leandro

cs.LGSep 26, 2026

Łukasiewicz Neural Networks Extended: Residual Architectures and Crystallization Strategies for Interpretable Rule Extraction

Authors: Carlos Leandro

Organizations: Departamento de Matemática, Instituto Superior de Engenharia de Lisboa (ISEL), Instituto Politécnico de Lisboa, Portugal

Abstract

A feed-forward neural network whose weights are integers and whose activation is the truncated identity implements, neuron by neuron, the connectives of Łukasiewicz many-valued logic. This exact correspondence --- established theoretically by Castro and Trillas and developed into a training algorithm by Leandro --- enables symbolic knowledge extraction: training produces not a black-box model but a logical formula. Two obstacles have limited the approach to shallow architectures and small datasets: crystallization (forcing weights to integers) succeeds only probabilistically under the original Levenberg--Marquardt training scheme, and the theoretical guarantees break down as networks grow deeper. This paper addresses both obstacles. First, we prove that residual connections (skip connections of the kind used in ResNets) extend Łukasiewicz neural networks to arbitrary depth while preserving the symbolic correspondence at merge neurons by construction: merge neurons in a Łukasiewicz residual block automatically satisfy the neuron-classification proposition, regardless of the inner layer weights; inner-layer neurons are trained toward representability by the crystallization strategy. Second, we analyse three crystallization strategies --- Levenberg--Marquardt (corrected), straight-through estimation (STE), and proximal regularization --- characterizing their theoretical guarantees, failure modes, and interpretability trade-offs.

Figures & tables

Leandro (2009)	Present paper
Proposition 2 (neuron classification)	Theorem 4 (residual block guarantee)
Rewriting algebra (Rule R, $\lambda$ -similarity)	Corrected LM training (Levenberg form)
LM training (Marquardt form — contains bug)	STE crystallization strategy
Experiments on MONK and small UCI sets	Proximal crystallization strategy
	Multi-dataset statistical comparison

Table 1: Contributions of Leandro (2009) [ 7 ] versus the present paper.

Strategy	Cryst. guaranteed	Sparsity	Exact Prop. 2
LM (corrected)	Probabilistic	No	Yes (when crystallizes)
STE	Yes	No	No (requires rewriting)
Proximal	Yes	Yes	No (requires rewriting)
LM + residual connections	Probabilistic	No	Yes by construction (merge)

Table 2: Theoretical properties of the three crystallization strategies. “Crystallization guaranteed”: all trials achieve

\Delta(N)<\varepsilon

. “Sparsity”: tendency to produce zero weights. “Exact Prop. 2 ”: extracted formula satisfies the proposition exactly without rewriting-algebra approximation.

Dataset	Train	Test	Features	Class balance	Source
Mushroom	9 898	2 476	111	$50.0\%$	UCI (one-hot encoded)
Heart Disease	242	61	22	$54.1\%$	Cleveland Clinic [ 21 ]
MONK-1	124	432	17	$50.0\%$	UCI [ 22 ]
MONK-2	169	432	17	$32.4\%$	UCI [ 22 ]
MONK-3	122	432	17	$51.9\%$	UCI (5% noise)
Breast Cancer	228	58	20	$30.8\%$	UCI Ljubljana

Table 3: Dataset characteristics. Class balance is the fraction of the majority class.

	Accuracy (mean $\pm$ std)			Crystallization rate
Dataset	LM-Res	STE	Proximal	LM-Res	STE	Proximal
Mushroom	$\mathbf{.668\pm.028}$	$.665\pm.040$	$.660\pm.000$	$6/10$	$\mathbf{10/10}$	$\mathbf{10/10}$
Heart Disease	$.570\pm.135$	$\mathbf{.607\pm.101}$	$.600\pm.000$	$9/10$	$\mathbf{10/10}$	$\mathbf{10/10}$
MONK-1	$.565\pm.218$	$\mathbf{.600\pm.125}$	$.558\pm.125$	$7/10$	$\mathbf{10/10}$	$\mathbf{10/10}$
MONK-2	$.631\pm.243$	$\mathbf{.704\pm.070}$	$.671\pm.000$	$7/10$	$\mathbf{10/10}$	$\mathbf{10/10}$
MONK-3 ∗	$\mathbf{.714\pm.212}$	$.632\pm.161$	$.472\pm.000$	$\mathbf{10/10}$	$\mathbf{10/10}$	$\mathbf{10/10}$

Table 4: Accuracy (mean

\pm

std, 10 trials) and crystallization rate. ∗ marks significant pairwise Wilcoxon tests (

p<0.05

). Best accuracy per dataset in bold .

	Patient A (disease)	Patient B (healthy)
ca	$1.00$	$0.00$
trestbps	$0.64$	$0.27$
oldpeak	$0.42$	$0.00$
thalach	$0.29$	$0.79$
cp=4 indicator	$1$	$0$
$\neg\mathtt{ca}$	$0.00$	$1.00$

Table 5: Evaluation trace for Eq. ( 18 ) on two test patients (features normalised to

[0,1]

Feature	Clinical meaning	Established
ca	Number of major vessels with $>50\%$ stenosis	✓
trestbps	Resting systolic blood pressure (mmHg)	✓
oldpeak	ST-segment depression at exercise	✓
thalach	Maximum heart rate achieved (bpm)	✓
cp=4	Asymptomatic chest pain presentation	✓

Table 6: Features selected in the Heart Disease formula (Eq. 18 ), with clinical interpretation. “Established”: recognized predictor of coronary artery disease [ 21 ] .

	Time (s)			$p$ -value
Dataset	LM-Res	STE	Proximal	LM/STE	LM/PRX	STE/PRX
Mushroom	$0.498$	$1.249$	$\mathbf{0.090}$	$.002^{\ast}$	$.002^{\ast}$	$.002^{\ast}$
Heart Disease	$\mathbf{0.076}$	$0.252$	$0.039$	$.014^{\ast}$	$.064$	$.002^{\ast}$
MONK-1	$\mathbf{0.212}$	$0.353$	$0.522$	$.131$	$.084$	$.160$
MONK-2	$\mathbf{0.149}$	$0.598$	$0.915$	$.002^{\ast}$	$.002^{\ast}$	$.432$
MONK-3	$\mathbf{0.033}$	$0.260$	$0.338$	$.002^{\ast}$	$.002^{\ast}$	$.004^{\ast}$

Table 7: Mean training time (seconds, 10 trials). Fastest method per dataset in bold .

p

-values from Wilcoxon test (

n=10

); ∗ :

p<0.05

Neural Network Interpretability

Neural network interpretability studies how models represent information and make predictions, and how to explain, test, or control their internal computations.

See all 333 papers

Complete Identification of Deep ReLU Networks through Łukasiewicz Logic
Jan 30, 2026Yani Zhang, Helmut BölcskeiParameter Identifiability ReLU Neural Networks
Chair for Mathematical Information Science, ETH Zürich
Neural Logic Networks for Interpretable Classification
Aug 11, 2025Vincent Perreault, Katsumi Inoue, Richard Labib +1Boolean Function Learning Neural Network Interpretability
Department of Mathematics and Industrial Engineering Polytechnique Montréal · National Institute of Informatics, Tokyo
Neuron-Anchored Rule Extraction for Large Language Models via Contrastive Hierarchical Ablation
May 4, 2026Francesco Sovrano, Gabriele Dominici, Marc LangheinrichLLM Interpretability Mechanistic Interpretability
Università della Svizzera italiana Lugano, Switzerland

Jan 30, 2026J/K move · Enter open · S save

Complete Identification of Deep ReLU Networks through Łukasiewicz Logic

Yani Zhang, Helmut Bölcskei

Chair for Mathematical Information Science, ETH Zürich

Parameter Identifiability ReLU Neural Networks Feedforward Neural Networks

Open paper AskPDF arXiv

Two deep ReLU networks can have entirely different architectures and parameters, yet realize the same function. We provide a complete characterization of this nonuniqueness. This is effected by building a symbolic calculus for deep ReLU networks, equivalence and simplification of networks becoming derivation of formulae, in close parallel to Shannon's analysis of switching circuits through Boolean logic. Inspired by Shannon, who turned circuit synthesis into the manipulation of Boolean formulae by the axioms of Boolean algebra, we turn ReLU network identification into the derivation of Łukasiewicz formulae by the axioms of many-valued (MV) logic. Two non-degenerate ReLU networks realize the same function on the unit cube if and only if one is obtained from the other by finitely many applications of the MV axioms for integer weights and biases, the divisible MV axioms for rational ones, and the Riesz MV axioms for real ones. The MV logic axioms characterize all symmetries of ReLU networks, the single-layer ones, which for tanh networks are the only kind, and the deep ones, spanning three or more layers. Our framework consists of three steps, an extraction algorithm turning a network into a substitution graph, whose represented formula has the network's input-output map as its truth function, a completeness theorem, by which functionally equivalent formulae are interderivable, and a construction algorithm returning from graphs to networks. The substitution graph is layered, carrying at each node a formula in the variables of the layer feeding it, encodes the network uniquely, and induces a new normal form for MV logic, compositional rather than flat as in the literature, hence retaining the algebraic structure of the network, with three local operations--node rewrite, layer collapse, layer expansion--realizing every derivation.

Abstract

Neural Network Interpretability

Explore similar work

Complete Identification of Deep ReLU Networks through Łukasiewicz Logic

Neural Logic Networks for Interpretable Classification

Neuron-Anchored Rule Extraction for Large Language Models via Contrastive Hierarchical Ablation