PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 82(96) (2007), 141–154 DOI 102298/PIM0796141O

A LOGIC WITH HIGHER ORDER CONDITIONAL PROBABILITIES

Zoran Ognjanović and Nebojša Ikodinović

Abstract. We investigate probability logic with the conditional probability operators. This logic, denoted LCP, allows making statements such as: P_{⩾s}α, CP_{⩾s}(α | β), CP_{⩽0}(α | β) with the intended meaning “the probability of α is at least s”, “the conditional probability of α given β is at least s”, “the conditional probability of α given β at most 0”. A possible-world approach is proposed to give semantics to such formulas. Every world of a given set of worlds is equipped with a probability space and conditional probability is derived in the usual way: P (α | β) = \frac{P (α∧β)}{P (β)} , P (β) > 0, by the (unconditional) probability measure that is defined on an algebra of subsets of possible worlds. Infinitary axiomatic system for our logic which is sound and complete with respect to the mentioned class of models is given. Decidability of the presented logic is proved.

1. Introduction

The aim of probabilistic logics is clearly to capture the rules of reasoning about uncertain knowledge. One of the crucial issue in uncertain reasoning is the notion of conditional probability. Nilsson, for example, in a review [10] of work subsequent to his paper [9], argue that the conditional probability of β given α reflects more accurately what we normally mean by the certainty of the rule ’if α then β’, then the probability of α → β does. In recent times, many authors stress the importance of conditional probabilities. Some of them even suggest to consider conditional probability and conditional events as basic notions, not derived from the notion of unconditional probability. This idea is actually quite old, but some formal treatments can be found in Popper (1934, 1938) and de Finetti (1936, 1949). The latter was the first who introduced the axioms for a direct definition of conditional probability (linking it to the concept of coherence, that allows to manage also ’partial’ assessments). In [1] a rich elaboration of different issue of reasoning with the conditional probability, but only at semantical level, along the ideas proposed by de Finetti, is provided. In [6] we investigated a probability logic which enriches propositional calculus with a class of conditional probability operators of de Finetti’s type. But, allowing iterations of probability operators in that framework could produce some problems. In this paper we consider probability logic suitable for reasoning about conditional probability that is based on Kolmogorov’s approach, allowing the iterations of probabilistic operators and mixing of classical and probabilistic formulas. Let’s mention that iteration of probability and mixing classical and probabilistic formulas are not allowed in most of the logic for reasoning about conditional probabilities that may be found in the literature. Higher order absolute (unconditional) probabilities were allowed in the logic presented in [11].

2000 Mathematics Subject Classification: Primary 68T37; Secondary 68T27, 03B48, 03B70.

Supported by Ministarstvo za nauku, tehnologije i razvoj Republike Srbije, through Matematički institut, under grant 1379.

The corresponding probability language is obtained by adding probability operators of the forms P_{⩾s}, CP_{⩾s} and CP_{⩽0} to classical languages. It allows making formulas such as P_{⩾s}α, with the intended meaning “the probability of truthfulness of α is greater than or equal to s” and CP_{⩾s}(α | β), with the intended meaning “the conditional probability of truthfulness of α given β is greater than or equal to s”. The probability operators behave like modal operators. As the corresponding semantics we introduce special types of Kripke models with addition of probability measure defined over the words. It is well known that if we have a finitary axiomatization, then the compactness theorem: ’if every finite subset of a set T of formulas is satisfiable, then T is satisfiable’ follows easily from the extended completeness theorem (’every set of formulas is satisfiable’). The compactness theorem does not hold for LCP. Namely, consider an arbitrary classical formula and the set T = {¬P_{=0}φ} ∪ {P_{<1/n}φ : n is a positive integer}; although every finite subset of T is satisfiable, the set T itself is not. A consequence is that, if we want the extended completeness theorem, we cannot obtain a finitary axiomatization. Building on [8, 12, 13, 14, 17], we define a system which we show to be sound and complete, using infinitary rules of inference (i.e., rules where a conclusion has a countable set of premises).

The rest of the paper is organized as follows. In Section 2 the syntax of the logic is given. Section 3 contains a description of the corresponding Kripke-style models and satisfiability and validity notions. A formulation of a sound and complete axiomatic system can be found in Section 4. Proofs of Soundness and Completeness theorems are presented in Section 5. The decidability is discussed in Section 6. We conclude in Section 7 with some remarks about similar approaches, open questions and further investigations.

2. Syntax

The language L of LCP consists of a countable set I = {p_{1}, p_{2}, … } of propositional letters, classical connectives ∧ and ¬, a list of unary probabilistic operators P_{⩾s} and binary probability operators CP_{⩾s} for every rational number s ∈ [0, 1], CP_{⩽0} and parentheses. The set For_{LCP} of formulas is the smallest set of a finite sequences of symbols of the language L containing the propositional letters and closed under formation rules: if α and β are formulas, then ¬α, P_{⩾}α, CP_{⩾s}(α | β), CP_{⩽0}(α | β) and α ∧ β are formulas. For example, the following is a formula: CP_{⩾0.2}(p_{1} → p_{2} | P_{⩾0.12}P_{⩾0.1}p_{1}).

We use the usual abbreviations for the other classical connectives ∨, →, ↔. It is convenient the following abbreviations in our logic, for every rational number s from [0, 1]:

• P_{<s}(α) =^{def} ¬P_{⩾s}(α), • P_{⩽s}(α) =^{def} P_{⩾1−s}(¬α),
• P_{>s}(α) =^{def} ¬P_{⩽s}(α), • P_{=s}(α) =^{def} P_{⩾s}(α) ∧ P_{⩽s}(α),

and:

• CP_{<s}(α | β) =^{def} ¬CP_{⩾s}(α | β),

• CP_{⩽s}(α | β) =^{def} CP_{⩾1−s}(¬α | β), for s ≠ 0,

• CP_{>s}(α | β) =^{def} ¬CP_{⩽s}(α | β),

• CP_{=s}(α | β) =^{def} CP_{⩾s}(α | β) ∧ CP_{⩽s}(α | β).

Also, ⊥ is used to denote θ ∧¬θ, for an arbitrary formula θ. We use various conventions such as rules about deleting parenthesis and priority of logical connectives.

3. Semantics

The usual way of introducing probability is axiomatic through the measuretheoretic framework proposed by Kolmogorov.

A probability space (Ω, H, μ) consists of • a non-empty set Ω (called the sample space),

• an algebra H of subsets of Ω containing Ω and closed under complementation and finite union (but not necessarily consisting of all subsets of Ω), whose elements are called events (or measurable sets),

