On the Logical Content of Knowledge Bases

1 Introduction

The standard treatment of knowledge in logic is modal: one introduces an operator $K$ such that $K\phi$ expresses that $\phi$ is known. Systems axiomatizing $K$ are known as epistemic logics. This framework has proved fruitful, enabling the analysis of common knowledge and multi-agent reasoning, and supplying formal methods for AI, game theory, economics, distributed computing, and natural-language semantics. Philosophical work in this tradition typically concerns the status of principles such as self-reflection ($K\phi \to KK\phi$), rather than the epistemic content of formulae themselves. In this sense, such systems are best viewed as accounts of knowability rather than of knowledge proper.

By contrast, we argue that knowledge should be taken as conceptually prior to logic. By this we mean that we might begin with a concept of knowledge and determine a logic from it. This is the process typically used in machine intelligence. For example, it is the process used in the traditional approach to AI known as logic programming (LP). This pragmatic approach to knowledge and reasoning motivates an alternative understanding of 'epistemic' logic that offers a deeper theoretical understanding of how logic can emerge from knowledge. The logics we derive according to this plan are not epistemic logics in the traditional sense, but rather logics whose semantics is given in terms of 'knowledge' (rather than, say, possible worlds).

We begin by introducing a primitive notion of a knowledge base $\mathcal{B}$: a structure in which items of information are directly connected. We then define logical signs depending on how one interprets its logical content. To illustrate, consider conjunction: what should it mean to say that '$\phi$ and $\psi$' holds for $\mathcal{B}$? Intuitively, it requires that both $\phi$ and $\psi$ are independently known by $\mathcal{B}$. This case is straightforward, perhaps even trivial. More interesting is the conditional: what should it mean to assert that 'if $\phi$, then $\psi$'? Intuitively, this says that $\psi$ is supported by $\mathcal{B}$ whenever $\phi$ is. Taken at face value this collapses into vacuity; to properly represent the hypothetical force of the if-then statement we consider extensions $\mathcal{C}$ of $\mathcal{B}$ such that $\psi$ is supported in them whenever $\phi$ is.

To make this analysis precise, we proceed relative to a simple account of knowledge as an atomic system: a collection of atomic propositions structured by some inferential connections. To know 'All humans are mortal' is to have in mind the inferential connection from '$x$ is a human' to '$x$ is mortal' as $x$ ranges over the names of all individuals. (In Prolog this is captured by a program clause $M(x) \mathbin{:\!-} H(x)$.) One might object that these inferential connections already presuppose some form of logic, since they are deductive in character. Importantly, though, no logical signs are in play here: none have yet been defined. The horizontal bar represents deduction at a meta-theoretic level. Our aim is to define the logical operators—implication, conjunction, disjunction, and negation—by appeal to the logical content encoded in these knowledge bases. This strategy places us within the tradition of proof-theoretic semantics and closely follows Dummett's programme: the meaning of a logical sign is fixed not by pointing to an external model, but by the inferential role the sign plays in reasoning.

2 Knowledge bases as atomic systems

An atomic system records an agent's commitments concerning the inferential relations between atomic sentences. These are pre-logical in the sense that they contain no logical operators. Formally, atomic systems are sets of atomic rules—inferential relations represented as natural deduction rules in the sense of Gentzen, generalized by Schroeder-Heister. We assume denumerably many atomic propositions $\mathbb{A}$.

An atomic system is a set of atomic rules. Commitment to the premisses entails commitment to the conclusion; we formalise this by a derivability judgement $\Gamma \vdash_{\mathcal{A}} C$, which holds iff there is an $\mathcal{A}$-derivation from $\Gamma$ to $C$. For those familiar with natural deduction after Gentzen, second-level rules (which include zeroth- and first-level rules) are familiar; third-level rules and beyond are much less common.

Not every form of atomic system need be admitted, corresponding to different conceptions of knowledge. A basis $\mathfrak{B}$ is a set of atomic systems; once fixed, we work relative to its bases and to a notion of base-extension that respects it. We consider in particular $\mathfrak{B}_1$ (zeroth- or first-level), $\mathfrak{B}_2$ (zeroth-, first-, or second-level), and $\mathfrak{B}_\omega$ (all atomic systems). In fact $\mathfrak{B}_2$ and $\mathfrak{B}_\omega$ are equivalent for derivability given an indefinite supply of fresh atoms, so we restrict to the first two.

