# Complexity of Łukasiewicz Modal Probabilistic Logics

Daniil Kozhemiachenko, Igor Sedlár

► To cite this version:

Daniil Kozhemiachenko, Igor Sedlár. Complexity of Łukasiewicz Modal Probabilistic Logics. Theoretical Aspects of Rationality & Knowledge (TARK 2025), Jul 2025, Düsseldorf, Germany. pp.344-358, 10.4204/EPTCS.437.28 . hal-05348645

HAL Id: hal-05348645

https://hal.science/hal-05348645v1

Submitted on 5 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Complexity of Łukasiewicz Modal Probabilistic Logics

Daniil Kozhemiachenko

Aix Marseille Univ, CNRS, LIS, Marseille, France

daniil.kozhemiachenko@lis-lab.fr

Igor Sedlár*

The Czech Academy of Sciences, Institute of Computer Science, Prague, Czech Republic

sedlar@cs.cas.cz

Modal probabilistic logics provide a framework for reasoning about probability in modal contexts, involving notions such as knowledge, belief, time, and action. In this paper, we study a particular family of these logics, extending the modal Łukasiewicz many-valued logic. These logics are shown to be capable of expressing nuanced probabilistic concepts, including upper and lower probabilities. Our main contribution is a PSPACE-completeness result for two variants of the local consequence problem, providing a precise computational characterisation.

## 1 Introduction

Probabilistic logics have been studied and applied in various fields for decades [19, 28]. In particular, they provide formal languages that express information about probabilistic models in a compact yet unambiguous way, and they can be used to facilitate and verify reasoning about these models. The many-valued approach to probabilistic logic goes back to the work of Hájek et al. [14, 15, 16, 24], where ‘α is probable’ is taken as an imprecise statement whose truth value (or truth degree) is identified with the probability of α. This approach contrasts with the better-known logic of Fagin et al. [10], which uses formulas involving linear inequalities over probabilistic terms to represent precise statements about probability – statements which are either true or false. Many-valued probabilistic logics are tailored for expressing imprecise information about probabilistic models in terms of properties that models do not simply “have” or “not have”, but which models have to some degree. A particular example are imprecise comparisons, indicating the degree to which two probabilities differ. Another advantage of the many-valued approach is its simpler syntax and axiomatisation. Nevertheless, as shown in [3], the many-valued approach and the linear approach are linked by entailment-preserving translations.

In computer science, artificial intelligence and economics, modal probabilistic logics are of particular importance. These logics formalise reasoning about probability in the presence of modal notions such as knowledge, belief, time and action [1, 2, 7, 9]. In [26], a many-valued framework for modal probabilistic logic was introduced by combining modal Łukasiewicz logic [21] with the propositional probabilistic logics of Hájek et al. Decidability of the basic many-valued modal probabilistic logic and some of its extensions was established by reduction to basic non-probabilistic modal Łukasiewicz logic, which is known to be decidable [29]. However, the reduction is not polynomial and so it does not by itself yield complexity results for many-valued modal probabilistic logics. This paper makes two contributions to this line of research. First, using the tableaux method, we show that the problem of deciding local consequence over finitely branching frames is PSPACE-complete even for a rather expressive extension of

<footnote>*Work of the second author was supported by the grant 22-16111S of the Czech Science Foundation. We would like to thank the reviewers for their comments, which helped us improve the paper.</footnote>
the language used in [26]. We also show that the problem of deciding local consequence over arbitrary frames is PSPACE-complete if we restrict ourselves to a specific fragment of the full language. Secondly, we argue that our framework is sufficiently expressive to formalise a variety of practically relevant concepts and scenarios, including upper and lower probabilities and their imprecise comparisons. These two contributions together establish many-valued modal logics as a viable framework for formalising the interplay between probability and modality.

The paper is structured as follows. Section 2 introduces our basic semantic structures, probabilistic frames, and provides several examples of these structures. It also discusses their relationship with similar structures proposed in the literature. Section 3 discusses a many-valued modal logic for reasoning about probabilistic frames. This logic is based on a modal extension of ŁΠ<sup>1</sup>&frasl;<sub>2</sub> [8], which is an expressive combination of Łukasiewicz and product fuzzy logics [14]. Section 4 shows how our logic can be used to represent and reason about a variety of practically relevant concepts and scenarios. Section 5 establishes our main technical results on the PSPACE-completeness of the local consequence problem (i) over finitely branching frames using the full language and (ii) over arbitrary frames using a specific fragment of the full language. Section 6 concludes the paper and lists some tasks left for the future.

## 2 Probabilistic frames

Recall that a *finitely additive probability measure* on a Boolean algebra $X$ is a function $P: X \to [0, 1]$ such that (i) $P(1_X) = 1$ and (ii) $P(x \lor y) = P(x) + P(y)$ for all $x,y$ such that $x \land y = 0_X$. A probability measure on a finite Boolean algebra is uniquely determined by its values on the atoms of the algebra.

**Definition 1 (Probabilistic frames).** Let A be an at most countable set. A *probabilistic A-frame* is a tuple $\mathfrak{F} = (W, R, S, \mu)$ such that $\langle W, R \rangle$ is a Kripke A-frame comprising a non-empty set W and a function R from A to binary relations on W, S is a Boolean subalgebra of $2^W$ containing W, and $\mu = \langle \mu_w \rangle_{w \in W}$ with each $\mu_w: S \to [0, 1]$ being a finitely additive probability measure on S.

The set of modal indices A can be used to represent various kinds of objects, for instance, agents or actions. As usual in modal logic, Kripke A-frames represent a collection of possible states of affairs, or *possible worlds*, connected with *accessibility relations* $R_a$ for $a \in A$. These relations can represent, for example, the qualitative uncertainty of agents ($wR_a u$ means that the information of agent $a$ in world $w$ is not sufficient to exclude $u$ as a possibility) or the effects of actions ($wR_a u$ means that world $u$ is a possible outcome of performing action $a$ in world $w$). The collection S of subsets of W represents *events* (or *propositions*). Intuitively, events correspond to features of possible worlds to which probabilities will be assigned. This assignment is carried out using the collection of functions $\mu$: for every world $w \in W$, $\mu_w(E)$ expresses the probability of event $E \in S$ in world $w$ — the crucial feature of *modal probabilistic frames* is that the probabilities of events can vary from world to world, much as the truth values of propositions can vary from world to world in standard modal semantics.

*Example 1.* Suppose a robot is sent to retrieve an item from a warehouse. If the warehouse light is on (i.e. *L* is true), then the probability of retrieving the correct item (i.e. *I* being true) is 0.8. On the other hand, if *L* is false, then the probability of *I* being true is 0.2. There are two possible start states, which represent the situation before the robot operates and are distinguished by whether the light is on or off. There are also four possible end states, as shown in Figure 1. The start states, $s_L$ and $s_{-L}$, are shown on the bottom line, and the end states $e_{L \land I}$, $e_{L \land \neg I}$, $e_{-L \land I}$ and $e_{-L \land \neg I}$ are shown on the top line. The arrows labelled with *b* represent the possible outcomes of the robot’s actions (it is assumed that the robot cannot turn the light switch). In the state $s_L$, the probability of the event $E_I = \{e_{L \land I}, e_{-L \land I}\}$, indicated using the thick circle, is 0.8 and the probability of the event $E_{-I} = \{e_{L \land \neg I}, e_{-L \land \neg I}\}$ is 0.2. In the state $s_{-L}$,
<figure><img src="image_2.png" /><figcaption>Figure 1: The robot in a warehouse example.</figcaption></figure>

the probabilities are reversed: $E_I$ has probability 0.2 and $E_{\neg I}$ has probability 0.8.<fnref n="1" /> The arrows labelled by $a$ represent the action of switching the warehouse light switch before the robot operates. This action clearly changes the probability of $E_I$ – the probability of $E_I$ increases when the light is switched on and decreases when it is switched off.

**Example 2.** Take the scenario from Example 1, but now suppose we have an agent $a$ who lacks information about the warehouse lights. In standard probabilistic fashion, $a$'s uncertainty could be modelled quantitatively by a subjective probability distribution on $\{s_L, s_{\neg L}\}$. However, such a distribution expresses more information than we seem to have. We know that $s_L$ and $s_{\neg L}$ are possibilities for the agent, but we don't know how likely the agent thinks these possibilities are. Without this additional information, we can use the resources of epistemic modal logic and model the agent's uncertainty qualitatively by a binary equivalence relation. This is again depicted in Figure 1 if the arrow labelled by $a$ is seen as representing agent $a$'s qualitative uncertainty. The idea of modelling qualitative uncertainty by a set of probability distributions is an old one [19, Ch. 2.3].

**Example 3.** Well-known kinds of probabilistic relational structures also provide examples of probabilistic frames. Example 1 suggests the following construction. A discrete-time Markov chain is a triple $\mathbf{M} = \langle\{1, \dots, n\}, \mathfrak{p}, \mathfrak{q}\rangle$ where $N = \{1, \dots, n\}$ represents a set of states, $\mathfrak{p}: N \times N \to [0, 1]$ is a transition probability function such that $\sum_{j=1}^n \mathfrak{p}(i, j) = 1$ for all $i \in N$, and $\mathfrak{q}: N \to [0, 1]$ is a start probability function such that $\sum_{i=1}^n \mathfrak{q}(i) = 1$. For each $m \in \mathbb{N}$, a Markov chain $\mathbf{M}$ gives rise to a probability measure on the set of all paths over $N$ of length $m$: $P(i_0, \dots, i_m) = \mathfrak{q}(i_0) \cdot \prod_{j=1}^m \mathfrak{p}(i_{j-1}, i_j)$. Every $\mathbf{M} = \langle N = \{1, \dots, n\}, \mathfrak{p}, \mathfrak{q}\rangle$ can be seen as a probabilistic $N$-frame $\mathfrak{F}\mathbf{M} = \langle N_0, R, 2^S, \langle\mu_i\rangle_{i \in N_0}\rangle$ where $N_0 = N \cup \{0\}$, $R_k(i, j)$ iff $j = k$ for $j, k \in N$ and $i \in N_0$, and $\mu_i(\{j\}) = \mathfrak{p}(i, j)$ if $i, j \in N$ and $\mu_0(\{i\}) = \mathfrak{q}(i)$.

