Probabilistic Abduction in a Fuzzy Logic Framework

Daniil Kozhemiachenko; Katsumi Inoue; Tommaso Flaminio

arxiv: 2604.22064 · v1 · submitted 2026-04-23 · 💻 cs.LO

Probabilistic Abduction in a Fuzzy Logic Framework

Tommaso Flaminio , Katsumi Inoue , Daniil Kozhemiachenko This is my paper

Pith reviewed 2026-05-08 13:30 UTC · model grok-4.3

classification 💻 cs.LO

keywords probabilistic abductionfuzzy probabilistic logicsolution recognitionexistence problemdisjunctive fragmentsclassical probabilistic abductionexplanation of observations

0 comments

The pith

Probabilistic observations such as rain occurring twenty percent of the time can be explained by abduction problems formalized inside a fuzzy probabilistic logic FP.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper takes observations about event probabilities and seeks explanations in the form of consistent probability distributions or other probabilistic statements that entail those observations. It encodes this task as abduction problems inside the fuzzy probabilistic logic FP and defines what counts as a valid solution. The core technical work examines the computational complexity of recognizing valid solutions and of deciding whether any solution exists, first in the full language of FP and then in its disjunctive-clause fragments. A further result translates the classical problem of finding the most likely explanation for an event into the same FP setting. A reader would care because the work supplies a uniform logical setting in which probabilistic explanations become objects that can be checked and searched algorithmically.

Core claim

We study the problem of explaining observations about the probabilities of events, such as it rains 20 percent of the time or rain and snow are equally likely. We explain these statements with a probability distribution or a statement about probabilities of other events that are consistent with our knowledge and entail the observation. We formalise this problem in a fuzzy probabilistic logic FP. We define and motivate the notions of abduction problems and their solutions. Our main technical contribution is a comprehensive study of the complexity of solution recognition and existence for a given abduction problem in FP for the case of full language and its disjunctive-clause fragments. We 0b0

What carries the argument

The fuzzy probabilistic logic FP, which encodes probabilistic observations and background knowledge as fuzzy formulas and turns the search for explanations into abduction problems whose solutions are checked for consistency and entailment.

If this is right

Solution recognition and existence for abduction problems become objects of precise complexity classification in both the full FP language and its disjunctive fragments.
Classical probabilistic abduction, including the search for most likely explanations, reduces to an instance of abduction inside FP.
Any background knowledge expressible in FP can be used to constrain the set of admissible explanations for an observed probability statement.
The disjunctive-clause fragments of FP inherit decidability or complexity bounds that may be lower than those of the full language.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Practical algorithms for generating probabilistic explanations could be obtained by implementing the decision procedures whose existence is established for the fragments.
The same FP encoding might be reused for other forms of uncertain reasoning that combine logic with numerical degrees of belief.
If the complexity results turn out to be tractable in common fragments, they could support automated explanation modules in probabilistic databases or knowledge bases.

Load-bearing premise

That the fuzzy probabilistic logic FP provides a faithful formalization of intuitive probabilistic abduction problems so that its complexity results apply to practical reasoning tasks.

What would settle it

A concrete probabilistic observation, such as a statement about conditional probabilities, for which no consistent solution exists in FP even though an intuitive explanation is available outside the logic.

Figures

Figures reproduced from arXiv: 2604.22064 by Daniil Kozhemiachenko, Katsumi Inoue, Tommaso Flaminio.