3 Logical content: intrinsic and extrinsic

What remains is to draw out the logical significance of knowledge bases—not by appealing to an external semantics of models, but by seeing how logic arises from the structure and behaviour of knowledge bases. There are two distinct attitudes one might take toward what the logical signs express. One may regard them as describing intrinsic relations within the body of knowledge: how its contents are internally ordered. This mirrors the model-theoretic conception based on truth-in-a-model after Tarski. Alternatively, one may regard them as expressing extrinsic relations: how a body of knowledge behaves when it is extended, revised, or placed in interaction with new information.

Writing $\Gamma \Vdash_{\mathcal{B}} \phi$ to mean that $\phi$ is supported when $\mathcal{B}$ is extended with commitments licensing the formulae in $\Gamma$, the extrinsic connectives are characterised by a uniform schema: an extrinsic connective $E$ matches the corresponding intrinsic connective $I$ in that $\phi\, E\, \psi$ holds exactly when, across all extensions, any atom $P$ supported given $\phi\, I\, \psi$ is supported in its own right:

$$\Vdash_{\mathcal{B}} \phi\, E\, \psi \quad \text{iff} \quad \text{for all } \mathcal{C} \supseteq \mathcal{B} \text{ and atoms } P,\ \text{if } \phi\, I\, \psi \Vdash_{\mathcal{C}} P, \text{ then } \Vdash_{\mathcal{C}} P.$$

Applying this pattern across the connectives—an intrinsic implication $\to$ (via a translation $\lfloor - \rfloor$ that places a formula inside the base) and an extrinsic implication $\multimap$, an intrinsic conjunction $\land$ and extrinsic conjunction $\otimes$, intrinsic disjunction $\lor$ and extrinsic disjunction $\oplus$, together with intrinsic and extrinsic units for absurdity $\bot$ and $\mathbf{0}$—yields the base-extension semantics collected in Figure 1. The extrinsic disjunction has natural readings: the 'or' in a 1000-ticket lottery is extrinsic, since one does not know which ticket wins, yet whichever wins, any consequence common to all the disjuncts follows.

4 Which logics arise

Does this semantics correspond to any known logic? The answer depends on the choices made. The intrinsic fragment corresponds to logic programming in the style of Miller and Harland based on (hereditary) Harrop formulae: the bases $\mathcal{B}$ are programs and $\Vdash_{\mathcal{B}} \phi$ says that $\phi$ may be computed from $\mathcal{B}$.

The extrinsic fragment is more surprising. Depending on the basis, one recovers two celebrated logics: using $\mathfrak{B}_1$ one recovers classical logic, while using $\mathfrak{B}_2$ one recovers intuitionistic logic. In this setting the extrinsic conjunction collapses into the intrinsic one. That a change of basis—while fixing the semantic clauses—should have this effect remains mysterious. Hybrid systems combining intrinsic and extrinsic connectives yield further logics: Stafford et al.'s system over $\mathfrak{B}_1$ gives Stafford's Logic, and over $\mathfrak{B}_2$ gives general inquisitive logic—intuitionistic logic together with the generalized Kreisel–Putnam axiom.

5 Conclusion

We have presented a framework for analysing the logical content of knowledge bases conceived as atomic systems. The logical constants are defined by the inferential structure of knowledge itself: intrinsically, through relations that hold within a base, and extrinsically, through the behaviour of those relations under extension. The resulting base-extension semantics yields a range of well-known logics—classical, intuitionistic, and intermediate systems—depending on the basis adopted. Under this view, these logics may be understood as epistemic: each expresses a distinct conception of how knowledge is structured and how it persists under revision. Rather than taking logic as prior to knowledge, we may view the traditional logical systems as arising from it as formal articulations of its inferential and dynamic organisation. Even within this minimal setting, a small variation—the presence or absence of hypotheses in the atomic rules, the move from $\mathfrak{B}_2$ to $\mathfrak{B}_1$—already gives rise to distinct logics. It is natural to ask what further logics emerge when these connectives are interpreted over richer models of knowledge.

References