**Example 4.** The following is a generalisation of probabilistic frames. A multi-agent probabilistic A-frame is a structure $\langle W, R, S, \mu \rangle$ such that $\langle W, R, S \rangle$ is as before and $\mu = \langle \mu_{w,a} \rangle_{w \in W, a \in G}$ for some $G \subseteq A$ such that $\mu_{w,a}: S \to [0, 1]$ is a finitely additive probability measure. Modal indices in $G$ represent agents and $\mu_{w,a}$ represents the subjective probability distribution of agent $a$ in $w$. That is, in multi-agent frames, probability measures $\mu$ have a world index and an agent index while accessibility relations $R$ are indexed by all $a \in A$ as before. Probabilistic frames correspond to the special case with only one fixed agent index $a_0 \in A$ which can be omitted. Multi-agent probabilistic frames where $W$ is finite, $S = 2^W$, $A = G$ and $R_a$ is an equivalence relation correspond to finite semantic knowledge-belief systems of [1], structures that extend finite Harsanyi type spaces [22] with S5-style knowledge operators. Intuitively, the relation $R_a$ represents the knowledge state of agent $a$ in a manner similar to Example 2. We confine the more general multi-agent framework to this example mainly for reasons of notational simplicity.

**Remark 1.** Probabilistic frames are similar to structures that have appeared in the literature. Aumann's in-finite semantic knowledge-based systems [1] assume that $S$ is closed under countable unions ($\sigma$-algebra)

<footnote n="1">¹We assume for the sake of simplicity that, in each end state $e$, the only event that has non-zero probability is $\{e\}$ and that the probability of this event is 1.</footnote>
and that $\mu_a(\cdot, E) : w \mapsto \mu_{w,a}(E)$ is an S-measurable mapping from $W$ to $[0, 1]$. This condition also appears in the definition of Markov kernels, probabilistic transition systems on infinite state spaces. The condition allows to define probabilities of events of the form “The probability of event $E$ is at least $r$” for $r \in [0, 1] \cap \mathbb{Q}$; see [22, 25, 31]. In this paper we focus only on probability assignments to Boolean events, and so we can use simpler structures. Fagin and Halpern [9] use similar A-frames $\langle W, R, \mathcal{P} \rangle$ with $\mathcal{P}(a, w) = \langle W_{a,w}, S_{a,w}, \mu_{a,w} \rangle$ being a probability space for $W_{a,w} \subseteq W$, $S_{a,w}$ a Boolean algebra of subsets of $W_{a,w}$ containing $W_{a,w}$, and $\mu_{a,w}$ a probability measure on $S_{a,w}$. That is, not only the probability measure but also the space of measurable events can vary from world to world.<fnref n="2" /> Our structures are simpler.

### 3 Modal many-valued probabilistic logic

We have seen that probabilistic frames are a general and versatile type of semantic structure. In this section, we introduce a language based on many-valued modal logic for expressing and reasoning about properties of probabilistic frames. We build on the work of Hájek et al. [14, 15, 16, 24], who focus on variants of the well-known Łukasiewicz fuzzy logic and its combinations with product fuzzy logic. The propositional fragment of our modal language can be seen as the language of $\mathbf{L}\Pi_{\frac{1}{2}}$ logic, a combination of Łukasiewicz and product logic and one of the most expressive propositional fuzzy languages.

Let $\text{Prop}$ be a countably infinite set of propositional variables. Let $\mathcal{L}_{\{\sim,\wedge\}}$ be the set of Boolean terms generated via the following grammar:

$$ \mathcal{L}_{\{\sim,\wedge\}} \ni \alpha := p \in \text{Prop} \mid \sim\alpha \mid (\alpha \wedge \alpha) $$

We use Greek letters $\alpha, \beta$ to range over $\mathcal{L}_{\{\sim,\wedge\}}$.

**Definition 2.** The modal probabilistic language $\mathcal{L}_{\text{Pr}}^{\mathcal{A}}$ is given by

$$ \mathcal{L}_{\text{Pr}}^{\mathcal{A}} \ni \phi := \text{Pr}(\alpha) \mid \neg\phi \mid (\phi \rightarrow \phi) \mid (\phi \bullet \phi) \mid (\phi \rightarrow_{\Pi} \phi) \mid \Box_a \phi \mid \frac{1}{2} $$

for $\alpha \in \mathcal{L}_{\{\sim,\wedge\}}$ and $a \in A$. We will assume a fixed A from now on and omit explicit reference to it in most notation. In what follows, we will call formulas of the form $\text{Pr}(\alpha)$ probabilistic atoms.

**Convention 1 (Notation).** Given $\phi \in \mathcal{L}_{\text{Pr}}$, we use $\text{Prop}(\phi)$ to denote the set of propositional variables occurring in $\phi$. Furthermore, $\ell(\phi)$ denotes the length of $\phi$, i.e., the number of occurrences of symbols in it. Similarly, for $\Gamma \subseteq \mathcal{L}_{\text{Pr}}$, we use $\text{Pr}[\Gamma]$ and $\ell[\Gamma]$ for the set of propositional variables in $\Gamma$ and its length. Finally, given a binary relation $R$ on $W$, we set $R(w) := \{w' \mid wRw'\}$.

**Definition 3 (Modal depth).** Let $\phi \in \mathcal{L}_{\text{Pr}}$. Its modal depth $(d(\phi))$ is defined inductively as follows: $d(p) = 0$, $d(\neg\phi) = d(\phi)$, $d(\phi \circ \chi) = \max(d(\phi), d(\chi))$ (with $\circ \in \{\rightarrow, \bullet, \rightarrow_{\Pi}\}$), $d(\Box_a\phi) = d(\phi) + 1$. Given $\Gamma \subseteq \mathcal{L}_{\text{Pr}}$, the modal depth of $\Gamma$ is $(d[\Gamma])$ is defined as follows: $d[\Gamma] = \max\{d(\phi) \mid \phi \in \Gamma\}$.

**Definition 4 (Semantics of $\mathbf{K}\mathbf{L}\Pi_{\frac{1}{2}}^{\text{Pr}}$).** A $\mathbf{K}\mathbf{L}\Pi_{\frac{1}{2}}^{\text{Pr}}$-model is a pair $\mathfrak{M} = \langle \mathfrak{F}, E \rangle$ with $\mathfrak{F}$ a probabilistic frame and an event function or valuation $E : \text{Prop} \to S$ extended to a homomorphism $\mathcal{L}_{\{\sim,\wedge\}} \to S$ in an obvious way. The probabilistic interpretation induced by $\mathfrak{M}$ is a function $\mathcal{J}_{\mathfrak{M}} : \mathcal{L}_{\text{Pr}} \times W \to [0, 1]$ s.t.

<footnote n="2">²We note that Fagin and Halpern's frames do not require that $\mu_a(\cdot, E) : w \mapsto \mu_{w,a}(E)$ be measurable; indeed, such a requirement requires a “common” space of measurable events. Instead, they use inner measures to define probabilities of events of the form “the probability of event $E$ is at least $r$”.</footnote>
$\mathcal{I}_{\mathfrak{M}}(\frac{1}{2}, w) = \frac{1}{2}$ and

$$ \mathcal{I}_{\mathfrak{M}}(\mathrm{Pr}(\alpha), w) = \mu_w(E(\alpha)) \qquad \mathcal{I}_{\mathfrak{M}}(\phi \to \chi, w) = \min(1, 1 - \mathcal{I}_{\mathfrak{M}}(\phi, w) + \mathcal{I}_{\mathfrak{M}}(\chi, w)) $$

$$ \mathcal{I}_{\mathfrak{M}}(\phi \bullet \chi, w) = \mathcal{I}_{\mathfrak{M}}(\phi, w) \cdot \mathcal{I}_{\mathfrak{M}}(\chi, w) \qquad \mathcal{I}_{\mathfrak{M}}(\phi \to \Pi \chi, w) = \begin{cases} 1 & \text{if } \mathcal{I}_{\mathfrak{M}}(\phi, w) \le \mathcal{I}_{\mathfrak{M}}(\chi, w) \\ \frac{\mathcal{I}_{\mathfrak{M}}(\chi, w)}{\mathcal{I}_{\mathfrak{M}}(\phi, w)} & \text{otherwise} \end{cases} $$

$$ \mathcal{I}_{\mathfrak{M}}(\neg\phi, w) = 1 - \mathcal{I}_{\mathfrak{M}}(\phi, w) \qquad \mathcal{I}_{\mathfrak{M}}(\Box_a\phi, w) = \inf\{\mathcal{I}_{\mathfrak{M}}(\phi, w') \mid w' \in R_a(w)\} $$

We say that $\phi \in \mathcal{L}_{\mathrm{Pr}}$ is $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}}$-valid on a pointed frame $\langle \mathfrak{F}, w \rangle$ (denoted $\mathfrak{F}, w \models_{\mathrm{Pr}} \phi$) if $\mathcal{I}_{\mathfrak{M}}(\phi, w) = 1$ for every $E : \mathrm{Prop} \to S$; $\phi$ is $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}}$-valid on $\mathfrak{F}$ ($\mathfrak{F} \models_{\mathrm{Pr}} \phi$) if $\mathfrak{F}, w \models_{\mathrm{Pr}} \phi$ for every $w \in \mathfrak{F}$. Given a class $\mathbb{F}$ of probabilistic frames, we say that $\phi$ is $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}}$-valid in $\mathbb{F}$ ($\mathbb{F} \models_{\mathrm{Pr}} \phi$) if $\mathfrak{F} \models_{\mathrm{Pr}} \phi$ for every $\mathfrak{F} \in \mathbb{F}$. Finally, $\phi$ is $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}}$-valid ($\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}} \models \phi$) if it is valid on all frames, and $\Gamma \subseteq \mathcal{L}_{\mathrm{Pr}}$ entails $\chi$ ($\Gamma \models_{\mathrm{Pr}} \chi$) if $\mathcal{I}_{\mathfrak{M}}(\chi, w) = 1$ in every $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}}$-model $\mathfrak{M}$ and $w \in \mathfrak{M}$ s.t. $\mathcal{I}_{\mathfrak{M}}(\phi, w) = 1$ for all $\phi \in \Gamma$.

