Distributed Relation Logic

Gerard Allwein, William L. Harrison, Thomas Reynolds

DOI: http://dx.doi.org/10.12775/LLP.2016.017


We extend the relational algebra of Chin and Tarski so that it is multisorted or, as we prefer, typed. Each type supports a local Boolean algebra outfitted with a converse operator. From Lyndon, we know that relation algebras cannot be represented as proper relation algebras where a proper relation algebra has binary relations as elements and the algebra is singly-typed. Here, the intensional conjunction, which was to represent relational composition in Chin and Tarski, spans three different local algebras, thus the term distributed in the title. Since we do not rely on proper relation algebras, we are free to re-express the algebras as typed. In doing so, we allow many different intensional conjunction operators.

We construct a typed logic over these algebras, also known as heterogeneous algebras of Birkhoff and Lipson. The logic can be seen as a form of relevance logic with a classical negation connective where the Routley-Meyer star operator is reified as a converse connective in the logic. Relevance logic itself is not typed but our work shows how it can be made so. Some of the properties of classical relevance logic are weakened from Routley-Meyer’s version which is too strong for a logic over relation algebras.


relation algebra; multisorted algebra; distributed logic; Kripke frames; Kripke models

Full Text:



Adámek, J., and J. Rosický, Locally Presentable and Accessible Categories, Lecture Note Series 189, London Mathematical Society, 1994. DOI: 10.1017/CBO9780511600579

Allwein, G., H. Demir, and L. Pike, “Logics for classes of Boolean monoids”, Journal of Logic, Language and Information, 13, 3 (2004): 241–266. DOI: 10.1023/B:JLLI.0000028336.64373.f6

Allwein, G., W. Harrison, and D. Andrews, “Simulation logic”, Logic and Logical Philosophy, 23, 3 (2014): 277–299. DOI: 10.12775/LLP.2013.027

Allwein, G., and W.L. Harrison, “Distributed modal logic”, pages 331–362 in Katalin Bimbó (ed.), J. Michael Dunn on Information Based Logic, Outstanding Contributions to Logic, Springer-Verlag, 2016. DOI: 10.1007/978-3-319-29300-4_16

Anderson, A.R., and N.D. Belnap, Jr., Entailment: The Logic of Relevance and Necessity, volume I, Princeton University Press, 1975.

Birkhoff, G., Lattice Theory, Third Edition, American Mathematical Society, 1967.

Birkhoff, G., and J.D. Lipson, “Heterogeneous algebras”, Journal of Computational Theory, 8 (1968): 115–133.

Blackburn, P., M. de Rijke, and Y. Venema, Modal Logic, Cambridge Tracts in Theoretical Computer Science, No. 53, Cambridge University Press, 2001. DOI: 10.1017/CBO9781107050884

Chin, L.H., and A. Tarski, “Distributive and modular laws in the arithmetic of relation algebras”, University of California Publications in Mathematics, 1951.

Dunn, J.M., “Gaggle theory: An abstraction of Galois connections and residuation with applications to negation and various logical operations”, pages 31–51 in Logics in AI, Proceedings European Workshop JELIA, LNCS 478, Springer-Verlag, 1990. DOI: 10.1007/BFb001843

Dunn, J.M., and G. Hardegree, Algebraic Methods in Philosophical Logic, Oxford Logic Guides 41, Oxford University Press, 2001.

Hoare, C.A.R., and J. He, “A weakest pre-specification”, Inform. Process.

Jónsson, B., and A. Tarski, “Boolean algebras with operators. Parts 1 and 2”, American Journal of Mathematics, 73–74 (1951–1952): 891–939, 127–162. DOI: 10.2307/2372074

Jónsson, B., and C. Tsinakis, “Relation algebras as residuated Boolean algebras”, Algebra Universalis, 30 (1993): 469–478.

Ng, K.C., “Relation algebras with transitive closure”, PhD thesis, University of California, Berkeley, 1984.

Pratt, V.R., “Dynamic algebras as a well behaved fragment of relation algebras”, Chapter 5 in Proceedings, Algebra and Computer Science, Lecture Notes in Computer Science, Springer-Verlag, 1990. DOI: 10.1007/BFb0043079

Routley, R., and R.K. Meyer, “The semantics of entailment”, pages 194–243 in H. Leblanc (ed.), Truth, Syntax, and Modality, Studies in Logic and the Foundations of Mathematics, North Holland, 1973. DOI: 10.1016/S0049-237X(08)71541-6

Routley, R., R.K. Meyer, V. Plumwood, and R.T. Brady, Relevant Logics and Their Rivals, Ridgeview Publishing Company, 1982.

Sahlqvist, H., “Completeness and correspondence in the first and second order semantics for modal logic”, pages 110–143 in Proceedings of the Third Scandanavian Logic Symposium, Uppsala, 1973, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, 1975. DOI: 10.1016/S0049-237X(08)70728-6

Stone, M.H., “The theory of representation for Boolean algebras”, Transactions of the American Mathematical Society, 40 (1936): 37–111. DOI: 10.2307/1989664

van Benthem, J., Modal Logic and Classical Logic, Bibliopolis, 1983.

ISSN: 1425-3305 (print version)

ISSN: 2300-9802 (electronic version)

Partnerzy platformy czasopism