• a finitely additive measure μ : H → [0, 1] (called probability) satisfying: – μ(Ω) = 1,

– μ(A_{1} ∪ A_{2}) = μ(A_{1}) + μ(A_{2}), for all disjoint sets A_{1}, A_{2} ∈ H.

Given a fixed A with μ(A) > 0, probability measure μ(· | A), called conditional probability, is defined as μ(B | A) = μ(A ∩ B)/μ(A). The requirement μ(A) > 0 is essential. If μ(A) = 0, then the conditional probability remains undefined. Let’s mention that Kolmogorov’s approach has become so entrenched that it is often referred to as the definition of conditional probability.

We use the possible-worlds approach to give semantics to probabilistic formulas.

Definition 3.1. An LCP -model is a structure M = (W, v, Prob), where: • W is a non empty set of elements called worlds,

• v : W ×I → {true, false} provides for each world w ∈ W a two-valued evaluation of the propositional letters, that is v(w, p) ∈ {true, false}, for each propositional letter p ∈ I and each world w ∈ W; the truth-evaluation v(w, ·) is extended to classical propositional formulas as usual,

• Prob assigns to every w ∈ W a structure (W (w), H(w), μ(w)), such that W (w) is non empty subset of W, H(w) is an algebra of subsets of W (w) and μ(w) : H(w) → [0, 1] is a finitely additive probability measure.

Definition 3.2. The satisfiability relation ⊨_{M}⊂ W × For_{LCP} fulfills the following condition for every LCP −model M = (W, v, Prob) and every world w ∈ W:

• if φ is a propositional letter, then: w ⊨_{M} φ iff v(w, φ) = 1,

• if φ = P_{⩾s}α, then: w ⊨_{M} φ iff μ(w)({w′ ∈ W (w) : w′ ⊨_{M} α}) ⩾ s,

• if φ = CP_{⩾s}(α | β), then: w ⊨_{M} φ iff either

μ(w)({w′ ∈ W (w) : w′ ⊨_{M} β}) = 0 or μ(w)({w′ ∈ W (w) : w′ ⊨_{M} β}) > 0

and

\frac{μ(w)(\{w′ ∈ W (w) : w′ ⊨_{M} α\} ∩ \{w′ ∈ W (w) : w′ ⊨_{M} β\})}{μ(w)(\{w′ ∈ W (w) : w′ ⊨_{M} β\})} ⩾ s,

• if φ = CP_{⩽0}(α | β), then: w ⊨_{M} φ iff

μ(w)({w′ ∈ W (w) : w′ ⊨_{M} α} ∩ {w′ ∈ W (w) : w′ ⊨_{M} β}) = 0

and

μ(w)({w′ ∈ W (w) : w′ ⊨_{M} β}) > 0,

• if φ = α ∧ β, then w ⊨_{M} φ iff w ⊨_{M} α and w ⊨_{M} β,

• if φ = ¬α, then w ⊨_{M} φ iff not w ⊨_{M} α. A formula φ is satisfiable in a given LCP −model M if there is a world w from

M such that w ⊨_{M} φ. A formula φ is valid, if for every LCP −model M and each world w from M, w ⊨_{M} φ.

An LCP −model M is measurable, if for every formula φ and every world w from M, {w′ ∈ W (w) : w′ ⊨_{M} φ} ∈ H(w). We denote the class of all measurable models by LCP_{Meas}. In the sequel [φ]_{M,w} denotes {w′ ∈ W (w) : w′ ⊨_{M} φ}. We will omit the subscript M, w from [φ]_{M,w} and write [φ] if M and w are clear from the context.

If μ(w)([β]_{M,w}) > 0, we will use μ(w)([α]_{M,w} | [β]_{M,w}) to denote

\frac{μ(w)([α]_{M,w} ∩ [β]_{M,w})}{μ(w)([β]_{M,w})}.

4. Axiomatic system

The axiomatic system Ax_{LCP} for LCP contains the following axiom schemata:

(1) all For_{LCP} -instances of classical propositional tautologies,

(2) P_{⩾0}α

(3) P_{⩽r}α → P_{<s}α, s > r

(4) P_{<s}α → P_{⩽s}α

(5) (P_{⩾r}α ∧ P_{⩾s}β ∧ P_{⩾1}(¬α ∨ ¬β)) → P_{⩾min(1,r+s)}(α ∨ β)

(6) (P_{⩽r}α ∧ P_{<s}β) → P_{<r+s}(α ∨ β), r + s ⩽ 1

(7) CP_{⩾s}(α | β) ∧ P_{⩾t}β → P_{⩾s·t}(α ∧ β), t > 0,

(8) P_{=0}(α ∧ β) ∧ P_{>0}β ↔ CP_{⩽0}(α | β), and inference rules:

(1) From α and α → β infer β.

(2) From α infer P_{⩾1}α.

(3) From β → P_{⩾s− \frac{1}{k}} α, for every integer k ⩾ \frac{1}{s}, infer β → P_{⩾s}α.

(4) From γ → (P_{⩾r}β → P_{⩾r·s}(α∧β)), for every rational number r from (0, 1), infer γ → CP_{⩾s}(α | β).

The above axiomatic system is extension of the axiomatic system for the unconditional probability logic analyzed in [11, 12]. The new axioms 7 and 8 and the inference rule 4 express the standard definition of the conditional probability. The infinitary inference rule 4 links, in the way to be expected, unary and binary probability operators

Definition 4.1. A formula α is a theorem (⊢ α) if there is an at most countable sequence of formulas α_{0}, α_{1}, …, α, such that every α_{i} is an axiom or it is derived from the preceding formulas of the sequence by an inference rule. In this paper we will also use the notion of deducibility. A formula α is deducible from a set T of sentences (T ⊢ α) if there is an at most countable sequence of formulas α_{0}, α_{1}, …, α, such that every α_{i} is an axiom or a formula from the set T, or it is derived from the preceding formulas by an inference rule, with the exception that the inference rule 2 can be applied on the theorems only. A set T of sentences is consistent if there is at least one formula which is not deducible from T, otherwise T is inconsistent. A consistent set T of formulas is said to be maximal consistent if for every formula α, either α ∈ T or ¬α ∈ T.

The next theorem gives some auxiliary statements.

Theorem 4.1. (1) (Deduction theorem) If T is a set of formulas, α is a formula, and T ∪ {α} ⊢ β, then T ⊢ α → β.

(2) Let α, β, γ be formulas. Then:

(a) ⊢ P_{⩾1}(α → β) → (P_{⩾s}α → P_{⩾s}β)

(b) ⊢ P_{⩾r}α → P_{⩾s}α, r > s

(c) ⊢ CP_{⩾0}(α | β)

(d) ⊢ CP_{⩽1}(α | β)

(e) ⊢ CP_{⩾1}(α | β) → CP_{=1}(α | β)

(f) ⊢ CP_{⩾1}(α | β) → CP_{⩾s}(α | β).

(g) if ⊢ α → β, then ⊢ CP_{⩾1}(β | α),

(h) ⊢ P_{=0}β → CP_{=1}(α | β).

Proof. 1. We use the transfinite induction on the length of the proof of β from T ∪ {α}. The classical cases follow as usual.

Suppose that β = γ → CP_{⩾s}(φ | ψ) is obtained from T ∪{α} by an application of the inference rule 4. Then:

T, α ⊢ γ → (P_{⩾r}ψ → P_{⩾r·s}(α ∧ β)), for all rational r from (0, 1), T ⊢ α → (γ → (P_{⩾r}ψ → P_{⩾r·s}(α ∧ β))), for all r, by the induction hypothesis, T ⊢ (α ∧ γ) → (P_{⩾r}ψ → P_{⩾r·s}(α ∧ β)), for all r T ⊢ (α ∧ γ) → CP_{⩾s}(φ | ψ), by the inference rule 4 T ⊢ α → β.

The other cases follow similarly.

2. We prove some of the statements, while the other can be shown in a similar way [13, 15].

(4.1) By Axiom 7, we have CP_{⩾1}(α | β) ⊢ CP_{⩾1}(α | β)∧P_{⩾t}β → P_{⩾t}(α∧β), for all t > 0, i.e. CP_{⩾1}(α | β) ⊢ P_{⩾t}β → P_{⩾t}(α ∧ β), for all t. Then, by 4.1, we have P_{⩾t}(α∧β) → P_{⩾t·s}(α∧β), and hence CP_{⩾1}(α | β) ⊢ P_{⩾t}β → P_{⩾t·s}(α∧β), for all t. An application the inference rule 4 gives CP_{⩾1}(α | β) ⊢ CP_{⩾s}(α | β), i.e. ⊢ CP_{⩾1}(α | β) → CP_{⩾s}(α | β), by Deduction theorem.

(4.1) Let ⊢ α → β. Then ⊢ α → (α ∧ β) and we have ⊢ P_{⩾1}(α → (α ∧ β)), by inference rule 2. From (4.1), ⊢ P_{⩾r}α → P_{⩾r·1}(α ∧ β), for every rational r ∈ [0, 1]. Now, by inference rule 4 (s = 1), we obtain ⊢ CP_{⩾1}(β | α).

(4.1) Axioms 1–6 and Rules 1–3 imply: ⊢ P_{=0}β → P_{=0}(α ∧ β) and ⊢ P_{=0}β → ¬P_{⩾r}β, for every rational r ∈ (0, 1]. Then, for s = 1 and every r ∈ [0, 1] we have ⊢ P_{=0}β → (P_{⩾r}β → P_{⩾r}(α ∧ β)), ⊢ P_{=0}β → CP_{=1}(α | β), by Rule 4. □

5. Soundness and Completeness

Theorem 5.1 (Soundness theorem). The axiomatic system Ax_{LCP} is sound with respect to LCP_{Meas} class of models.

Proof. Soundness of our system follows from the soundness of propositional classical logics and from the properties of probability, so we give only a sketch of a straightforward but tedious proof. We can show that every instance of an axiom schemata holds in every world of every LCP_{Meas}-model, while the inference rules preserve validity.

It is easy to see that if α is an instance of a classical propositional tautologies, then for every model M and each world from M, w ⊨_{M} α.

Axioms 2–8 concern to the properties of measures and obviously holds in every world of a model. For example, let us consider Axiom 6. Let M be an LCP - model and w an arbitrary world from M. Then, from [α]_{M,w} = ([α]_{M,w} ∩ (W (w) ∖ [β]_{M,w})) ∪ [α]_{M,w}, we have μ(w)([α]_{M,w}) ⩾ μ(w)([α]_{M,w} ∩ (W (w) ∖ [β]_{M,w})), for arbitrary α and β. From [α ∨ β]_{M,w} = ([α]_{M,w} ∩ (W (w) ∖ [β]_{M,w})) ∪ [β]_{M,w} it follows that μ(w)([α∨β]_{M,w}) ⩽ μ(w)([α]_{M,w})+μ(w)([β]_{M,w}), i.e., Axiom 6 is valid. Similarly, from μ(w)([α]_{M,w} | [β]_{M,w}) · μ(w)([β]_{M,w}) = μ(w)([α]_{M,w} ∩ [β]_{M,w}), μ(w)([β]_{M,w}) > 0, follows that the axioms 7 and 8 are valid. The other axioms can be proved to be valid in a similar way.

Rule 1 is validity-preserving for the same reason as in classical logic. Consider Rule 2 and suppose that a formula α is valid. Then, for every world w from a model M = ⟨W, v, Prob⟩, [α]_{M,w} = W (w) and μ(w)(W (w)) = 1. Hence, P_{⩾1}α is valid too.

Rule 3 preserves validity because of the properties of the set of rational numbers. Let us consider Rule 4. Let M = ⟨W, v, Prob⟩ be an LCP_{Meas}-model, and

w ∈ W such that w ⊨_{M} A → (P_{⩾r}β → P_{⩾r·s}(α ∧ β)), for every rational number r ∈ [0, 1]. Let w ⊨_{M} A. If μ(w)([β]) = 0, then w ⊨_{M} CP_{⩾1}(α | β), and w ⊨_{M} A → CP_{⩾s}(α | β). Now, let μ(w)([β]) = r_{0} > 0. Since the set of premisses holds in w, and w ⊨_{M} P_{⩾r}β, for every r ⩽ r_{0}, it must be μ(w)([α] ∩ [β]) ⩾ r · s (for r ⩽ r_{0}). If μ(w)([α] | [β]) ⩾ s, we have μ(w)([α] ∩ [β]) = μ(w)([α], [β]) · μ(w)([β]) < s · r_{0}, i.e. w ⊭_{M} P_{⩾s·r_{0}}(α ∧ β). Thus, μ(w)([α] | [β]) ⩾ s, and w ⊨_{M} CP_{⩾s}(α | β). □