Other Łukasiewicz connectives can be defined in a standard manner:

$$ \begin{array}{lclcl} \top & := & \mathrm{Pr}(p) \to \mathrm{Pr}(p) & \quad \Delta\phi & := \neg\phi \to \Pi \bot \\ \bot & := & \neg\top & \quad \Diamond_a\phi & := \neg\Box_a\neg\phi & \quad \phi \oplus \chi := \neg\phi \to \chi \\ & & & \quad \phi \vee \chi := (\phi \to \chi) \to \chi & \quad \phi \wedge \chi := \neg(\phi \vee \neg\chi) \\ & & & \quad \phi \leftrightarrow \chi := (\phi \to \chi) \odot (\chi \to \phi) & \quad \phi \odot \chi := \neg(\neg\phi \oplus \neg\chi) \end{array} $$

Using Definition 4, one can obtain their semantics:

$$ \mathcal{I}_{\mathfrak{M}}(\top, w) = 1 \qquad \mathcal{I}_{\mathfrak{M}}(\phi \oplus \chi, w) = \min(1, \mathcal{I}_{\mathfrak{M}}(\phi, w) + \mathcal{I}_{\mathfrak{M}}(\chi, w)) $$

$$ \mathcal{I}_{\mathfrak{M}}(\bot, w) = 0 \qquad \mathcal{I}_{\mathfrak{M}}(\phi \odot \chi, w) = \max(0, \mathcal{I}_{\mathfrak{M}}(\phi, w) + \mathcal{I}_{\mathfrak{M}}(\chi, w) - 1) $$

$$ \mathcal{I}_{\mathfrak{M}}(\Delta\phi, w) = \begin{cases} 1 & \text{if } \mathcal{I}_{\mathfrak{M}}(\phi, w) = 1 \\ 0 & \text{otherwise} \end{cases} \qquad \mathcal{I}_{\mathfrak{M}}(\phi \vee \chi, w) = \max(\mathcal{I}_{\mathfrak{M}}(\phi, w), \mathcal{I}_{\mathfrak{M}}(\chi, w)) \\ \mathcal{I}_{\mathfrak{M}}(\phi \wedge \chi, w) = \min(\mathcal{I}_{\mathfrak{M}}(\phi, w), \mathcal{I}_{\mathfrak{M}}(\chi, w)) $$

$$ \mathcal{I}_{\mathfrak{M}}(\phi \leftrightarrow \chi, w) = 1 - |\mathcal{I}_{\mathfrak{M}}(\phi, w) - \mathcal{I}_{\mathfrak{M}}(\chi, w)| \qquad \mathcal{I}_{\mathfrak{M}}(\Diamond_a\phi, w) = \sup\{\mathcal{I}_{\mathfrak{M}}(\phi, w') \mid w' \in R_a(\phi)\} $$

We note that the semantics of $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}}$ can be equivalently reformulated if we redefine frames by allowing $S$ to be an arbitrary Boolean algebra independent from $W$. We call these frames and their respective models *sample-independent* (SI-frames and SI-models).

**Definition 5.**

* An SI probabilistic A-frame over $X$ (SI-frame) is a tuple $\mathfrak{F} = (W, R, X, \mu)$ with $\langle W, R \rangle$ being a Kripke A-frame, $X \neq \emptyset$ a Boolean algebra, and $\mu = \langle \mu_w \rangle_{w \in W}$ being a tuple of finitely additive probability measures on $X$.

* An SI-$\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}}$-model is a tuple $\mathfrak{M} = (\mathfrak{F}, E)$ with $\mathfrak{F}$ being a sample-independent probabilistic frame and $E : \mathrm{Prop} \to X$. The notions of probabilistic interpretations induced by $\mathfrak{M}$, entailment, and validity are the same as in Definition 4.

**Theorem 1.** Let $\phi \in \mathcal{L}_{\mathrm{Pr}}$. Then $\phi$ is $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}}$-valid iff $\phi$ is $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}}$-valid on SI-models.

*Proof.* Clearly, if $\phi$ is $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}}$-valid on SI-models, then it is valid on $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}}$-models. For the converse, let $\phi$ be not $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}}$-valid on SI-models. Thus, $\mathcal{I}_{\mathfrak{M}}(\phi, w) = x < 1$ for some SI-model $\mathfrak{M} =$
$\langle W, R, X, \mu, E \rangle$. If $|X| \le |2^W|$, it is clear, that $\mathfrak{M}$ is also a $\mathbf{KL}\mathbf{\Pi}_{\frac{1}{2}}^{\mathbf{1}^{\mathrm{Pr}}}$-model. Otherwise let $|X| = 2^{|W|+n}$. We define a $\mathbf{KL}\mathbf{\Pi}_{\frac{1}{2}}^{\mathbf{1}^{\mathrm{Pr}}}$ model $\mathfrak{M}' = \langle W', R', X, \mu, E \rangle$ as follows. Let $W' = W \cup \{w_1, \dots, w_n\}$ for new states $w_1, \dots, w_n$; let further, $wR'_aw'$ iff $\{w, w'\} \subseteq W$ and $wR_aw'$. Now, using that the measures and valuations of propositional variables in $\mathfrak{M}$ and $\mathfrak{M}'$ coincide, one can show by induction on $\phi$ that $\mathcal{I}_{\mathfrak{M}}(\phi, w) = \mathcal{I}_{\mathfrak{M}'}(\phi, w)$ for every $w \in W$. The result follows. $\square$

An important property of SI-models is that given $\mathfrak{M}$ and $\phi \in \mathcal{L}_{\mathrm{Pr}}$, one can assume that $X = 2^{2^{\mathrm{Prop}(\phi)}}$. Intuitively, this means that to verify whether an $\mathcal{L}_{\mathrm{Pr}}$-formula is valid, it suffices to check probability distributions over Boolean terms that can be composed of its variables.

**Proposition 1.** Let $\mathfrak{M} = \langle W, R, X, \mu, E \rangle$ be an SI-model. Define $\mathfrak{M}_{\phi}^{\mathcal{C}} = \langle W, R, 2^{2^{\mathrm{Prop}(\phi)}}, \mu^{\mathcal{C}}, E^{\mathcal{C}} \rangle$ s.t.

$$ \begin{gather*} \forall p \in \mathrm{Prop} : E^{\mathcal{C}}(p) = \{Y \mid p \in Y, Y \subseteq \mathrm{Prop}(\phi)\} \\ \forall w \in W, Y \subseteq \mathrm{Prop}(\phi) : \mu_w^{\mathcal{C}}(\{Y\}) = \mu_w \left( E \left( \bigwedge_{p \in Y} p \wedge \bigwedge_{q \notin Y} \neg q \right) \right) \end{gather*} $$

Then $\mathcal{I}_{\mathfrak{M}}(\phi, w) = \mathcal{I}_{\mathfrak{M}}^{\mathcal{C}}(\phi, w)$ for every $w \in W$ and $\phi \in \mathcal{L}_{\mathrm{Pr}}$.

*Proof.* Induction on $\phi$. For the basis case, we let w.l.o.g. $\phi = \mathrm{Pr}(\alpha)$ for some $\alpha = \bigvee_{i=1}^n \tau_i$ in the DNF each part of which contains all variables of $\phi$. Now, $\mathcal{I}_{\mathfrak{M}}(\mathrm{Pr}(\alpha), w) = x$ means that $\mu_w \left( E \left( \bigvee_{i=1}^n \tau_i \right) \right) = x$, i.e., $\sum_{i=1}^n \mu_w(E(\tau_i)) = x$. From here, using the fact that $Y \models \tau$ iff $Y = \{p \mid p \in \tau\}$, we obtain that $\mu_w^C(E^C(\tau_i)) = \mu_w((\tau_i))$ for every $i \in \{1, \dots, n\}$. Thus, $\sum_{i=1}^n \mu_w^C(E^C(\tau_i)) = \sum_{i=1}^n \mu_w(E(\tau_i)) = x$, as required.

The cases of propositional connectives can be shown by a straightforward application of the induction hypothesis. The case of $\phi = \Box \chi$ follows easily since $\langle W, R \rangle$-reducts in $\mathfrak{M}$ and $\mathfrak{M}_{\phi}^{\mathcal{C}}$ coincide. $\square$

In what follows, we will use $\mathcal{L}\square$ to denote the fragment of $\mathcal{L}_{\mathrm{Pr}}$ s.t. only the probabilistic atoms of the form $\mathrm{Pr}(p)$ with $p \in \mathrm{Prop}$ are allowed. We will also use $\mathbf{KL}\mathbf{\Pi}_{\frac{1}{2}}$ to denote the $\mathcal{L}\square$-fragment of $\mathbf{KL}\mathbf{\Pi}_{\frac{1}{2}}^{\mathrm{Pr}}$ and $\models$ for its entailment (satisfaction) relation. As every two distinct probabilistic atoms concern two independent events, it is clear that $\mathbf{KL}\mathbf{\Pi}_{\frac{1}{2}}$-models can be built on Kripke frames, ignoring measures, i.e., treating each $\mathrm{Pr}(p)$ as a propositional variable. Namely, given a Kripke frame $\mathfrak{F} = \langle W, R \rangle$, and a map $v : \mathrm{Prop} \times W \to [0, 1]$, a $\mathbf{KL}\mathbf{\Pi}_{\frac{1}{2}}$-model is a pair $\mathfrak{M} = \langle \mathfrak{F}, v \rangle$. A $\mathbf{KL}\mathbf{\Pi}_{\frac{1}{2}}$-interpretation $\mathcal{I}_{\mathfrak{M}}$ induced by $\mathfrak{M}$ is defined as for $\mathbf{KL}\mathbf{\Pi}_{\frac{1}{2}}^{\mathrm{Pr}}$ with the exception that $\mathcal{I}_{\mathfrak{M}}(\mathrm{Pr}(p), w) = v(p, w)$.

