Three-valued formalization of logic programming: is it needed?

ABSTRACT

The central issue of this paper concerns the truth value undefined in Przymusinsi's 3-valued formalization of nonmonotonic reasoning and logic programming. We argue that this formalization can lead to the problem of unintended semantics and loss of disjunctive information. We modify the formalization by proposing two general principles for logic program semantics: justifiability and minimal undefinedness. The former is shown to be a general property for almost all logic program semantics, and the latter requires the use of the undefined only when it is necessary. We show that there are three types of information embedded in the undefined: the disjunctive, the factoring, and the “difficult-to-be-assigned”. In the modified formalization, the first two can be successfully identified and branched into multiple models. This leaves only the “difficult-to-be-assigned” as the undefined. It is shown that the truth value undefined is needed only for a very special type of programs whose practicality is yet to be evidenced.

REFERENCES

• 1: K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 2: F. Bry, Logic programming as constructivism: a formalization and its application to databases, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-50, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73725]
• 3: Doyle J., A Truth Maintenance System, Artificial Intelligence Vol. 12, (1979), pp. 231-272.
• 4: Dung P. and K. Kanchanasut, A Fixpoint Approach to Declarative Semantics of Logic Programs, in Proc. North American Conference on Logic Programming, E. Lust and R. Overbeek (ed.), MIT Press, 1989, pp. 604-625.
• 5: Fitting M., A Kripke-Kleene Semantics for Logic Programs, Journal of Logic Programming 2, 4 (1985), pp. 295-312.
• 6: Gelfond M. and V. Lifschitz, The Stable Model Semantics for Logic Programming, in Proc. 5th Sy~sium/Conference on Logic Programming, R. A. Kowalski and K. A. Bowen (ed.), MIT Press, 1988, pp. 1070-1080.
• 7: S. Hanks , D. McDermott, Nonmonotonic logic and temporal projection, Artificial Intelligence, v.33 n.3, p.379-412, Nov. 1987 [doi>10.1016/0004-3702(87)90043-9]
• 8: Kleene S., Introduction to Metamathematics, Wolters-Noordhoff Publishing, New York, 1971.
• 9: Kenneth Kunen, Negation in logic programming, Journal of Logic Programming, v.4 n.4, p.289-308, December 1, 1987 [doi>10.1016/0743-1066(87)90007-0]
• 10: V. Lifschitz, On the declarative semantics of logic programs with negation, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 11: Marek W. and V.S. Subrahmanian, The Relationship betwee~ Logic Program Semantics and Non-monotonic Reasoning, in Proc. 6th Conference on Logic Programming, G. Levi and M. Martelli (ed.), MIT Press, 1989.
• 12: Paul H. Morris, The anomalous extension problem in default reasoning, Artificial Intelligence, v.35 n.3, p.383-399, July 1988 [doi>10.1016/0004-3702(88)90022-7]
• 13: PrzymusinskaH. and T. C. Przymusinski, Weakly Perfect Model Semantics for Logic Programs, in Proc. 5th Symposium~Conference on Logic Programming , R. A. K0walski and K. A. Bowen (ed.), MIT Press, 1988, pp. 1106-1120.
• 14: Przymusinski T. C., Perfect Model Semantics, in Proc. 5th Symposium/Conference on Logic Programming, R. A. Kowalski and K. A. Bowen (ed.), MIT Press, 1988, pp. 1080-1096.
• 15: Teodor C. Przymusinski, Three-valued formalizations of non-monotonic reasoning and logic programming, Proceedings of the first international conference on Principles of knowledge representation and reasoning, p.341-348, December 1989
• 16: T. C. Przymusinski, Every logic program has a natural stratification and an iterated least fixed point model, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.11-21, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73723]
• 17: J. C. Shepherdson, Negation in logic programming, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 18: A. V. Gelder, Negation as failure using tight derivations for general logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 19: Allen Van Gelder , Kenneth Ross , John S. Schlipf, Unfounded sets and well-founded semantics for general logic programs, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.221-230, March 1988, Austin, Texas, United States [doi>10.1145/308386.308444]
• 20: A. Van Gelder, The alternating fixpoint of logic programs with negation, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73722]
• 21: You J. and L. Li, Supported Circumscription and Its Relation to Logic Programming with Negation, in Proc. North American Conference on Logic Programming, MIT Press, 1989.
• 22: You J. and L. Yuan, A Three-Valued Formalization of Deductive Databases and Logic Programming, forthcoming.
• 23: Yuan L. and J. You, A Circumscriptive Formula for Deductive Databases and Logic Programs, submitted for publication, 1989.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  H. Information Systems
  H.2 DATABASE MANAGEMENT

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Nonmonotonic reasoning and belief revision

General Terms:
Design, Languages, Management, Performance, Theory, Verification