Unifiability and Structural Completeness in Relation Algebras and in Products of Modal Logic S5

Wojciech Dzik; Beniamin Wróbel

doi:10.18778/0138-0680.44.1.2.01

Authors

Wojciech Dzik University of Silesia, Institute of Mathematics, Bankowa 12, 40 007 Katowice, Poland
Beniamin Wróbel University of Silesia, Institute of Mathematics, Bankowa 12, 40 007 Katowice, Poland

DOI:

https://doi.org/10.18778/0138-0680.44.1.2.01

Keywords:

admissible rules, passive rules, unification, projective unification, almost structural completeness, n-modal logic S5ⁿ, relation algebras, representable diagonal-free cylindric algebras

Abstract

Unifiability of terms (and formulas) and structural completeness in the variety of relation algebras RA and in the products of modal logic S5 is investigated. Nonunifiable terms (formulas) which are satisfiable in varieties (in logics) are exhibited. Consequently, RA and products of S5 as well as representable diagonal-free n-dimensional cylindric algebras, RDfn, are almost structurally complete but not structurally complete. In case of S5ⁿ a basis for admissible rules and the form of all passive rules are provided.

References

Andreka H., Maddux R., Representations for Small Relation Algebras, Notre Dame Journal of Formal Logic 35 (4),(1994), pp. 550–562.
Google Scholar DOI: https://doi.org/10.1305/ndjfl/1040408612

Baader F., Ghilardi S., Unification in Modal and Description Logics, Logic Journal of the IGPL, vol. 19 (6), (2011), pp. 705–730.
Google Scholar DOI: https://doi.org/10.1093/jigpal/jzq008

Baader F., Snyder W., Unification Theory, [in:] A. Robinson, A. Voronkov, (eds.) Handbook of Automated Reasoning, Elsevier Science Publisher, 2001.
Google Scholar DOI: https://doi.org/10.1016/B978-044450813-3/50010-2

Burris S., Discriminator Varieties and Symbolic Computation, Journal of Symbolic Computation, Volume 13 (1992), pp. 175-207.
Google Scholar DOI: https://doi.org/10.1016/S0747-7171(08)80089-2

Dzik W., Unification Types in Logic, Silesian University Press, Katowice 2007.
Google Scholar

Dzik W., Remarks on projective unifiers, Bulletin of the Section of Logic 40:1/2 (2011), pp. 37–46.
Google Scholar

Dzik W., Wojtylak P., Projective Unification in Modal Logic, Logic Journal of the IGPL 20(1), (2012), pp. 121–153.
Google Scholar DOI: https://doi.org/10.1093/jigpal/jzr028

Dzik W., Wojtylak P., Modal consequence relations extending S4.3, Notre Dame Journal of Formal Logic, 2015 (in print).
Google Scholar

Gabbay D. M., Kurucz A., Wolter F., Zakharyaschev M., Manydimensional Modal Logic, Elsevier Science Publisher, 2003.
Google Scholar

Ghilardi S., Unification through Projectivity, Journal of Symbolic Computation 7 (1997), pp. 733–752.
Google Scholar DOI: https://doi.org/10.1093/logcom/7.6.733

Ghilardi S., Unification in Intuitionistic Logic, Journal of Symbolic Logic 64(2), (1999), pp. 859–880.
Google Scholar DOI: https://doi.org/10.2307/2586506

Ghilardi S., Best Solving Modal Equations, Annals of Pure and Applied Logic 102 (2000), pp. 183–198.
Google Scholar DOI: https://doi.org/10.1016/S0168-0072(99)00032-9

Henkin L., Monk J., Tarski A., Cylindric algebras. Part II, The foundations of Mathematics, Volume 115, Elsevier Science Publishers (1985).
Google Scholar

Hirsch R., Hodkinson I., Relation Algebras by Games, North-Holland, 2002.
Google Scholar

Maddux R. D., Relation Algebras, Elsevier Science Publishers (2006).
Google Scholar

Pogorzelski W. A. and Wojtylak P., Completeness theory for propositional logics, Studies in Universal Logic, Birkhäuser, Bassel-Boston-Berlin (2008).
Google Scholar

Rybakov V. V., Admissible Rules for Logics Containing S4.3, Sibirski Math. Journal 25 (1984), pp. 141–145.
Google Scholar DOI: https://doi.org/10.1007/BF00968695

Rybakov V. V., Terziler M., Gencer C., An essay on unification and inference rules for modal logics, Bulletin of the Section of Logic 28 (1999), pp. 145–157.
Google Scholar

Rybakov V. V., Terziler M., Gencer C., Unification and passive inference rules for modal logics, Journal of Applied Non-Classical Logics 10 (2000), pp. 369–377.
Google Scholar DOI: https://doi.org/10.1080/11663081.2000.10511004

Tarski A., On the calculus of relations, Journal of Symbolic Logic 6(1941), pp. 73–89.
Google Scholar DOI: https://doi.org/10.2307/2268577