**Proposition 2.** For finite $\Gamma \cup \{\chi\} \subseteq \mathcal{L}\square$, $\Gamma \models \chi$ iff $\Gamma \models_{\mathrm{Pr}} \chi$.

*Proof.* If $\Gamma \not\models_{\mathrm{Pr}} \chi$, then take any countermodel $\mathfrak{M}$ and construct a $\mathbf{KL}\mathbf{\Pi}_{\frac{1}{2}}$-model $\mathfrak{M}'$ by $v(p, w) := \mathcal{I}_{\mathfrak{M}}(\mathrm{Pr}(p), w)$. It is clear that $\mathcal{I}_{\mathfrak{M}}(\phi, w) = \mathcal{I}_{\mathfrak{M}}(\phi, w)$ for all $\phi \in \mathcal{L}\square$ and so $\Gamma \not\models \chi$. Conversely, if $\Gamma \not\models \chi$, then take any countermodel $\mathfrak{M}$ and define an SI-model $\mathfrak{M}'$ where $X = 2^{\mathrm{Prop}[\Gamma \cup \{\chi\}]}$ and where $\mu_w$ is determined by $\mu_w(\{p\}) = v(p, w)$. Moreover, let $E(p) = \{p\}$ if $p$ occurs in $\Gamma \cup \{\chi\}$ and let $E(p) = \emptyset$ otherwise. It is clear that $\mathcal{I}_{\mathfrak{M}}(\phi, w) = \mathcal{I}_{\mathfrak{M}'}(\phi, w)$ for all $\phi \in \mathcal{L}\square$ such that $\phi$ is a subformula of a formula occurring in $\Gamma \cup \{\chi\}$. Hence, by the obvious extension of Theorem 1 to local consequence, $\Gamma \not\models_{\mathrm{Pr}} \chi$. $\square$
# 4 Expressivity

Note that the truth degree of an implication $\phi \rightarrow \psi$ is inversely proportional to the truncated difference between the truth degrees of $\phi$ and $\psi$.<fnref n="3" /> Thus, $\phi \rightarrow \psi$ can be read as “The truth degree of $\phi$ is not much higher than the truth degree of $\psi$”. If the truth degree of $\phi$ is less or equal to the truth degree of $\psi$, then the truth degree of $\phi \rightarrow \psi$ is 1. If, on the other hand, the truth degree of $\phi$ is higher than the truth degree of $\psi$, then the truth degree of $\phi \rightarrow \psi$ is 1 minus the difference. Similarly, the truth degree of $\phi \leftrightarrow \psi$ is inversely proportional to the absolute difference between the values of $\phi$ and $\psi$. Consequently, we can read $\phi \leftrightarrow \psi$ as “The truth degree of $\phi$ does not differ much from the truth degree of $\psi$”.

Recall that, given a set $\mathcal{P}$ of probability measures on a Boolean algebra $X$, the lower and upper probability of $x \in X$, respectively, are defined as $\mathcal{P}_*(x) = \inf\{\mu(x) \mid \mu \in \mathcal{P}\}$ and $\mathcal{P}^*(x) = \sup\{\mu(x) \mid \mu \in \mathcal{P}\}$ (see [18] and [19, Ch. 2.3]). Lower and upper probabilities are useful for expressing qualitative uncertainty. For example, the interval $[\mathcal{P}_*(x), \mathcal{P}^*(x)]$ can be seen as putting lower and upper bounds on an agent's ignorance concerning the probability of $x$. A crucial feature of the many-valued modal framework is that lower and upper probabilities are directly expressed by formulas of the language. Given a model $\mathfrak{M}$ and a world $w$, the modal formula $\Box_a \mathrm{Pr}(\alpha)$ can be seen as a probabilistic term expressing the lower probability of $\alpha$ with respect to $\mathcal{P} = \{\mu_{w'} \mid w' \in R_a(w)\}$ since

