Palavras-chave
Como Citar
Resumo
We investigate expressiveness and definability issues with respect to minimal models, particularly in the scope of Circumscription. First, we give a proof of the failure of the Löwenheim-Skolem Theorem for Circumscription. Then we show that, if the class of P; Z-minimal models of a first-order sentence is ∆- elementary, then it is elementary. That is, whenever the circumscription of a firstorder sentence is equivalent to a first-order theory, then it is equivalent to a finitely axiomatizable one. This means that classes of models of circumscribed theories are either elementary or not ∆-elementary. Finally, using the previous result, we prove that, whenever a relation Pi is defined in the class of P; Z-minimal models of a firstorder sentence φ and whenever such class of P; Z-minimal models is ∆-elementary, then there is an explicit definition ψ for Pi such that the class of P; Z-minimal models of φ is the class of models of φ ∧ ψ. In order words, the circumscription of P in φ with Z varied can be replaced by φ plus this explicit definition ψ for Pi.Referências
BETH, E.W. “On Padoa’s method in the theory of definitions”. Indagtiones Mathematicae, 15, 1953.
CADOLI, M., EITER, T. and GOTTLOB, G. “Complexity of propositional nested circumscription and nested abnormality theories”.
ACM Transactions on Computational Logic, 6(2), p.232-272, 2005.
DAWAR, A. and GUREVICH, Y. “Fixed-point logics”. Bulletin of Symbolic Logic, 8(1), p. 65-88, 2002. DOYLE, J. “Circumscription and Implicit Definability”. Journal of Au- tomated Reasoning, 1(4), p. 391-405, 1985.
EBBINGHAUS, H.-D. and FLUM, J. Finite Model Theory. SpringerVerlag, 1995.
EBBINGHAUS, H.-D., FLUM, J. and THOMAS, W. Mathe- matical Logic. Springer-Verlag, New York, NY, 1994.
FLUM, J. “On the (infinite) model theory of fixed-point logics”. In Caicedo and Montenegro, editors, Models, algebras and proofs, number 2003 in Lecture Notes in Pure and Applied Mathematics, p. 67-75. Marcel Dekker, 1999.
FERREIRA, F.M. and MARTINS, A.T. “On minimal models”. Logic Journal of the IGPL, 15(5-6), p. 503-526, 2007.
HRBACEK, K. and JECH, T. Introduction to Set Theory. Marcel Dekker, 1999.
HUME, D. An Enquiry Concerning Human Understanding. 1748. Oxford University Press, 2007.
LIFSCHITZ, V. “Circumscription”. In D. M. Gabbay, C. J. Hogger, and J. A. Robinson, editors, Handbook of Logic in Artificial Intelli- gence and Logic Programming-Nonmonotonic Reasoning and Uncer- tain Reasoning, V. 3, p. 297-352. Clarendon Press, Oxford, 1994.
LIFSCHITZ, V. “Nested abnormality theories”. Intelli- Gence, 74(2): p. 351- 365, 1995.
MCCARTHY, J. “Circumscription – a form of non-monotonic reasonIng”. Artificial Intelligence, 13(1-2), p. 27-39, 1980.
MCCARTHY, J. “Applications of circumscription to formalizing common-sense knowledge”. Artificial Intelligence, 28(1), 1986.
MCDERMOTT, D. and DOYLE, J. “Non-monotonic logic I”. Artifi- cial Intelligence, 13(1-2), p. 41-72, 1980.
MOINARD, Y. and ROLLAND, R. “Circumscription and definability”. In International Joint Conference on Artificial Intelligence, p. 432-437, 1991.
PADOA, A. “Essai d’une théorie algébrique des nombres en tiers, precedé d’une introduction logique a une théorie deductive quelconque”. In Bibliothèque Du Congrès International de Philosophie, volume 3, p. 118-123, 1900.
REITER, R. “On closed world data bases”. In H. Gallaire and J. Minker, editors, Logic and Data Bases, p. 55-76, New York, 1978.
REITER, R. “A logic for default reasoning”. Artificial Intelligence, 13(1-2), p.81-132, 1980.
SCHLIPF, J. “Decidability and definability with circumscription”. Annals of Pure and Applied Logic, 35(2): p.173-191, 1987.
SCHLIPF, J van BENTHEM, J. “Minimal predicates, fixed-points, and definability”. Journal of Symbolic Logic, 70(3): p. 696-712, 2005.
Downloads
