NP-containment for the coherence test of assessments of conditional probability: a fuzzy logical approach

In this paper we investigate the problem of testing the coherence of an assessment of conditional probability following a purely logical setting. In particular we will prove that the coherence of an assessment of conditional probability χ can be characterized by means of the logical consistency of a suitable theory T _χ defined on the modal-fuzzy logic FP _k (RŁ_Δ) built up over the many-valued logic RŁ_Δ. Such modal-fuzzy logic was previously introduced in Flaminio (Lecture Notes in Computer Science, vol. 3571, 2005) in order to treat conditional probability by means of a list of simple probabilities following the well known (smart) ideas exposed by Halpern (Proceedings of the eighth conference on theoretical aspects of rationality and knowledge, pp 17–30, 2001) and by Coletti and Scozzafava (Trends Logic 15, 2002). Roughly speaking, such logic is obtained by adding to the language of RŁ_Δ a list of k modalities for “probably” and axioms reflecting the properties of simple probability measures. Moreover we prove that the satisfiability problem for modal formulas of FP _k (RŁ_Δ) is NP-complete. Finally, as main result of this paper, we prove FP _k (RŁ_Δ) in order to prove that the problem of establishing the coherence of rational assessments of conditional probability is NP-complete.      

A probabilistic extension of intuitionistic logic

We introduce a probabilistic extension of propositional intuitionistic logic. The logic allows making statements such as P_≥sα, with the intended meaning “the probability of truthfulness of α is at least s”. We describe the corresponding class of models, which are Kripke models with a naturally arising notion of probability, and give a sound and complete infinitary axiomatic system. We prove that the logic is decidable.     

A bipolar model of assertability and belief

Valuation pairs are introduced as a bipolar model of the assertability of propositions. These correspond to a pair of dual valuation functions, respectively, representing the strong property of definite assertability and the dual weaker property of acceptable assertability. In the case where there is uncertainty about the correct valuation pair for a language then a probability distribution is defined on possible valuation pairs. This results in two measures, μ⁺ giving the probability that a sentence is definitely assertable, and μ⁻ giving the probability that a sentence is acceptable to assert. It is shown that μ⁺ and μ⁻ can be determined directly from a two dimensional mass function m defined on pairs of sets of propositional variables. Certain natural properties of μ⁺ and μ⁻ are easily expressed in terms of m, and in particular we introduce certain consonance or nestedness assumptions. These capture qualitative information in the form of assertability orderings for both the propositional variables and the negated propositional variables. On the basis of these consonance assumptions we show that label semantics, intuitionistic fuzzy logic and max-min fuzzy logic can all be viewed as special cases of this bipolar model. We also show that bipolar belief measures can be interpreted within an interval-set model.     

A logical and algebraic treatment of conditional probability

This paper is devoted to a logical and algebraic treatment of conditional probability. The main ideas are the use of non-standard probabilities and of some kind of standard part function in order to deal with the case where the conditioning event has probability zero, and the use of a many-valued modal logic in order to deal probability of an event as the truth value of the sentence is probable, along the lines of Hájeks book [H98] and of [EGH96]. To this purpose, we introduce a probabilistic many-valued logic, called FP(S), which is sound and complete with respect a class of structures having a non-standard extension [0,1] of [0,1] as set of truth values. We also prove that the coherence of an assessment of conditional probabilities is equivalent to the coherence of a suitably defined theory over FP(S) whose proper axioms reflect the assessment itself.Mathematics Subject Classification (2000): 03B50, 06D35     

Probabilities of Sentences about Very Sparse Random Graphs

We consider random graphs with edge probability βn^?α, where n is the number of vertices of the graph, β > 0 is fixed, and α = 1 or α = (l + 1) /l for some fixed positive integer l. We prove that for every first-order sentence, the probability that the sentence is true for the random graph has an asymptotic limit.     

A case study in logical deconstruction: Formalizing J.D. Thompson's Organizations in Action in a multi-agent action logic

Logic is a popular word in the social sciences, but it is rarely used as a formal tool. In the past, the logical formalisms were cumbersome and difficult to apply to domains of purposeful action. Recent years, however, have seen the advance of new logics specially designed for representing actions. We present such a logic and apply it to a classical organization theory, J.D. Thompson's Organizations in Action. The working hypothesis is that formal logic draws attention to some finer points in the logical structure of a theory, points that are easily neglected in the discursive reasoning typical for the social sciences. Examining Organizations in Action we find various problems in its logical structure that should, and, as we argue, could be addressed.     

Scenario Reduction Algorithms in Stochastic Programming

We consider convex stochastic programs with an (approximate) initial probability distribution P having finite support supp P, i.e., finitely many scenarios. The behaviour of such stochastic programs is stable with respect to perturbations of P measured in terms of a Fortet-Mourier probability metric. The problem of optimal scenario reduction consists in determining a probability measure that is supported by a subset of supp P of prescribed cardinality and is closest to P in terms of such a probability metric. Two new versions of forward and backward type algorithms are presented for computing such optimally reduced probability measures approximately. Compared to earlier versions, the computational performance (accuracy, running time) of the new algorithms has been improved considerably. Numerical experience is reported for different instances of scenario trees with computable optimal lower bounds. The test examples also include a ternary scenario tree representing the weekly electrical load process in a power management model.     