$$ \mathcal{I}_{\mathfrak{M}}(\Box_a \mathrm{Pr}(\alpha), w) = \inf\{\mathcal{I}_{\mathfrak{M}}(\mathrm{Pr}(\alpha), w') \mid w' \in R_a(w)\} = \inf\{\mu_{w'}(E(\alpha)) \mid w' \in R_a(w)\} = \mathcal{P}_*(E(\alpha)). $$

Similarly, $\Diamond_a \mathrm{Pr}(\alpha)$ expresses the upper probability of $\alpha$. It follows that, on the epistemic interpretation of $a \in A$, the formula $\Box_a \mathrm{Pr}(\alpha) \leftrightarrow \Diamond_a \mathrm{Pr}(\alpha)$ expresses the amount of qualitative certainty of agent $a$ concerning $\alpha$. In particular, the truth degree of $\Box_a \mathrm{Pr}(\alpha) \leftrightarrow \Diamond_a \mathrm{Pr}(\alpha)$ is inversely proportional to the size of the interval $[\mathcal{P}_*(E(\alpha)), \mathcal{P}^*(E(\alpha))]$. Let us write $\mathrm{Cert}_a(\alpha)$ instead of $\Box_a \mathrm{Pr}(\alpha) \leftrightarrow \Diamond_a \mathrm{Pr}(\alpha)$. We can use Łukasiewicz implication to express comparisons between the amounts of qualitative uncertainty of two agents. For instance, $\mathrm{Cert}_a(\alpha) \rightarrow \mathrm{Cert}_b(\alpha)$ says that $a$ is not much more certain about $\alpha$ than $b$.<fnref n="4" />

**Remark 2.** Halpern and Pucella [18] introduce a propositional probabilistic logic suitable for reasoning about upper probabilities. A Halpern-Pucella model is, using our notation, a tuple $(W, S, \mathcal{P}, E)$ where $W$ is a set, $S$ is a Boolean subalgebra of $2^W$ and $E$ is a function from a set of propositional variables to $S$ – similarly as in our models – and $\mathcal{P}$ is a set of probability measures on $S$. The language Halpern and Pucella use is a variant of the non-modal linear inequality language of [10] with a primitive upper probability operator. Halpern and Pucella provide a sound and complete axiomatisation of their logic and show that the corresponding satisfiability problem is NP-complete. Marchioni [27] introduces a propositional many-valued logic for reasoning about upper probabilities in semantic structures derived from Halpern-Pucella models.<fnref n="5" /> The logic is based on Rational Łukasiewicz logic [12] and it does not contain modal operators. Marchioni provides a sound and (finitely) strongly complete axiomatisation of his logic, and he shows that the corresponding satisfiability problem is NP-complete.

Our framework can be seen as a generalisation of both [18] and [27]. Halpern-Pucella models are a KD45-like version of our K-like probabilistic models. Instead of having a fixed set of “globally” accessible states giving rise to $\mathcal{P}$, we introduce an accessibility relation which expresses the idea that each state has its own set of “locally” accessible states. This difference is well reflected in the comparison

<footnote n="3">³In particular, $\mathcal{I}_{\mathfrak{M}}(\phi \rightarrow \psi, w) = 1 - \max\{\mathcal{I}_{\mathfrak{M}}(\phi, w) - \mathcal{I}_{\mathfrak{M}}(\psi, w), 0\}$.</footnote>

<footnote n="4">⁴A similar interpretation applies, of course, if we read $a \in A$ as actions. Then $\mathrm{Cert}_a(\alpha)$ expresses the extent to which action $a$ “fixes” the probability of $\alpha$.</footnote>

<footnote n="5">⁵Instead of a set of probability measures $\mathcal{P}$, Marchioni uses an upper probability measure $\pi: S \rightarrow [0, 1]$, that is, a function that satisfies certain conditions that allow it to represent an upper probability given by a set of probability measures. The reader is referred to [18, 27] for details.</footnote>
of the computational complexity: as shown below, deduction problems in our framework are PSPACE-complete as opposed to coNP-complete in the case of [18] and [27]. Another difference is in the language we are using. Instead of a primitive upper/lower probability operator, we use a combination ♦Pr/□Pr of a modal operator and the probability operator Pr.<fnref n="6" /> The same syntactic approach to representing lower probabilities is taken by Corsi et al. [6]. Their semantics is a special case of our probabilistic models with only one equivalence accessibility relation (mono-modal S5-style probabilistic models). On the other hand, Corsi et al. [6] work with a richer language that allows for the inclusion of □ within the scope of Pr. They demonstrate that their modal probabilistic framework can formalise reasoning about probability, belief functions, and lower probabilities within a unified framework. The main results of [6] are related to complete axiomatisations, and complexity is not studied.

We can also use Łukasiewicz implication to express how actions modify the probability of certain events. For example, $\Pr(\alpha) \to \Box_a \Pr(\alpha)$ says that action *a* cannot *decrease* the probability of $\alpha$ much — the truth degree in *w* is 1 if $\mu_w(E(\alpha)) \le \inf\{\mu_{w'}(E(\alpha)) | w' \in R_a(w)\}$, that is, the probability of $\alpha$ cannot *decrease* at all, and it is 1 minus the difference otherwise. Similarly, $\Diamond_a \Pr(\alpha) \to \Pr(\alpha)$ says that *a* cannot *increase* the probability of $\alpha$ much. We can write $\text{NoDec}_a(\alpha)$ instead of $\Pr(\alpha) \to \Box_a \Pr(\alpha)$ and, as before, use formulas of the form $\text{NoDec}_a(\alpha) \to \text{NoDec}_b(\alpha)$ to express comparisons between actions *a* and *b*. Similarly for $\Diamond_a \Pr(\alpha) \to \Pr(\alpha)$ written as $\text{NoInc}_a(\alpha)$. We reiterate that these comparisons are not precise statements (true or false) but rather imprecise – that is, true to a degree.

It is well known that in the presence of the constant $\frac{1}{2}$ and the “arithmetic” operators $\bullet$ and $\to_{\Pi}$, one can define constants $\mathbf{q}$ for all rational numbers $q \in [0, 1] \cap \mathbb{Q}$ in Łukasiewicz logic. In combination with Łukasiewicz $\to$ and $\leftrightarrow$, this allows us to express comparisons with rational thresholds. For example, the formula $0.7 \to \Diamond_a \Pr(\alpha)$ read in terms of actions says that the supremum (“best case”) of the possible probabilities of $\alpha$ resulting from action *a* is not much lower than 0.7. The definable operator $\triangle$ turns imprecise statements into precise ones. For instance, $\triangle(0.7 \to \Pr(\alpha))$ has truth degree 1 if probability of $\alpha$ is at least 0.7 and has truth degree 0 otherwise. This means that we may define a restricted version of the “Markovian” modalities of [1, 22, 25] etc.: $L_q(\alpha) := \triangle(q \to \Pr(\alpha))$ is true (has truth degree 1) in states where the probability of $\alpha$ is at least $q \in [0, 1] \cap \mathbb{Q}$ and false (has truth degree 0) otherwise.<fnref n="7" /> In addition, if *a* is interpreted epistemically, then $\Box_a L_q(\alpha)$ expresses a crisp statement about epistemic attitudes towards probabilities — namely, “Agent *a* believes that the probability of $\alpha$ is at least *q*”.

We observe briefly that just as in the propositional case, constants do not change the expressivity of the language. The following statement generalises [14, Lemmas 3.3.11 and 3.3.13].

**Proposition 3.** Let $\Gamma \subseteq \mathcal{L}_{\Pr}$ be finite and $n$ be the least common denominator of the constants in $\Gamma$. Then there is $\Gamma'$ without constants s.t. $\Gamma$ is satisfiable iff $\Gamma'$ is and $\Gamma'$ is of polynomial size w.r.t. $\max(\ell[\Gamma], n)$.

*Proof.* As $\Gamma$ is finite, $n$ exists. We can express $1/n$ as follows. For fresh $\{q_1, \dots, q_n, q\} \subseteq \text{Prop}$, we set

$$ \frac{1}{n}(q) := \underbrace{(\Pr(q) \oplus \dots \oplus \Pr(q))}_{n-1 \text{ times}} \leftrightarrow \neg \Pr(q) \qquad \mathbf{m/n}(q_m) := \Pr(q_m) \leftrightarrow \underbrace{(\Pr(q) \oplus \dots \oplus \Pr(q))}_{m \text{ times}} $$

It is clear that $\mathcal{I}(\mathbf{1}/n(q), w) = 1$ iff $\mathcal{I}_{\mathfrak{M}}(\Pr(q), w) = 1/n$ and $\mathcal{I}_{\mathfrak{M}}(\mathbf{m}/n(q_m), w) = 1$ iff $\mathcal{I}(\Pr(q_m), w) = m/n$ (and $v(q) = 1/n$). Now, given $\phi \in \mathcal{L}_{\Pr}$, we define $\phi^b$ as follows:

$$ \Pr(\alpha)^b = \Pr(\alpha) \qquad \mathbf{m/n}^b = \Pr(q_m) \qquad (\Diamond\phi)^b = \Diamond\phi^b \qquad (\phi \circ \chi)^b = \phi^b \circ \chi^b \qquad (\Diamond \in \{\neg, \Delta, \Box\}, \circ \in \{\to, \to_{\Pi}, \bullet\}) $$

<footnote n="6">⁶In addition, our syntax and semantics are both multi-modal, allowing for modelling multiple agents or actions.</footnote>

<footnote n="7">⁷This is only a restricted version since $L_q$ cannot be nested in our language.</footnote>
Now let $\mathcal{d}[\Gamma] = \max\{\mathcal{d}(\phi) | \phi \in \Gamma\}$ and define

$$ \Gamma^{\flat} = \{\phi^{\flat} | \phi \in \Gamma\} \cup \{\Box^{i1}/n(q) | i \in \{0, \dots, \mathcal{d}[\Gamma]\}\} \cup \bigcup_{i=0}^{\mathcal{d}[\Gamma]} \{\Box^{i1}/n(q_m) | 1/n \text{ occurs in } \Gamma\} $$

It is clear that $\Gamma^{\flat}$ is only polynomially larger than $\Gamma$ when $\ell(\Gamma) \ge n$.

Now let $\mathfrak{M}$ be a $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\text{Pr}}$-model and $w \in \mathfrak{M}$ s.t. $\mathcal{I}_{\mathfrak{M}}(\phi, w) = 1$ for each $\phi \in \Gamma$. By Proposition 1, we may w.l.o.g. assume that $\mathfrak{M} = \langle W, R, 2^{2^{\text{Prop}[\Gamma]}}, \mu, E^C \rangle$ is an SI-model over $2^{2^{\text{Prop}[\Gamma]}}$. We define an SI-model $\mathfrak{M}^{\flat} = \langle W, R, 2^{2^{\text{Prop}[\Gamma^{\flat}]}}, \mu^{\flat}, E^{\flat} \rangle$ s.t. $\mu_w^{\flat}(E^{\flat}(\alpha)) = \mu_w(E^C(\alpha))$ for each $\alpha$ s.t. $\text{Prop}(\alpha) \cap \{q_1, \dots, q_n, q\} = \emptyset$, $\mu_w^{\flat}(E(q_m)) = \frac{m}{n}$ for every $q_m$, and $\mu_w^{\flat}(E(q)) = \frac{1}{n}$. It is now clear that $\mathcal{I}_{\mathfrak{M}^{\flat}}(\text{Prop}(q_m), w) = \frac{m}{n}$ in every $w \in \mathfrak{M}$. Thus, as values of formulas depend only on states not further than their modal depth we have $\mathcal{I}_{\mathfrak{M}}(\phi, w) = \mathcal{I}_{\mathfrak{M}^{\flat}}(\phi^{\flat}, w)$ for every $\phi \in \Gamma$. The result follows. $\square$

In [16], $\rightarrow_{\Pi}$ is used to express conditional probabilities $\text{Pr}(\alpha | \beta) := \text{Pr}(\beta) \rightarrow_{\Pi} \text{Pr}(\alpha \wedge \beta)$. It follows from this definition that $\text{Pr}(\alpha | \beta)$ has truth degree 1 if the probability of $\beta$ is 0. A many-valued probabilistic logic with primitive formulas expressing conditional probabilities was proposed in [13]. Flaminio [11] shows that reasoning about conditional probabilities can be carried out in a probabilistic logic based on an extension of Rational Łukasiewicz logic (RŁ) with the $\Delta$ operator, where the satisfiability problem is NP-complete. Our reason to base our logic on $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}$ instead of RŁ with $\Delta$ is that the former can express additional statements about probability, such as independence statements.

We now turn to linking the expressive resources of our language to the examples discussed in Section 2. Example 1 can be formalised using $L, I, S \in \text{Prop}$, expressing “light on”, “item retrieved” and “start state”, respectively. It is clear how the event function $E$ should be defined on the frame depicted in Figure 1 — for instance, $E(\neg S \wedge I) = \{e_{L \wedge I}, e_{-L \wedge I}\}$. The formula $\text{Pr}(\neg S \wedge I)$ expresses the probability of the event $E(\neg S \wedge I)$, “the robot will retrieve the correct item”, and the formula $\Box_a \text{Pr}(\neg S \wedge I)$ expresses the probability of this event after the execution of action $a$, that is, after switching the light switch. In each start state, the action $a$ has exactly one output state — $s_L$ is switched to $s_{-L}$ and vice versa. The formula $\text{Pr}(\neg S \wedge I) \rightarrow \Box_a \text{Pr}(\neg S \wedge I)$ says that switching the light switch cannot decrease the probability of the robot retrieving the correct item much. In state $s_L$, the truth degree of this formula is 0.4 since the truth degree of $\text{Pr}(\neg S \wedge I)$ in $s_L$ is 0.8 and in $s_{-L}$ it is 0.2. On the other hand, the truth degree of $\text{Pr}(\neg S \wedge I) \rightarrow \Box_a \text{Pr}(\neg S \wedge I)$ in $s_{-L}$ is 1. The formula $\text{Pr}(\neg S \wedge I) \leftrightarrow \Box_a \text{Pr}(\neg S \wedge I)$, saying that the probability of the robot retrieving the correct item is not changed much by $a$, has truth degree 0.4 in both start states $s_L$ and $s_{-L}$.

Example 3 shows that finite discrete-time Markov chains can be seen as probabilistic frames. Take a Markov chain $\mathbf{M} = \langle N, \mathfrak{p}, \mathfrak{q} \rangle$ where $N = \{1, \dots, n\}$, and consider an extension of $\mathfrak{F}_\mathbf{M}$ with an event function $E$ such that $E(\alpha_i) = \{i\}$ for $i \in N_0$ and a tuple of Boolean formulas $\alpha_i$. The probability of a path $P(i_0, \dots, i_m) = q(i_0) \cdot \prod_{j=1}^m \mathfrak{p}(i_{j-1}, i_j)$ corresponds to the truth degree of the formula

$$ \text{Pr}(i_0, \dots, i_m) := \text{Pr}(\alpha_{i_0}) \diamond_i \text{Pr}(\alpha_{i_1}) \diamond_i \dots \diamond_i \text{Pr}(\alpha_{i_{m-1}}) \dots) $$

in the state 0.<fnref n="8" /> For instance, the probability of $P(1, 2, 3)$ is the truth degree of $\text{Pr}(\alpha_1) \diamond_1 \text{Pr}(\alpha_2) \diamond_2 \text{Pr}(\alpha_3)$. As before, we can use the resources of our language to express comparisons between probabilities of various paths, e.g., $\text{Pr}(1, 2, 3) \rightarrow \text{Pr}(1, 3, 2)$ or $\Delta(\text{Pr}(1, 2, 3) \rightarrow \text{Pr}(1, 3, 2))$.

