Book contents
- Frontmatter
- Contents
- Preface
- Part I Introduction
- Part II Channel Theory
- 4 Classifications and Infomorphisms
- 5 Operations on Classifications
- 6 Distributed Systems
- 7 Boolean Operations and Classifications
- 8 State Spaces
- 9 Regular Theories
- 10 Operations on Theories
- 11 Boolean Operations and Theories
- 12 Local Logics
- 13 Reasoning at a Distance
- 14 Representing Local Logics
- 15 Distributed Logics
- 16 Logics and State Spaces
- Part III Explorations
- Answers to Selected Exercises
- Bibliography
- Glossary of Notation
- Index of Definitions
- Index of Names
16 - Logics and State Spaces
Published online by Cambridge University Press: 05 November 2011
- Frontmatter
- Contents
- Preface
- Part I Introduction
- Part II Channel Theory
- 4 Classifications and Infomorphisms
- 5 Operations on Classifications
- 6 Distributed Systems
- 7 Boolean Operations and Classifications
- 8 State Spaces
- 9 Regular Theories
- 10 Operations on Theories
- 11 Boolean Operations and Theories
- 12 Local Logics
- 13 Reasoning at a Distance
- 14 Representing Local Logics
- 15 Distributed Logics
- 16 Logics and State Spaces
- Part III Explorations
- Answers to Selected Exercises
- Bibliography
- Glossary of Notation
- Index of Definitions
- Index of Names
Summary
In Lecture 8 we saw how to construct state spaces from classifications and vice versa. In Lecture 12 we saw how to associate a canonical logic Log(S) with any state space S. In this lecture we study the relation between logics and state spaces in more detail. Our aim is to try to understand how the phenomena of incompleteness and unsoundness get reflected in the state-space framework. We will put our analysis to work by exploring the problem of nonmonotonicity in Lecture 19.
Subspaces of State Spaces
Our first goal is to show that there is a natural correspondence between the subspaces of a state space S and logics on the event classification of S. We develop this correspondence in the next few results.
Definition 16.1. Let S be a state space. An S-logic is a logic ℒ on the event classification Evt(S) such that Log(S) ⊑ ℒ.
The basic intuition here is that an S-logic should build in at least the theory implicit in the state-space structure of S. We call a state σ of S ℒ-consistent if {σ}⊬ℒ and let Ωℒ the set of ℒ-inconsistent states.
Proposition 16.2.If S is a state space and ℒ is an S-logic, then ⊬ℒΩℒ. Indeed, Ωℒ is the smallest set of states such that ⊢ℒΩℒ.
Proof. To prove the first claim, let (Г, Δ) be any partition of the types of Evt(S) with Ωℒ∈Δ. We need to see that Г⊢ℒΔ.
- Type
- Chapter
- Information
- Information FlowThe Logic of Distributed Systems, pp. 195 - 200Publisher: Cambridge University PressPrint publication year: 1997