Title

Neke verovatnosne logike i njihove primene u rtačunarstvu

Creator

Ognjanović, Zoran, 1964-

Copyright date

1999

Object Links

Select license

Autorstvo 3.0 Srbija (CC BY 3.0)

License description

Dozvoljavate umnožavanje, distribuciju i javno saopštavanje dela, i prerade, ako se navede ime autora na način odredjen od strane autora ili davaoca licence, čak i u komercijalne svrhe. Ovo je najslobodnija od svih licenci. Osnovni opis Licence: http://creativecommons.org/licenses/by/3.0/rs/deed.sr_LATN Sadržaj ugovora u celini: http://creativecommons.org/licenses/by/3.0/rs/legalcode.sr-Latn

Language

Serbian

Cobiss-ID

Inventory ID

D-1101, D-1282

Theses Type

Doktorska disertacija

Other responsibilities

mentor

Rašković, Miodrag

član komisije

Mijajlović, Žarko

član komisije

Marković, Zoran

član komisije

Banković, Dragić

Academic Expertise

Prirodno-matematičke nauke

University

Univerzitet u Kragujevcu

Faculty

Prirodno-matematički fakultet

Alternative title

Some probability logics and their applications in computer sciences

Publisher

Kragujevac : [Z. Ognjanović],

Format

PDF/A (listova)

description

datum odbrane: 03.09.1999.

Abstract (en)

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 problem 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.

Authors Key words

matematičla logika, veštačka inteligencija, rezonovanje u prisustvu neizvesnosti

Authors Key words

51

Type

monograph
manuscript text - theses
Text

Abstract (en)

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 problem 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.

“Data exchange” service offers individual users metadata transfer in several different formats. Citation formats are offered for transfers in texts as for the transfer into internet pages. Citation formats include permanent links that guarantee access to cited sources. For use are commonly structured metadata schemes : Dublin Core xml and ETUB-MS xml, local adaptation of international ETD-MS scheme intended for use in academic documents.