<footnote n="8">⁸Note that, for all $m > 0$, the power set of the set of all paths of length $m$ forms a finite Boolean algebra. This justifies the notation $P(i_0, \dots, i_m)$.</footnote>
In practical applications, one very often encounters finitely branching frames, that is, probabilistic frames where $R_a(w)$ is finite for all $a \in A$ and all $w \in W$. For example, take frames where $R_a$ is a partial function for all $a \in A$, representing deterministic actions.<fnref n="9" /> Another obvious example are finite frames where worlds are individuated by values of a finite set of discrete random variables. We write $|\models_{\text{Pr}}^{\text{fb}}$ and $|\models^{\text{fb}}$ to denote the entailment (satisfaction) relations over the class of finitely-branching frames in $\mathbf{KŁΠ}_{\frac{1}{2}}^{\text{Pr}}$ and $\mathbf{KŁΠ}_{\frac{1}{2}}$, respectively.

# 5 Decidability and complexity

Let us now tackle the complexity of reasoning in $\mathbf{KŁΠ}_{\frac{1}{2}}^{\text{Pr}}$. We will consider two fundamental tasks. First, *model-checking* — given a $\mathbf{KŁΠ}_{\frac{1}{2}}^{\text{Pr}}$-model $\mathfrak{M}$, a state $w \in \mathfrak{M}$, and a formula $\phi$, determine the truth degree of $\mathcal{I}_{\mathfrak{M}}(\phi, w)$. The second task is *finitary entailment* over finitely branching models — given a finite $\Gamma \cup \{\chi\}$, decide whether $\Gamma \models_{\text{Pr}}^{\text{fb}} \chi$.

As expected, model-checking can be done in polynomial time.

**Theorem 2.** Given a finite model $\mathfrak{M} = (W, R, S, \mu, E)$, $w \in W$, and $\phi \in \mathcal{L}_{\text{Pr}}$, it takes polynomial time w.r.t. $|W| + |S| + \ell(\phi)$ to determine the truth degree of $\mathcal{I}_{\mathfrak{M}}(\phi, w)$.

*Proof.* We proceed by induction on $\phi$. For a basis case of $\phi = \text{Pr}(\alpha)$, we first determine $\|\alpha\|$ which takes polynomial time w.r.t. $\ell(\phi) + |S|$. Then, using the definition of $\mu_w$, we calculate $\mu_w(\|\alpha\|)$ which also takes polynomial time. The cases of propositional connectives can be tackled by straightforward application of the induction hypothesis. Finally, to determine $v(\Box\chi, w)$, we calculate $v(\chi, w')$ in every $w' \in R(w)$, which takes polynomial time by the induction hypothesis. Then, we take the minimal among those, which gives us the result. $\square$

Let us now tackle the complexity of $\mathbf{KŁΠ}_{\frac{1}{2}}^{\text{Pr}}$-entailment over finitely-branching frames. We begin with the presentation of tableaux for $\mathbf{KŁΠ}_{\frac{1}{2}\text{fb}}$ — the logic $\mathbf{KŁΠ}_{\frac{1}{2}}$ over finitely-branching frames.

**Definition 6 (Constraints).** We fix a countable set $W = \{w, w', w_0, w_1, \dots\}$ of state labels and define:

* a labelled formula to be $w : \phi$ with $w \in W$ and $\phi \in \mathcal{L}_{\text{Pr}}$;

* a formulaic constraint as $w : \phi \triangleright i$ s.t. $w : \phi$ is a labelled formula, $\triangleright \in \{\leq, \geq\}$ and $i$ a polynomial;

* a numerical constraint as $w : i \triangleleft j$ with $w \in W$, $\triangleleft \in \{\leq, <\}$, and $i$ and $j$ polynomials.

**Definition 7** ($\mathcal{T}(\mathbf{KŁΠ}_{\frac{1}{2}\text{fb}})$ — constraint tableaux for $\mathbf{KŁΠ}_{\frac{1}{2}\text{fb}}$). A constraint tableau is a downward branching tree of formulaic constraints, numerical constraints, and relational terms of the form $wR_a w'$ ($w, w' \in W$). A branch can be extended by an application of a rule from Fig. 2. Given a tableau branch $\mathcal{B} = \mathcal{F} \cup \mathcal{N}$, we let $W_{\mathcal{B}} = \{w \mid w \in W, \text{ and } w \text{ occurs in } \mathcal{B}\}$ and set

$$ \mathcal{F} = \{w_1 : \phi_1 \triangleright i_1, \dots, w_m : \phi_m \triangleright i_m\} \quad \mathcal{N} = \{w'_1 : i'_1 \triangleright j'_1, \dots, w'_n : i'_n \triangleright j'_n, w''_1 : \frac{1}{2} \triangleright j'_1, \dots, w''_r : \frac{1}{2} \triangleright j'_r\} $$

We define $\mathcal{F}^{\|} = \{x_w : \phi \triangleright i \mid w : \phi \triangleright i \in \mathcal{F}\}$ and $\mathcal{N}^{\|} = \{x \triangleright y \mid w : (x \triangleright y) \in \mathcal{N}\}$ for every $w \in W_{\mathcal{B}}$ and set $\mathcal{B}^{\|} = \mathcal{F}^{\|} \cup \mathcal{N}^{\|}$. Furthermore, we set $\mathcal{F}^{\|} = \bigcup_{w \in \mathcal{B}} \mathcal{F}_w^{\|}$, $\mathcal{N}^{\|} = \bigcup_{w \in \mathcal{B}} \mathcal{N}_w^{\|}$, and $\mathcal{B}^{\|} = \bigcup_{w \in \mathcal{B}} \mathcal{B}_w^{\|}$.

A tableau branch $\mathcal{B}$ is called *open* if its corresponding system of inequalities $\mathcal{B}^|$ has a solution over $[0, 1]$ and is *closed* otherwise. An open branch is *complete* if its conclusion is also present on the branch for every premise of a rule on the branch. A tableau is closed when all its branches are closed.

<footnote n="9">⁹Finitely branching Kripke frames are used in the semantics of Strict Deterministic Propositional Dynamic Logic [20], for example. Finitely branching probabilistic frames provide semantics for a fragment of a probabilistic version of this logic.</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 2: Tableaux rules: $j$ is a new variable; $w'$ is fresh on the branch and $u$ is present on the branch; $w: \psi = j$ is a shorthand for $\{w: \psi \ge j, w: \psi \le j\}$.</figcaption></figure>

**Definition 8 (Realising model).** Let $\mathcal{B}$ be a complete open branch, $\mathcal{B}^\dagger$ its corresponding system of inequalities, $S_{\mathcal{B}^\dagger}$ its solution, and given a variable $x_{w:\phi}$, let $S_{\mathcal{B}^\dagger}(x_{w:\phi})$ denote its value in $S_{\mathcal{B}^\dagger}$. We say that a $K\mathcal{L}\Pi_{\frac{1}{2}}$-model $\mathfrak{M} = (W, R, v)$ realises $S_{\mathcal{B}^\dagger}$ if $W = \{w \mid w \text{ occurs on } \mathcal{B}\}$, $R_a = \{\langle w, w' \rangle \mid wR_a w' \in \mathcal{B}\}$, and $\mathcal{I}_{\mathfrak{M}}(\phi, w) = S_{\mathcal{B}^\dagger}(x_{w:\phi})$ for each $\phi$. In particular, if $w: \phi \triangleright i \in \mathcal{B}$ and $\mathcal{I}_{\mathfrak{M}}(\phi, w) = S_{\mathcal{B}^\dagger}(x_{w:\phi})$, we say that $\mathfrak{M}$ realises $w: \phi \triangleright i$. We say that $\mathfrak{M}$ realises $\mathcal{B}$ if there is some solution of $\mathcal{B}^\dagger$ that is realised by $\mathfrak{M}$.

Observe from the definition above that to construct a full countermodel, it suffices to have one complete open branch. Let us show the completeness of $\mathcal{I}(K\mathcal{L}\Pi_{\frac{1}{2}}_{fb})$. The next theorem can be proved in a standard manner.

**Theorem 3.** Let $\Gamma \cup \{\chi\} \subseteq \mathcal{L}_{Pr}$ be finite. Then $\Gamma \models^{fb} \chi$ iff the tableau beginning with $\{w: \phi \ge 1 \mid \phi \in \Gamma\} \cup \{w: \chi \le d, d < 1\}$ is closed.

*Proof.* For the sake of simplicity, we assume that our language is mono-modal. The proof can be carried out in the same manner when $|A| \ge 2$.

For the soundness part, we observe first that closed branches do not have realising models. Now, it suffices to show that if $\mathfrak{M}$ realises the premises of a rule, it also realises the conclusion. For propositional rules, this follows straightforwardly from Definition 4. Let us now consider modal rules. Assume that $\mathfrak{M}$ realises $w: \Box \phi \le i$. Then $\mathcal{I}(\Box \phi, w) \le i$ and there must be some $w' \in R(w)$ s.t. $\mathcal{I}(\phi, w') \le i$. Hence, the conclusion is also realised. The rule $\Box \ge$ can be dealt with similarly.

For the completeness part, we show that every complete open branch $\mathcal{B}$ has a realising model. Let $S_{\mathcal{B}^\dagger}$ be a solution of the system of inequalities $\mathcal{B}^\dagger$ that corresponds to $\mathcal{B}$. We construct the model $\mathfrak{M} = (W, R, v)$ as follows: $W = \{w \mid w \text{ occurs on } \mathcal{B}\}$, $R = \{\langle w, w' \rangle \mid wRw' \in \mathcal{B}\}$, $v(p, w) = S_{\mathcal{B}^\dagger}(x_{w:p})$. It remains to show that $\mathcal{I}_{\mathfrak{M}}(\chi, w) = S_{\mathcal{B}^\dagger}(x_{w:\chi})$ for every $\chi$ occurring on $\mathcal{B}$.

