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