Logical considerations on default semantics

Springer Science and Business Media LLC - Tập 20 - Trang 195-226 - 1997
William C. Rounds1, Guo‐Qiang Zhang2
1Artificial Intelligence Laboratory, University of Michigan, Ann Arbor, USA
2Department of Computer Science, University of Georgia, Athens, USA

Tóm tắt

We consider a reinterpretation of the rules of default logic. We make Reiter’s default rules into a constructive method of building models, not theories. To allow reasoning in first‐order systems, we equip standard first‐order logic with a (new) Kleene 3‐valued partial model semantics. Then, using our methodology, we add defaults to this semantic system. The result is that our logic is an ordinary monotonic one, but its semantics is now nonmonotonic. Reiter’s extensions now appear in the semantics, not in the syntax. As an application, we show that this semantics gives a partial solution to the conceptual problems with open defaults pointed out by Lifschitz [V. Lifschitz, On open defaults, in: Proceedings of the Symposium on Computational Logics (1990)], and Baader and Hollunder [F. Baader and B. Hollunder, Embedding defaults into terminological knowledge representation formalisms, in: Proceedings of Third Annual Conference on Knowledge Representation (Morgan‐Kaufmann, 1992)]. The solution is not complete, chiefly because in making the defaults model‐theoretic, we can only add conjunctive information to our models. This is in contrast to default theories, where extensions can contain disjunctive formulas, and therefore disjunctive information. Our proposal to treat the problem of open defaults uses a semantic notion of nonmonotonic entailment for our logic, related to the idea of “only knowing”. Our notion is “only having information” given by a formula. We discuss the differences between this and “minimal‐knowledge” ideas. Finally, we consider the Kraus–Lehmann–Magidor [S. Kraus, D. Lehmann and M. Magidor, Nonmonotonic reasoning, preferential models, and cumulative logics, Artificial Intelligence 44 (1990) 167–207] axioms for preferential consequence relations. We find that our consequence relation satisfies the most basic of the laws, and the Or law, but it does not satisfy the law of Cut, nor the law of Cautious Monotony. We give intuitive examples using our system, on the other hand, which on the surface seem to violate these two laws. We make some comparisons, using our examples, to probabilistic interpretations for which these laws are true, and we compare our models to the cumulative models of Kraus, Lehmann, and Magidor. We also show sufficient conditions for the laws to hold. These involve limiting the use of disjunction in our formulas in one way or another. We show how to make use of the theory of complete partially ordered sets, or domain theory. We can augment any Scott domain with a default set. We state a version of Reiter’s extension operator on arbitrary domains as well. This version makes clear the basic order‐theoretic nature of Reiter’s definitions. A three‐variable function is involved. Finding extensions corresponds to taking fixed points twice, with respect to two of these variables. In the special case of precondition‐free defaults, a general relation on Scott domains induced from the set of defaults is shown to characterize extensions. We show how a general notion of domain theory, the logic induced from the Scott topology on a domain, guides us to a correct notion of “affirmable sentence” in a specific case such as our first‐order systems. We also prove our consequence laws in such a way that they hold not only in first‐order systems, but in any logic derived from the Scott topology on an arbitrary domain.

Từ khóa


Tài liệu tham khảo

E. Adams, The Logic of Conditionals (D. Reidel, Netherlands, 1975).

F. Baader and B. Hollunder, Embedding defaults into terminological knowledge representation formalisms, in: Proceedings of Third Annual Conference on Knowledge Representation (Morgan-Kaufmann, 1992).

F. Bacchus, A. Grove, J. Halpern and D. Koller, Statistical foundations for default reasoning, in: Proceedings of IJCAI (1993).

J. Barwise, The Situation in Logic, 17 (Center for Study of Language and Information, Stanford, California, 1989).

S. Blamey, Partial logic, in: Handbook of Philosophical Logic, Vol. III, eds. Gabbay and Guenthner (Reidel, Dordrecht, 1986).

G. Brewka, Cumulative default logic: In defense of nonmonotonic inference rules, Artificial Intelligence 50(1) (1991) 183–205.

