Autoepistemic logic

Short description: Formal logic for the representation and reasoning of knowledge about knowledge

The autoepistemic logic is a formal logic for the representation and reasoning of knowledge about knowledge. While propositional logic can only express facts, autoepistemic logic can express knowledge and lack of knowledge about facts.

The stable model semantics, which is used to give a semantics to logic programming with negation as failure, can be seen as a simplified form of autoepistemic logic.

Syntax

The syntax of autoepistemic logic extends that of propositional logic by a modal operator [math]\displaystyle{ \Box }[/math] indicating knowledge: if [math]\displaystyle{ F }[/math] is a formula, [math]\displaystyle{ \Box F }[/math] indicates that [math]\displaystyle{ F }[/math] is known. As a result, [math]\displaystyle{ \Box \neg F }[/math] indicates that [math]\displaystyle{ \neg F }[/math] is known and [math]\displaystyle{ \neg \Box F }[/math] indicates that [math]\displaystyle{ F }[/math] is not known.

This syntax is used for allowing reasoning based on knowledge of facts. For example, [math]\displaystyle{ \neg \Box F \rightarrow \neg F }[/math] means that [math]\displaystyle{ F }[/math] is assumed false if it is not known to be true. This is a form of negation as failure.

Semantics

The semantics of autoepistemic logic is based on the expansions of a theory, which have a role similar to models in propositional logic. While a propositional model specifies which atomic propositions are true or false, an expansion specifies which formulae [math]\displaystyle{ \Box F }[/math] are true and which ones are false. In particular, the expansions of an autoepistemic formula [math]\displaystyle{ T }[/math] make this determination for every subformula [math]\displaystyle{ \Box F }[/math] contained in [math]\displaystyle{ T }[/math]. This determination allows [math]\displaystyle{ T }[/math] to be treated as a propositional formula, as all its subformulae containing [math]\displaystyle{ \Box }[/math] are either true or false. In particular, checking whether [math]\displaystyle{ T }[/math] entails [math]\displaystyle{ F }[/math] in this condition can be done using the rules of the propositional calculus. In order for a specification to be an expansion, it must be that a subformula [math]\displaystyle{ F }[/math] is entailed if and only if [math]\displaystyle{ \Box F }[/math] has been assigned the value true.

In terms of possible world semantics, an expansion of [math]\displaystyle{ T }[/math] consists of an S5 model of [math]\displaystyle{ T }[/math] in which the possible worlds consist only of worlds where [math]\displaystyle{ T }[/math] is true. [The possible worlds need not contain all such consistent worlds; this corresponds to the fact that modal propositions are assigned truth values before checking derivability of the ordinary propositions.] Thus, autoepistemic logic extends S5; the extension is proper, since [math]\displaystyle{ \neg \Box p }[/math] and [math]\displaystyle{ \neg \Box \neg p }[/math] are tautologies of autoepistemic logic, but not of S5.

For example, in the formula [math]\displaystyle{ T = \Box x \rightarrow x }[/math], there is only a single “boxed subformula”, which is [math]\displaystyle{ \Box x }[/math]. Therefore, there are only two candidate expansions, assuming [math]\displaystyle{ \Box x }[/math] is true or false, respectively. The check for them being actual expansions is as follows.

[math]\displaystyle{ \Box x }[/math] is false : with this assumption, [math]\displaystyle{ T }[/math] becomes tautological, as [math]\displaystyle{ \Box x \rightarrow x }[/math] is equivalent to [math]\displaystyle{ \neg \Box x \vee x }[/math], and [math]\displaystyle{ \neg \Box x }[/math] is assumed true; therefore, [math]\displaystyle{ x }[/math] is not entailed. This result confirms the assumption implicit in [math]\displaystyle{ \Box x }[/math] being false, that is, that [math]\displaystyle{ x }[/math] is not currently known. Therefore, the assumption that [math]\displaystyle{ \Box x }[/math] is false is an expansion.

[math]\displaystyle{ \Box x }[/math] is true : together with this assumption, [math]\displaystyle{ T }[/math] entails [math]\displaystyle{ x }[/math]; therefore, the initial assumption that is implicit in [math]\displaystyle{ \Box x }[/math] being true, i.e., that [math]\displaystyle{ x }[/math] is known to be true, is satisfied. As a result, this is another expansion.

The formula [math]\displaystyle{ T }[/math] has therefore two expansions, one in which [math]\displaystyle{ x }[/math] is not known and one in which [math]\displaystyle{ x }[/math] is known. The second one has been regarded as unintuitive, as the initial assumption that [math]\displaystyle{ \Box x }[/math] is true is the only reason why [math]\displaystyle{ x }[/math] is true, which confirms the assumption. In other words, this is a self-supporting assumption. A logic allowing such a self-support of beliefs is called not strongly grounded to differentiate them from strongly grounded logics, in which self-support is not possible. Strongly grounded variants of autoepistemic logic exist.

Generalizations

In uncertain inference, the known/unknown duality of truth values is replaced by a degree of certainty of a fact or deduction; certainty may vary from 0 (completely uncertain/unknown) to 1 (certain/known). In probabilistic logic networks, truth values are also given a probabilistic interpretation (i.e. truth values may be uncertain, and, even if almost certain, they may still be "probably" true (or false).)

See also

• Non-monotonic logic
• Modal logic

References

• Gottlob, G. (July 1995). "Translating default logic into standard autoepistemic logic". Journal of the ACM 42 (4): 711–740. doi:10.1145/210332.210334. 
• Janhunen, T. (1998). "On the intertranslatability of autoepistemic, default and priority logics". in Dix, Jürgen; del Cerro, Luís Fariñas; Furbach, Ulrich. Logics in Artificial Intelligence: European Workshop, JELIA '98, Dagstuhl, Germany, October 12–15, 1998 : Proceedings. Lecture Notes in Computer Science: Lecture notes in artificial intelligence. Springer. pp. 216–232. ISBN 3540495452. https://archive.org/details/springer_10.1007-3-540-49545-2. 
• Marek, W.; Truszczyński, M. (July 1991). "Autoepistemic logic". Journal of the ACM 38 (3): 588–618. doi:10.1145/116825.116836. 
• Moore, R.C. (January 1985). "Semantical considerations on nonmonotonic logic". Artificial Intelligence 25: 75–94. doi:10.1016/0004-3702(85)90042-6. 
• Niemelä, I. (1988). "Decision procedure for autoepistemic logic". in Lusk, Ewing; Overbeek, Ross. 9th International Conference on Automated Deduction: Argonne, Illinois, USA, May 23-26, 1988. Proceedings. Lecture Notes in Computer Science. 310. Springer. pp. 675–684. ISBN 978-3-540-19343-2. https://books.google.com/books?id=xd57Kjl60q0C&pg=PA675.