Mathematical Problems from Applied Logic I

by Gabbay, Dov M.; Goncharov, Sergei S.; Zakharyaschev, Michael

• ISBN13: 9780387286884
• ISBN10: 0387286888
• Format: Hardcover
• Copyright: 2005-12-01
• Publisher: Springer Verlag

Summary

Mathematical Problems from Applied Logic I presents chapters from selected, world renowned, logicians. Important topics of logic are discussed from the point of view of their further development in light of requirements arising from their successful application in areas such as Computer Science and AI language. An overview of the current state as well as open problems and perspectives are clarified in such fields as non-standard inferences in description logics, logic of provability, logical dynamics, and computability theory. The book contains interesting contributions concerning the role of logic today, including some unexpected aspects of contemporary logic and the application of logic.

Table of Contents

Nonstandard Inferences in Description Logics: The Story So Far	1	(76)
Franz Baader
Ralf Kusters
Introduction	2	(4)
Description Logics and Standard Inferences	6	(5)
Nonstandard Inferences---Motivation and Definitions	11	(12)
Motivation	12	(3)
Definitions	15	(6)
Techniques	21	(2)
A Structural Characterization of Subsumption	23	(9)
Getting started --- The characterization for εL	24	(3)
Extending the characterization to ALε	27	(4)
Characterization of subsumption for other DLs	31	(1)
The Least Common Subsumer	32	(4)
The LCS for εL	32	(2)
The LCS for ALε	34	(2)
The LCS for other DLs	36	(1)
The Most Specific Concept	36	(8)
Existence and approximation of the MSC	36	(8)
The most specific concept in the presence of cyclic TBoxes	44	(1)
Rewriting	44	(9)
The minimal rewriting decision problem	45	(1)
The minimal rewriting computation problem	46	(6)
Approximation	52	(1)
Matching	53	(11)
Deciding matching problems	54	(1)
Solutions of matching problems	55	(3)
Computing matchers	58	(6)
Matching in other DLs and extensions of matching	64	(1)
Conclusion and Future Perspectives	64	(2)
References	66	(11)
Problems in the Logic of Provability	77	(60)
Lev Beklemishev
Albert Visser
Introduction	78	(3)
Informal Concepts of Proof	81	(10)
Formal and informal provability and the problem of equivalence of proofs	81	(4)
Strengthening Hilbert's thesis	85	(2)
Coordinate-free proof theory	87	(4)
Basics of Provability Logic	91	(2)
Provability Logic for Intuitionistic Arithmetic	93	(9)
Propositional logics of arithmetical theories	94	(3)
Admissible rules	97	(3)
The provability logic of HA and related theories	100	(2)
Provability Logic and Bounded Arithmetic	102	(4)
Classification of Bimodal Provability Logics	106	(3)
Magari Algebras	109	(5)
Interpretability Logic	114	(6)
Graded Provability Algebras	120	(5)
List of Problems	125	(12)
References	129	(8)
Open Problems in Logical Dynamics	137	(56)
Johan van Benthem
Logical Dynamics	137	(2)
Standard Epistemic Logic	139	(5)
Language	140	(1)
Semantics	141	(1)
Basic model theory	142	(1)
Axiomatics	143	(1)
Complexity	143	(1)
Open problems, even here	144	(1)
Public Announcement: Epistemic Logic Dynamified	144	(13)
World elimination: the system PAL	145	(5)
What are the real update laws?	150	(3)
Model theory of learning	153	(2)
Communication and planning	155	(1)
Group knowledge	156	(1)
Dynamic Epistemic Logic	157	(7)
Information from arbitrary events: product update	158	(2)
Update evolution	160	(2)
Questions of language design	162	(1)
Extensions of empirical coverage	163	(1)
Background in Standard Logics	164	(6)
Modal logic	165	(1)
First-order logic	166	(2)
Fixed-point logics	168	(2)
From Information Update to Belief Revision	170	(8)
From knowledge to belief	170	(1)
Dynamic doxastic logic	171	(4)
Better-known theories of belief revision	175	(2)
Probabilistic update	177	(1)
Temporal Epistemic logic	178	(6)
Broader temporal perspectives on update	178	(1)
Knowledge and ignorance over time	179	(2)
Representation of update logics	181	(2)
Connections with other parts of mathematics	183	(1)
Game Logics and Game Theory	184	(1)
Conclusion	185	(8)
References	186	(7)
Computability and Emergence	193	(40)
S Barry Cooper
An Emergent World around Us	194	(1)
Descriptions, Algorithms, and the Breakdown of Inductive Structure	195	(7)
Ontology and Mathematical Structure	202	(2)
Where does It All Start?	204	(5)
Towards a Model Based on Algorithmic Content	209	(5)
Levels of Reality	214	(7)
Algorithmic Content Revisited	221	(3)
What Is to Be Done?	224	(9)
References	228	(5)
Samsara†	233	(44)
John N Crossley
Introduction	234	(1)
The structure of the paper	234	(1)
An Example of a Process	235	(1)
What Logics Do We Need?	236	(22)
Extracting constructions from proofs	242	(1)
The Lambda Calculus and the Curry--Howard correspondence	243	(2)
Proofs as types	245	(3)
Strong normalization and program extraction	248	(2)
Beyond traditional logic in program extraction	250	(6)
Proofs from programs	256	(1)
Programs then proofs	257	(1)
What are Logical Systems and What Should They Be?	258	(4)
Higher order logic	259	(2)
A note on set theory	261	(1)
Computation and proof	262	(1)
The Nature of Proof	262	(7)
The question of scale and the role of technology	263	(5)
Foundations	268	(1)
Final Remarks	269	(8)
References	270	(7)
Two Doors to Open	277	(40)
Wilfrid Hodges
Logic and Cognitive Science	279	(21)
Spatial intuition	281	(4)
Kurt Godel and the choice of representation	285	(8)
A sample cognitive description of reasoning	293	(5)
Frege versus Peirce: comparison of representations	298	(2)
Medieval Arabic Semantics	300	(17)
References	313	(4)
Applied Logic: A Manifesto	317	(28)
Lawrence S Moss
What is Applied Logic?	317	(2)
Mathematics and Logic, but Different from Mathematical Logic	319	(7)
Mathematical Logic and Mathematics	320	(2)
Where applied logic differs	322	(2)
Applied mathematics is good mathematics	324	(1)
Applied logic is applied mathematics	325	(1)
Applied Philosophical Logic	326	(2)
Applied philosophical logic = theoretical AI	328	(1)
What Does Computer Science Have to Do with It?	328	(4)
Logic is the calculus of computer science	329	(1)
Computer science motivates logic	330	(1)
Going beyond the traditional boundaries of logic	331	(1)
Other Case Studies	332	(9)
Neural networks and non-monotonic logic	332	(1)
Dynamic epistemic logic	333	(2)
Linguistics, logic, and mathematics	335	(4)
But is it dead?	339	(2)
Being as catholic as Possible	341	(4)
References	343	(2)
Index	345