In order to prove the completeness theorems for our logics, we show that every consistent set of sentences is satisfiable. We describe how a consistent set T of sentences can be extended to a suitable maximal consistent set, and how a canonical model can be constructed out of such maximal consistent sets. Finally, we prove that for every world w from the canonical model, a sentence α is satisfied in w if and only if α ∈ w, and as a consequence we obtain that the set T is satisfiable.

Theorem 5.2. Every consistent set of formulas can be extended to a maximal consistent set.

Proof. Let T be a consistent set of formulas and let α_{0}, α_{1}, … be an enumeration of all formulas. We define a sequence of sets T_{i}, i = 0, 1, 2, … such that:

(1) T_{0} = T,

(2) for every i ⩾ 0, if T_{i} ∪ {α_{i}} is consistent, then T_{i+1} = T_{i} ∪ {α_{i}}; otherwise T_{i+1} = T_{i} ∪ {¬α_{i}}.

(3) if T_{i+1} is obtained by adding a formula of the form ¬(β → P_{⩾s}γ), then for some positive integer n, β → ¬P_{⩾s− \frac{1}{n}} γ, is also added to T_{i+1}, so that T_{i+1} is consistent,

(4) if T_{i+1} is obtained by adding a formula of the form ¬(β → CP_{⩾s}(γ | δ)), then for some rational number r′ ∈ (0, 1), β → ¬(P_{⩾r′}δ → P_{⩾r′·s}(γ ∧ δ)), is also added to T_{i+1}, so that T_{i+1} is consistent.

The set obtained by the step 1 is obviously consistent. The step 2 produces consistent sets, too. For if T_{i}, α_{i} ⊢ ⊥, by the deduction theorem we have T_{i} ⊢ ¬α_{i}, and since T_{i} is consistent, so it is T_{i}∪{¬α_{i}}. Consider the step 3. If T_{i}∪{β → P_{⩾s}γ} is not consistent, then the set T_{i} can be consistently extended as it is described above. Suppose that it is not the case. Then:

(1) T_{i}, ¬(β → P_{⩾s}γ), β → ¬P_{⩾s− \frac{1}{k}} γ ⊢ ⊥, for every k > \frac{1}{s}, by the hypothesis (2) T_{i}, ¬(β → P_{⩾s}γ) ⊢ ¬(β → ¬P_{⩾s− \frac{1}{k}} γ) for every k > \frac{1}{s}, by the deduction

theorem

(3) T_{i}, ¬(β → P_{⩾s}γ) ⊢ β → P_{⩾s− \frac{1}{k}} γ for every k > \frac{1}{s}, from 2., by the classical tautology ¬(α → γ) → (α → ¬γ)

(4) T_{i}, ¬(β → P_{⩾s}γ) ⊢ β → P_{⩾s}γ, from 3, by the inference rule 3
(5) T_{i} ⊢ ¬(β → P_{⩾s}γ) → β → P_{⩾s}γ, from 4, by Deduction theorem
(6) T_{i} ⊢ β → P_{⩾s}γ

Since T_{i} ∪ {β → P_{⩾s}γ} is not consistent, from T_{i} ⊢ β → P_{⩾s}γ it follows that T_{i} is not consistent, a contradiction. Thus, the step 3 produces consistent sets. Finally, consider the step 4 of the construction. If the set T_{i} ∪{¬(β → CP_{⩾s}(γ | δ))}, is not consistent, then the set T_{i} can be consistently extended as it is described above. Suppose that it is not the case. Then:

T_{i}, ¬(β → CP_{⩾s}(γ | δ)), β → ¬(P_{⩾r}δ → P_{⩾r·s}(γ ∧ δ)) ⊢ ⊥, for all r T_{i}, ¬(β → CP_{⩾s}(γ | δ)) ⊢ (β → ¬(P_{⩾r}δ → P_{⩾r·s}(γ ∧ δ))) → ⊥, for all r, T_{i}, ¬(β → CP_{⩾s}(γ | δ)) ⊢ ¬(β → ¬(P_{⩾r}δ → P_{⩾r·s}(γ ∧ δ))), for all r, by the classical tautology ¬(A → B) → (A → ¬B), T_{i}, ¬(β → CP_{⩾s}(γ | δ)) ⊢ β → (P_{⩾r}δ → P_{⩾r·s}(γ ∧ δ)), for all r, T_{i}, ¬(β → CP_{⩾s}(γ | δ)) ⊢ β → CP_{⩾s}(γ | δ), by the inference rule 4. Thus, T_{i} is not consistent, a contradiction; hence, the step 4 produces consistent

sets.

Let \overline{T} = ∪_{i}T_{i}. We can show that \overline{T} is a deductively closed set which does not contain all formulas, and as a consequence that \overline{T} is consistent. First note that for every sentence α, if T_{i} ⊢ α, then it must be α ∈ \overline{T}. For if α = α_{k}, and α ∉ \overline{T}, then T_{max{i,k}+1} ⊢ α and T_{max{i,k}+1} ⊢ ¬α, a contradiction. Let α be a sentence, and \overline{T} ⊢ α. If the deduction of α from \overline{T} is a finite sequence, then there is some i ⩾ 0 such that T_{i} ⊢ α, and α ∈ \overline{T}. Suppose that the sequence β_{1}, β_{2}, …, α of formulas which forms the proof of α from \overline{T} is countably infinite. We can show that for every i, if β_{i} is obtained by an application of an inference rule, and all the premises of β_{i} belong to \overline{T}, then β_{i} ∈ \overline{T}. Suppose β_{i} is obtained by the inference rule 1 and its premises β_{i}^{1} and β_{i}^{2} belong to \overline{T}. There must be some k such that β_{i}^{1}, β_{i}^{2} ∈ T_{k}. Since T_{k} ⊢ β_{i}, it must be β_{i} ∈ \overline{T}. If β_{i} is obtained by the inference rule 2, then β_{i} is a theorem and it must be β_{i} ∈ \overline{T}. If it is not, then α_{k} = ¬β_{i} ∈ T_{k+1}, and T_{k+1} is not consistent. Suppose that β_{i} = β → P_{⩾s}γ is obtained by the infinitary inference rule 3, and that the premises β_{i}^{1} = β → P_{⩾s− \frac{1}{k}} γ, β_{i}^{2} = β → P_{⩾s− \frac{1}{k+1}} γ, … belong to \overline{T}. If β → P_{⩾s} ∉ \overline{T}, by the step 3 of the construction of \overline{T}, there is a j > \frac{1}{s}, such that β → ¬P_{⩾s− \frac{1}{j}} γ ∈ \overline{T}. Let l = max\{k, j\}. By the axioms 2 and 3,

