Three-valued Łukasiewicz logic on line graphs: exclusion valuations, matchings and indeterminacy density

We study the three-element Łukasiewicz chain L3 with truth values {0, 1/2, 1}, in which 1/2 is the unique fixed point of negation and is read as "undetermined". The first part collects the algebraic and definability facts used later, with short proofs: L3 is a simple MV-chain with Boolean centre {0,1} and no homomorphism onto {0,1}; every function on L3 is a term function once the constant 1/2 is available; without it, the term functions are exactly the functions preserving {0,1}, of which there are 2^(2^n)·3^(3^n−2^n) in n variables; and the Kleene connectives with constants define exactly the functions that are monotone in the information order (with a short constructive proof), with 11 and 197 such functions in one and two variables. We then place L3-valuations on the vertices of a line graph L(R) subject to an exclusion rule: a sharp value (0 or 1) forces 1/2 on every neighbour. Admissible valuations are in bijection with matchings of R whose edges carry a binary label, so their number is Σ m_k(R)·2^k, the independence polynomial of L(R) at 2. For a z-regular graph R the fraction of undetermined vertices is at least (z−1)/z, with equality exactly for perfect matchings. Admissible valuations are closed under negation and consensus and form a meet-semilattice in the information order. Finally we record the F2-rank of the line-graph adjacency matrix, rank = |V(R)| − 1 − [|V(R)| even] for connected R. All numerical statements are checked by the accompanying Python script verify_l3.py. The LaTeX source is included.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-16
DOI
https://doi.org/10.5281/zenodo.24291788
Primary Topic
Advanced Algebra and Logic
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Three-valued Łukasiewicz logic on line graphs: exclusion valuations, matchings and indeterminacy density

Zoran Stepanoski
Zenodo (CERN European Organization for Nuclear Research)
Advanced Algebra and Logic
preprint

Three-valued Łukasiewicz logic on line graphs: exclusion valuations, matchings and indeterminacy density

Zoran Stepanoski
preprint en

Abstract

We study the three-element Łukasiewicz chain L3 with truth values {0, 1/2, 1}, in which 1/2 is the unique fixed point of negation and is read as "undetermined". The first part collects the algebraic and definability facts used later, with short proofs: L3 is a simple MV-chain with Boolean centre {0,1} and no homomorphism onto {0,1}; every function on L3 is a term function once the constant 1/2 is available; without it, the term functions are exactly the functions preserving {0,1}, of which there are 2^(2^n)·3^(3^n−2^n) in n variables; and the Kleene connectives with constants define exactly the functions that are monotone in the information order (with a short constructive proof), with 11 and 197 such functions in one and two variables. We then place L3-valuations on the vertices of a line graph L(R) subject to an exclusion rule: a sharp value (0 or 1) forces 1/2 on every neighbour. Admissible valuations are in bijection with matchings of R whose edges carry a binary label, so their number is Σ m_k(R)·2^k, the independence polynomial of L(R) at 2. For a z-regular graph R the fraction of undetermined vertices is at least (z−1)/z, with equality exactly for perfect matchings. Admissible valuations are closed under negation and consensus and form a meet-semilattice in the information order. Finally we record the F2-rank of the line-graph adjacency matrix, rank = |V(R)| − 1 − [|V(R)| even] for connected R. All numerical statements are checked by the accompanying Python script verify_l3.py. The LaTeX source is included.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Algebra and Logic
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon