Reasoning About Probabilities, Actions, and Knowledge in Fuzzy Modal Logic
Daniil Kozhemiachenko, Igor Sedlár · 2026
Read Reasoning About Probabilities, Actions, and Knowledge in Fuzzy Modal Logic by Daniil Kozhemiachenko, Igor Sedlár (2026) 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-2604-22459.txt.
Introduction
Kozhemiachenko and Sedlár build a fuzzy modal logic for reasoning about chance, action, and knowledge together. It can state claims such as how an action raises or lowers the chance that someone knows a fact. Meaning is given on Kripke frames, networks of possible worlds, fitted with probability measures. The authors then map how hard it is to decide whether formulas can be true, across the full language and varied fragments. For several fragments they pin down polynomial-time decidability, marking where the logic stays tractable.
Catalog record
| CREATOR | Daniil Kozhemiachenko, Igor Sedlár |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 125260 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.22459
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reasoning About Probabilities, Actions, and Knowledge in Fuzzy Modal Logic Daniil Kozhemiachenko, Igor Sedlár Abstract We explore a fuzzy modal logic that can formalise probabilistic reasoning about actions and knowledge. In particular, we deal with contexts involving statements about events expressed via modal formulas, e.g., ‘after doing a a , the probability of A A knowing that p p holds increases / decreases / is equal to 0.25 0.25 ’, ‘according to A A , p p is equally likely to happen after doing a a or b b ’, etc. We define the semantics of the logic on Kripke frames equipped with probability measures. We analyse the complexity of deciding the satisfiability of formulas of our logic over finitely branching models, for the full language and its fragments of varying expressivity. In particular, we identify several fragments of our logic where satisfiability is decidable in polynomial time. 1 Introduction Probabilistic reasoning is a well-established field in artificial intelligence and knowledge representation and reasoning. It has found numerous applications in logic programming [ 29 , 26 , 31 ] , ontologies [ 27 , 30 ] , and formal argumentation [ 25 , 18 ] . An important approach to the formalisation of probabilistic reasoning is probabilistic logics . These are formal systems that formalise reasoning with probabilistic statements such as ‘if the probability of p is twice as much as the probability of q , then the probability of q is less than 0.5 ’. In this paper, we consider a fuzzy modal logic that can formalise probabilistic reasoning about actions and knowledge. We study the complexity of the full language and its fragments, including those for which satisfiability is decidable in polynomial time. This presents a perspective on the computational properties of formal verification and automated reasoning with probabilistic specifications that describe agents’ knowledge and actions. Probabilistic Logics Probabilistic logics were first proposed by Nilsson ( ? ). The propositional fragment of Nilsson’s logic was further studied by Fagin et al. ( ? ). Later, Fagin and Halpern ( ? ) considered an expansion of probabilistic logic with epistemic modalities. Bacchus et al. ( ? ) propose a framework for a probabilistic logic of action and belief based on Reiter’s situation calculus. Halpern and Pucella ( ? ) considered logics with operators expressing upper probabilities to model qualitative uncertainty about probabilities. Halpern and O’Neill ( ? ) apply probabilistic epistemic logic to reasoning about anonymity in multi-agent systems. Since then, even more expressive systems of probabilistic logics have been extensively studied. In particular, Ognjanovic et al. ( ? ), Doder and Perovic ( ? ), and Doder and Ognjanovic ( ? ) consider temporal probabilistic logic. Tomovic et al. ( ? ) studied an epistemic expansion of the first-order probabilistic logic, and Doder et al. ( ? ) explored a multi-agent logic for reasoning about lower and upper probabilities. Probabilistic Reasoning in Fuzzy Logics An important alternative approach to probabilistic logics is to use so-called fuzzy logics to reason about probabilities. Fuzzy logics were introduced by Zadeh ( ? ; ? ) to reason about imprecise statements such as ‘it is cold outside’, ‘the symptoms are severe’, etc. In fuzzy logics, formulas are evaluated over the interval [0,1] , and their values are interpreted as degrees of truth from 0 (absolutely false) to 1 (absolutely true). Fuzzy logics have multiple applications in artificial intelligence. In particular, He et al. ( ? ) develop an autonomous bidding strategy based on fuzzy logic. Semantics of fuzzy logic is used to support learning and reasoning in real-world domains [ 15 , 6 ] and statistical relational learning [ 5 ] . Furthermore, van Krieken et al. ( ? ) analyse the interaction between different fuzzy logic semantics and learning. Chen et al. ( ? ) use fuzzy logic in reasoning problems with knowledge graphs. Reasoning about uncertainty in fuzzy logics is usually formalised with two-layered formulas . Namely, the probability of an event \alpha ( inner or event formula ) is the truth degree of the probabilistic atom — the formula \mathsf{Pr}(\alpha) , interpreted as ‘ \alpha is probable’. Initially [ 20 , 19 ] , the events were formalised using classical propositional formulas, and probabilistic atoms were combined with connectives of Łukasiewicz logic into outer formulas . Hájek et al. ( ? ) expand this framework into the language of Product fuzzy logic with rational constants [ 16 ] to express thresholds and conditional probabilities. It is shown by Baldi et al. ( ? ) that propositional fuzzy probabilistic logics have the same expressivity as logics of Fagin et al. ( ? ). It is argued that the same expressive power comes with a much simpler syntax and axiomatisation. Modal expansions of fuzzy probabilistic logics have also been extensively studied. In particular, Godo et al. ( ? ) expressed Dempster–Shafer belief functions with formulas of the form \mathsf{Pr}(\Box\alpha) . Using the work of Marchioni ( ? ), Corsi et al. ( ? ) showed that lower probabilities can be expressed via formulas of the form \Box\mathsf{Pr}(\alpha) . They considered a logic where epistemic modalities are used to both express events and statements about their probabilities. Majer and Sedlár ( ? ) and Kozhemiachenko and Sedlár ( ? ) considered a fuzzy probabilistic modal logic with arbitrary \Box -like modalities and propositional event formulas, allowing for a broader model of lower probabilities where uncertainty is not necessarily epistemic in nature, but may arise as a result of non-determinism in outcomes of actions. Contributions Although probabilistic fuzzy modal logics have received much attention, to the best of our knowledge, the framework proposed by Corsi et al. ( ? ) is the only one where modalities can appear on both layers. It also seems that the computational properties of such logics are considerably less studied. Thus, in this paper, we bring together the frameworks of [ 14 ] and [ 28 ] and explore a logic that we call \mathsf{EA^{Pr}} , whose language is based upon a modal expansion of the combined Łukasiewicz and Product logics where epistemic and action modalities appear both in inner- and outer-layer formulas. As we will see in Section 3 , this enables us to reason with a wide range of events and express various relations between their probabilities. We show that the language can (i) express probabilistic statements about modal events involving knowledge or effects of actions (e.g. statements about the probability of an agent knowing a proposition or a proposition holding after a specific action is performed) and (ii) represent lower and upper probabilities of events arising from epistemic uncertainty or from uncertainty about outcomes of actions. As we discuss in more detail below, system specifications of these forms are important in areas such as multi-agent systems, cybersecurity, and robotics. The main technical result in the paper is an extensive study of the complexity of \mathsf{EA^{Pr}} . We establish that the validity (and satisfiability) problem for arbitrary formulas over finitely-branching models is \mathsf{PSPACE} -complete. We also consider several fragments of our language where validity is decidable in polynomial time . Our contributions shed light on the computational features of formal verification and automated reasoning for probabilistic