A sequent calculus for logic of knowledge and past time: Completeness and decidability

We consider logic of knowledge and past time. This logic involves the discrete-time linear temporal operators next, until, weak yesterday, and since. In addition, it contains an indexed set of unary modal operators agent i knows.We consider the semantic constraint of the unique initial states for this logic. For the logic, we present a sequent calculus with a restricted cut rule. We prove the soundness and completeness of the sequent calculus presented. We prove the decidability of provability in the considered calculus as well. So, this calculus can be used as a basis for automated theorem proving. The proof method for the completeness can be used to construct complete sequent calculi with a restricted cut rule for this logic with other semantical constraints as well. Published in Lietuvos Matematikos Rinkinys, Vol. 46, No. 3, pp. 427–437, July–September, 2006.     

Bisimulations between generalized Veltman models and Veltman models

Interpretability logic is an extension of provability logic. Veltman models and generalized Veltman models are two semantics for interpretability logic. We consider a connection between Veltman semantics and generalized Veltman semantics. We prove that for a complete image‐finite generalized Veltman modelW there is a Veltman model W ′ that is bisimular to W. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Toward extended fuzzy logic—A first step

Fuzzy logic adds to bivalent logic an important capability—a capability to reason precisely with imperfect information. Imperfect information is information which in one or more respects is imprecise, uncertain, incomplete, unreliable, vague or partially true. In fuzzy logic, results of reasoning are expected to be provably valid, or p-valid for short. Extended fuzzy logic adds an equally important capability—a capability to reason imprecisely with imperfect information. This capability comes into play when precise reasoning is infeasible, excessively costly or unneeded. In extended fuzzy logic, p-validity of results is desirable but not required. What is admissible is a mode of reasoning which is fuzzily valid, or f-valid for short. Actually, much of everyday human reasoning is f-valid reasoning.f-Valid reasoning falls within the province of what may be called unprecisiated fuzzy logic, FLu. FLu is the logic which underlies what is referred to as f-geometry. In f-geometry, geometric figures are drawn by hand with a spray pen—a miniaturized spray can. In Euclidean geometry, a crisp concept, C, corresponds to a fuzzy concept, f-C, in f-geometry. f-C is referred to as an f-transform of C, with C serving as the prototype of f-C. f-C may be interpreted as the result of execution of the instructions: Draw C by hand with a spray pen. Thus, in f-geometry we have f-points, f-lines, f-triangles, f-circles, etc. In addition, we have f-transforms of higher-level concepts: f-parallel, f-similar, f-axiom, f-definition, f-theorem, etc. In f-geometry, p-valid reasoning does not apply. Basically, f-geometry may be viewed as an f-transform of Euclidean geometry.What is important to note is that f-valid reasoning based on a realistic model may be more useful than p-valid reasoning based on an unrealistic model.     

A paraconsistent extension of Sylvan’s logic

We deal with Sylvan’s logic CC_ω. It is proved that this logic is a conservative extension of positive intuitionistic logic. Moreover, a paraconsistent extension of Sylvan’s logic is constructed, which is also a conservative extension of positive intuitionistic logic and has the property of being decidable. The constructed logic, in which negation is defined via a total accessibility relation, is a natural intuitionistic analog of the modal system S5. For this logic, an axiomatization is given and the completeness theorem is proved. Supported by RFBR grant No. 06-01-00358 and by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools, project NSh-4787.2006.1. __________ Translated from Algebra i Logika, Vol. 46, No. 5, pp. 533–547, September–October, 2007.     

Statistical maps: A categorical approach

In probability theory, each random variable f can be viewed as channel through which the probability p of the original probability space is transported to the distribution p _f , a probability measure on the real Borel sets. In the realm of fuzzy probability theory, fuzzy probability measures (equivalently states) are transported via statistical maps (equivalently, fuzzy random variables, operational random variables, Markov kernels, observables). We deal with categorical aspects of the transportation of (fuzzy) probability measures on one measurable space into probability measures on another measurable spaces. A key role is played by D-posets (equivalently effect algebras) of fuzzy sets. Supported by VEGA 1/2002/06.     

The case for an interval-based representation of linguistic truth

This paper develops an interval-based approach to the concept of linguistic truth. A special-purpose interval logic is defined, and it is argued that, for many applications, this logic provides a potentially useful alternative to the conventional fuzzy logic.The key idea is to interpret the numerical truth value v(p) of a proposition p as a degree of belief in the logical certainty of p, in which case p is regarded as true, for example, if v(p) falls within a certain range, say, the interval [0.7, 1]. This leads to a logic which, although being only a special case of fuzzy logic, appears to be no less linguistically correct and at the same time offers definite advantages in terms of mathematical simplicity and computational speed.It is also shown that this same interval logic can be generalized to a lattice-based logic having the capacity to accommodate propositions p which employ fuzzy predicates of type 2.     

A simple logic for reasoning about incomplete knowledge