β → P_{⩾s− \frac{1}{l}} γ ∈ \overline{T}, and β → ¬P_{⩾s− \frac{1}{l}} γ ∈ \overline{T}. There is a set T_{m} which also contains these formulas. It follows that T_{m} ∪ \{β\} is not consistent, and β ∉ \overline{T}. There is some j such that ¬β ∈ T_{j}, T_{j} ⊢ β → ⊥, T_{j} ⊢ β → P_{⩾s}γ, and β → P_{⩾s}γ ∈ \overline{T}, a contradiction. Finally, suppose that β_{i} = γ → CP_{⩾s}(φ | ψ) is obtained by the infinitary inference rule 4, and that the premises β_{i}^{j} = γ → (P_{⩾r_{j}}ψ → P_{⩾r_{j}·s}(φ∧ψ)) belong to \overline{T} (r_{1}, r_{2}, … is an enumeration of all rational numbers from (0, 1)). If γ → CP_{⩾s}(φ | ψ) ∉ \overline{T}, by the construction of \overline{T}, there is a m, such that γ → ¬(P_{⩾r_{j}}ψ → P_{⩾r_{j}·s}(φ ∧ ψ)) ∈ \overline{T}. There is a set T_{k} which contains formulas γ → (P_{⩾r_{j}}ψ → P_{⩾r_{j}·s}(φ ∧ ψ)) and γ → ¬(P_{⩾r_{j}}ψ → P_{⩾r_{j}·s}(φ ∧ ψ)). It follows that T_{k} ∪\{γ\} is not consistent, and γ ∉ \overline{T}. Then there is l such that ¬γ ∈ T_{l}, T_{l} ⊢ γ → ⊥ and T_{l} ⊢ γ → CP_{⩾s}(φ | ψ), a contradiction. Thus, the set \overline{T} is deductively closed. It does not contain all formulas. If for some α, both α and ¬α belong to \overline{T}, then there is a set T_{i} such that α, ¬α ∈ T_{i}, a contradiction because every T_{i} is consistent. Thus, \overline{T} is consistent.

From the step 2 of the construction, it follows that the set \overline{T} is maximal. □

The next theorem summarizes some obvious properties of the maximal consistent sets of formulas.

Theorem 5.3. Let \overline{T} be a maximal consistent set of sentences. Let α and β be sentences. Then the following hold:

(1) If α ∈ \overline{T}, then ¬α ∉ \overline{T}.
(2) α ∧ β ∈ \overline{T} iff α ∈ \overline{T} and β ∈ \overline{T}.
(3) If \overline{T} ⊢ α, then α ∈ \overline{T}, i.e., \overline{T} is deductively closed.
(4) If α ∈ \overline{T} and α → β ∈ \overline{T}, then β ∈ \overline{T}.
(5) If P_{⩾s}α ∈ \overline{T}, and s ⩾ r, then P_{⩾r}α ∈ \overline{T}.

(6) If r is a rational number and r = sup\{s : P_{⩾s}α ∈ \overline{T} \}, then P_{⩾r}α ∈ \overline{T}.

Proof. As an example we prove 6. Let r = sup\{s : P_{⩾s}α ∈ \overline{T} \}. By the inference rule 3, \overline{T} ⊢ P_{⩾r}α, and, since \overline{T} is deductively closed set, P_{⩾r}α ∈ \overline{T}. The other cases follow similarly. □

Theorem 5.4 (Completeness theorem). Every consistent set T of formulas has an LCP_{Meas}-model.

Proof. Let T be a consistent set of formulas. Let the tuple M = (W, v, Prob) be defined as follows:

• W is the set of all maximal consistent sets,

• v : W × I → {true, false} is an assignment such that for every world w ∈ W and every propositional letter p ∈ I, v(w, p) = true iff p ∈ w,

• Prob(w) = (W (w), H(w), μ(w)) is a structure such that:

– W (w) = W,

– H(w) is a set of [φ] = {w ∈ W : φ ∈ w}, for every formula φ,

– μ(w)([φ]) = sup{s : P_{⩾s}(φ) ∈ w}. First we have to prove that M is an LCP_{Meas}−model. For every w ∈ W, H(w)

is an algebra of subsets of W (w). Really, for an arbitrary formula α, W (w) = [α ∨ ¬α] ∈ H(w). Also, if [α] ∈ H(w), then the complement of [α] is the set [¬α], and it belongs to H(w), and if [α_{1}], … [α_{n}] ∈ H(w), then the union [α_{1}]∪…∪[α_{n}] ∈ H(w) because [α_{1}] ∪ … ∪ [α_{n}] = [α_{1} ∨ … ∨ α_{n}]. Thus, for every w, H(w) is an algebra of subsets of W (w).

Now, we will show that the following hold for all sentences α, and β, and every w ∈ W:

(1) If [α] = [β], then μ(w)([α]) = μ(w)([β]),

(2) μ(w)([α]) ⩾ 0,
(3) μ(w)([α]) = 1 − μ(w)([¬α]), and

(4) μ(w)([α] ∪ [β]) = μ(w)([α]) + μ(w)([β]), for all sentence α and β such that

[α] ∩ [β] = ∅,

i.e. μ(w) is a finite additive probability measure on H(w).

1. It is enough to prove that [α] ⊂ [β] implies μ(w)([α]) ⩽ μ(w)([β]). From [α] ⊂ [β] it follows that ⊢ ¬(α ∧ ¬β), and ⊢ P_{⩾1}(α → β). If P_{⩾s}α ∈ w, then by Theorem 4.1. 4.1, P_{⩾s}β ∈ w, and we conclude that μ(w)([α]) ⩽ μ(w)([β]).

2. Since P_{⩾0}α is an axiom, μ(w)([α]) ⩾ 0.

3. Let r = μ(w)([α]) = sup{s : P_{⩾s}α ∈ w}. Suppose that r = 1. Then, by Theorem 5.3. 6 we have P_{⩾1}α = P_{⩽0}¬α = ¬P_{>0}¬α, and ¬P_{>0}¬α ∈ w. If for some s > 0, P_{⩾s}¬α ∈ w, by the axiom 3’ it must be P_{>0}¬α ∈ w, a contradiction. It follows that μ(w)([¬α]) = 1. Suppose that r < 1. Then, for every rational number r′ ∈ (r, 1], ¬P_{⩾r′}α = P_{<r′}α, and P_{<r′}α ∈ w. By the axiom 3, P_{⩽r′}α and P_{⩾1−r′}(¬α) belong to w. On the other hand, if there is a rational number r′′ ∈ [0, r) such that P_{⩾1−r′′}(¬α) ∈ w, then ¬P_{>r′′}α ∈ w, a contradiction. Hence, sup{s : P_{⩾s}(¬α) ∈ w} = 1 − sup{s : P_{⩾s}α ∈ w}.