We proceed by induction on $\chi$. The base case of $\chi \in \text{Prop}$ holds by construction of $\mathfrak{M}$. The propositional cases can be verified by a straightforward application of the induction hypothesis. Let us now consider the case of $\chi = \Box \psi$. Assume that $w: \Box \psi \le i \in \mathcal{B}$. As $\mathcal{B}$ is complete, $\{wRw', w': \psi \le i\} \subseteq \mathcal{B}$. By the induction hypothesis, $\mathfrak{M}$ realises $w': \psi \le i$. Thus, there is $w' \in R(w)$ s.t. $\mathcal{I}_{\mathfrak{M}}(\psi, w') \le i$. It follows that $\mathcal{I}_{\mathfrak{M}}(\Box \psi, w) \le i$, as required. Now assume that $w: \Box \psi \ge i \in \mathcal{B}$. If there is no $u$ s.t. $wRu \in \mathcal{B}$,
it means that $R(w) = \emptyset$, whence $\mathcal{I}_{\mathfrak{M}}(\Box\psi, w) = 1$. Thus, $w: \Box\psi \ge i$ is realised. If there is some $u$ s.t. $wRu \in \mathcal{B}$, then for each such $u, u: \psi \ge i \in \mathcal{B}$. Again, by the induction hypothesis, all these constraints are realised, whence $\mathcal{I}_{\mathfrak{M}}(\Box\psi, w) \le i$, as required. $\square$

We are finally ready to establish the computational complexity of $|\models_{\mathrm{Pr}}^{\mathrm{fb}}$. We adapt the technique from [17] and combine it with a standard decision algorithm for $\mathbf{K}$ from [4].

**Theorem 4.** Let $\Gamma \cup \{\chi\} \subseteq \mathcal{L}_{\mathrm{Pr}}$ be finite. Then it is PSPACE-complete to decide whether $\Gamma \models_{\mathrm{Pr}}^{\mathrm{fb}} \chi$.

*Proof.* Let us begin with the PSPACE-hardness. We provide a reduction from the validity in $\mathbf{K}$, which is known to be PSPACE-complete. Namely, let $\phi$ be a formula over $\{\neg, \rightarrow, \Box\}$ and let further, $\phi^\Delta$ be the result of replacing each variable $p$ occurring in $\phi$ with $\Delta\mathrm{Pr}(p)$. Now observe that $\Delta$-formulas have values in $\{0, 1\}$ and $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}}$-connectives behave classically on $\{0, 1\}$. As $\mathbf{K}$ is complete over finitely branching frames, $\phi$ is $\mathbf{K}$-valid iff $\phi^\Delta$ is $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}^{\mathrm{Pr}}$-valid on finitely branching frames.

Let us now provide a PSPACE decision procedure. We assume that $\Xi = \Gamma \cup \{\chi\}$, that there are $r$ different probabilistic atoms in $\Xi$, and $\mathrm{Prop}[\Xi] = \{p_1, \dots, p_m\}$. Observe that tableaux for finite sets of formulas terminate since rules have the branching factor of at most 2 and decompose formulas. Consider the following set: $\mathcal{T}(\Xi) = \{w_1^0: \chi \le c, c < 1\} \cup \{w_1^0: \phi \ge 1 \mid \phi \in \Gamma\}$. By [5, Theorem 3.3], it is in PSPACE to determine whether the given branch is closed as $\mathcal{B}_w^{\Box}$'s are systems of polynomial inequalities over $\mathbb{R}$.

The algorithm works in two stages. First, we build a $\mathbf{K}\mathbf{L}\mathbf{\Pi}\frac{1}{2}$-tableau in a depth-first manner. Second, we recall that by Proposition 1, we can assume that all $\alpha$'s are evaluated on $2^{2^{\mathrm{Prop}(\phi)}}$. At this stage, we check that the values of modal atoms are coherent as a measure on $S = 2^{2^{\mathrm{Prop}[\Xi]}}$, i.e., that there is a probability measure $\mu$ s.t. $\mu_w(E(\alpha)) = x_{w: \mathrm{Pr}(\alpha)}$ for every modal atom $\mathrm{Pr}(\alpha)$ and state label $w$ in $\Xi$.

We begin by applying propositional rules to $\mathcal{T}(\Xi)$, guessing the branch if needed and checking whether the resulting system of inequalities has solutions. Once there are no formulas in $w_1^0$ with a propositional principal connective, we pick a constraint $w_1^0: \Box\psi \le i$ and apply the $\Box\le$ rule to it. This produces a new state $w_{1,1}^1$ and a relational term $w_1^0Rw_{1,1}^1$. Now we can apply rules $\Box\ge$ using this new state. In this new state, we apply propositional rules until no formulas with principal propositional connectives remain. We proceed this way until we reach a state, say $w_{1,1}^n$ generated from $w_{1,1}^{n-1}$, which does not contain modal formulas. Observe that $n \in \mathcal{O}(\ell[\Xi])$ because the length of the branch in the model is bounded by the maximal number of nested modalities in a formula of $\Xi$.