The semantics of modal logics for reasoning about belief or knowledge is often described in terms of accessibility relations, which is too expressive to account for mere epistemic states of an agent. This paper proposes a simple logic whose atoms express epistemic attitudes about formulae expressed in another basic propositional language, and that allows for conjunctions, disjunctions and negations of belief or knowledge statements. It allows an agent to reason about what is known about the beliefs held by another agent. This simple epistemic logic borrows its syntax and axioms from the modal logic KD. It uses only a fragment of the S5 language, which makes it a two-tiered propositional logic rather than as an extension thereof. Its semantics is given in terms of epistemic states understood as subsets of mutually exclusive propositional interpretations. Our approach offers a logical grounding to uncertainty theories like possibility theory and belief functions. In fact, we define the most basic logic for possibility theory as shown by a completeness proof that does not rely on accessibility relations.     

Prime spectra of non-commutative generalizations of MV-algebras

Non-commutative generalizations of MV-algebras were introduced by G. Georgescu and A. Iorgulesco as well as by the author; the generalizations are equivalent and are called GMV-algebras. We show that GMV-algebras can be considered as special cases of Grishin algebras. As MV-algebras are algebraic models of the Łukasiewicz logic and Grishin algebras have the analogous role for the classical bilinear logic, GMV-algebras correspond to a non-commutative logic between the above logics. Further, by A. Dvurečenskij, any GMV-algebra is isomorphic to an interval of an l-group, which in general is not commutative. This generalizes D. Mundici's representation of MV-algebras by means of intervals of abelian l-groups. In the paper (using this representation) we describe the properties of prime ideal spectra of GMV-algebras and of their factor algebras and ideals and prove that the spectrum of closed ideals of any GMV-algebra is homeomorphic to that of a completely distributive GMV-algebra. Received January 4, 2001; accepted in final form May 2, 2002.     

Inquisitive logic as an epistemic logic of knowing how

In this paper, we present an alternative interpretation of propositional inquisitive logic as an epistemic logic of knowing how. In our setting, an inquisitive logic formula α being supported by a state is formalized as knowing how to resolve α (more colloquially, knowing how α is true) holds on the S5 epistemic model corresponding to the state. Based on this epistemic interpretation, we use a dynamic epistemic logic with both know-how and know-that operators to capture the epistemic information behind the innocent-looking connectives in inquisitive logic. We show that the set of valid know-how formulas corresponds precisely to the inquisitive logic. The main result is a complete axiomatization with intuitive axioms using the full dynamic epistemic language. Moreover, we show that the know-how operator and the dynamic operator can both be eliminated without changing the expressivity over models, which is consistent with the modal translation of inquisitive logic existing in the literature. We hope our framework can give an intuitive alternative interpretation to various concepts and technical results in inquisitive logic, and also provide a powerful and flexible tool to handle both the inquisitive reasoning and declarative reasoning in an epistemic context.     

Entropy of formulas

A probability distribution can be given to the set of isomorphism classes of models with universe {1, ..., n} of a sentence in first-order logic. We study the entropy of this distribution and derive a result from the 0–1 law for first-order sentences.      

Sémantique algébrique ďun système logique basé sur un ensemble ordonné fini

In order to modelize the reasoning of an intelligent agent represented by a poset T, H. Rasiowa introduced logic systems called “Approximation Logics”. In these systems a set of constants constitutes a fundamental tool. In this papers, we consider logic systems called L′_T without this kind of constants but limited to the case where T is a finite poset. We prove a weak deduction theorem. We introduce also an algebraic semantics using Hey ting algebra with operators. To prove the completeness theorem of the L′_T system with respect to the algebraic semantics, we use the method of H. Rasiowa and R. Sikorski for first order logic. In the propositional case, a corollary allows us to assert that it is decidable to know “if a propositional formula is valid”. We study also certain relations between the L′_T logic and the intuitionistic and classical logics.     

Hypersequent calculi for intuitionistic logic with classical atoms

We discuss a propositional logic which combines classical reasoning with constructive reasoning, i.e., intuitionistic logic augmented with a class of propositional variables for which we postulate the decidability property. We call it intuitionistic logic with classical atoms. We introduce two hypersequent calculi for this logic. Our main results presented here are cut-elimination with the subformula property for the calculi. As corollaries, we show decidability, an extended form of the disjunction property, the existence of embedding into an intuitionistic modal logic and a partial form of interpolation.     

The Projective Beth Property and Interpolation in Positive and Related Logics

We look at the interplay between the projective Beth property in non-classical logics and interpolation. Previously, we proved that in positive logics as well as in superintuitionistic and modal ones, the projective Beth property PB2 follows from Craig's interpolation property and implies the restricted interpolation property IPR. Here, we show that IPR and PB2 are equivalent in positive logics, and also in extensions of the superintuitionistic logic KC and of the modal logic Grz.2. Supported by RFBR grant No. 06-01-00358, by INTAS grant No. 04-77-7080, and by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools, project NSh-2069.2003.1. __________ Translated from Algebra i Logika, Vol. 45, No. 1, pp. 85–113, January–February, 2006.