4. Let [α] ∩ [β] = ∅, μ(w)([α]) = r and μ(w)([β]) = s. Since [β] ⊂ [¬α], by the step 3, we have r + s ⩽ r + (1 − r) = 1. Suppose that r > 0, and s > 0. By the well known properties of the supremum, and monotonicity (Theorem 4.1.4.1) for every rational number r′ ∈ [0, r), and every rational number s′ ∈ [0, s), we have P_{⩾r′}α, P_{⩾s′}β ∈ w. It follows by the axiom 5 that P_{⩾r′+s′}(α ∨ β) ∈ w. Hence, r + s ⩽ sup{t : P_{⩾t}(α ∨ β) ∈ w}. If r + s = 1, then the assertion trivially holds. Suppose r + s < 1. If r + s < t_{0} = sup{t : P_{⩾t}(α ∨ β) ∈ w}, then for every rational number t′ ∈ (r + s, t_{0}) we have P_{⩾t′}(α ∨ β) ∈ w. We can choose rational numbers r′′ > r and s′′ > s such that: ¬P_{⩾r′′}α, P_{<r′′}α ∈ w, ¬P_{⩾s′′}β, P_{<s′′}(β) ∈ w, and r′′ + s′′ = t′ ⩽ 1. By the axiom 4, P_{⩽r′′}α ∈ w. Using the axiom 6 we have P_{<r′′+s′′}(α ∨ β), ¬P_{⩾r′′+s′′}(α ∨ β), and ¬P_{⩾t′}(α ∨ β) ∈ w, a contradiction. Hence, μ(w)([α] ∪ [β]) = μ(w)([α]) + μ(w)([β]). Finally suppose that r = 0 or s = 0. Then we can reason as above, with the only exception that r′ = 0 or s′ = 0.

Finally, by the induction on the complexity of formulas we can prove that for every formula α, end every world w ∈ W, w ⊨_{M} α iff α ∈ w.

To begin the induction, let α be a propositional letter. Then, w ⊨_{M} α iff v(w, α) = true iff α ∈ w, by the definition of v. Let α = ¬β. Then w ⊨_{M} ¬β iff w ⊭_{M} β iff β ∉ w iff ¬β ∈ w. Let α = β ∧ γ. w ⊨_{M} β ∧ γ iff w ⊨_{M} β and w ⊨_{M} γ iff β ∈ w and γ ∈ w iff β ∧ γ ∈ w. Let α = P_{⩾s}β. If α ∈ w, sup{r : P_{⩾r}β ∈ w} = μ(w)([β]) ⩾ s, and w ⊨_{M} P_{⩾s}β. For the other direction, suppose that w ⊨_{M} P_{⩾s}β, i.e., that sup{r : P_{⩾r}β ∈ w} ⩾ s. If μ(w)([β]) > s, then, by the well known property of supremum and monotonicity of μ(w), P_{⩾s}β ∈ w. If μ(w)([β]) = s, then by Theorem 5.3. 6, P_{⩾s}β ∈ w. Now, let α = CP_{⩽0}(β | γ). If α ∈ w, then, by Axiom 8, P_{=0}(β ∧ γ), P_{>0}γ ∈ w, i.e. μ(w)([β] ∩ [γ]) = 0 and μ(w)([γ]) > 0. Then, \frac{μ(w)([β]∩[γ])}{μ(w)([γ])} = 0, and hence w ⊨_{M} CP_{⩽0}(β | γ). On the

other hand, if w ⊨_{M} CP_{⩽0}(β | γ), i.e. \frac{μ(w)([β]∩[γ])}{μ(w)([γ])} ⩽ 0, we have μ(w)([γ]) > 0 and μ(w)([β] ∩ [γ]) = 0, by Axiom 8. Then, there is t_{0} > 0 such that t_{0} = sup{t : P_{⩾t}γ ∈ w}, and hence there is rational number t′ such that P_{⩾t′}γ ∈ w. So, P_{>0}γ ∈ w. Also, it is not difficult to Prove that P_{=0}(β ∧ γ) ∈ w. Then, it follows that CP_{⩽0}(β | γ) ∈ w. At the end, let α = CP_{⩾s}(β | γ). Suppose CP_{⩾s}(β | γ) ∈ w. We have either P_{=0}γ ∈ w or P_{=0}γ ∉ w. If P_{=0}γ ∈ w, then μ(w)([γ]) = 0, and hence w ⊨_{M} CP_{⩾s}(β | γ), for all s. If P_{=0}γ ∉ w, then w ⊨_{M} CP_{⩾s}(β | γ) iff \frac{μ(w)([β]∩[γ])}{μ(w)([γ])} ⩾ s iff μ(w)([β] ∩ [γ]) ⩾ s·μ(w)([γ]). Let t_{0} = μ(w)([γ]) > 0. For every t < t_{0} we have P_{⩾t}γ ∈ w and P_{⩾t·s}(β ∧ γ) ∈ w (by Axiom 7 and CP_{⩾s}(β | γ) ∈ w). So, \frac{μ(w)([β]∩[γ])}{μ(w)([γ])} ⩾ s and w ⊨_{M} CP_{⩾s}(β | γ). Now, let w ⊨_{M} CP_{⩾s}(β | γ). If w ⊨_{M} P_{=0}γ, then P_{=0}γ ∈ w, and hence CP_{=1}(β | γ) ∈ w. Since we have CP_{=1}(β | γ) → CP_{⩾s}(β | γ) for every s, CP_{⩾s}(β | γ) ∈ w. If w ⊭_{M} P_{=0}γ, then μ(w)([γ]) = t_{0} > 0. Let μ(w)([β] ∩ [γ]) = r. Then we have \frac{r}{t_{0}} ⩾ s, i.e. r ⩾ t_{0} · s (since w ⊨_{M} CP_{⩾s}(β | γ), i.e. \frac{μ(w)([β]∩[γ])}{μ(w)([γ])} ⩾ s). For every rational number t′ ⩽ t_{0}, and every rational number r′ ⩽ r, we have P_{⩾t′}γ, P_{⩾r′}(β ∧ γ) ∈ w. Also, for every t′ > t_{0}, ¬P_{⩾t′}γ ∈ w. So, for every t′ ⩽ t_{0}, P_{⩾t′}γ → P_{⩾t′·s}(β ∧ γ) ∈ w (t′·s ⩽ t·s ⩽ r), and for every t′ > t, P_{⩾t′}γ → P_{⩾t′·s}(β∧γ) ∈ w (since ¬P_{⩾t′}γ ∈ w). Now, by the inference rule 4 we have CP_{⩾s}(β | γ) ∈ w. □