**Figure 1.** Figure 1: Semantics of Ł Q △. • a map ∂ : W → [0, 1] is a probability distribution on W iff P w∈W ∂(w) = 1. Definition 3 (Probabilistic models). Given a finite set V ⊆ Var, a probabilistic model for V is a tuple M = ⟨2 V, µ⟩ s.t. µ : 22 V → [0, 1] is a probability measure on 2 2 V . For p∈V, ϕ∈LCPL s.t. Var(ϕ) ⊆ V, and a probabilistic model M=⟨2 V, µ⟩, we define the truth set of ϕ (∥ϕ∥M) as follows: • ∥p∥M = {X ∈ 2 … view at source ↗

read the original abstract

We study the problem of explaining observations about the probabilities of events, such as "it rains $20\%$ of the time", "rain and snow are equally likely", etc. We explain these statements with a probability distribution or a statement about probabilities of (other) events that are consistent with our knowledge and entail the observation. We formalise this problem in a fuzzy probabilistic logic $\mathsf{FP}$. We define and motivate the notions of abduction problems and their solutions. Our main technical contribution is a comprehensive study of the complexity of solution recognition and existence for a given abduction problem in $\mathsf{FP}$ for the case of full language and its disjunctive-clause fragments. We also obtain a translation of classical probabilistic abduction (finding the most likely explanation of a given event) to $\mathsf{FP}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper sets up fuzzy probabilistic logic FP for abduction on probability statements and gives complexity results for solution recognition and existence in the full language plus disjunctive fragments.

read the letter

The main thing to know is that they formalize probabilistic abduction inside a new fuzzy logic FP, define what counts as a solution to an abduction problem, and then classify the complexity of recognizing solutions and deciding if any exist, both for the full language and for its disjunctive-clause restrictions. They also give a translation that embeds classical probabilistic abduction into this setting. The definitions and motivation sections are clear enough that the problem statement makes sense on its own terms, and splitting the complexity analysis by language fragment is a useful move that shows where the problem stays in P or jumps to NP-complete. The translation result is a straightforward bridge to existing work on most-likely explanations. The soft spots are modest. The paper remains entirely theoretical, with no worked examples that show FP handling a concrete observation better than standard probabilistic logics, and no discussion of how the fuzzy truth values interact with actual probability distributions in practice. That leaves the claim that FP is a faithful formalization resting mostly on the initial motivation rather than demonstrated advantage. The complexity results themselves look like standard reductions once the framework is fixed, so the real novelty sits in the choice of FP rather than in unexpected hardness thresholds. This is for people who already work on probabilistic logics, abduction, or complexity of reasoning tasks in AI. A reader who wants a new formal setting plus a complexity map for it will find the paper usable. It deserves peer review because the claims are specific, the fragments are well-chosen, and the translation is checkable; any referee can focus on whether the fuzzy semantics actually support the intended abduction notion without circularity.

Referee Report

1 major / 1 minor

Summary. The paper formalizes the problem of explaining probabilistic observations (e.g., 'it rains 20% of the time') via abduction in the fuzzy probabilistic logic FP. It defines abduction problems and solutions, then claims a comprehensive complexity analysis of solution recognition and existence for the full FP language and its disjunctive-clause fragments, together with a translation of classical probabilistic abduction (most-likely explanation) into FP.

Significance. If the claimed complexity results hold, the work would supply a formal complexity landscape for abduction in fuzzy probabilistic logics and a bridge to classical probabilistic abduction, which could support the design of reasoning systems that handle uncertain probabilistic statements in AI and knowledge representation.

major comments (1)

[Abstract] Abstract: the central claim of a 'comprehensive study of the complexity of solution recognition and existence' is stated without any theorem, complexity class, reduction, or proof sketch. This absence makes the main technical contribution impossible to assess from the provided text.

minor comments (1)

The abstract would be clearer if it briefly indicated the complexity classes obtained (e.g., P, NP-complete) rather than only announcing that a study was performed.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the feedback. We address the major comment point by point below.

read point-by-point responses

Referee: [Abstract] Abstract: the central claim of a 'comprehensive study of the complexity of solution recognition and existence' is stated without any theorem, complexity class, reduction, or proof sketch. This absence makes the main technical contribution impossible to assess from the provided text.

Authors: We agree that the abstract states the main contribution at a high level without enumerating specific theorems, complexity classes, reductions or proof sketches. The full manuscript contains these details: explicit theorems classifying the complexity of solution recognition and existence for the full FP language and its disjunctive-clause fragments, the corresponding polynomial-time reductions, proof sketches, and the translation of classical probabilistic abduction into FP. We will revise the abstract to include a concise indication of these results so that the technical contribution is more readily assessable from the abstract. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents a formalization of probabilistic abduction in fuzzy probabilistic logic FP, followed by complexity results for solution recognition and existence (full language and disjunctive fragments) plus a translation from classical probabilistic abduction. No equations, definitions, or steps in the abstract or high-level claims reduce by construction to fitted parameters, self-citations, or renamed inputs. The technical contributions on complexity appear independent and externally verifiable via standard complexity-theoretic methods, with the translation asserted as a separate mapping rather than a self-referential loop. This is the expected non-finding for a complexity-analysis paper whose core results do not rely on internal redefinitions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities beyond the introduction of the logic FP itself; no fitted values or ad-hoc postulates are mentioned.

pith-pipeline@v0.9.0 · 5431 in / 1102 out tokens · 47050 ms · 2026-05-08T13:30:09.538976+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

InAdvances in Soft Computing

Abduction problem in probabilistic constraint logic programming. InAdvances in Soft Computing. London: Springer London. 85–98. V ojtáš, P. 2001. Fuzzy logic programming.Fuzzy Sets And Systems124(3):361–370. V ojtáš, P. 1999. Fuzzy Logic Abduction. In Mayor, G., and Suñer, J., eds.,Proceedings of the EUSFLAT-ESTYLF Joint Conference, 319–322. Universitat de...

work page 2001
[2]

Given a PITζ= Jn i=1(Pr(τi)⋄ ci), it isNP-complete to check whetherζisFP-satisfiable

work page
[3]

Proof.We begin with the Item 1.NP-membership follows from Proposition 1

Given two PITsζ 1 andζ 2 it iscoNP-complete to check whetherζ 1 |=FP ζ2. Proof.We begin with the Item 1.NP-membership follows from Proposition 1. We provide a reduction from the classical non-validity problem of DNFs, which isNP-complete. Namely, letϕ= mW i=1 nV j=1 li j be a formula in DNF, and define ζϕ := mK i=1  Pr   n^ j=1 li j   ≤ 0   We sho...

work page arXiv 2025
[4]

There is no PILλ ′ s.t.E(λ ′)⊆H,λ|= FP λ′,λ ′ |=FP λ♭ V,λ ′ ̸|=FP λ, andλ ♭ V ̸|=FP λ′

work page
[5]

Proof sketch.We begin with Item 1 and consider only the case ofλ=Pr(σ)≥ cwithc= k n for brevity

There is no PILλ ′′ s.t.E(λ ′′)⊆H,λ|= FP λ′′,λ ′′ |=FP λ∗,λ ′′ ̸|=FP λ, andλ ∗ ̸|=FP λ′′. Proof sketch.We begin with Item 1 and consider only the case ofλ=Pr(σ)≥ cwithc= k n for brevity. Other cases can be dealt with similarly. Now, assume for contradiction that there is someλ ′ s.t.λ|= FP λ′,λ ′ |=FP λ♭ V,λ ′ ̸|=FP λ, andλ ♭ V ̸|=FP λ′. We consider the f...

work page 2025
[6]

We set∂ f(w1) = min{f(π)|π∈Υ}

work page
[7]

, r}, pickπ∈Υs.t.♯ f(π) =iand set∂ f(wi) =f(π)−∂ f(wi−1)

