Cathoristic logic. A logic for capturing inferences between atomic sentences. (English) Zbl 1440.03042

Di Pierro, Alessandra (ed.) et al., From lambda calculus to cybersecurity through program analysis. Essays dedicated to Chris Hankin on the occasion of his retirement. Cham: Springer. Lect. Notes Comput. Sci. 12065, 17-85 (2020).
Summary: Cathoristic logic is a multi-modal logic where negation is replaced by a novel operator allowing the expression of incompatible sentences. We present the syntax and semantics of the logic including complete proof rules, and establish a number of results such as compactness, a semantic characterisation of elementary equivalence, the existence of a quadratic-time decision procedure, and Brandom’s incompatibility semantics property. We demonstrate the usefulness of the logic as a language for knowledge representation.
For the entire collection see [Zbl 1435.68026].


03B45 Modal logic (including the logic of norms)
03B65 Logic of natural languages
68T27 Logic in artificial intelligence
68T30 Knowledge representation
Full Text: DOI


[1] Haskell implementation of cathoristic logic. Submitted with the paper (2014)
[2] Abramsky, S.: Computational interpretations of linear logic. TCS 111, 3-57 (1993) · Zbl 0791.03003
[3] Allan, K. (ed.): Concise Encyclopedia of Semantics. Elsevier, Boston (2009)
[4] Aronoff, M., Rees-Miller, J. (eds.): The Handbook of Linguistics. Wiley-Blackwell, Hoboken (2003)
[5] Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic. Cambridge University Press, Cambridge (2001) · Zbl 0988.03006
[6] Brachman, R., Levesque, H.: Knowledge Representation and Reasoning. Morgan Kaufmann, Burlington (2004) · Zbl 1341.68228
[7] Brandom, R.: Making It Explicit. Harvard University Press, Cambridge (1998)
[8] Brandom, R.: Between Saying and Doing. Oxford University Press, Oxford (2008)
[9] Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order. Cambridge University Press, Cambridge (1990) · Zbl 0701.06001
[10] Davidson, D.: Essays on Actions and Events. Oxford University Press, Oxford (1980)
[11] Enderton, H.B.: A Mathematical Introduction to Logic. Academic Press, Cambridge (2001) · Zbl 0992.03001
[12] Evans, R., Short, E.: Versu. http://www.versu.com. https://itunes.apple.com/us/app/blood-laurels/id882505676?mt=8
[13] Evans, R., Short, E.: Versu - a simulationist storytelling system. IEEE Trans. Comput. Intell. AI Games 6(2), 113-130 (2014)
[14] Fikes, R., Nilsson, N.: Strips: a new approach to the application of theorem proving to problem solving. Artif. Intell. 2, 189-208 (1971) · Zbl 0234.68036
[15] Girard, J.-Y.: Linear logic. TCS 50, 1-101 (1987) · Zbl 0625.03037
[16] Hennessy, M.: Algebraic Theory of Processes. MIT Press Series in the Foundations of Computing. MIT Press, Cambridge (1988) · Zbl 0744.68047
[17] Hennessy, M., Milner, R.: Algebraic laws for non-determinism and concurrency. JACM 32(1), 137-161 (1985) · Zbl 0629.68021
[18] Honda, K.: A Theory of Types for the \(\pi \)-Calculus, March 2001. http://www.dcs.qmul.ac.uk/ kohei/logics
[19] Honda, K., Vasconcelos, V.T., Kubo, M.: Language primitives and type discipline for structured communication-based programming. In: Hankin, C. (ed.) ESOP 1998. LNCS, vol. 1381, pp. 122-138. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0053567
[20] Honda, K., Yoshida, N.: A uniform type structure for secure information flow. SIGPLAN Not. 37, 81-92 (2002) · Zbl 1323.68375
[21] O’Keeffe, A., McCarthy, M. (eds.): The Routledge Handbook of Corpus Linguistics. Routledge, Abingdon (2010)
[22] Peregrin, J.: Logic as based on incompatibility (2010). http://philpapers.org/rec/PERLAB-2 · Zbl 1261.03040
[23] Pitts, A.M.: Nominal Sets: Names and Symmetry in Computer Science. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge (2013) · Zbl 1297.68008
[24] Russell, B.: An Inquiry into Meaning and Truth. Norton and Co, New York (1940)
[25] Sangiorgi, D.: Introduction to Bisimulation and Coinduction. Cambridge University Press, Cambridge (2012) · Zbl 1252.68008
[26] Sassone, V., Nielsen, M., Winskel, G.: Models for concurrency: towards a classification. TCS 170(1-2), 297-348 (1996) · Zbl 0874.68120
[27] Smith, D., Genesereth, M.: Ordering conjunctive queries. Artif. Intell. 26, 171-215 (1985) · Zbl 0569.68077
[28] Sommers, F.: The Logic of Natural Language. Clarendon Press, Oxford (1982)
[29] Takeuchi, K., Honda, K., Kubo, M.: An interaction-based language and its typing system. In: Halatsis, C., Maritsas, D., Philokyprou, G., Theodoridis, S. (eds.) PARLE 1994. LNCS, vol. 817, pp. 398-413. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-58184-7_118
[30] Troelstra, A.S., Schwichtenberg, H.: Basic Proof Theory, 2nd edn. Cambridge University Press, Cambridge (2000) · Zbl 0957.03053
[31] Turbanti, G.: Modality in Brandom’s incompatibility semantics. In: Proceedings of the Amsterdam Graduate Conference - Truth, Meaning, and Normativity (2011)
[32] van Dalen, D.: Logic and Structure. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-85108-0 · Zbl 1048.03001
[33] Wittgenstein, L.: Philosophische Bemerkungen. Suhrkamp Verlag, Frankfurt (1981). Edited by R. Rhees
[34] Wittgenstein, L.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.