Extended Abstract: On the informal semantics of knowledge representation languages and the case of Logic Programming. (Marc Denecker)

The informal semantics of a formal language aims to explain the ``intuitive'' meaning of the logical symbols, and of the formulas and theories of the language. In the context of a KR language, it aims to express the knowledge conveyed by formulas and theories about the application domain, in a precise and systematic way.

It is a controversial concept. Informal semantics is about ``intuition'', a non-mathematical entity about which no theorems can be proven. In formal science, one often avoids to talk about such soft topics. The human interpretation of a formula may be claimed to be subjective. Or it may be claimed to be only a thought, locked up in our mind, unobservable from the outside and hence, out of reach for the methods of formal science. In view of such considerations, one may prefer to view a (declarative) formal language as a tool to encode computational problems. In that view, the question of its informal ``intuitive'' semantics seems of no scientific relevance. Strictly speaking, the meaning of negation as failure is not a scientific question here.

In this course, we will view a formal KR language as a formal study of certain types of knowledge. The question of its informal semantics then becomes the corner stone of such a study, as it relates the formal entities (the formulas) to the informal objects that they intend to represent (the knowledge). The scientific thesis of such a study is then that a formal semantics correctly formalizes the informal semantics.

The course starts with some considerations on viewing a formal language as a formal study of some forms of knowledge. The discussion is based on, a.o., Poppers ideas of formal science. We discuss the issues of subjectiveness and non-observability of the human interpretation of logic formulas and discuss experimentation and falsifiability in this context. The goal of this discussion is to derive insights needed to understand the current status of informal semantics in Logic Programming:

• A theory of informal semantics is to be defined in a compositional way. This is more challenging for non-monotonic languages and languages with expressions without truth-functional meaning (e.g., rules?).

• A formal semantics does not determine informal semantics. Formal and Informal semantics are related through the interpretation of semantic structures. If we change the interpretation of semantic structures, we change the informal semantics. This is shown in the context of first order logic (FOL) with an artificial example. It appears in Logic Programming where models are interpreted one time as Tarskian representations of states of affairs, and at other times as belief sets.

• It is often easy to set up ``experiments'' to verify if a formal semantics formalizes an informal semantics, or whether two informal semantics of the same language agree, or whether an informal semantics of a program corresponds to the actual knowledge that the program intends to represent, or how to interpret a logical symbol of the logic. (E.g., is negation meant objectively or epistemically?). Such experiments are useful instruments to bring some rigour in discussions of informal semantics.

Also several useful quality criteria emerge:

• The quality of an informal semantics depends: how general is it (how much of the formal language is covered?), can we understand it, and is it precise?

• Applicability: a theory of informal semantics is only relevant if it has explanatory power for the users of the logic: if in the relevant applications, the knowledge and the informal semantics of its formal representation coincide!

In the second part of the lecture, we apply the above ideas and instruments on Logic Programming. A brief historical overview is given on the topic of informal semantics. Many of the early papers on LP semantics took the view of LP as a programming language and tell us nothing about informal semantics and the meaning of negation as failure. But LP was also viewed as a language for querying deductive databases (leading to Datalog) and for Knowledge Representation (KR). Later, several extensions of LP were proposed to represent incomplete knowledge (Abductive Logic Programming, Extended Logic Programming leading to Answer Set Programming). Three main ideas for informal semantics were born there: the Closed World Assumption by Ray Reiter, logic programs as definitions by Keith Clark, and the (auto)epistemic/default interpretation by Michael Gelfond.

We then analyze these informal semantics using the instruments introduced above: where these informal semantics agree and disagree, how they were formalized, how to interpret semantical objects, the meaning of negation and the rule operator and which informal semantics applies in the context of concrete examples.

The last part of the lecture is devoted to definitions and the definitional view of logic programming. Definitions extend CWA but are more precise and much more general. They are not equivalent with the epistemic view and neither subsumes the other. But there are more applications for definitions than for epistemic theories. In the view of logic programs as definitions, we argue that negation is classical but the rule operator is not (which confirms what Clark suggested long ago). We recall Harel's critique on completion semantics for expressing inductive definitions, including a proof that in general, inductive definitions cannot be expressed in FO. We discuss the integration of the definitional knowledge in the classical logic paradigm as it was done in the logic FO(ID). It is considered what the declarative view of a logic program as a definition can contribute in the view of LP as a programming language, as a query language and as a KR language.