Then, for eachi∈ {2, . . . , r}, pickπ∈Υs.t.♯ f(π) =iand set∂ f(wi) =f(π)−∂ f(wi−1)

work page
[8]

It is clear that the probability measureµ ∂f induced by∂ f is coherent withf

Ifmax{f(π)|π∈Υ}<1, set additionally,∂(w 0) = 1−∂(w r). It is clear that the probability measureµ ∂f induced by∂ f is coherent withf. The result now follows. Proposition 4.For every finite CIP theoryΓ⊆ L Q Pr, there is anL Q Ł -theoryΨ Γ s.t. 1.Ψ Γ isŁ-satisfiable iffΓisFP-satisfiable; 2.Ψ Γ is constructible in polynomial time w.r.t. the size ofΓ. Proof.We...

work page 2025
[9]

Proof of Item 1.We adapt the proof of (Inoue and Kozhemiachenko 2025, Theorem 15)

decidable in polynomial time if it has sufficient solutions; 2.NP-complete to check if it has concise full solutions. Proof of Item 1.We adapt the proof of (Inoue and Kozhemiachenko 2025, Theorem 15). To show that the existence of sufficient solutions is decidable in polynomial time, we construct a polynomial embedding of SPCF abduction problems into clas...

work page 2025
[10]

There are▷, ▷ ′ ∈ {≥, >},◁, ◁ ′ ∈ {≤, <}, andc, d∈[0,1] Q such thatc > dand (a)v(r Pr(π)▷c) = 1andv(r Pr(π)◁d) = 1, or (b)v(r Pr(π)▷c) = 1andv(r Pr(π)▷′d) = 0, or (c)v(r Pr(π)◁c) = 0andv(r Pr(π)▷d) = 0, or (d)v(r Pr(π)◁c) = 0andv(r Pr(π)◁′d) = 1

