Completeness of many-sorted equational logic

J. A. Goguen, J. Meseguer

Research output: Contribution to journalArticle

Abstract

The rules of deduction which are usually used for many-sorted equational logic in computer science, for example in the study of abstract data types, are not sound. Correcting these rules by introducing explicit quantifiers yields a system which, although it is sound, is not complete; some new rules are needed for the addition and deletion of quantifiers. This note is intended as an informal, but precise, introduction to the main issues and results. It gives an example showing the unsoundness of the usual rules; it also gives a completeness theorem for our new rules, and gives necessary and sufficient conditions for the old rules to agree with the new.

Original languageEnglish (US)
Pages (from-to)24-32
Number of pages9
JournalACM SIGPLAN Notices
Volume16
Issue number7
DOIs
StatePublished - Jan 7 1981
Externally publishedYes

Fingerprint

Acoustic waves
Abstract data types
Computer science

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design

Cite this

Completeness of many-sorted equational logic. / Goguen, J. A.; Meseguer, J.

In: ACM SIGPLAN Notices, Vol. 16, No. 7, 07.01.1981, p. 24-32.

Research output: Contribution to journalArticle

Goguen, J. A. ; Meseguer, J. / Completeness of many-sorted equational logic. In: ACM SIGPLAN Notices. 1981 ; Vol. 16, No. 7. pp. 24-32.
@article{b75fec4706984c7080df457f026d8392,
title = "Completeness of many-sorted equational logic",
abstract = "The rules of deduction which are usually used for many-sorted equational logic in computer science, for example in the study of abstract data types, are not sound. Correcting these rules by introducing explicit quantifiers yields a system which, although it is sound, is not complete; some new rules are needed for the addition and deletion of quantifiers. This note is intended as an informal, but precise, introduction to the main issues and results. It gives an example showing the unsoundness of the usual rules; it also gives a completeness theorem for our new rules, and gives necessary and sufficient conditions for the old rules to agree with the new.",
author = "Goguen, {J. A.} and J. Meseguer",
year = "1981",
month = "1",
day = "7",
doi = "10.1145/947864.947865",
language = "English (US)",
volume = "16",
pages = "24--32",
journal = "ACM SIGPLAN Notices",
issn = "1523-2867",
publisher = "Association for Computing Machinery (ACM)",
number = "7",

}

TY - JOUR

T1 - Completeness of many-sorted equational logic

AU - Goguen, J. A.

AU - Meseguer, J.

PY - 1981/1/7

Y1 - 1981/1/7

N2 - The rules of deduction which are usually used for many-sorted equational logic in computer science, for example in the study of abstract data types, are not sound. Correcting these rules by introducing explicit quantifiers yields a system which, although it is sound, is not complete; some new rules are needed for the addition and deletion of quantifiers. This note is intended as an informal, but precise, introduction to the main issues and results. It gives an example showing the unsoundness of the usual rules; it also gives a completeness theorem for our new rules, and gives necessary and sufficient conditions for the old rules to agree with the new.

AB - The rules of deduction which are usually used for many-sorted equational logic in computer science, for example in the study of abstract data types, are not sound. Correcting these rules by introducing explicit quantifiers yields a system which, although it is sound, is not complete; some new rules are needed for the addition and deletion of quantifiers. This note is intended as an informal, but precise, introduction to the main issues and results. It gives an example showing the unsoundness of the usual rules; it also gives a completeness theorem for our new rules, and gives necessary and sufficient conditions for the old rules to agree with the new.

UR - http://www.scopus.com/inward/record.url?scp=0040463821&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0040463821&partnerID=8YFLogxK

U2 - 10.1145/947864.947865

DO - 10.1145/947864.947865

M3 - Article

AN - SCOPUS:0040463821

VL - 16

SP - 24

EP - 32

JO - ACM SIGPLAN Notices

JF - ACM SIGPLAN Notices

SN - 1523-2867

IS - 7

ER -