Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cables, Trains and Types Read chapter Read first chapter

2020 | OriginalPaper | Chapter

Cathoristic Logic

A Logic for Capturing Inferences Between Atomic Sentences

Authors : Richard Evans, Martin Berger

Published in: From Lambda Calculus to Cybersecurity Through Program Analysis

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Cables, Trains and Types
next chapter A Type Theory for Probabilistic –calculus
Appendix
Available only for authorised users
Footnotes
1
Efficient handling of free/bound variables is an active field of research, e.g. nominal approaches to logic [23]. The problem was put in focus in recent years with the rising interest in the computational cost of syntax manipulation in languages with binders.
 
2
“Cathoristic” comes from the Greek \(\kappa \alpha \theta o \rho \acute{\i } \zeta \epsilon i \nu \): to impose narrow boundaries. We are grateful to Tim Whitmarsh for suggesting this word.
 
3
“Tantum” is Latin for “only”.
 
4
We will precisify this claim in later sections; (1) first-order logic’s representation of incompatibility is longer in terms of formula length than cathoristic logic’s (see Sect. 4.2); and (2) logic programs in cathoristic logic can be optimised to run significantly faster than their equivalent in first-order logic (see Sect. 5.3).
 
5
[8] pp. 47–48.
 
6
[7] pp. 88–89, our emphasis.
 
7
Compare Russell [24] p. 117: “A sentence is of atomic form when it contains no logical words and no subordinate sentence”. We use a broader notion of atomicity by focusing solely on whether or not it contains a subordinate sentence, allowing logical words such as “and” as long as they are conjoining noun-phrases and not sentences.
 
8
To see that “Jack loves Jill” is not a constituent of “Jack loves Jill and Joan”, observe that “and” conjoins constituents of the same syntactic type. But “Jack loves Jill” is a sentence, while “Joan” is a noun. Hence the correct parsing is “Jack (loves (Jill and Joan))”, rather than “(Jack loves Jill) and Joan”.
 
9
See [28] p. 282 for a spirited defence of predicate conjunction against Fregean regimentation.
 
10
Although natural languages are full of examples of inferences from dyadic to monadic predicates, there are certain supposed counterexamples to the general rule that a dyadic predicate always implies a monadic one. For example, “Jack explodes the device” does not, on its most natural reading, imply that “Jack explodes”. Our response to cases like this is to distinguish between two distinct monadic predicates \(explodes_1\) and \(explodes_2\):
  • \(X explodes_1\) iff X is an object that undergoes an explosion
  • \(X explodes_2\) iff X is an agent that initiates an explosion
Now “Jack explodes the device” does imply that “Jack \(explodes_2\)” but does not imply that “Jack \(explodes_1\)”. There is no deep problem here - just another case where natural language overloads the same word in different situation to have different meanings.
 
11
The application had thousands of paying users, and was available for download on the App Store for the iPad [12].
 
12
E.g. STRIPS [14].
 
13
Brandom [8] defines incompatibility slightly differently: he defines the set of sets of formulae which are incompatible with a set of formulae. But in cathoristic logic, if a set of formulae is incompatible, then there is an incompatible subset of that set with exactly two members. So we can work with the simpler definition in the text above.
 
14
[8] p. 123.
 
15
The converse of \((\lnot 2)\) follows from \((\lnot 1)\) and the general structural laws above.
 
16
\(\psi \) is the minimal incompatible of \(\phi \) iff for all \(\xi \), if \(\mathsf {Inc}(\{\phi \} \cup \{\xi \})\) then \(\xi \models \psi \).
 
17
The notion of incompatibility applies to all logics: two formulae are incompatible if there is no model which satisfies both.
 
18
We assume, in this discussion, that married is a many-to-one predicate. We assume that polygamy is one person attempting to marry two people (but failing to marry the second).
 
Literature
1.
Haskell implementation of cathoristic logic. Submitted with the paper (2014)
2.
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)CrossRef
6.
Brachman, R., Levesque, H.: Knowledge Representation and Reasoning. Morgan Kaufmann, Burlington (2004)MATH
7.
Brandom, R.: Making It Explicit. Harvard University Press, Cambridge (1998)
8.
Brandom, R.: Between Saying and Doing. Oxford University Press, Oxford (2008)CrossRef
9.
Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order. Cambridge University Press, Cambridge (1990)MATH
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)MATH
12.
13.
Evans, R., Short, E.: Versu - a simulationist storytelling system. IEEE Trans. Comput. Intell. AI Games 6(2), 113–130 (2014)CrossRef
14.
Fikes, R., Nilsson, N.: Strips: a new approach to the application of theorem proving to problem solving. Artif. Intell. 2, 189–208 (1971)CrossRef
15.
16.
Hennessy, M.: Algebraic Theory of Processes. MIT Press Series in the Foundations of Computing. MIT Press, Cambridge (1988)MATH
17.
Hennessy, M., Milner, R.: Algebraic laws for non-determinism and concurrency. JACM 32(1), 137–161 (1985)CrossRef
18.
19.
20.
Honda, K., Yoshida, N.: A uniform type structure for secure information flow. SIGPLAN Not. 37, 81–92 (2002)CrossRef
21.
O’Keeffe, A., McCarthy, M. (eds.): The Routledge Handbook of Corpus Linguistics. Routledge, Abingdon (2010)
22.
23.
Pitts, A.M.: Nominal Sets: Names and Symmetry in Computer Science. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge (2013)
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)MATH
26.
Sassone, V., Nielsen, M., Winskel, G.: Models for concurrency: towards a classification. TCS 170(1–2), 297–348 (1996)MathSciNetCrossRef
27.
28.
Sommers, F.: The Logic of Natural Language. Clarendon Press, Oxford (1982)
29.
30.
Troelstra, A.S., Schwichtenberg, H.: Basic Proof Theory, 2nd edn. Cambridge University Press, Cambridge (2000)CrossRef
31.
Turbanti, G.: Modality in Brandom’s incompatibility semantics. In: Proceedings of the Amsterdam Graduate Conference - Truth, Meaning, and Normativity (2011)
32.
33.
Wittgenstein, L.: Philosophische Bemerkungen. Suhrkamp Verlag, Frankfurt (1981). Edited by R. RheesMATH
34.
Wittgenstein, L.: Tractatus Logico-Philosophicus: Logisch-Philosophische Abhandlung. Suhrkamp Verlag, Frankfurt (2003). Originally published: 1921CrossRef
Metadata
Title
Cathoristic Logic
Authors
Richard Evans
Martin Berger
Copyright Year
2020
Book
From Lambda Calculus to Cybersecurity Through Program Analysis

Print ISBN: 978-3-030-41102-2

Electronic ISBN: 978-3-030-41103-9

Copyright Year: 2020

DOI
https://doi.org/10.1007/978-3-030-41103-9_2