work page
[11]

We consider only the first case since the second one can be dealt with in a similar way

There are▷, ▷ ′ ∈ {≥, >},◁, ◁ ′ ∈ {≤, <}, andc, d∈[0,1] Q such thatc≥d,▷̸=▷ ′,◁̸=◁ ′, and (a)v(r Pr(π)▷c) = 1andv(r Pr(π)◁′d) = 1, or (b)v(r Pr(π)▷c) = 1andv(r Pr(π)▷′d) = 0, or (c)v(r Pr(π)◁c) = 0andv(r Pr(π)▷′d) = 0, or (d)v(r Pr(π)◁c) = 0andv(r Pr(π)◁′d) = 1. We consider only the first case since the second one can be dealt with in a similar way. In th...

work page
[12]

There are▷, ▷ ′ ∈ {≥, >},◁, ◁ ′ ∈ {≤, <}, andc, d∈[0,1] Q such thatc > dand (a)v(r Pr(π)▷c) = 1andv(r Pr(ϱ)◁d) = 1, or (b)v(r Pr(π)▷c) = 1andv(r Pr(ϱ)▷′d) = 0, or (c)v(r Pr(π)◁c) = 0andv(r Pr(ϱ)▷d) = 0, or (d)v(r Pr(π)◁c) = 0andv(r Pr(ϱ)◁′d) = 1

work page
[13]

Just as before, we consider only case 1 because case 2 can be tackled in the same way

There are▷, ▷ ′ ∈ {≥, >},◁, ◁ ′ ∈ {≤, <}, andc, d∈[0,1] Q such thatc≥d,▷̸=▷ ′,◁̸=◁ ′, and (a)v(r Pr(π)▷c) = 1andv(r Pr(ϱ)◁′d) = 1, or (b)v(r Pr(π)▷c) = 1andv(r Pr(ϱ)▷′d) = 0, or (c)v(r Pr(π)◁c) = 0andv(r Pr(ϱ)▷′d) = 0(with⟨◁, ▷ ′⟩ ∈ {⟨<,≥⟩,⟨≤, >⟩}), or (d)v(r Pr(π)◁c) = 0andv(r Pr(ϱ)◁′d) = 1. Just as before, we consider only case 1 because case 2 can be t...

work page
[14]

Proof.Assume thatτis a solution toP p

there is a probabilistic modelM ′ =⟨2 V, µ′⟩s.t.µ ′ is coherent withpandPr µ′ (χ|ϕ∧τ) = 1. Proof.Assume thatτis a solution toP p. Thenϕ, τ|= CPL χand there is a probabilistic modelM p =⟨2 V, µp⟩coherent withps.t.µ p(∥ϕ∧τ∥ M)>0. Now,ϕ, τ|= CPL χimplies that∥ϕ∧τ∥ M ⊆ ∥χ∥ M for all probabilistic modelsM=⟨2 V, µ⟩. It follows thatµ(∥ϕ∧τ∥ M)≤µ(∥χ∥ M). This give...

work page
[15]

Proof.We begin with hardness for Items 1 and 3