6. Decidability

We will use a kind of filtration, as well as linear programming theory to show that the logic LCP is decidable.

Theorem 6.1. If an LCP -formula α is satisfiable, then it is satisfiable in a finite LCP -model.

Proof. Let Subfor(α) be the set of all subformulas of α. Suppose α holds in a world of an LCP -model M = ⟨W, v, Prob⟩. Let ≈ be an equivalence relation over W^{2}, such that w ≈ u iff (∀θ ∈ Subfor(α)) (w ⊨_{M} θ iff u ⊨_{M} θ). The quotient set W/ ≈ is finite, W/ ≈= {C_{w_{1}}, …, C_{w_{n}}} (from every class we choose an element and denoted it by w_{i}). We consider a model M^{∗} = ⟨W^{∗}, v^{∗}, Prob^{∗}⟩, where W^{∗} = {w_{1}, …, w_{n}}, v^{∗}(w, p) = v(w, p), for every propositional letter p and Prob^{∗} is defined as follows: W^{∗}(w_{i}) = {w : (∃u ∈ C_{w})u ∈ W (w_{i})}, H^{∗}(w_{i}) is the power set of W^{∗}(w_{i}), for every u ∈ W^{∗}, μ^{∗}(w_{i})(u) = μ(w_{i})(C_{u} ∩ W (w_{i})) and for every D ∈ H^{∗}(w_{i}), μ^{∗}(w_{i})(D) = ∑_{u∈D} μ(w_{i})(C_{u} ∩ W (w_{i})). Since we have

μ^{∗}(w_{i})(W^{∗}(w_{i})) = ∑_{u∈W^{∗}(w_{i})} μ(w_{i})(C_{u} ∩ W (w)) = ∑_{Cu∈W/≈} μ(w_{i})(C_{u} ∩ W (w)) = 1,

μ^{∗}(w_{i}) is a probability. It is easy to prove that M^{∗} is an LCP −model. Now, every formula θ ∈ Subfor(α) is satisfiable in M iff it is satisfiable in M^{∗}. If θ is a propositional letter, and w ⊨_{M} θ, then w_{i} ⊨_{M} θ holds for w_{i} ∈ C_{w}. Obviously, w_{i} ⊨_{M} θ iff w_{i} ⊨_{M^{∗}} θ. If θ = θ_{1} ∧ θ_{2}, w ⊨_{M} θ and w_{i} ∈ C_{w}, then w_{i} ⊨_{M} θ iff w_{i} ⊨_{M} θ_{1} and w_{i} ⊨_{M} θ_{2} iff w_{i} ⊨_{M^{∗}} θ_{1} and w_{i} ⊨_{M^{∗}} θ_{2} iff w_{i} ⊨_{M^{∗}} θ. The case θ = ¬φ follows similarly. If θ = P_{⩾s}β and w ⊨_{M} θ, then w_{i} ⊨_{M} θ holds for w_{i} ∈ C_{w}, and

w_{i} ⊨_{M} θ ⇔ μ(w_{i})({u ∈ W (w_{i}) : u ⊨_{M} β}) ⩾ r

⇔ μ(w_{i})( ⋃_{u⊨_{M}β} C_{u} ∩ W (w_{i})) ⩾ r

⇔ μ(w_{i})( ⋃_{w_{j}⊨_{M}β} C_{w_{j}} ∩ W (w_{i})) ⩾ r

⇔ μ(w_{i})( ⋃_{w_{j}⊨_{M^{∗}} β} C_{w_{j}} ∩ W (w_{i})) ⩾ r

⇔ μ^{∗}(w_{i})({w_{j} ∈ W (w_{i}) : w_{j} ⊨_{M^{∗}} β}) ⩾ r

⇔ w_{i} ⊨_{M^{∗}} θ.

The cases θ = CP_{⩾s}(β | γ) and θ = CP_{⩽0}(β | γ) follow similarly.

The model M^{∗} from the theorem has no more then 2^{n} worlds, where n is a number of subformulas of the considered formula α. □

Theorem 6.2. The logic LCP is decidable.

Proof. Suppose that α holds in a world w of an model M = (W, v, Prob). Let

Subfor(α) = {φ_{1}, …, φ_{k}}

be the set of all subformulas of α. In each world holds exactly one conjunction of the form ±φ_{1}∧…∧±φ_{k}, called characteristic formula of that world. Let α_{1}, …, α_{2^{k}} be the list of all characteristic formulas. By Theorem 6.1, there is an LCP −model of cardinality ⩽ 2^{k} and α is satisfiable in at least one world from the model. For every natural number l ⩽ 2^{k}, we consider models which have l worlds. In each of these worlds holds exactly one characteristic formula. So, for every l we consider all sets containing l characteristic formulas, which are propositional consistent and at least one contains α. For every such choice and each world w_{i} (i.e. the corresponding characteristic formula α_{i}) let X_{r_{1}}β_{r_{1}}, …, X_{r_{p}}β_{r_{p}}, Y_{s_{1}}(γ_{1} | δ_{1}),…, Y_{s_{q}}(γ_{q} | δ_{q}), CP_{⩽0}(η_{1} | θ_{1}), …, CP_{⩽0}(η_{t} | θ_{t}), p+q +t ⩽ k, be an enumeration of all probability formulas which appear as conjuncts in α_{i}, where X_{r} is a probability operator from the set {P_{⩾r}, P_{<r}} and Y_{s} is a probability operator from the set {CP_{⩾s}, CP_{<s}}. We consider the following systems of linear equalities and inequalities with unknowns x_{j}^{i} (denoting μ(w_{i})(w_{j})), i = 0, 1, …, l, j = 1, 2, …, l (we use expression of the form φ ∈ α_{i} to denote that the formula φ appears as a conjunct in α_{i}):

∑_{j=1}^{l} x_{j}^{i} = 1; x_{j}^{i} ⩾ 0 (i = 1, …, l),

