SOPML: reasoning about all possible knowledge

18^th May 2018, 11:00
Louwe Kuijer
University of Liverpool

Abstract

Epistemic logic (EL) allows us to reason about what an agent knows. But statements about knowledge can only be represented in EL if they are about a specific piece of knowledge. For example, let p mean "it is raining". Then "Alice believes that Bob correctly believes that it is raining" can be represented as ?a(p??bp), and EL gives us exact conditions for determining when the sentence is true.

But EL cannot represent statements about an agents total body of knowledge. For example, it cannot express sentences like "Alice believes that Bob holds at least one correct belief" or "Alice believes everything that is believed by both Bob and Claire". Second Order Propositional Modal Logic (SOPML) is an extension of EL that does allow us to express such things. Unfortunately, it comes at a heavy price in computational complexity.

In this talk I will introduce SOPML, show how it can express sentences like the ones described above, and explain why its decisions problems are hard.