inΠ P 2 to check ifτis a preferred solution toP p; 3.Σ P 2 -complete to check ifP p has solutions. Proof.We begin with hardness for Items 1 and 3. Recall that classical abduction problems are a particular case of probabilistic abduction problems. As is well-known from (Eiter and Gottlob 1995), solution recognition for classical abduction problems isDP-com...

work page 1995

[1] [1]

InAdvances in Soft Computing

Abduction problem in probabilistic constraint logic programming. InAdvances in Soft Computing. London: Springer London. 85–98. V ojtáš, P. 2001. Fuzzy logic programming.Fuzzy Sets And Systems124(3):361–370. V ojtáš, P. 1999. Fuzzy Logic Abduction. In Mayor, G., and Suñer, J., eds.,Proceedings of the EUSFLAT-ESTYLF Joint Conference, 319–322. Universitat de...

work page 2001

[2] [2]

Given a PITζ= Jn i=1(Pr(τi)⋄ ci), it isNP-complete to check whetherζisFP-satisfiable

work page

[3] [3]

Proof.We begin with the Item 1.NP-membership follows from Proposition 1

Given two PITsζ 1 andζ 2 it iscoNP-complete to check whetherζ 1 |=FP ζ2. Proof.We begin with the Item 1.NP-membership follows from Proposition 1. We provide a reduction from the classical non-validity problem of DNFs, which isNP-complete. Namely, letϕ= mW i=1 nV j=1 li j be a formula in DNF, and define ζϕ := mK i=1  Pr   n^ j=1 li j   ≤ 0   We sho...

work page arXiv 2025

[4] [4]

There is no PILλ ′ s.t.E(λ ′)⊆H,λ|= FP λ′,λ ′ |=FP λ♭ V,λ ′ ̸|=FP λ, andλ ♭ V ̸|=FP λ′

work page

[5] [5]

Proof sketch.We begin with Item 1 and consider only the case ofλ=Pr(σ)≥ cwithc= k n for brevity

There is no PILλ ′′ s.t.E(λ ′′)⊆H,λ|= FP λ′′,λ ′′ |=FP λ∗,λ ′′ ̸|=FP λ, andλ ∗ ̸|=FP λ′′. Proof sketch.We begin with Item 1 and consider only the case ofλ=Pr(σ)≥ cwithc= k n for brevity. Other cases can be dealt with similarly. Now, assume for contradiction that there is someλ ′ s.t.λ|= FP λ′,λ ′ |=FP λ♭ V,λ ′ ̸|=FP λ, andλ ♭ V ̸|=FP λ′. We consider the f...

work page 2025

[6] [6]

We set∂ f(w1) = min{f(π)|π∈Υ}

work page

[7] [7]

, r}, pickπ∈Υs.t.♯ f(π) =iand set∂ f(wi) =f(π)−∂ f(wi−1)

Then, for eachi∈ {2, . . . , r}, pickπ∈Υs.t.♯ f(π) =iand set∂ f(wi) =f(π)−∂ f(wi−1)

work page

[8] [8]

It is clear that the probability measureµ ∂f induced by∂ f is coherent withf

Ifmax{f(π)|π∈Υ}<1, set additionally,∂(w 0) = 1−∂(w r). It is clear that the probability measureµ ∂f induced by∂ f is coherent withf. The result now follows. Proposition 4.For every finite CIP theoryΓ⊆ L Q Pr, there is anL Q Ł -theoryΨ Γ s.t. 1.Ψ Γ isŁ-satisfiable iffΓisFP-satisfiable; 2.Ψ Γ is constructible in polynomial time w.r.t. the size ofΓ. Proof.We...

work page 2025

[9] [9]

Proof of Item 1.We adapt the proof of (Inoue and Kozhemiachenko 2025, Theorem 15)

decidable in polynomial time if it has sufficient solutions; 2.NP-complete to check if it has concise full solutions. Proof of Item 1.We adapt the proof of (Inoue and Kozhemiachenko 2025, Theorem 15). To show that the existence of sufficient solutions is decidable in polynomial time, we construct a polynomial embedding of SPCF abduction problems into clas...

