A logic to reason about likelihood

摘要

We present a logic LL which uses a modal operator L to help capture the notion of being likely. Despite the fact that likelihood is not assigned quantitative values through probabilities, LL captures many of the properties of likelihood in an intuitively appealing way. We give a possible-worlds style semantics to LL, and, using standard techniques of modal logic, we give a complete axiomatization for LL and show that satisfiability of LL formulas can be decided in exponential time. We discuss how the logic might be used in areas such as medical diagnosis, where decision making in the face of uncertainties is crucial. We conclude by using LL to give a formal proof of correctness of some aspects of a protocol for exchanging secrets.