Skip to main content
SpringerLink
Log in

Nondeterministic three-valued logic: Isotonic and guarded truth-functions

  • Published:
Studia Logica Aims and scope Submit manuscript

Abstract

Nondeterministic programs occurring in recently developed programming languages define nondeterminate partial functions. Formulas (Boolean expressions) of such nondeterministic languages are interpreted by a nonempty subset of {T (“true”), F (“false”), U (“undefined)}. As a semantic basis for the propositional part of a corresponding nondeterministic three-valued logic we study the notion of a truth-function over {T, F, U} which is computable by a nondeterministic evaluation procedure. The main result is that these truth-functions are precisely the functions satisfying four basic properties, called\( \subseteq \)-isotonic,\( \subseteq \) −-isotonic, hereditarily guarded, and hereditarily guard-using, and that a function satisfies these properties iff it is explicitly definable (in a certain normal form) from “if..then..else..fi”, binary choice, and constants.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. D. Ichbiah, J. G. B. Barnes, J. C. Heliard, B. Krieg-Brückner, O. Ronbine, B. A. Wichmann,Rationale for the design of the ADA programming language.ACM Sigplan Notices 14, 6, 1979.

    Google Scholar 

  2. F. L. Bauer,Program development by stepwise transformations — the project CIP. In:F. L. Bauer, M. Broy (eds.):Program Construction. Lecture Notes in Computer Science 69, 237–272, 1979.

  3. F. L. Bauer, H. Wössner,Algorithmic Language and Program Development, Springer-Verlag: Berlin-Heidelberg-New York, 1982.

    Google Scholar 

  4. M. Broy, R. Gnatz, M. Wirsing,Problemspezifikation — eine Grundlage für Programmentwicklung. In:R. Raulefs (ed.):Workshop on Reliable Software, Bonn, 1978. Hanser Verlag: München-Wien, 235–246, 1979.

    Google Scholar 

  5. M. Broy, R. Gnatz, M. Wirsing Semantics of nondeterministic and noncontinuous constructs. In:F. L. Bauer, M. Broy (eds.):Program Construction. Lecture Notes in Computer Science 69, 553–592, 1979.

  6. E. W. Dijkstra,Guarded commands, nondeterminacy and formal derivation of programs.Comm. ACM 18, 453–457, 1975.

    Article  Google Scholar 

  7. E. W. Dijkstra,A Discipline of Programming Prentice-Hall: Englewood Cliffs, 1976.

    Google Scholar 

  8. H. Egli,A mathematical model for nondeterministic computation. Unpublished memo, ETH Zürich, 1975.

  9. M. Hennessy, E. A. Ashcroft,The semantics of nondeterminism. In:S. Michaelson, R. Milner (eds.):Automata, Languages and Programming. Proc. 3rd ICALP, Edinburgh Univ. Press, 478–493, 1976.

  10. S. C. Kleene,Introduction to Metamathematics North-Holland: Amsterdam, 332–340, 1952.

    Google Scholar 

  11. Z. Manna,Mathematical theory of Computation McGraw-Hill: New York, 1974.

    Google Scholar 

  12. J. McCarthy,A basis for a mathematical theory of computation. In:P. Braffort,D. Hirschberg (eds.):Computer Programming and Formal Systems North-Holland: Amsterdam, 1963.

    Google Scholar 

  13. G. Mirkowska,Algorithmic logic with nondeterministic programs. In:Fundamenta Informaticae 3, 45–64, 1980.

    Google Scholar 

  14. G. Mirkowska,Model existence theorem in algorithmic logic with non-deterministic programs. In:ibid.. 157–170, 1980.

    Google Scholar 

  15. M. Nivat,Nondeterministic programs: an overview. Invited paper, IFIP Congress, 1980.

  16. H. Rasiowa,An Algebraic Approach to Nonclassical Logics Studies in Logic 78. North-Holland: Amsterdam, 1974.

    Google Scholar 

  17. N. Rescher,Many-valued Logic McGraw-Hill: New York, 1969.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Mathematik, Universität Hannover, Welfengarten 1, D-3000, Hannover 1

    Peter Päppinghaus

  2. Institut für Informatik, Technische Universität München, Postfach 20 24 20, D-8000, München 2

    Martin Wirsing

Authors
  1. Peter Päppinghaus
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Martin Wirsing
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Päppinghaus, P., Wirsing, M. Nondeterministic three-valued logic: Isotonic and guarded truth-functions. Stud Logica 42, 1–22 (1983). https://doi.org/10.1007/BF01418755

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01418755

Keywords

Search

Navigation