Truth versus information in logic programming

DOI10.1017/S1471068413000069zbMATH Open1302.68053DBLPjournals/tplp/NaishS14arXiv1305.0141OpenAlexW3105042245WikidataQ57664999 ScholiaQ57664999MaRDI QIDQ2933087FDOQ2933087

Harald Søndergaard, Lee Naish

Publication date: 10 December 2014

Published in: Theory and Practice of Logic Programming (Search for Journal in Brave)

Abstract: The semantics of logic programs was originally described in terms of two-valued logic. Soon, however, it was realised that three-valued logic had some natural advantages, as it provides distinct values not only for truth and falsehood, but also for "undefined". The three-valued semantics proposed by Fitting and by Kunen are closely related to what is computed by a logic program, the third truth value being associated with non-termination. A different three-valued semantics, proposed by Naish, shared much with those of Fitting and Kunen but incorporated allowances for programmer intent, the third truth value being associated with underspecification. Naish used an (apparently) novel "arrow" operator to relate the intended meaning of left and right sides of predicate definitions. In this paper we suggest that the additional truth values of Fitting/Kunen and Naish are best viewed as duals. We use Belnap's four-valued logic, also used elsewhere by Fitting, to unify the two three-valued approaches. The truth values are arranged in a bilattice which supports the classical ordering on truth values as well as the "information ordering". We note that the "arrow" operator of Naish (and our four-valued extension) is essentially the information ordering, whereas the classical arrow denotes the truth ordering. This allows us to shed new light on many aspects of logic programming, including program analysis, type and mode systems, declarative debugging and the relationships between specifications and programs, and successive executions states of a program. This paper is to appear in Theory and Practice of Logic Programming (TPLP).

Full work available at URL: https://arxiv.org/abs/1305.0141

zbMATH Keywords

many-valued logicmodesprogram analysisinformation orderintended interpretationdeclarative debugginglogic program specificationspecification semantics

Mathematics Subject Classification ID

Many-valued logic (03B50) Logic programming (68N17) Logic in computer science (03B70) Semantics in the theory of computing (68Q55)

Cites Work

• Title not available (Why is that?)
• A lattice-theoretical fixpoint theorem and its applications
• The Semantics of Predicate Logic as a Programming Language
• On notation for ordinal numbers
• A typed logic of partial functions reconstructed classically
• Computer science today. Recent trends and developments
• Bilattices and the semantics of logic programming
• A logic covering undefinedness in program proofs
• A kripke-kleene semantics for logic programs*
• Fixpoint semantics for logic programming a survey
• Negation in logic programming
• Kleene's Logic, Generalized
• Logic programming revisited
• Derivation of Logic Programs
• The family of stable models
• Partiality and nondeterminacy in program proofs
• A three-valued semantics for logic programmers
• Paraconsistent declarative semantics for extended logic programs
• Logic-based program synthesis and transformation. 19th international symposium, LOPSTR 2009, Coimbra, Portugal, September 2009. Revised selected papers
• Proof systems for reasoning about computation errors
• Bottom-up dataflow analysis of normal logic programs
• Hypothesis-based semantics of logic programs in multivalued logics
• The recursion-theoretic complexity of the semantics of predicate logic as a programming language
• Static analysis. 1st international symposium, SAS '94, Namur (Belgium), September 28--30, 1994. Proceedings
• Towards a logical semantics for pure Prolog

Cited In (2)

• Bilattices and the semantics of logic programming
• Correctness and Completeness of Logic Programs

This page was built for publication: Truth versus information in logic programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933087)