Quantifier-free logic for multialgebraic theories
Yngve Lamo, Michał Walicki · Electronic Notes in Theoretical Computer Science · 2003
We develop a new quantifier-free logic for deriving consequences of multialgebraic theories. Multilagebras are used as models for nondeterminism in the context of algebraic specifications. They are many sorted algebras with set valued operations. Formulae are sequents over atoms allowing one to state set-inclusion or identity of 1-element sets (determinacy). We introduce a sound and complete Rasiowa-Sikorski logic for proving multilagebraic tautologies. We then extend this system for proving consequences of specifications based on translation of finite theories into logical formulae. Finally, we show how such a translation may be avoided – introduction of the specific cut rules leads to a sound and complete Gentzen system for proving directly consequences of specifications. The improvements over earlier logics for multialgebras concern mainly the ability to handle empty carriers (as well as empty result-sets) without the use of quantifiers, and to derive consequences of (potentially infinite) theories without the use of general cut.