Once formulas in $w_{1,1}^n$ are decomposed into modal atoms, we have the following system of polynomial inequalities that corresponds to the current branch $\mathcal{B}$ and state $w_{1,1}^n$ ($\psi$'s are formulas in $w_{1,1}^n$):

$$x_{w_{1,1}^n}: \psi_1 \triangleright l_1' \dots x_{w_{1,1}^n}: \psi_k \triangleright l_k' \quad x_{w_{1,1}^n}: \mathrm{Pr}(\alpha_1) \triangleright l_1 \dots x_{w_{1,1}^n}: \mathrm{Pr}(\alpha_r) \triangleright l_n \quad j_1 \triangleleft j_1' \dots j_r \triangleleft j_r' \quad (\mathcal{B}_{w_{1,1}^n}^{\Box})$$

We now need to check that the values of $x_{w_{1,1}^n}: \mathrm{Pr}(\alpha)$'s are coherent as a probability measure. To do this, we consider the following system of linear inequalities for every $i \in \{1, \dots, r\}$:

$$\sum_{e \in \{0,1\}^m} u_e = 1 \qquad \sum_{e \in \{0,1\}^m} a_{i,e} \cdot u_e = x_{w_{1,1}^n}: \mathrm{Pr}(\alpha_i) \qquad (\exp \mathcal{B}_{w_{1,1}^n}^{\Box})$$

Here, the $e$ indices represent the subsets of $\mathrm{Prop}[\Xi]$, i.e., the atoms of $2^{2^{\mathrm{Prop}[\Xi]}}$: $a_{i,e} = 1$ when $e \models \alpha_i$ (this takes polynomial time to establish), and the value of $u_e$ is the measure assignment to $e$. For example, if

<footnote n="10">¹⁰Here, the upper index denotes the 'depth' of the state on the branch; the lower left index stands for the position of the state on the level; the lower right index identifies the position of the predecessor on its level.</footnote>
there are only two variables: $p$ and $q$, then $u_{01}$ corresponds to the measure of $\{q\}$ and $u_{11}$ to the measure of $\{p, q\}$. Thus, $(\exp \mathcal{B}_{w_{1,1}}^{\|})$ has solutions iff the values of $x_{w_{1,1}}:\text{Pr}(\alpha_i)$'s are coherent as a measure.

Now observe that $u_e$'s do not occur in $(\mathcal{B}_{w_{1,1}}^{\|})$ and that $(\exp \mathcal{B}_{w_{1,1}}^{\|})$ has only $r+1$ lines. Thus, even though there are $2^{\text{Pr} \text{op}[\Xi]}$ variables $u_e$, we can guess a list $L$ of $r+1$ words $e$ over $\{0, 1\}$ using [10, Lemma 2.5] and let $u_e = 0$ for each $e \notin L$. This produces the following system of inequalities.

$$ \sum_{e \in L} u_e = 1 \qquad \sum_{e \in L} a_{i,e} \cdot u_e = x_{w_{1,1}^n} : \text{Pr}(\alpha_i) \qquad (\text{poly} \mathcal{B}_{w_{1,1}}^{\|}) $$

Clearly, $(\text{poly} \mathcal{B}_{w_{1,1}}^{\|})$ is of polynomial size w.r.t. $\ell[\Xi]$ and has solutions iff $(\exp \mathcal{B}_{w_{1,1}}^{\|})$ does. We can now treat $(\text{poly} \mathcal{B}_{w_{1,1}}^{\|})$ and $(\mathcal{B}_{w_{1,1}}^{\|})$ as quantifier-free formulas of the real field theory and consider their conjunction. By [5, Theorem 3.3], it is in PSPACE to check whether it is satisfiable over $[0, 1]$. If it is unsatisfiable, there is no solution to $(\mathcal{B}_{w_{1,1}}^{\|})$ that makes the values of $x_{w_{1,1}^n} : \text{Pr}(\alpha)$'s coherent with a measure and the values of $x_{w_{1,1}^n} : \psi$'s with the semantics of $\mathbf{KL}\Pi\frac{1}{2}^{\text{Pr}}$. In this case, we close $\mathcal{B}$. Otherwise, we delete $(\mathcal{B}_{w_{1,1}^n}^{\|})$, mark the constraint $w_{1,1}^{n-1} : \square \tau \le j$ that produced $w_{1,1}^n$ as 'safe', and delete the term $w_{1,1}^{n-1} R w_{1,1}^n$. We then pick the next constraint in $w_{1,1}^{n-1}$ that can produce a new state and repeat the process. Once all constraints of the form $w_{1,1}^{n-1} : \square \tau' \le j'$ are marked safe, we guess poly $\mathcal{B}_{w_{1,1}^{n-1}}$ and consider its conjunction with $\mathcal{B}_{w_{1,1}^{n-1}}$. Note, furthermore, that if all probabilistic atoms occurring in $w_{1,1}^{n-1}$ are in the scope of $\square$, it suffices to check that $\mathcal{B}_{w_{1,1}^{n-1}}$ has solutions. We repeat the process until either $w_1^0$ is marked safe (in which case, $\Gamma \models_{\text{Pr}} \chi$) or all branches of our tableau are closed (whence, $\Gamma \models_{\text{Pr}} \chi$).

Finally, recall that the depth of the model is bounded from above by $\ell[\Xi] + 1$; moreover, each state $w$ contains only $\mathcal{B}_w^\|$ and $\text{poly} \mathcal{B}_w^\|$, whose sizes are polynomial w.r.t. $\ell[\Xi]$. Thus, we need polynomial space to execute the procedure. The result follows. $\square$

We finish the section with two brief observations. First, in Example 4, we considered multi-agent probabilistic frames. One can readily see that our language can be straightforwardly expanded to incorporate such frames by allowing probabilistic atoms of the form $\text{Pr}_a(\alpha)$ with $a \in A$. The proof of PSPACE-completeness of the resulting logic can also be adapted expectedly. Second, we were dealing with the complexity of reasoning in $\mathbf{KL}\Pi\frac{1}{2}^{\text{Pr}}$ over finitely-branching frames. Note, however, that we do not need the restriction to finitely branching frames if we consider the fragment $\mathcal{L}_{\text{add}}$ of $\mathcal{L}_{\text{Pr}}$ that contains all rational constants but does not contain $\bullet$ and $\rightarrow \Pi$. We use $\mathbf{KL}_{\mathcal{Q}}^{\text{Pr}}$ to denote the $\mathcal{L}_{\text{add}}$-fragment of $\mathbf{KL}\Pi\frac{1}{2}^{\text{Pr}}$.

**Theorem 5.** Let $\Gamma \cup \{\chi\} \subseteq \mathcal{L}_{\text{add}}$ be finite. Then, it is PSPACE-complete to decide whether $\Gamma \models_{\text{Pr}} \chi$.

*Proof sketch.* By Proposition 3, we can eliminate rational constants from $\Gamma \cup \{\chi\}$ without the use of $\bullet$ and $\rightarrow \Pi$. Thus, by [30, Lemma 4.6], the resulting logic is complete w.r.t. witnessed models. Hence, the $\mathcal{T}(\mathbf{KL}\Pi\frac{1}{2}_{\text{fb}})$-rules are sound. Now we use the same procedure as in the proof of Theorem 4. $\square$

# 6 Conclusion

Building on the work of Hájek et al. [14, 15, 16, 24], this paper investigated many-valued logics for reasoning about probability in the presence of modal notions such as knowledge, belief and action. Our main technical result, extending the contributions of [26], is that the problem of deciding local
consequence over finitely branching frames is PSPACE-complete for a rather expressive logic. Over arbitrary frames, it is PSPACE-complete for a specific fragment of the full logic.

Several interesting research problems remain to be tackled in the future. First, we would like to extend our complexity result for $KŁΠ_{1/2}^{1Pr}$ beyond finitely branching frames and the result for $KŁ_Q^{Pr}$ to stronger fragments. Interestingly enough, even for some fragments weaker than $KŁΠ_{1/2}^{1Pr}$, this would require solving some open problems in many-valued logic. For example, $KPL^{Pr}$ (the fragment without $1/2$ and $→Π$) is PSPACE-complete if first-order PL [23] is complete with respect to witnessed models. We would also like to extend our results to modal logics stronger than K. Second, we would like to compare the expressivity of our framework with the corresponding fragment of [9], especially when it comes to expressing statements about lower and upper probabilities.

## References

[1] R.J. Aumann (1999): *Interactive epistemology II: Probability*. International Journal of Game Theory 28(3), pp. 301–314, doi:10.1007/s001820050112.

[2] F. Bacchus, J.Y. Halpern & H.J. Levesque (1999): *Reasoning about noisy sensors and effectors in the situation calculus*. Artificial Intelligence 111(1-2), pp. 171–208, doi:10.1016/S0004-3702(99)00031-4.

[3] P. Baldi, P. Cintula & C. Noguera (2020): *Classical and Fuzzy Two-Layered Modal Logics for Uncertainty: Translations and Proof-Theory*. International Journal of Computational Intelligence Systems 13, pp. 988–1001, doi:10.2991/ijcis.d.200703.001.

[4] P. Blackburn, M. de Rijke & Y. Venema (2010): *Modal logic*, 4, print. with corr. edition. Cambridge tracts in theoretical computer science 53, Cambridge University Press.

[5] J. Canny (1988): *Some algebraic and geometric computations in PSPACE*. In: Proceedings of the twentieth annual ACM symposium on Theory of computing — STOC '88, ACM Press, New York, New York, USA, pp. 460–467, doi:10.1145/62212.62257.

[6] E.A. Corsi, T. Flaminio, L. Godo & H. Hosni (2023): *A modal logic for uncertainty: a completeness theorem*. In E. Miranda, I. Montes, E. Quaeghebeur & B. Vantaggi, editors: Proceedings of the Thirteenth International Symposium on Imprecise Probability: Theories and Applications, Proceedings of Machine Learning Research 215, PMLR, pp. 119–129.

[7] D. Doder & A. Perović (2020): *Probabilistic Temporal Logics*. In Z. Ognjanović, editor: Probabilistic Extensions of Various Logical Systems, Springer International Publishing, pp. 71–108, doi:10.1007/978-3-030-52954-3_3.

[8] F. Esteva, L. Godo & F. Montagna (2001): *The LΠ and LΠ_{1/2} logics: two complete fuzzy systems joining Łukasiewicz and Product Logics*. Archive for Mathematical Logic 40(1), pp. 39–67, doi:10.1007/s001530050173.

[9] R. Fagin & J.Y. Halpern (1994): *Reasoning about knowledge and probability*. Journal of the ACM 41(2), pp. 340–367, doi:10.1145/174652.174658.

[10] R. Fagin, J.Y. Halpern & N. Megiddo (1990): *A logic for reasoning about probabilities*. Information and computation 87(1–2), pp. 78–128, doi:10.1016/0890-5401(90)90060-U.

[11] Tommaso Flaminio (2007): *NP-containment for the coherence test of assessments of conditional probability: a fuzzy logical approach*. Archive for Mathematical Logic 46(3–4), pp. 301–319, doi:10.1007/s00153-007-0045-3.

[12] Brunella Gerla (2001): *Rational Łukasiewicz logic and DMV-algebras*. Neural Networks World 11, pp. 579–584.

[13] L. Godo & E. Marchioni (2006): *Coherent Conditional Probability in a Fuzzy Logic Setting*. Logic Journal of IGPL 14(3), pp. 457–481, doi:10.1093/jigpal/jz1019.
[14] P. Hájek (1998): *Metamathematics of Fuzzy Logic*. Trends in Logic 4, Springer, Dordrecht, doi:10.1007/978-94-011-5300-3.

[15] P. Hájek, L. Godo & F. Esteva (1995): *Fuzzy logic and probability*. In P. Besnard & S. Hanks, editors: *UAI'95: Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence*, Morgan Kaufmann, San Francisco, pp. 237-244, doi:10.5555/2074158.2074185.

[16] P. Hájek, L. Godo & F. Esteva (2000): *Reasoning about probability using fuzzy logic*. Neural Network World 10(5), pp. 811-824.

[17] P. Hájek & S. Tulipani (2001): *Complexity of fuzzy probability logics*. Fundamenta Informaticae 45(3), pp. 207-213, doi:10.3233/FUN-2001-45304.

[18] J. Y. Halpern & R. Pucella (2002): *A Logic for Reasoning about Upper Probabilities*. Journal of Artificial Intelligence Research 17, pp. 57-81, doi:10.1613/jair.985.

[19] J.Y. Halpern (2017): *Reasoning about uncertainty*, 2nd edition. The MIT Press, doi:10.7551/mitpress/10951.001.0001.

[20] J.Y. Halpern & J.H. Reif (1983): *The propositional dynamic logic of deterministic, well-structured programs*. Theoretical Computer Science 27(1-2), pp. 127-165, doi:10.1016/0304-3975(83)90097-x.

[21] G. Hansoul & B. Teheux (2013): *Extending Łukasiewicz Logics with a Modality: Algebraic Approach to Relational Semantics*. Studia Logica 101(3), pp. 505-545, doi:10.1007/s11225-012-9396-9.

[22] A. Heifetz & P. Mongin (2001): *Probability Logic for Type Spaces*. Games and Economic Behavior 35(1-2), pp. 31-53, doi:10.1006/game.1999.0788.

[23] R. Horčík & P. Cintula (2004): *Product Łukasiewicz Logic*. Archive for Mathematical Logic 43(4), pp. 477-503, doi:10.1007/s00153-004-0214-6.

[24] P. Hájek & D. Harmancová (1995): *Medical fuzzy expert systems and reasoning about beliefs*. In: *Artificial Intelligence in Medicine*. AIME 1995, Springer Berlin Heidelberg, pp. 403-404, doi:10.1007/3-540-60025-6_159.

[25] D. Kozen, R. Mardare & P. Panangaden (2013): *Strong Completeness for Markovian Logics*. In K. Chatterjee & J. Sgall, editors: *Mathematical Foundations of Computer Science 2013*, Lecture Notes in Computer Science 8087, Springer, Berlin, Heidelberg, pp. 655-666, doi:10.1007/978-3-642-40313-2_58.

[26] O. Majer & I. Sedlár (2025): *On Many-Valued Modal Probabilistic Logics*. In: *IEEE International Symposium on Multiple-Valued Logic (ISMVL 2025)*, pp. 26-31, doi:10.1109/ISMVL64713.2025.00014.

[27] E. Marchioni (2008): *Representing Upper Probability Measures over Rational Łukasiewicz Logic*. Mathware and Soft Computing 15(2), pp. 159-173. Available at http://eudml.org/doc/42219.

[28] Z. Ognjanović, M. Rašković & Z. Marković (2016): *Probability Logics: Probability-Based Formalization of Uncertain Reasoning*. Springer International Publishing, Cham, doi:10.1007/978-3-319-47012-2.

[29] A. Vidal (2021): *On transitive modal many-valued logics*. Fuzzy Sets and Systems 407, pp. 97-114, doi:10.1016/j.fss.2020.01.011.

[30] A. Vidal (2022): *Undecidability and non-axiomatizability of modal many-valued logics*. The Journal of Symbolic Logic 87(4), pp. 1576-1605, doi:10.1017/jsl.2022.32.

[31] C. Zhou (2007): *Complete Deductive Systems for Probability Logic with Application to Harsanyi Type Spaces*. PhD Thesis, Indiana University.