work page 2025

[10] [10]

There are▷, ▷ ′ ∈ {≥, >},◁, ◁ ′ ∈ {≤, <}, andc, d∈[0,1] Q such thatc > dand (a)v(r Pr(π)▷c) = 1andv(r Pr(π)◁d) = 1, or (b)v(r Pr(π)▷c) = 1andv(r Pr(π)▷′d) = 0, or (c)v(r Pr(π)◁c) = 0andv(r Pr(π)▷d) = 0, or (d)v(r Pr(π)◁c) = 0andv(r Pr(π)◁′d) = 1

work page

[11] [11]

We consider only the first case since the second one can be dealt with in a similar way

There are▷, ▷ ′ ∈ {≥, >},◁, ◁ ′ ∈ {≤, <}, andc, d∈[0,1] Q such thatc≥d,▷̸=▷ ′,◁̸=◁ ′, and (a)v(r Pr(π)▷c) = 1andv(r Pr(π)◁′d) = 1, or (b)v(r Pr(π)▷c) = 1andv(r Pr(π)▷′d) = 0, or (c)v(r Pr(π)◁c) = 0andv(r Pr(π)▷′d) = 0, or (d)v(r Pr(π)◁c) = 0andv(r Pr(π)◁′d) = 1. We consider only the first case since the second one can be dealt with in a similar way. In th...

work page

[12] [12]

There are▷, ▷ ′ ∈ {≥, >},◁, ◁ ′ ∈ {≤, <}, andc, d∈[0,1] Q such thatc > dand (a)v(r Pr(π)▷c) = 1andv(r Pr(ϱ)◁d) = 1, or (b)v(r Pr(π)▷c) = 1andv(r Pr(ϱ)▷′d) = 0, or (c)v(r Pr(π)◁c) = 0andv(r Pr(ϱ)▷d) = 0, or (d)v(r Pr(π)◁c) = 0andv(r Pr(ϱ)◁′d) = 1

work page

[13] [13]

Just as before, we consider only case 1 because case 2 can be tackled in the same way

There are▷, ▷ ′ ∈ {≥, >},◁, ◁ ′ ∈ {≤, <}, andc, d∈[0,1] Q such thatc≥d,▷̸=▷ ′,◁̸=◁ ′, and (a)v(r Pr(π)▷c) = 1andv(r Pr(ϱ)◁′d) = 1, or (b)v(r Pr(π)▷c) = 1andv(r Pr(ϱ)▷′d) = 0, or (c)v(r Pr(π)◁c) = 0andv(r Pr(ϱ)▷′d) = 0(with⟨◁, ▷ ′⟩ ∈ {⟨<,≥⟩,⟨≤, >⟩}), or (d)v(r Pr(π)◁c) = 0andv(r Pr(ϱ)◁′d) = 1. Just as before, we consider only case 1 because case 2 can be t...

work page

[14] [14]

Proof.Assume thatτis a solution toP p

there is a probabilistic modelM ′ =⟨2 V, µ′⟩s.t.µ ′ is coherent withpandPr µ′ (χ|ϕ∧τ) = 1. Proof.Assume thatτis a solution toP p. Thenϕ, τ|= CPL χand there is a probabilistic modelM p =⟨2 V, µp⟩coherent withps.t.µ p(∥ϕ∧τ∥ M)>0. Now,ϕ, τ|= CPL χimplies that∥ϕ∧τ∥ M ⊆ ∥χ∥ M for all probabilistic modelsM=⟨2 V, µ⟩. It follows thatµ(∥ϕ∧τ∥ M)≤µ(∥χ∥ M). This give...

work page

[15] [15]

Proof.We begin with hardness for Items 1 and 3

inΠ P 2 to check ifτis a preferred solution toP p; 3.Σ P 2 -complete to check ifP p has solutions. Proof.We begin with hardness for Items 1 and 3. Recall that classical abduction problems are a particular case of probabilistic abduction problems. As is well-known from (Eiter and Gottlob 1995), solution recognition for classical abduction problems isDP-com...

work page 1995