J. Dix, Classifying semantics of logic programs, in: Proceedings of First International Workshop on Logic Programming and Non-Monotonic Reasoning, eds. A. Nerode, W. Marek and V. Subrahmanian (MIT Press, 1991) pp. 166–180.

P. Doherty and W. Lukaszewicz, Distinguishing between facts and default assumptions, in: Non-Monotonic Reasoning and Partial Semantics, chapter 3 (Ellis Horwood, 1992).

D.W. Etherington, Reasoning with Incomplete Information, Research Notes in Artificial Intelligence (Morgan-Kaufmann, 1988).

R. Guerreiro and M. Casanova, An alternative semantics for default logic (preprint) (1990).

J. Halpern and Y. Moses, A guide to modal logies of knowledge and belief, in: Proc. IJCAI-85 (1985) pp. 480–490.

M. Kaminski, A comparative study of open defaults. Presentation at 1994 Symposium on Logic and Artificial Intelligence, Fort Lauderdale (January 1994).

R. Kasper and W. Rounds, The logic of unification in grammar, in: Linguistic and Philosophy (1991).

S. Kraus, D. Lehmann and M. Magidor, Nonmonotonic reasoning, preferential models, and cumulative logics, Artificial Intelligence 44 (1990) 167–207.

J. Lawson, The duality of continuous posets, Houston Journal of Mathematics 5 (1979) 357–394.

H.J. Levesque, All I know: A study in autoepistemic logic, Artificial Intelligence 42 (1990) 263–309.

V. Lifschitz, On open defaults, in: Proceedings of the Symposium on Computational Logics (1990).

V. Lifschitz, Nonmonotonic databases and epistemic queries, in: Proc. IJCAI-91 (1991) pp. 381–386.

F. Lin and Y. Shoham, Epistemic semantics for fixed-point nonmonotonic logics, in: Proc. Third Conference on Theoretical Aspects of Reasoning about Knowledge (1990) pp. 184–198.

D. Makinson, General theory of cumulative inference, in: Proceedings of Second Internationals, Conference on Nonmonotonic Reasoning (LNAI 346) (Springer-Verlag, 1989) pp. 1–18.

J. Pearl, From Adams' conditional to default expressions, causal conditionals, and counterfactuals, in: Festschrift for Ernest Adams (Cambridge University Press, 1993). To appear.

R. Reiter, A logic for default reasoning, Artificial Intelligence 13 (1980) 81–132.

G.-Q. Zhang, W. Rounds and C. Huang, in: Proceedings of the 30th Hawaii International Conference on System Sciences, Maui, Hawaii (1997) Vol. V, pp. 383–391.

W. Rounds and G.-Q. Zhang, Attunement to constraints in nonmonotonic reasoning, in: Logic Language, and Computation, Vol. 1, CSLI Lecture Notes, Vol. 58 (CSLI Publication, Stanford, CA, 1996) pp. 479–494.

W. Rounds and G.-Q. Zhang, Domain theory meets default logic, Logic and Computation 5 (1995) 1–25.

G. Schwarz and M. Truszczynski, Modal logic s4f and the minimal knowledge paradigm, in: Proc. Fourth Conference on Theoretical Aspects of Reasoning about Knowledge, ed. Y. Moses (1992) pp. 184–198.

D.S. Scott, Domains for denotational semantics, in: Lecture Notes in Computer Science 140 (1982).

Y. Shoham, A semantical approach to nonmonotonic logics, in: Readings in Nonmonotonic Reasoning, ed. M.L. Ginsberg (Morgan-Kaufmann, 1987).

S. Vickers, Topology via Logic (Cambridge University Press, 1988).

M. Young, Nonmonotonic sorts for feature structures, in: Proceedings of AAAI-92 (1992) pp. 596–601.

G.-Q. Zhang, Logic of Domains (Birkhauser, Boston, 1991).

Thông tin
Thông tin xuất bản

Springer Science and Business Media LLC

Tập 20

195-226

Thông tin tác giả