Complexity of Abduction in Łukasiewicz Logic

Katsumi Inoue, Daniil Kozhemiachenko · 2025

Read Complexity of Abduction in Łukasiewicz Logic by Katsumi Inoue, Daniil Kozhemiachenko (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-13847.txt.

Introduction

Katsumi Inoue and Daniil Kozhemiachenko present a 2025 paper on the cost of finding explanations in a logic where truth comes in degrees. Everyday claims like "the lift is loaded" are partly true rather than simply true or false. The logic they use gives every statement a value on a scale.

Abduction means proposing causes that would explain what is seen. The authors define such problems for this fuzzy logic, enriched with statements that bound a variable's value. They then grade the core tasks: checking a candidate answer, deciding whether one exists, and judging whether a guess is needed. In the clause only fragment, the tasks prove cheaper than in the full language, unlike the classic case.

Catalog record

CREATORKatsumi Inoue, Daniil Kozhemiachenko
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE100 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-13847

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Complexity of Abduction in Łukasiewicz Logic Katsumi Inoue, Daniil Kozhemiachenko Abstract We explore the problem of explaining observations in contexts involving statements with truth degrees such as ‘the lift is loaded’, ‘the symptoms are severe’, etc. To formalise these contexts, we consider infinitely-valued Łukasiewicz fuzzy logic Ł . We define and motivate the notions of abduction problems and explanations in the language of Ł expanded with ‘interval literals’ of the form p ≥ 𝐜 p\geq\mathbf{c} , p ≤ 𝐜 p\leq\mathbf{c} , and their negations that express the set of values a variable can have. We analyse the complexity of standard abductive reasoning tasks (solution recognition, solution existence, and relevance / necessity of hypotheses) in Ł for the case of the full language and for the case of theories containing only disjunctive clauses and show that in contrast to classical propositional logic, the abduction in the clausal fragment has lower complexity than in the general case. 1 Introduction Abduction, deduction, and induction are three main forms of reasoning [ \citeauthoryearFlach and Kakas2000 ] . Abduction (finding explanations) has multiple applications in artificial intelligence, such as diagnosis [ \citeauthoryearEl Ayeb, Marquis, and Rusinowitch1993 , \citeauthoryearJosephson and Josephson2009 , \citeauthoryearKoitz-Hristov and Wotawa2018 ] , commonsense reasoning [ \citeauthoryearPaul1993 , \citeauthoryearBhagavatula et al.2020 ] , formalisation of scientific reasoning [ \citeauthoryearMagnani2011 ] , and machine learning [ \citeauthoryearDai et al.2019 ] . In logic-based abduction [ \citeauthoryearEiter and Gottlob1995 ] , the reasoning task is to find an explanation for an observation \chi from a theory \Gamma , i.e., a formula \phi s.t. \Gamma,\phi\models\chi but \Gamma,\phi\not\models\bot (i.e., \Gamma and \phi should consistently entail \chi ). Observe, however, that in many applications, one needs not only to state whether a formula is true but also to specify to which degree it holds. E.g., a lift may be safe to use only when loaded to at least 5\% of its maximal capacity (otherwise, its software will register it as empty) and to no more than 90\% of the capacity. Or the cruising speed of a car can be defined as 60\ldots 90~\mathrm{kmh} (with the maximal speed being 150~\mathrm{kmh} ). As classical logic has only two values, it is not well-suited to reason about contexts involving truth degrees. On the other hand, fuzzy logics evaluate formulas in the real-valued interval [0,1] and thus are much better suitable to formalising such contexts than classical logic. In particular, to formalise the examples above, we can set v(l)\geq 0.05 and v(s)\in[0.4,0.6] where the truth degrees of l and s denote, respectively, the load of the lift and the speed of the car w.r.t. its maximal speed. Fuzzy Logic Originally [ \citeauthoryearZadeh1965 , \citeauthoryearZadeh1975 ] fuzzy logics were introduced to reason about imprecise statements such as ‘it is cold outside’, ‘the symptoms are severe’, etc. The values between [0,1] are interpreted as degrees of truth from 0 (absolutely false) to 1 (absolutely true). Fuzzy logic has also been applied to reasoning about uncertainty (cf., e.g., [ \citeauthoryearHájek and Tulipani2001 ] and [ \citeauthoryearBaldi, Cintula, and Noguera2020 ] ) and beliefs [ \citeauthoryearRodriguez et al.2022 ] . In knowledge representation and reasoning, fuzzy logics have found multiple applications in representing graded and fuzzy ontologies [ \citeauthoryearStraccia2016 ] . In such ontologies, concept assertions and terminological axioms have degrees of truth. Moreover, fuzzy versions of description logics and their computational properties have been extensively investigated [ \citeauthoryearBorgwardt and Peñaloza2012 , \citeauthoryearBorgwardt2014 , \citeauthoryearBorgwardt, Distel, and Peñaloza2014 , \citeauthoryearBorgwardt and Peñaloza2017 ] . In addition to that, fuzzy logic has found multiple applications in artificial intelligence. Recent work on machine learning tries to combine perception by deep learning and symbolic knowledge representation. Neurosymbolic frameworks such as [ \citeauthoryearDiligenti, Gori, and Saccà2017 , \citeauthoryearBadreddine et al.2022 ] adopt semantics of fuzzy logic to support learning and reasoning in real-world domains. [ \citeauthoryearKrieken, Acar, and Harmelen2022 ] analyse how different fuzzy logic semantics affect the behaviour of learning. Fuzzy logic has also been used in reasoning problems with knowledge graphs [ \citeauthoryearChen, Hu, and Sun2022 ] and MaxSAT [ \citeauthoryearHaniková, Manyà, and Vidal2023 ] . Furthermore, t-norms (functions used to interpret conjunctions in fuzzy logic) are applied for autonomous driving with requirements [ \citeauthoryearStoian, Giunchiglia, and Lukasiewicz2023 ] . Abduction in Fuzzy Logic Abduction in different systems of fuzzy logic has long attracted attention. To the best of our knowledge, it was first presented by [ \citeauthoryearYamada and Mukaidono1995 ] . There, the authors formalised abduction problems in the infinitely-valued Łukasiewicz fuzzy logic Ł and proposed explanations in the form of fuzzy sets , i.e., assignments of values from [0,1] to propositional variables. This approach was further expanded by [ \citeauthoryearVojtáš1999 ] to Gödel and Product fuzzy logics. Solutions to abduction problems in multiple fuzzy logics were further systematised by [ \citeauthoryeard’Allonnes, Akdag, and Bouchon-Meunier2007 ] and [ \citeauthoryearChakraborty et al.2013 ] . Abduction in fuzzy logic has found multiple applications, in particular, diagnosis [ \citeauthoryearMiyata, Furuhashi, and Uchikawa1998 ] , machine learning [ \citeauthoryearBergadano, Cutello, and Gunetti2000 ] , fuzzy logic programming [ \citeauthoryearVojtáš2001 , \citeauthoryearEbrahim2001 ] , decision-making and learning in the presence of incomplete information [ \citeauthoryearMellouli and Bouchon-Meunier2003 , \citeauthoryearTsypyschev2017 ] , and robot perception [ \citeauthoryearShanahan2005 ] . Contributions Still, the complexity of fuzzy abduction largely remains unexplored. To the best of our knowledge, the only discussion is given by [ \citeauthoryearVojtáš1999 ] . There, the author explores fuzzy abduction in definite logic programmes (i.e., sets of rules of the form \langle B\leftarrow A_{1},\ldots,A_{n},x\rangle where each A_{i} is an atom and x belongs to the real-valued interval [0,1] ). In particular, the author claims (cf. [ \citeauthoryearVojtáš1999 , §4.4] for details) that ‘[a]s linear programming is lying in \mathsf{NP} complexity class (even much lower) as prolog does, to find minimal solutions for a definite [fuzzy logic programming abduction problem] …does not increase the complexity and remains in \mathsf{NP} ’. Thus, there seems to be no formal study of the complexity of abduction in fuzzy logic. In this paper, we make a step towards a study of the complexity of abduction in fuzzy logic. We concentrate on the Łukasiewicz logic as it is one of the most expressive ones. In particular, it can express rational numbers and continuous linear functions over [0,1] (cf. [ \citeauthoryearMcNaughton1951 ] for details). In addition, it still retains many classical relations between its conjunction, disjunction, implication, and negation. We formalise abduction in Ł and explore its computational properties. Our contribution is twofold. First, we propose and motivate a new form of solutions — interval terms — that allow to express intervals of values a variable is permitted to have. Second, we establish an (almost) complete characterisation of the complexity of standard reasoning problems (solution recognition, solution existence, relevance and necessity of hypotheses) for the case of theories containing arbitrary formulas and those comprised of disjunctive clauses. Plan of the Paper The paper is structured as follows. In Section 2 , we present the Łukasiewicz logic. In Section 3 , we propose and motivate interval terms that we will use as solutions to Łukasiewicz abduction problems. Sections 4 and 5 are dedicated to the study of the complexity of abductive reasoning in the Łukasiewicz logic and its clausal

Read the complete text