Complexity of Abduction in Łukasiewicz Logic
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914143180685312 |
|---|---|
| author | Inoue, Katsumi Kozhemiachenko, Daniil |
| author_facet | Inoue, Katsumi Kozhemiachenko, Daniil |
| contents | 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 Łukasiewicz logic expanded with `interval literals' of the form $p\geq\mathbf{c}$, $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 Łukasiewicz logic 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_13847 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity of Abduction in Łukasiewicz Logic Inoue, Katsumi Kozhemiachenko, Daniil Logic in Computer Science 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 Łukasiewicz logic expanded with `interval literals' of the form $p\geq\mathbf{c}$, $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 Łukasiewicz logic 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. |
| title | Complexity of Abduction in Łukasiewicz Logic |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2507.13847 |