Asymptotic Conditional Probability in Modal Logic: A Probabilistic Reconstruction of Nonmonotonic Logic

摘要

We analyze the asymptotic conditional validity of modal formulas, i.e., the probability that a formula ψ is valid in the finite Kripke structures in which a given modal formula Φ is valid, when the size of these Kripke structures grows to infinity. We characterize the formulasψthat are almost surely valid (i.e., with probability 1) in case Φ is a flat, S5-consistent formula, and show that these formulas ψ are exactly those which follow fromΦaccording to the nonmonotonic modal logic S5{sub}G. Our results provide - for the first time - a probabilistic semantics to a well-known nonmonotonic modal logic, establishing a new bridge between nonmonotonic and probabilistic reasoning, and give a computational account of the asymptotic conditional validity problem in Kripke structures.