∑_{j:β∈α_{j}} x_{j}^{i} ⩾ r_{k}, if P_{⩾r_{k}}β ∈ α_{i}; ∑_{j:β∈α_{j}} x_{j}^{i} < r_{k}, if P_{<r_{k}}β ∈ α_{i}; ∑_{j:γ∧δ∈α_{j}} x_{j}^{i} ⩾ s ∑_{j:γ∈α_{j}} x_{j}^{i} and ∑_{j:γ∈α_{j}} x_{j}^{i} > 0, or ∑_{j:γ∈α_{j}} x_{j}^{i} = 0, if CP_{⩾s}(γ | δ) ∈ α_{i}; ∑_{j:γ∧δ∈α_{j}} x_{j}^{i} < s ∑_{j:γ∈α_{j}} x_{j}^{i} and ∑_{j:γ∈α_{j}} x_{j}^{i} > 0, if CP_{<s}(γ | δ) ∈ α_{i}; ∑_{j:η∧θ∈α_{j}} x_{j}^{i} = 0, ∑_{j:θ∈α_{j}} x_{j}^{i} > 0, if CP_{⩽0}(η | θ) ∈ α_{i}.

Since the problem of satisfiability of α is reduced to the linear system solving problem, the LCP is decidable. □

7. Conclusions

In this paper we have presented a probability logic which is suitable for reasoning about higher-order conditional probability in the sense of Kolmogorov. It might be applied, for example, to consider Miller’s principle, a well-known principle relating higher order probabilities. Among a number of variants of Miller’s principle, one of most interesting can be expressed in LCP by the formula CP_{⩾s}(φ | P_{⩾s}φ). Since Miller’s principle is not sound with respect to the class of LCP -models, it would be interesting to characterize structures satisfying it.

There are some papers that consider conditional probabilities from the logical point. Hawthorne [4] described a range of nonmonotonic conditional that behave like conditional probability functions at various levels of probabilistic supports. These conditional were defined as semantic relation on an object language for propositional logic. In [5] he extended the semantics of the most prominent family of these nonmonotonic conditionals to a language for predicate logic. In [2] conditional probability is defined syntactically. However, a complicated machinery of real closed fields is needed to obtain the corresponding sound and complete axiomatization. In [16, 17] a logic, which contains several types of probabilistic operators (including operators of the form “the conditional probability of α given β is s), is defined. The range of the probability functions is taken to be the unit interval of a recursive nonarchimedean field. Thus, it is possible to define another probabilistic operator with the intended meaning “probabilities of α ∧ β and β are almost the same” which may be used to model default reasoning. In [3] a treatment of nonstandard conditional probability by means of fuzzy logic is given. Using de Finetti’s approaches to conditional probability, a fuzzy modal logic is introduced in [7], such that for each pair of classical propositional formulas α and β, the probability of the conditional event “α given β” is taken as the truth-value of the (fuzzy) modal proposition P (α | β). One of the interesting problems might be to find axiomatization of the logic with higher order conditional probability operators of de Finetti’s type. Namely, allowing iterations of probability operators can help us to formalize uncertainty of probabilities. Another direction for further research might be extending our logic to corresponding first order logics. All these formalizations can be seen as useful tool in modelling and understanding real-world problems.

References

[1] S. Coletti, R. Scozzafava, Probabilistic logic in a coherent setting, Kluwer, Dordrecht, 2002.

[2] R. Fagin, J. Halpern, N. Megiddo, A logic for reasoning about probabilities, Information and Computation 87:1/2 (1990), 78–128.

[3] T. Flaminio, F. Montagna, A logical and algebraic treatment of conditional probability; in: L. A. Zadeh (ed.) Proceedings of IPMU ’04, Perugia, Italy, 2004, 493–500.

[4] J. Hawthorne, On the logic of nonmonotonic conditionals and conditional probabilities, J. Philos. Logic 25:1 (v), 185–218.

[5] J. Hawthorne, On the logic of nonmonotonic conditionals and conditional probabilities: Predicate logic, J. Philos. Logic 27:1 (1998), 1–34.

[6] N. Ikodinović, Z. Ognjanović, A logic with coherent conditional probabilities, Proceedings of the 8th European Conference Symbolic and Quantitative Approaches to Reasoning with Uncertainty ECSQARU-2005, Barcelona, Spain, July 6-9, 2005 editor Luis Godo, Lecture Notes in Computer Science Vol. 3571 726–736, 2005.

[7] E. Marchioni, L. Godo, A Logic for Reasoning about Coherent Conditional Probability: A Modal Fuzzy Logic Approach, JELIA 2004: 213-225.

[8] Z. Marković, Z. Ognjanović, M. Rašković, A Probabilistic Extension of Intuitionistic Logic, Math. Logic Quart. 49:5 (2003), 415–424.

[9] N. Nilsson, Probabilistic logic, Artificial Inteligence 28 (1986), 71–87.

[10] N. Nilsson, Probabilistic logic revised, Artificial inteligence 59 (1993), 39–42.

[11] Z. Ognjanović, M. Rašković, A logic with higher order probabilities, Publ. Inst. Math. Nouv. Sér. 60(74) (1996), 1–4.

[12] Z. Ognjanović, M. Rašković, Some probability logics with new types of probability operators, J. Logic Comput. 9:2 (1999), 181–195.

[13] Z. Ognjanović, M. Rašković, Some first order probability logics, Theoret. Comput. Sci. 247:1-2 (2000), 191–212.

[14] M. Rašković, Classical logic with some probability operators, Publ. Inst. Math. Nouv. Sér. 53(67) (1993), 1–3.

[15] M. Rašković, Z. Ognjanović, A first order probability logic – LP_{Q}, Publ. Inst. Math. Nouv. Sér. 65(79) (1999), 1–7.

[16] M. Rašković, Z. Ognjanović, Z. Marković, A probabilistic Approach to Default Reasoning, 10th International Workshop on Non-Monotonic Reasoning NMR2004, Westin Whistler, Canada, June 6-8, 335–341, 2004.

[17] M. Rašković, Z. Ognjanović, Z. Marković, A Logic with Conditional Probabilities, 9th Euroean conference JELIA’04 Logics in Artificial Inteligence, Lecture notes in artificial inteligence (LNCS/LNAI) 3229, 226–238, 2004.

Matematički institut Kneza Mihaila 36 11000 Beograd, p.p. 367 Serbia

zorano@mi.sanu.ac.yu

Prirodno-matematički fakultet 34000 Kragujevac Serbia

ikodinovic@kg.ac.yu