Neke verovatnosne logike i njihove primene u rtačunarstvu
Some probability logics and their applications in computer sciences
Committee membersMijajlović, Žarko
MetadataShow full item record
Part1. Subjective and objective interpretations of probability are described. The organization of the text is given. Part2. Some propositional probability logics are introduced. Their languages, models, satisfiability relations, and (in)finitary axiomatic systems are given. In this paper the terms finitary and infinitary concern meta language only. Object languages are countable, formulas are finite, while only proofs are allowed to be infinite. Basically, the considered languages are obtained by adding unary probabilistic operators of the form P≥s with the intended meaning “the probability is greater than s”. A Kripke-like possible-world approach to interpret probabilityformulas such that they remain either true or false is proposed. Since the compactness theorem does not hold for some of the considered logics, infinitary axiomatic systems allows proving the corresponding extended completeness theorems. Decidability of the logics is proved using a reduction of the satisfiability probl...em to the linear programming problem. Part 3. In this part some first order probability logics are considered. In a paper of Abadi and Halpern is proved that there is no recursive axiomatization of these logics, so the presented approach involving infinitary inference rules is the only way to achieve any complete axiomatization. Part 4. New types of probability operators of the form QF, where F is a recursive rational subset of [0, 1] are introduced. A formula QFA is satisfied in a probability model if the measure of the set of worlds that satisfy A is in F. The new operators are suitable for describing events in discrete sample spaces. It is show that the new operators are not definable in languages of probability logics that have been used so far. Part 5. A propositional and a first-order logic for reasoning about discrete linear time and finitely additive probability are given. The languages of these logics allow formulas that say ‘sometime in the future, A holds with probability at least s’. Sound and complete infinitary axiomatizations for the logics are provided. Part 6. In this part a probabilistic extension of modal logic is investigated. It is showed that those logics are closely related, but that modal necessity (denoted by □) is a stronger notion than probability necessity (probability one, P≥1). An example of probability version of Barcan-formula which assures this conclusion is given. Part 7. Decidability of the considered logics is shown by reducing the corresponding satisfiability problem to the linear programming problem. Two automated theorem provers based on that idea are described. Appendix A. This appendix contains the main definitions and formulations of some statements related to probability, Loeb’measure, infinitary logics, and computation complexity. Appendix B. This appendix describes some other approaches in the field: work of Keisler concerning the probabilistic quantifiers, and some other papers about probabilistic operators written by Nilsson, Fagin, Halpern etc.