Trivalent Logics and their applications Proceedings of the ESSLLI 2012 Workshop Edited by ´ Paul Egr´e and David Ripley Version 08/11/2012 Contents Foreword and acknowledgements ´ e and David Ripley Paul Egr´ iii Programme Committee v Workshop Description vii Invited papers: Arnon Avron, Grzegorz Malinowski, Katrin Schulz ix Contributed papers 1 1 A Multi-Valued Delineation Semantics for Absolute Adjectives Heather Burnett 1 2 Are True and False not Enough? Vincent Degauquier 17 3 Modeling the Suppression Task under Three-Valued Lukasiewicz and Well-Founded Se- mantics Emmanuelle-Anna Dietz and Steffen H¨ olldobler 27 4 Reasoning about Rough Sets Using Three Logical Values Beata Konikowska and Arnon Avron 39 5 Doing the right things — trivalence in deontic action logic Piotr Kulicki and Robert Trypuz 53 6 Trivalent logics arising from L-models for the Lambek calculus with constants Stepan Kuznetsov 65 7 A trivalent logic that encapsulates intuitionistic and classical logic Tin Perkov 71 8 TCS for presuppositions J´er´emy Zehr and Orin Percus 77 i Foreword and acknowledgments Welcome to this ESSLLI 2012 workshop on Trivalent Logics and their Applications! Besides our contributors and invited speakers to this workshop, we wish to thank all the people and institutions who helped us organize this event, in particular the members of our programme committee and the additional referees listed below. We also express our gratefulness to the following sponsors: • Pablo Cobreros’ Project ‘Borderlineness and Tolerance’ (FFI2010-16984) funded by the Ministerio de Ciencia e Innovaci´on, Government of Spain • Fran¸cois R´ecanati’s CCC project under the European Research Council (FP7/2007- 2013) / ERC Advanced Grant agreement n229 441-CCC) • Philippe Schlenker’s EURYI project ‘Presupposition: A formal pragmatic ap- proach’ hosted by Institut Jean-Nicod • The CNRS, Institut Jean-Nicod, and the University of Melbourne for additional support. Special thanks moreover go to Andreas Herzig for encouraging this proposal and to the ESSLLI 2012 organizing committee for their support and for hosting our workshop. We received 14 submissions for this workshop, 8 of which were accepted for pre- sentation, and 1 as alternative. Three initially scheduled papers could not be included in these proceedings as the speakers had to cancel their participation: a contributed paper by Yasutada Sudo and colleagues, a contributed paper by Mark Jago, and an invited paper by Janneke Huitink. We thank Katrin Schulz in particular for accepting to replace Janneke Huitink as a plenary speaker. We hope this workshop will be productive and look forward to seeing you there! ´ e and David Ripley, August 2012 Paul Egr´ iii Program Committee Arnon Avron Pablo Cobreros Paul Egr´e (co-chair) Janneke Huitink Grzegorz Malinowski David Ripley (co-chair) Robert van Rooij Additional Reviewers Wojciech Buszkowski Szymon Frankowski Hans Smessaert Anna W´ojtowicz v Workshop description Three-valued logics have been an object of extensive study since at least the work of Lukasiewicz, with applications to a wide range of natural language phenomena, including presupposition, conditionals and vagueness. While many-valued logics can be studied on their own, there has been a regain of interest for three-valued logics in recent years, with the emergence of new perspectives regarding their applicability to natural language. In the theory of presupposition projection, in particular, the question of whether the projection of presupposition can be dealt with by means of a trivalent truth- functional semantics has been the object of renewed attention, in particular because truth-functional trivalent approaches appear as a main competitor to both dynamic and pragmatic approaches (viz. Beaver and Krahmer 2001, George 2008, Fox 2008, all of them giving special attention to so-called middle-Kleene logic proposed by Pe- ters, and the recent debates with Schlenker). In the area of vagueness, ways have been proposed to combine the canonical paracomplete and paraconsistent three- valued logics of Kleene and Priest in order to deal with the paradoxes of vagueness, and to account for phenomena such as meaning coarsening and strengthening (viz. Avron et Konikowska 2008, Cobreros et al. 2012). In the literature on condition- als, finally, the question remains largely open of the selection between a wide range of candidates for the definition of a suitable three-valued conditional (viz. Bradley 2002, Cantwell 2008, Huitink 2009, Rothschild 2009). From a more foundational point of view, finally, the meaning attached to the third truth value can vary signif- icantly depending on the problem under consideration and the definition of logical consequence considered to be relevant. The aim of this workshop is to promote new contributions for the extension of two-valued logic with a third truth-value. Submissions have been encouraged on logical and linguistics aspects of the use of 3-valued logics, with relevance on the following topics: • applications of trivalent logic to quantification in natural language • trivalent logics for conditionals / vagueness / presupposition • are vagueness and presupposition susceptible of a unified treatment in trivalent logic? • logical consequence and proof-theory for three-valued logic vii • unification and classification of 3-valued logics • connection between 3-valued logics and other non-classical logics • partial 2-valued logics vs. 3-valued logics • do we need more than three truth-values? can we dispense with a third truth value? viii Invited papers Arnon Avron (Tel Aviv University) Using Trivalent Semantics for Paraconsistent Reasoning We describe a general method for a systematic and modular generation of cut-free calculi for thousands of paraconsistent logics. The method relies on the use of 3- valued non-deterministic semantics for these logics. *** Grzegorz Malinowski (University of L´od´z) Logical three-valuedness and beyond The modern history of many-valuedness starts with Lukasiewiczs construction of three-valued logic. This pioneering, philosophically motivated and matrix based construction, first presented in 1918, was in 1922 extended to n-valued cases, includ- ing two infinite. Soon several constructions of many-valued logic appeared and the history of the topic became rich and interesting. However, as it is widely known, the problem of interpretation of multiple values is still among vexed questions of con- temporary logic. With the talk, which essentially groups my earlier settlements, I intend to put a new thread into discussion on the nature of logical many-valuedness. The topics, touched upon, are: matrices, tautological and non-tautological many- valuedness , Tarskis structural consequence and the Lindenbaum-Wjcicki complete- ness result, which supports the Suszkos claim on logical two- valuedness of any struc- tural logic. Futher to that, two facets of many-valuedness referential and inferential are unravelled. The first fits the standard approach and it results in multiplication of semantic correlates of sentences, and not logical values in a proper sense. It is based on the matrix approach and results in a multiple-element referential extensionality. In that paradigm, the central concepts are: the tautological many-valuedness and many- valued consequence. The second many-valuedness is a metalogical property of quasi-consequence and refers to partition of the matrix universe into more than two disjoint subsets, used in the definition of inference, using the inference rules, which from non-rejected premises lead to the accepted conclusions. *** Katrin Schulz (ILLC, Amsterdam) TBA ix Contributed papers 1  A Multi-Valued Delineation Semantics for Absolute Adjectives Heather Burnett University of California, Los Angeles [email protected] 1 Introduction This paper provides a novel semantic analysis of the gradability of adjectives of the absolute class within a delineation (i.e. comparison-class-based) semantic framework (first presented in [8]). It has been long observed that the syntac- tic category of bare adjective phrases can be divided into two principle classes: scalar (or gradable) vs non-scalar (non-gradable). The principle test for scalar- ity of an adjective P is the possibility of P to appear (without coercion) in the explicit comparative construction. Thus, we find a first distinction between adjectives like tall, expensive, straight, empty, and dry on the one hand (ok: taller, more expensive, straighter, emptier, drier ) and atomic, pregnant, and ge- ographical on the other (?more atomic, ?more pregnant, ?more geographical ). It has been argued by many authors that the class of scalar adjectives is fur- ther decomposed into two principle subclasses: relative adjectives (henceforth RAs: ex. tall, short, expensive, intelligent) and absolute adjectives (henceforth AAs: ex. empty, straight, dry, clean). Although RAs and AAs behave differently in many syntactic and semantic constructions, the fundamental difference be- tween these two classes of adjectives is generally taken to be that members of the former class have context-sensitive semantic denotations (denotations that vary depending on contextually given comparison classes); whereas, members of the latter class have semantic denotations that are independent of context (cf. [16], [7], [12]). As discussed in [13], this empirical observation raises a puzzle for the delineation approach, since, as will be outlined below, in this framework, the scales associated with adjectival constituents are derived through looking at how their semantic denotations vary across comparison classes. The inability of comparison-class-based frameworks to treat the difference between absolute and relative adjectives has been taken (for example by [6]) to be a major argument against a delineation semantics for scalar adjectives and in favour of a semantics in which degrees and scales are primitives. In this paper, I present a new solution to the puzzle of the gradability of AAs within the delineation approach, one that takes into account the empirical obser- vation that these constituents can be used imprecisely or vaguely (cf. [10], [11], [6], a.o.). I show that by integrating a simplified version of [8]’s comparison-class- based logical system with the similarity-based multi-valued logical framework proposed by [4] to model the vagueness/imprecision associated with these predi- 1 2 Heather Burnett cates, we can arrive at new logical framework that can treat the absolute/relative distinction without degrees in the ontology. The paper is organized as follows: in section 2, I present the delineation framework for the semantic analysis of gradable predicates. Then, in section 3, I present the main ways in which adjectives like tall differ from adjectives like empty, and I argue that the latter adjectives challenge the comparison-class- based approach. In section 4, I present the empirical observation that absolute adjectives are subject to the phenomenon of vagueness/imprecision, and I in- troduce the multi-valued logical system that I will be employing to model this phenomenon, [4]’s Tolerant, Classical, Strict (TCS). Finally, in section 5, I give my analysis of the gradability of AAs within a delineation extension of TCS. In particular, I propose that the non-trivial scales associated with AAs are derived through looking at comparison-class-based variation in predicate-relative simi- larity/indifference relations, and I show how these relations can be constructed within this new approach using methods in the same vein as [1] and [14]. The new framework is formally laid out (with the proofs of the main results of the paper) in the appendix. 2 Delineation Semantics Delineation semantics is a framework for analyzing the semantics of gradable expressions that takes the observation that they are context sensitive to be their key feature. A delineation approach to the semantics of positive and comparative constructions was first proposed by [8], and has been further developed by many authors in the past 30 years. In this framework, scalar adjectives denote sets of individuals and, furthermore, they are evaluated with respect to comparison classes, i.e. subsets of the domain D. The basic idea is that the extension of a gradable predicate can change depending on the set of individuals that it is being compared with. In other words, the semantic denotation of the positive form of the scalar predicate (i.e. tall ) can be assigned a different set of individuals in different comparison classes. Definition 1. CC-relativized interpretation of predicates (informal). 1. For a scalar adjective P and a contextually given comparison class X ⊆ D, (1) JPKX ⊆ X. 2. For an individual a, a scalar adjective P , and a contextually given compari- son class X ⊆ D, (2) Ja is PKX = 1 iff JaK ∈ JP KX . Unlike degree semantics (cf. [6]), delineation semantics takes the positive form as basic and derives the semantics of the comparative form from quantification over comparison classes. Informally, John is taller than Mary is true just in case there is some comparison class with respect to which John counts as tall and Mary counts as not tall. A Multi-Valued Delineation Semantics for Absolute Adjectives 3 Definition 2. Semantics for the comparative (informal). For two indi- viduals a, b and a scalar adjective P , Ja is P-er than bK = 1 iff a >P b, where >P is defined as: (3) x >P y iff there is some comparison class X such that x ∈ JP KX and y∈/ JP KX . As it stands, the analysis of the comparative in definition 2 is very weak and allows some very strange and un-comparative-like relations1 , if we do not say anything about how the extensions of gradable predicates can change in different comparison classes (CCs). A solution to this problem involves imposing some constraints on how predicates like tall can be applied in different CCs. In this work, I will adopt the set of constraints on the application of gradable predicates presented in [1] and [2]. Van Benthem proposes three axioms governing the behaviour of individuals across comparison classes. They are the following (presented in my notation): For x, y ∈ D and X ⊆ D such that x ∈ JPKX and y ∈ / JPKX , (4) No Reversal (NR:) There is no X 0 ⊆ D such that y ∈ JPKX 0 and / JPKX 0 . x∈ (5) Upward difference (UD): For all X 0 , if X ⊆ X 0 , then there is some z, z 0 : z ∈ JPKX 0 and z 0 ∈ / JPKX 0 . (6) Downward difference (DD): For all X 0 , if X 0 ⊆ X and x, y ∈ X 0 , then there is some z, z 0 : z ∈ JPKX 0 and z 0 ∈ / JPKX 0 . No Reversal states that if x >P y, there is no X 0 such that y is in JP KX 0 , but x is not. Upward Difference states that if, in the comparison class X, there is a P /not P contrast, then a P /not P contrast is preserved in every larger CC. Finally, Downward Difference says that if in some comparison class X, there is a P/not P contrast involving x and y, then there remains a contrast in every smaller CC that contains both x and y. van Benthem shows that these axioms give rise to strict weak orders: irreflexive, transitive and almost connected relations2 . 1 For example, suppose in the CC {a, b}, a ∈ JP K{a,b} and b ∈ / JP K{a,b} . So a >P b. And suppose moreover that, in the larger CC {a, b, c}, b ∈ JP K{a,b,c} and a ∈ / JP K{a,b,c} . So b >P a. But clearly, natural language comparatives do not work like this: If John is {taller, fatter, wider. . . } than Mary, Mary cannot also be {taller, fatter, wider. . . } than John. In other words, >P must be asymmetric. 2 The definitions of irreflexivity, transitivity and almost connectedness are given below. Definition 3. Irreflexivity. A relation > is irreflexive iff there is no x ∈ D such that x > x. Definition 4. Transitivity. A relation > is transitive iff for all x, y, z ∈ D, if x > y and y > z, then x > z. Definition 5. Almost Connectedness. A relation > is almost connected iff for all x, y ∈ D, if x > y, then for all z ∈ D, either x > z or z > y. 4 Heather Burnett Definition 6. Strict weak order. A relation > is a strict weak order just in case > is irreflexive, transitive, and almost connected. As discussed in [8], [2] and [14], strict weak orders (also known as ordinal scales in measurement theory) intuitively correspond to the types of relations expressed by many kinds of comparative constructions3 . Thus, the theorem in 1 is an important result in the semantic analysis of comparatives, and it shows that scales associated with gradable predicates can be constructed from the context- sensitivity of the positive form and certain axioms governing the application of the predicate across different contexts. Theorem 1. Strict Weak Order. For all P , >P is a strict weak order. Proof. [1]; [2], p. 116. t u This analysis seems appropriate for relative predicates like tall and short; however, as we will see in the next section, it does not capture the certain aspects of the meaning of absolute predicates like empty and straight. 3 The Absolute/Relative Distinction Following many authors, I take the principle way in which AAs like empty and straight differ from RAs like tall and fat is that AAs are not context-sensitive in the same way that RAs are. One test that shows this is the definite descrip- tion test. As observed by [6] and [15] a.o., adjectives like tall and empty differ in whether they can ‘shift’ their thresholds (i.e. criteria of application) to dis- tinguish between two individuals in a two-element comparison class when they appear in a definite description. For example, suppose there are two containers (A and B), and neither of them are particularly tall; however, A is (noticeably) taller than B. In this situation, if someone asks me (7-a), then it is very clear that I should pass A. Now suppose that container A has less liquid than container B, but neither container is particularly close to being completely empty. In this situation, unlike what we saw with tall, (7-b) is infelicitous. (7) a. Pass me the tall one. b. Pass me the empty one. In other words, unlike RAs, AAs cannot change their criteria of application to distinguish between objects that lie in the middle of their associated scale. Using this test, we can now make the argument that adjectives like full, straight, 3 For example, one cannot be taller than oneself; therefore >tall should be irreflexive. Also, if John is taller than Mary, and Mary is taller than Peter, then we know that John is also taller than Peter. So >tall should be transitive. Finally, suppose John is taller than Mary. Now consider Peter. Either Peter is taller than Mary (same height as John or taller) or he is shorter than John (same height as Mary or shorter). Therefore, >tall should be almost connected. A Multi-Valued Delineation Semantics for Absolute Adjectives 5 and bald are absolute, since (8-a) is infelicitous if neither object is (close to) completely full/straight/bald. Likewise, we can make the argument that dirty, wet, and bent are also absolute, since (8-b) is infelicitous when comparing two objects that are at the middle of the dirtiness/wetness/curvature scale (i.e. both of them are dirty/wet/bent). (8) Absolute Adjectives a. Pass me the full/straight/bald one. b. Pass me the dirty/wet/bent one. Furthermore, we can make the argument that long, expensive, and even colour adjectives like blue are relative, since the (9) is felicitous when comparing two objects when both or neither are particularly long/expensive/blue4 . (9) Relative Adjectives Pass me the long/expensive/blue one. How can we capture this distinction in a delineation framework? An idea that has been present in the literature for a long time, and has recently been incarnated in, for example, [7] and [12], is that unlike tall or long that have a context sensitive meaning, adjectives like straight, empty or bald are not context sensitive (hence the term absolute adjective). That is, in order to know who the bald people are or which rooms are empty, we do not need compare them to a certain group of other individuals, we just need to look at their properties. To incorporate this idea into the delineation approach, I propose (following an idea in [14]) that, in a semantic framework based on comparison classes, what it means to be non-context-sensitive is to have your denotation be invariant across classes. Thus, for an absolute adjective Q and a comparison class X, it suffices to look at what the extension of Q is in the maximal CC, the domain D, in order to know what JQKX is. I therefore propose that a different axiom set governs the semantic interpretation of the members of the absolute class that does not apply to the relative class: the singleton set containing the absolute adjective axiom. (10) Absolute Adjective Axiom (AAA). If Q ∈ AA, then for all X ⊂ D and x ∈ X, x ∈ JQKX iff x ∈ JQKD . In other words, the semantic denotation of an absolute adjective is set with respect to the total domain, and then, by the AAA, the interpretation of Q in D is replicated in each smaller comparison class. The AAA is very powerful: as shown by theorem 2, the scales that the semantic denotations of absolute constituents give rise to are very small, essentially trivial. Theorem 2. If Q satisfies the AAA, >Q is homomorphic to the two element boolean algebra (sometimes written 2). Proof. Consider the function h : D → 2. 4 For an example of the use of a colour adjective like blue to distinguish between two not particularly blue objects, see [5]. 6 Heather Burnett (11) For all x ∈ D, h(x) = 1 iff x ∈ JQKD . Show for all x, y ∈ D, if x >Q y then h(x) >2 h(y). Immediately from the definition of h. t u Absolute adjectives thus raise a puzzle for delineation analyses: (12) The Puzzle of Absolute Adjectives: If AAs have non-context-sensitive semantic denotations, how can they be gradable? In the rest of the paper, I will provide a solution to this puzzle. 4 Vagueness/Imprecision with AAs Of course, saying that adjectives like empty, bald, and straight are not at all context-sensitive is clearly false. As observed by very many authors (ex. [16], [10], [11], [7], [6] a.o.), the criteria for applying an absolute adjective can vary depending on context, as exemplified in (13). (13) a. Only two people came to opening night; the theatre was empty. b. Two people didn’t evacuate; the theatre wasn’t empty when they started fumigating. Rather than being attributed directly to the context-sensitivity of their semantic denotation, the contextual variation in the application of absolute predicates is generally attributed to something that is variably called “imprecision”, “loose talk” or “vagueness”, among other things. I therefore propose that the context- sensitivity that allows for the construction of non-trivial scales is not semantic, as in the case of relative adjectives (as outlined in section 2), but pragmatic: although the semantic denotation of an absolute predicate does not vary across comparison classes, its denotation on its imprecise use does. As mentioned in the introduction, the approach that I will adopt to model the effects of vagueness/imprecision is [4]’s Tolerant, Classical, Strict (TCS). This system was developed as a way to preserve the intuition that vague and imprecise predicates5 are tolerant (i.e. satisfy ∀x∀y[P (x) & x ∼P y → P (y)], where ∼P is a ‘little by little’ or indifference relation for a predicate P ), without running into the Sorites paradox6 . [4] adopt a non-classical logical framework with three notions of satisfaction: classical satisfaction, tolerant satisfaction, and its dual, 5 The system in [4] was proposed to model the puzzling properties of vague language with relative predicates like tall ; however, I suggest that the results in this paper show that it has a natural application to modelling similar effects with absolute adjectives. 6 Note that on their imprecise use, absolute predicates like bald and empty give rise to Soritical-type reasoning: how many hairs must someone have before they stop being considered bald? How many seats must be filled before a theatre is no longer considered empty? A Multi-Valued Delineation Semantics for Absolute Adjectives 7 strict satisfaction. Formulas are tolerantly/strictly satisfied based on classical truth and predicate-relative, possibly non-transitive indifference relations. For a given predicate P , an indifference relation, ∼P , relates those individuals that are viewed as sufficiently similar with respect to P . For example, for the predicate empty, ∼empty would be something like the relation “differ by a number of objects that is irrelevant for our purposes/contain roughly the same number of objects”. Since these relations are given by context, we assume that they are part of the model. I give the definition of the indifference relations (within a comparison class-based framework) below. Definition 7. CC-relativized indifference relations. For all scalar adjec- tives P and comparison classes X ⊆ D, (14) ∼X P is a binary relation on the elements of X that is reflexive and sym- metric (but not necessarily transitive). In this framework, we say that Room A is empty is tolerantly true just in case Room A contains a number of objects that do not cause us to make a distinction between it and a completely empty room in the context. For the pur- poses of the analyses in this paper, I will suppose that classical satisfaction and classical denotations correspond to regular semantic satisfaction and semantic denotations, while tolerant and strict satisfaction and denotations correspond to pragmatic notions7 . The three notions of satisfaction are defined (informally) within a comparison-class-based system8 as shown below. Definition 8. Classical (JKc ), tolerant (JKt ), and strict (JKs ) interpreta- tion of predicates. For all scalar adjectives P and X ⊆ D, 1. JP KcX ⊆ X. 2. JP KtX = {x : ∃d ∼X c P x and d ∈ JP KX }. s X c 3. JP KX = {x : ∀d ∼P x, d ∈ JP KX }. Definition 9. Classical, tolerant, and strict satisfaction. For all individ- uals a, scalar predicates P , and comparison classes X ⊆ D, t/c/s t/c/s (15) Ja is PKX = 1 iff JaK ∈ JP KX . The definitions of the tolerant and strict comparative relations are parallel to the classical comparative (definition 2). Definition 10. Classical/tolerant/strict comparative (informal). For two t/c/s individuals a, b and a scalar adjective P , Ja is P-er than bKt/c/s = 1 iff a >P b, t/c/s where >P is defined as: 7 As such, my interpretation of the framework bares many similarities with [9]’s Prag- matic Halos approach to modelling “pragmatic slack” or “loose talk”. 8 Note that, in his 1980 paper, Klein adopts a supervaluationist account of the vague- ness of scalar adjectives. Thus, the integration of Klein’s basic semantics for the comparative construction with a similarity-based account of vagueness is a depar- ture from the system presented in [8]. 8 Heather Burnett t/c/s t/c/s (16) x >P y iff there is some comparison class X such that x ∈ JP KX t/c/s / JP KX . and y ∈ The precise definition of TCS, set within a comparison-class-based approach to the semantics of scalar terms, is given in the appendix. 5 Analysis of Absolute Adjectives In order to account for how AAs can have, at the same time, a semantic de- notation that is constant across CCs, but at the same time be associated with non-trivial scales, I propose that what can vary across CCs are the indifference relations i.e., the ∼XQ s. For example, if I compare Homer Simpson, who has ex- actly two hairs, directly with Yul Brynner (who has zero hairs), the two would not be considered indifferent with respect to baldness (Homer has hair!). How- ever, if I add Marge Simpson into the comparison class (she has a very large hairdo), then Yul and Homer start looking much more similar, when it comes to baldness. Thus, I propose, it should be possible to order individuals with respect to how close to being completely bald (or empty or straight) they are by look- ing at in which comparison classes they are considered indifferent to completely bald/empty/straight individuals9 . In what follows, I present a set of axioms that constrain indifference relations between individuals across comparison classes. Recall that I proposed that, un- like relative adjectives which are only subject to van Benthem’s axioms (NR, UD, and DD), absolute adjectives are subject to the AAA. Then, in the spirit of [1] and [13], I will show that these axioms will allow us to construct non-trivial strict weak orders from the tolerant meaning of absolute predicates10 . 5.1 Pragmatic Axiom Set I propose the following axioms to constrain indifference relations11 . 9 The idea is conceptually similar in some sense (although extremely different in its execution) to a suggestion made by [12], with respect to how an adjective like empty can be both absolute and gradable. 10 For lack of space, I will only address the analysis of so-called total or universal AAs like empty, bald, and straight. However, the analysis of partial/existential AAs like dirty and wet is essentially the dual of the analysis of total AAs, with non-trivial scales being constructed out of strict denotations instead of tolerant ones. See [3] for discussion. 11 One of the axioms (T-NS) makes reference to a ‘tolerantly greater than or equal relation’ (≥tQ ): We first define an equivalence relation ≈P : Definition 11. Tolerantly Equivalent. (≈t ) For a predicate Q and a, b ∈ D, (i) a ≈tQ b iff a 6>tQ b and b 6>tQ a. Now we define ≥t : A Multi-Valued Delineation Semantics for Absolute Adjectives 9 (17) Tolerant No Skipping (T-NS): For an AA Q, X ∈ P(D) and x, y ∈ X, if x ∼X t t Q y and there is some z ∈ X such that x ≥Q z ≥Q y, then X x ∼Q z. Tolerant No Skipping says that, if person A is indistinguishable from person B, and there’s a person C lying in between persons A and B on the relevant tolerant scale, then A and C (the greater two of {A, B, C}) are also indistin- guishable. As discussed in the appendix, T-NS performs a very similar function to van Benthem’s No Reversal. We now have two axioms that talk about how indifference relations can change across comparison classes. I call these the granularity axioms. (18) Granularity 1 (G1): For an AA Q, X ∈ P(D), and x, y ∈ X, if 0 0 X0 x ∼X Q y, then for all X ⊆ D : X ⊆ X , x ∼Q y. G1 says that if person A and person B are indistinguishable in comparison class X, then they are indistinguishable in all supersets of X. This is meant to reflect the fact that the larger the domain is (i.e. the larger the comparison class is), the more things can cluster together12 . (19) Granularity 2 (G2): For an AA Q, X, X 0 ⊆ D, and x, y ∈ X, if X0 X0 X ⊂ X 0 and x 6∼X 0 Q y and x ∼Q y, then ∃z ∈ X − X : x 6∼Q z. G2 says that, if person A and person B are distinguishable in one CC, X, and then there’s another CC, X’, in which they are indistinguishable, then there is some person C in X’-X that is distinguishable from person A. This axiom is similar in spirit to van Benthem’s Upward Difference in that it ensures that, if there is a contrast/distinction in one comparison class, the existence of contrast is maintained in all the larger CCs. The final axiom that we need is Minimal Difference: (20) Minimal Difference (MD): For an AA Q and x, y ∈ D, if x >cQ y, {x,y} then x 6∼Q y. Minimal Difference says that, if, at the finest level of granularity, you would make a classical distinction between two individuals, then they are not indistinguishable at that level of granularity. MD is similar in spirit to van Ben- them’s Downward Difference because it allows us to preserve contrasts down to the smallest comparison classes. With these axioms, we can prove the main result of the paper (which is proved in the appendix): Definition 12. Tolerantly greater than or equal. (≥t ) For a, b ∈ D, (ii) a ≥tQ b iff a >tQ b or a ≈tQ b. 12 G1 can be weakened a bit to allow some indifference relations to be undone in larger CCs. In this case, we derive semi-orders instead of strict weak orders (cf. [3]). 10 Heather Burnett (21) Theorem 3. If Q is an absolute adjective, then >tQ is a strict weak order. 6 Conclusion In this paper, I gave a new analysis of the semantics and pragmatics of ab- solute adjectives, and, in particular, I addressed the question of how AAs can have a non-context-sensitive semantic denotation but still be gradable with a delineation framework. I showed that the scales (i.e. strict weak orders) that are associated with absolute predicates can be derived in within the multi-valued delineation TCS system from certain intuitive statements about how individu- als can and cannot be indifferent across comparison classes. Thus, I argue that the puzzles raised by absolute adjectives for the delineation approach can be solved, provided that we have an appropriate framework to treat vagueness and imprecision. References 1. J. van Benthem. (1982). “Later than late: On the logical origin of the temporal order”. Pacific Philosophical Quarterly, 63:193203. 2. J. van Benthem. (1990). The Logic of Time. Dordrecht: Reidel. 3. H. Burnett. (2012). The Grammar of Tolerance: On Vagueness, Context-Sensitivity, and the Origin of Scale Structure. PhD Dissertation. UCLA. ´ e, D. Ripley, and R. van Rooij. (2011). “Tolerant, Classical, 4. P. Cobreros, P. Egr´ Strict.” Journal of Philosophical Logic. (forthcoming). 5. D. Fara. (2000). “Shifting Sands: An interest-relative theory of vagueness.” Philo- sophical Topics. 20: 45-81. 6. C. Kennedy. (2007). “Vagueness and Grammar: The study of relative and absolute gradable predicates.” Linguistics and Philosophy. 30: 1-45. 7. C. Kennedy and L. McNally. (2005). “Scale structure and the semantic typology of gradable predicates”. Language. 81:345-381. 8. E. Klein. (1980). “A semantics for positive and comparative adjectives”. Linguistics and Philosophy. 4:1-45. 9. P. Lasersohn. (1999). “Pragmatic Halos.” Language. 75: 522-571. 10. D. Lewis. (1979). “Score-keeping in a language game”. Journal of Philosophical Logic, 8: 339-359. 11. M. Pinkal. (1995). Logic and Lexicon. Dordrecht: Kluwer Academic Publishers. 12. F. R´ecanati. (2010). Truth-Conditional Pragmatics. Oxford: OUP. 13. R. van Rooij. (2011). “Vagueness and Linguistics”. In G Ronzitti, editor, The vagueness handbook, Dordrecht: Springer. pp. 1-57. 14. R. van Rooij. (2011). “Implicit vs explicit comparatives”. In Paul Egr´e and Nathan Klinedinst (eds.), Vagueness and Language Use, Palgrave Macmillan. 15. K. Syrett et al. (2010). “Meaning and context in children’s understanding of grad- able adjectives”. Journal of Semantics, 27:1-35. 16. P. Unger. (1975). Ignorance. Oxford: Clarendon Press. A Multi-Valued Delineation Semantics for Absolute Adjectives 11 7 Appendix: Framework and Proofs 7.1 The Framework: Delineation TCS Language Definition 13. Vocabulary. The vocabulary consists of the following expres- sions: 1. A series of individual constants: a1 , a2 , a3 . . . 2. A series of individual variables: x1 , x2 , x3 . . . 3. Two series of unary predicate symbols: – Relative scalar adjectives: P1 , P2 , P3 . . . – Absolute scalar adjectives: Q1 , Q2 , Q3 . . . 4. For every unary predicate symbol P , there is a binary predicate >P . 5. Quantifiers and connectives ∀, ∨ and ¬, plus parentheses. Definition 14. Syntax. 1. Variables and constants (and nothing else) are terms. 2. If t is a term and P is a predicate symbol, then P (t) is a well-formed formula (wff ). 3. If t1 and t2 are terms and P is a predicate symbol, then t1 >P t2 is a wff. 4. For any variable x, if φ and ψ are wffs, then ¬φ, φ ∨ ψ, and ∀xφ are wffs. 5. Nothing else is a wff. Semantics Definition 15. C(lassical)-model. A c-model is a tuple M = hD, mi where D is a non-empty domain of individuals, and m is a function from pairs consisting of a member of the non-logical vocabulary and a comparison class (a subset of the domain) satisfying: – For each individual constant a1 , m(a1 ) ∈ D. – For each X ∈ P(D) and for each predicate P , m(P, X) ⊆ X. Definition 16. T(olerant)-model. A t-model is a tuple M = hD, m, ∼i, where hD, mi is a model and ∼ is a function from predicate/comparison class pairs such that: – For all P and all X ∈ P(D), ∼X P is a binary relation on X that is reflexive, symmetric, but not necessarily transitive. Definition 17. Assignment. An assignment for a c/t-model M is a function g : {xn : n ∈ N} → D (from the set of variables to the domain D). Definition 18. Interpretation. An interpretation J·KM,g is a pair hM, gi, where M is a t-model, and g is an assignment. 12 Heather Burnett Definition 19. Interpretation of terms (J·KM,g ). For a model M , an assign- ment g, 1. If x1 is a variable, Jx1 KM,g = g(x1 ). 2. If a1 is a constant, Ja1 KM,g = m(a1 ). In what follows, for an interpretation J·KM,g , a variable x1 , and a constant a1 , let g[a1 /x1 ] be the assignment for M which maps x1 to a1 , but agrees with g on all variables that are distinct from x1 . Definition 20. Classical Satisfaction (J·Kc ). For all interpretations J·KM,g , all X ∈ P(D), all formulas φ, ψ, all predicates P , and all terms t1 , t2 ,   1 if Jt1 KM,g ∈ m(P, X) c 1. JP (t1 )KM,g,X = 0 if Jt1 KM,g ∈ X − m(P, X)   i otherwise ( c 1 if there is some X 0 ⊆ D : JP (t1 )KcM,g,X 0 = 1 and JP (t2 )KcM,g,X 0 = 0 2. Jt1 >P t2 KM,g,X = 0 otherwise   c 1 if JφKM,g,X = 0 3. J¬φKcM,g,X = 0 if JφKcM,g,X = 1   i otherwise   c c 1 if JφKM,g,X = 1 or JψKM,g,X = 1 4. Jφ ∨ ψKcM,g,X = 0 if JφKcM,g,X = JψKcM,g,X = 0   i otherwise  c 1 if for every a1 ∈ X, JφKM,g[a1 /x1 ],X = 1  5. J∀x1 φKcM,g,X = 0 if for some a1 ∈ X, JφKcM,g[a1 /x1 ],X = 0   i otherwise Definition 21. Tolerant Satisfaction(J·Kt ). For all interpretations J·KM,g , all X ∈ P(D), all formulas φ, ψ, all predicates P , and all terms t1 , t2 ,   X c 1 if there is some a1 ∼P Jt1 KM,g : JP (a1 )KM,g,X = 1 t 1. JP (t1 )KM,g,X = 0 if Jt1 KM,g ∈ X, and there is no a1 ∈ X : a1 ∼X P Jt1 KM,g   i otherwise ( 1 if there is some X 0 ⊆ D : JP (t1 )KtM,g,X 0 = 1 and JP (t2 )KtM,g,X 0 = 0 2. Jt1 >P t2 KtM,g,X = 0 otherwise   s 1 if JφKM,g,X = 0 3. J¬φKtM,g,X = 0 if JφKsM,g,X = 1   i otherwise   t t 1 if JφKM,g,X = 1 or JψKM,g,X = 1 4. Jφ ∨ ψKtM,g,X = 0 if JφKtM,g,X = JψKtM,g,X = 0   i otherwise A Multi-Valued Delineation Semantics for Absolute Adjectives 13   1 if for every a1 ∈ X, JφKtM,g[a1 /x1 ],X = 1 5. J∀x1 φKtM,g,X = 0 if for some a1 ∈ X, JφKtM,g[a1 /x1 ],X = 0   i otherwise Definition 22. Strict Satisfaction(JKs ). For all interpretations J·KM,g , all X ∈ P(D), all formulas φ, ψ, all predicates P , and all terms t1 , t2 ,   X c 1 if for all a1 ∼P Jt1 KM,g : JP (a1 )KM,g,X = 1 1. JP (t1 )KsM,g,X = 0 if Jt1 KM,g ∈ X, and there is no a1 ∈ X : a1 ∼X P Jt1 KM,g   i otherwise ( s 1 if there is some X 0 ⊆ D : JP (t1 )KsM,g,X 0 = 1 and JP (t2 )KsM,g,X 0 = 0 2. Jt1 >P t2 KM,g,X = 0 otherwise   t 1 if JφKM,g,X = 0 3. J¬φKsM,g,X = 0 if JφKtM,g,X = 1   i otherwise   s s 1 if JφKM,g,X = 1 or JψKM,g,X = 1 4. Jφ ∨ ψKsM,g,X = 0 if JφKtM,g,X = JψKtM,g,X = 0   i otherwise  s 1 if for every a1 ∈ X, JφKM,g[a1 /x1 ],X = 1  s s 5. J∀x1 φKM,g,X = 0 if for some a1 ∈ X, JφKM,g[a1 /x1 ],X = 0   i otherwise 13 Proposed Axioms for AAs (22) Absolute Adjective Axiom (AAA): For all X ∈ P(D) and a1 ∈ X, JQ1 (a1 )KcM,g,X = 1 iff JQ1 (a1 )KcM,g,D = 1. (23) Tolerant No Skipping (T-NS): For an AA Q1 , X ∈ P(D) and a1 , a2 ∈ X, if a1 ∼X Q1 a2 and there is some a3 ∈ X such that Ja1 ≥Q1 a3 JM,g,X = 1 and Ja3 ≥Q1 a2 KtM,g,X = 1, then a1 ∼X t Q1 a3 . (24) Granularity 1 (G1): For an AA Q1 , X ∈ P(D), and a1 , a2 ∈ X, if 0 0 X0 a1 ∼X Q1 a2 , then for all X ∈ P(D) : X ⊆ X , a1 ∼Q1 a2 . (25) Granularity 2 (G2): For an AA Q1 , X, X 0 ∈ P(D), and a1 , a2 ∈ X, if X0 X0 X ⊂ X 0 and a1 6∼X 0 Q1 a2 and a1 ∼Q1 a2 , then ∃a3 ∈ X − X : a1 6∼Q1 a3 . (26) Minimal Difference (MD): For an AA Q1 and a1 , a2 ∈ D, if Ja1 >Q1 {x,y} a2 KcM,g,X = 1, then a1 6∼Q1 a2 . 13 Tolerantly greater than or equal. (≥t ) For an interpretation J·KM,g,X , a predicate P , a1 , a2 ∈ D, a1 ≥tP a2 iff Ja1 >P a2 KtM,g,X = 1 or a1 ≈tP a2 . 14 Heather Burnett 7.2 Proofs Firstly, Minimal Difference ensures that classical absolute denotations are sub- sets of tolerant denotations: Lemma 1. Tolerant Subset. If Q ∈ AA, then, for all X ⊆ D, a1 , a2 ∈ D, if Ja1 >Q a2 KcM,g,X , then Ja1 >Q a2 KtM,g,X . Proof. Suppose Ja1 >Q a2 KcM,g,X . Then, by definition 20, there is some X 0 ⊆ D such that JQ(a1 )KcM,g,X 0 = 1 and JQ(a2 )KcM,g,X 0 = 0. Now consider {a1 , a2 }. By downward difference, JQ(a1 )KcM,g,{a1 ,a2 } = 1 and JQ(a2 )KcM,g,{a1 ,a2 } = 0. By the definition of JKt , JQ(a1 )KtM,g,{a1 ,a2 } = 1. Furthermore, by Minimal Difference, {a ,a2 } a1 6∼Q 1 a2 . So JQ(a2 )KtM,g,{a1 ,a2 } = 0. By definition 21, Ja1 >Q a2 KtM,g,X . t u Secondly, with only T-No Skipping, we can prove that a version of van Ben- tham’s No Reversal holds at the tolerant level. Lemma 2. Tolerant No Reversal (T-NR): For X ⊆ D, and a1 , a2 ∈ D if JQ(a1 )KtM,g,X = 1 and JQ(a2 )KtM,g,X = 0, then there is no X 0 ⊆ D such that JQ(a2 )KtM,g,X 0 = 1 and JQ(a1 )KtM,g,X 0 = 0. Proof. Suppose JQ(a1 )KtM,g,X = 1 and JQ(a2 )KtM,g,X = 0. Suppose, for a contra- diction that there is an X 0 ⊆ D such that JQ(a2 )KtM,g,X 0 = 1 and JQ(a1 )KtM,g,X 0 = 0. Therefore, Ja1 >Q a2 KtM,g,X = 1 and Ja2 >Q a1 KtM,g,X = 1. Furthermore, by assumption and definition 21, there is some a3 ∼X c Q a1 such that JQ(a3 )KM,g,X = X t c 1, and a3 6∼Q a2 . Since JQ(a1 )KM,g,X 0 = 0, by the AAA, JQ(a1 )KM,g,X 0 = 0. So Ja3 >Q a2 KcM,g,X = 1. By lemma 1, Ja3 >Q a2 KtM,g,X = 1, and so Ja3 >Q a2 KtM,g,X = 1 and Ja2 >Q a1 KtM,g,X = 1. Since a3 ∼X Q a1 , by No Skipping, a3 ∼X Q 2a . ⊥ t u Using the complete axiom set {NS, G1, G2, MD}, we can show that, for all Q ∈ AA, the tolerant comparative (>tQ ) is a strict weak order. Lemma 3. Irreflexivity. For all X ⊆ D and a1 ∈ D, Ja1 >Q a1 KtM,g,X = 0. Proof. Since it is impossible, for any X ⊆ D, for an element to be both in JQKtM,g,X and not in JQKtM,g,X , by definition 21, >tQ is irreflexive. t u Lemma 4. Transitivity. For all X ⊆ D and a1 , a2 , a3 ∈ D, if Ja1 >Q a2 KtM,g,X = 1 and Ja2 >Q a3 KtM,g,X = 1, then Ja1 >Q a3 KtM,g,X = 1. Proof. Suppose Ja1 >Q a2 KtM,g,X = 1 and Ja2 >Q a3 KtM,g,X = 1 to show that Ja1 >Q a3 KtM,g,X = 1. Then there is some X 0 ⊆ D such that JQ(a1 )KtM,g,X 0 = 1 and JQ(a2 )KtM,g,X 0 = 0. Thus, there is some a4 ∈ X 0 : JQ(a4 )KcM,g,X 0 = 1, and 0 0 a4 ∼XQ a1 . Now consider X ∪ {a3 }. By the AAA and the assumption that Ja1 >Q a2 KM,g,X = 1 and Ja2 >Q a3 KtM,g,X = 1, JQ(a2 )KcM,g,X∪{a3 } = 0 and t A Multi-Valued Delineation Semantics for Absolute Adjectives 15 JQ(a3 )KcM,g,X 0 ∪{a3 } = 0. Case 1: X 0 ∪ {a3 } = X 0 . Since JQ(a3 )KtM,g,X 0 = 1 and JQ(a2 )KtM,g,X 0 = 0, by theorem 2, JQ(a3 )KtM,g,X 0 = 0, and Ja1 >Q a3 KtM,g,X = 1. X Case 2: X 0 ∪{a } X 0 ⊂ X 0 ∪ {a3 }. Since X 0 ⊂ X 0 ∪ {a3 } and a4 ∼X Q a1 , by G1, a4 ∼Q 3 a1 . c t By the AAA, JQ(a4 )KM,g,X 0 ∪{a3 } = 1. So JQ(a1 )KM,g,X∪{a3 } = 1. Suppose, for a contradiction that JQ(a3 )KtM,g,X 0 ∪{a3 } = 1. Then there is some a5 ∈ X0 ∪{a } X 0 ∪ {a3 } : JQ(a5 )KcM,g,X 0 ∪{a3 } = 1 and a5 ∼Q 3 a3 . By assumption and since JQ(a2 )KM,g,X 0 , by MD, Ja5 >Q a2 KM,g,X = 1 and Ja2 >Q a3 KtM,g,X = 1. So c t X 0 ∪{a3 } 0 by T- No Skipping, a5 ∼Q a2 . Since JQ(a2 )KtM,g,X 0 = 0, a5 6∼X Q a2 . So by X0 ∪{a3 } G2, since X 0 ∪ {a3 } − X 0 = {a3 }, a5 6∼Q a3 . ⊥. So JQ(a3 )KtM,g,X 0 ∪{a3 } = 0, and Ja1 >Q a3 KtM,g,X = 1. X t u Lemma 5. Almost Connectedness. For all X ⊆ D and a1 , a2 ∈ D, if Ja1 >Q a2 KtM,g,X = 1 then for all a3 ∈ D, either Ja1 >Q a3 KtM,g,X = 1 or Ja3 >Q a2 KtM,g,X = 1. Proof. Let Ja1 >Q a2 KtM,g,X = 1 and Ja3 >Q a2 KtM,g,X = 0 to show Ja1 >Q a3 KtM,g,X = 1. Case 1: JQ(a1 )KcM g,D = 1. Since Ja1 >Q a2 KtM,g,X = 1 and Ja3 >Q a2 KtM,g,X = 0, JQ(a3 )KcM,g,D = 0. So Ja1 >Q a3 KcM,g,X = 1, and, by lemma 1, Ja1 >Q a3 KtM,g,X = 1. X Case 2: JQ(a1 )KcM g,D = 0. Since Ja1 >Q a2 KtM,g,X = 1, there is some X 0 ⊆ D such that JQ(a1 )KtM,g,X 0 = 1 and JQ(a2 )KtM,g,X 0 = 0. So there is some 0 a4 ∈ X 0 : JQ(a4 )KcM,g,X 0 = 1 and a4 ∼X 0 Q a1 . Now consider X ∪ {a3 }. Since t c c Ja3 >Q a2 KM,g,X = 0, JQ(a1 )KM,g,X 0 ∪{a3 } = 0 and JQ(a2 )KM,g,X 0 ∪{a3 } = 0 0 X 0 ∪{a } and JQ(a3 )KcM,g,X 0 ∪{a3 } = 0. Since a4 ∼X Q a1 , by G1, a4 ∼Q 3 a1 and by c t the AAA, JQ(a4 )KM,g,X 0 ∪{a3 } = 1. So, by definition 21, JQ(a1 )KM,g,X 0 ∪{a3 } = 1. Now suppose for a contradiction that JQ(a3 )KtM,g,X 0 ∪{a3 } = 1. Then there X0 ∪{a } is some a5 ∈ X 0 ∪ {a3 } : JQ(a5 )KcM,g,X 0 ∪{a3 } = 1 and a5 ∼Q 3 a3 . Since c c c JQ(a5 )KX 0 ∪{a3 } = 1 and JQ(a2 )KX 0 ∪{a3 } = 0, Ja5 >Q a2 KM,g,X = 1; so by lemma 1, Ja5 >Q a2 KtM,g,X = 1. Furthermore, since, by assumption, Ja3 >Q a2 KtM,g,X = 0, Ja2 ≥Q a3 KtM,g,X = 1. Since Ja5 ≥Q a2 KtM,g,X = 1 and Ja2 ≥Q a3 KtM,g,X = 1, X 0 ∪{a } 3 3 X 0 ∪{a } and a5 ∼Q a3 , by Tolerant No Skipping, a5 ∼Q a2 . However, since 0 JQ(a2 )KtM,g,X 0 = 0, and by the AAA, JQ(a5 )KcM,g,X 0 = 1, a5 6∼X Q a2 . Since X 0 ∪{a3 } X 0 ⊂ X 0 ∪ {a3 } and a5 ∼Q a2 , by G2, there is some a6 ∈ X 0 ∪ {a3 } − X 0 0 X ∪{a } X0 ∪{a3 } such that a6 6∼Q 3 a3 . Since X 0 ∪ {a3 } − X 0 = {a3 }, a5 6∼Q a3 . ⊥ So JQ(a3 )KtM,g,X 0 ∪{a3 } = 0 and Ja1 >Q a3 KtM,g,X = 1. X t u We can now prove the main theorem of the paper: Theorem 3. If Q is an absolute adjective, <tQ is a strict weak order. Proof. Immediate from lemmas 3, 4 and 5. t u  Are True and False Not Enough?? Vincent Degauquier Université catholique de Louvain, Institut supérieur de Philosophie Place du Cardinal Mercier 14, 1348 Louvain-la-Neuve, Belgium [email protected] Abstract. Trivalent logic is usually interpreted as a non-classical logic that violates the principle of bivalence. However, this logic can also be interpreted as a bivalent logic that ignores either the principle of com- pleteness or the principle of consistency. In light of these bivalent inter- pretations, the three-valued interpretation can be understood either in a paraconsistent or paracomplete perspective. With this in mind, we inves- tigate the semantic and proof-theoretic relationships between the para- consistent and paracomplete conceptions of trivalent logic. More specifi- cally, our purpose is to provide a unified framework for characterizing the notion of logical consequence specific to these conceptions. To do this, we propose a notion of validity and an associated hypersequent-inspired calculus for each of the two conceptions of trivalent logic. Keywords: bivalence, completeness, consistency, logical consequence, sequent calculus. Introduction Logic is traditionally defined according to underlying principles. Among them, three seem particularly important. The principle of bivalence (understood in its etymological sense) says that there are exactly two truth values, usually called True and False. The principle of completeness states that a sentence has at least one truth value. The principle of consistency states that a sentence has at most one truth value. A logic that satisfies the conjunction of these three principles is called classical. By contrast, a logic is called non-classical if it does not obey at least one of them. In relation to these principles, trivalent logic is usually interpreted as a non- classical logic that violates the principle of bivalence but requires the addition of the principles of completeness and consistency. However, this logic can also be interpreted as a bivalent logic that ignores exactly one of these last two principles. In light of the bivalent interpretations, the three-valued interpretation can be understood either in a paraconsistent or paracomplete perspective. Depending on which viewpoint is embraced, the meaning of the third truth value is different. ? This is an abridged and slightly modified version of the paper ‘Cuts, Gluts and Gaps’ due to appear in Logique et Analyse. 18 Vincent Degauquier By means of these bivalent interpretations, we investigate the semantic and proof-theoretic relationships between the paraconsistent and paracomplete con- ceptions of trivalent logic. More specifically, our purpose is to provide a unified framework for characterizing the notion of logical consequence within each of these conceptions. To do this, we identify the core of the notion of logical con- sequence common to these two conceptions of trivalent logic. The proof-theoretic approach we have chosen is sequent calculus. We propose a notion of validity and an associated hypersequent-inspired calculus for each of the two aforementioned conceptions of trivalent logic. In order to develop a theoretical framework broad enough to reach the core of the trivalent notion of logical consequence, we make use of a generalized notion of sequent closely related to that of hypersequent. In this way, we will identify the rules common to the paraconsistent and paracomplete trivalent calculi as well as the rules specific to each of them. 1 Language A first-order predicate language L is composed of a countable set of symbols consisting of a non-empty set of n-ary relation symbols, a set of n-ary function symbols, a countable set of variables and the usual logical symbols (¬, ∧, ∨, →, ∀ and ∃). The nullary function symbols are called constants and the nullary relation symbols are called propositional symbols. As for syntax, the notions of term and formula are defined in the usual way. Nevertheless, formulas equivalent up to their bound variables are identified so that their bound variables are supposed to be Bourbaki’s squares. In this way, any occurrence of a variable in a formula is free. The substitution operation is defined as follows: If A is a formula, α1 , ..., αn are distinct variables and t1 , ..., tn are terms, then A[α1 := t1 , ..., αn := tn ] denotes the formula resulting from the simultaneous substitution of ti for αi in A, for all i (1 ≤ i ≤ n). 2 Bivalent logics Three bivalent logics differ from classical logic insofar as they ignore the princi- ple of completeness and/or the principle of consistency: consistent logic (which is closely related to Kleene’s strong three-valued logic) satisfies the principle of consistency, complete logic (which is closely related to Priest’s logic of para- dox) satisfies the principle of completeness and positive logic (which is closely related to Belnap’s useful four-valued logic) ignores both of these principles. In addition to classical logic, three bivalent (non-classical) logics can therefore be distinguished. A bivalent model M (simply called model hereafter) for a language L is composed of a structure for L and an interpretation of the proper symbols of L in this structure (see [4]). A structure for L consists of a universe, a set of relations on this universe and a set of functions defined on this universe and with values in this universe. Are True and False not Enough? 19 For every n ∈ N, if L has n-ary relation symbols, the structure must have at least one n-ary relation. For every n ∈ N, if L has n-ary function symbols, the structure must have at least one n-ary function. The universe |M| of a model M is a non-empty set. An n-ary relation R is an ordered pair of subsets of |M| such that R = hR+ , R− i. The first term n of the ordered pair denotes the set of n-tuples of elements of the universe that verify the relation R and the second term of the ordered pair denotes the set of n-tuples of elements of the universe that falsify the relation. An interpretation of L assigns an object in the universe to every constant, an n-ary function defined on the universe to every n-ary function symbol of L and an n-ary relation to every n-ary relation symbol of L. The interpretation of an n-ary relation symbol R of L in the universe of the  model M is denoted RM n + and is equated to the ordered pair (R )M , (R )M of subsets of |M| . n − n A valuation is an assignment of objects to variables. If v is a valuation, α~ is a sequence of distinct variables α1 , ..., αn and ~o is a sequence of elements o1 , ..., on in |M|, then v[~ α 7→ ~o] is the valuation that differs from v insofar as the variable αi denotes the element oi , for all i (1 ≤ i ≤ n). More specifically, the valuation v[~α 7→ ~o] is defined as follows: – v[~ α 7→ ~o](β) = oi , if β is the same variable as αi (1 ≤ i ≤ n). – v[~ α→ 7 ~o](β) = v(β), if β is distinct from every αi (1 ≤ i ≤ n). By combining a valuation v and an interpretation of constants and function symbols in M, all terms of the language are given a value. The joint extension of interpretation and valuation is denoted vM . Moreover, if ~t is a sequence of terms t1 , ..., tn , then vM (~t) denotes the sequence vM (t1 ), ..., vM (tn ). It is required that: – vM (β) = v(β), for every variable β. – vM (F ~t) = FM (vM (~t)), for every n-ary function symbol F . Truth and falsity of a formula A are defined in a model under a valuation. Given a model M and a valuation v, truth (denoted by M + v A) and falsity (denoted by M − v A) of formulas of the language are defined inductively: + M + v Rt1 ...tn if and only if hvM (t1 ), ..., vM (tn )i ∈ RM M v Rt1 ...tn if and only if hvM (t1 ), ..., vM (tn )i ∈ RM − − + M v ¬A if and only if M v A − + M − v ¬A if and only if M v A M v (A ∧ B) if and only if M + + v A and M v B + M v (A ∧ B) if and only if M v A and/or M − − − v B M + v (A ∨ B) if and only if M + v A and/or M + v B M v (A ∨ B) if and only if M v A and M v B − − − M + v (A → B) if and only if M v A and/or M v B − + + M v (A → B) if and only if M v A and M v B − − + M + v ∀α A if and only if M v[α7→o] A, for all o ∈ |M| M − v ∀α A if and only if M v[α7→o] A, for some o ∈ |M| − 20 Vincent Degauquier + M + v ∃α A if and only if M v[α7→o] A, for some o ∈ |M| v ∃α A if and only if M v[α7→o] A, for all o ∈ |M| M − − Remark 1. Although the notation might suggest it, the definitions of the connec- tives listed above are not equivalent to the usual definitions. By distinguishing truth from non-falsity and falsity from non-truth, the positive definitions of truth and falsity make the traditional definitions of logical connectives ambigu- ous. While it does not exist in classical logic, this ambiguity must be removed in a non-classical bivalent logic. It is therefore possible to propose several positive definitions corresponding to the classical definition of a connective but none of them fit perfectly with it. This translation problem is particularly acute in the cases of negation and implication. A model M is consistent if and only if (Rn )+ M ∩ (R )M = ∅, for every n-ary n − relation R on |M|. A model M is complete if and only if (Rn )+ M ∪(R )M = |M| , n − n for every n-ary relation R on |M|. In this sense, a model is called classical if and only if it is both consistent and complete. Fact 1 (Principle of completeness). Let M be a complete model. 1. if M 2+ v A, then M v A, for all formulas A. − 2. if M 2v A, then M + − v A, for all formulas A. Fact 2 (Principle of consistency). Let M be a consistent model. 1. if M + v A, then M 2v A, for all formulas A. − 2. if M v A, then M 2+ − v A, for all formulas A. Depending on whether a bivalent logic restricts the class of models to that of consistent, complete or classical models, this logic will be called consistent, com- plete or classical, respectively. In general, bivalent logic that takes into account the class of models without restriction is called positive. 3 Towards a third truth value Starting with a bivalent interpretation, the development of trivalent logic does not simply consist in adding a third truth value. Instead, it consists in giving new definitions of truth and falsity. In general, we can say that a formula is true in a many-valued logic if and only if it is both true and not false in bivalent logic. Similarly, we can say that a formula is false in a many-valued logic if and only if it is both false and not true in bivalent logic. As for the third truth value, two options are possible from the bivalent view- point. The consistent interpretation suggests that the third truth value in triva- lent logic is assigned to a formula if and only if it is neither true nor false in bivalent logic (see [7]). On the other hand, the complete interpretation suggests that the third truth value in trivalent logic is assigned to a formula if and only if it is both true and false in bivalent logic (see [9]). Are True and False not Enough? 21 This choice concerning the third truth value highlights the distinction be- tween paracomplete and paraconsistent interpretations of trivalent logic. In light of the bivalent interpretation, four new truth values can therefore be defined (see [2]). Let h{t, f, n, b}, ≤i be a lattice such that: tr @I@ @ n r @r b @ I @@  @ @r @ f Using the lattice above and assuming that t = f , f = t, n = n and b = b, an inductive definition of a many-valued model can be provided. A many-valued translation of a model M under a valuation v for a language L, denoted by MTv , is a function from the set of formulas of L to the set {t, f, n, b} such that: MTv (Rt1 ...tn ) = t if and only if M + v Rt1 ...tn and M 2v Rt1 ...tn − + Mv (Rt1 ...tn ) = f if and only if M 2v Rt1 ...tn and M − T v Rt1 ...tn MTv (Rt1 ...tn ) = n if and only if M 2+v Rt1 ...tn and M 2 − v Rt1 ...tn + Mv (Rt1 ...tn ) = b if and only if M v Rt1 ...tn and M v Rt1 ...tn T − MTv (¬A) = MTv (A) MTv (A ∧ B) = inf ({MTv (A), MTv (B)}) MTv (A ∨ B) = sup({MTv (A), MTv (B)}) MTv (A → B) = sup({MTv (A), MTv (B)}) MTv (∀α A) = inf ({MTv[α7→o] (A) | o ∈ |M|}) MTv (∃α A) = sup({MTv[α7→o] (A) | o ∈ |M|}) The following proposition establishes the correspondence between the bivalent interpretation and the many-valued interpretation of truth values. Proposition 1. For all formulas A: 1. MTv (A) = t if and only if M + v A and M 2v A − + 2. Mv (A) = f if and only if M 2v A and M − T v A 3. MTv (A) = n if and only if M 2+v A and M 2− v A + 4. Mv (A) = b if and only if M v A and M v A T − The many-valued translation of a model is called consistent, complete or classical if and only if its image is {t, f, n}, {t, f, b} or {t, f }, respectively. From proposition 1 and facts 1 and 2, it immediately follows that the many-valued translation of a model M is consistent, complete or classical if and only if M is consistent, complete or classical, respectively. 22 Vincent Degauquier For this reason, we will apply the term ‘positive logic’, without distinction, to the bivalent logic that takes into account the class of models without restriction and to the many-valued logic that takes into account the class of many-valued translations without restriction. Similarly, a many-valued logic that restricts the class of many-valued translations to that of consistent, complete or classical translations will simply be called consistent, complete or classical logic, respec- tively. 4 Sequent calculi A sequent is called valid, glut-valid, gap-valid and classic-valid if it is semanti- cally correct in positive logic, complete logic, consistent logic and classical logic, respectively. Similarly, a sequent is called derivable, glut-derivable, gap-derivable and classic-derivable if it is proof-theoretically correct in positive logic, complete logic, consistent logic and classical logic, respectively. A sequent is a quadruple hΠ, Γ, ∆, Σi, where Π, Γ , ∆ and Σ are finite mul- tisets over the set of formulas of the language (see [1], [6] and [8]). The sequent hΠ, Γ, ∆, Σi is denoted Π; Γ ∆; Σ. A multiset is a sequence modulo the or- dering. More specifically, a multiset M over S is an ordered pair hS, f i, where S is a set and f : S → N is a function that indicates the multiplicity of each element of S. The underlying set of a multiset M = hS, f i is the set µ such that µ = {s ∈ S | f (s) 6= 0}. M is called finite, if µ is finite, and M is called empty, if µ is empty. The notation M 6= ∅ means that M is not empty. Let M1 and M2 be multisets such that M1 = hS, f1 i and M2 = hS, f2 i. M is the intersection of M1 and M2 , denoted M1 ∩ M2 , if M = hS, f i is a multiset, where f (s) = f1 (s), if f1 (s) ≤ f2 (s), and f (s) = f2 (s), if f2 (s) ≤ f1 (s), for all s ∈ S. M is the union of M1 and M2 , denoted M1 ∪ M2 , if M = hS, f i is a multiset, where f (s) = f1 (s) + f2 (s), for all s ∈ S. The multisets M1 ∪ M2 and hS, f i, where {s ∈ S | f (s) 6= 0} = {A} and f (A) = 1, are denoted M1 , M2 and A, respectively. Let Π; Γ ∆; Σ be a sequent such that π, γ, δ and σ are the underlying sets of Π, Γ , ∆ and Σ, respectively. Then, Π; Γ ∆; Σ is valid if and only if + for every model M and valuation v, M 2− v A, for all A ∈ π, and M v A, for + all A ∈ γ, implies M v A, for some A ∈ δ, and/or M 2v A, for some A ∈ σ. − The definition of validity can be preserved for consistent and/or complete logics. Depending on whether the notion of valid sequent is restricted to consis- tent models or to complete models, a sequent is called gap-valid or glut-valid, respectively. If only the class of models which are both consistent and complete is taken into account, then a sequent is called classic-valid. For each bivalent logic, a sequent calculus and a notion of derivability cor- responding to that of validity are now set out. (A completeness proof for these sequent calculi is provided in [3].) The rules for these sequent calculi are as follows. The main feature of these rules is that the weakening and contraction structural rules are absorbed into the rules of inference (see [3]). Are True and False not Enough? 23 Π; Γ ∆; A, Σ Π, A; Γ ∆; Σ ¬iL ¬iR Π; Γ, ¬A ∆; Σ Π; Γ ¬A, ∆; Σ Π; Γ A, ∆; Σ Π; Γ, A ∆; Σ ¬eL ¬eR Π, ¬A; Γ ∆; Σ Π; Γ ∆; ¬A, Σ Π; Γ, A, B ∆; Σ Π; Γ A, ∆; Σ Π; Γ B, ∆; Σ ∧iL ∧iR Π; Γ, (A ∧ B) ∆; Σ Π; Γ (A ∧ B), ∆; Σ Π, A, B; Γ ∆; Σ Π; Γ ∆; A, Σ Π; Γ ∆; B, Σ ∧eL ∧eR Π, (A ∧ B); Γ ∆; Σ Π; Γ ∆; (A ∧ B), Σ Π; Γ, A ∆; Σ Π; Γ, B ∆; Σ Π; Γ A, B, ∆; Σ ∨iL ∨iR Π; Γ, (A ∨ B) ∆; Σ Π; Γ (A ∨ B), ∆; Σ Π, A; Γ ∆; Σ Π, B; Γ ∆; Σ Π; Γ ∆; A, B, Σ ∨eL ∨eR Π, (A ∨ B); Γ ∆; Σ Π; Γ ∆; (A ∨ B), Σ Π; Γ ∆; A, Σ Π; Γ, B ∆; Σ Π, A; Γ B, ∆; Σ →iL →iR Π; Γ, (A → B) ∆; Σ Π; Γ (A → B), ∆; Σ Π; Γ A, ∆; Σ Π, B; Γ ∆; Σ Π; Γ, A ∆; B, Σ →eL →eR Π, (A → B); Γ ∆; Σ Π; Γ ∆; (A → B), Σ Π; ∀αA, Γ, A[α := t] ∆; Σ i Π; Γ A[α := β], ∆; Σ i ∀L ∀R Π; Γ, ∀αA ∆; Σ Π; Γ ∀αA, ∆; Σ ∀αA, Π, A[α := t]; Γ ∆; Σ e Π; Γ ∆; A[α := β], Σ e ∀L ∀R Π, ∀αA; Γ ∆; Σ Π; Γ ∆; ∀αA, Σ Π; Γ, A[α := β] ∆; Σ i Π; Γ A[α := t], ∆, ∃αA; Σ i ∃L ∃R Π; Γ, ∃αA ∆; Σ Π; Γ ∃αA, ∆; Σ Π, A[α := β]; Γ ∆; Σ e Π; Γ ∆; A[α := t], Σ, ∃αA e ∃L ∃R Π, ∃αA; Γ ∆; Σ Π; Γ ∆; ∃αA, Σ The usual restrictions for the ∀iR , ∀eR , ∃iL and ∃eL rules hold. The eigenvariable β must not appear in the conclusion of these rules. The notion of derivation as well as those of initial sequent and endsequent are defined inductively in the usual way. Roughly speaking, a derivation is a finite rooted tree in which the nodes are sequents. The root of the tree (at the bottom) is called the endsequent and the leaves of the tree (at the top) are called initial sequents. The length of a derivation is the number of sequents in that derivation. A sequent is derivable if and only if there exists a derivation in which it is the endsequent and all initial sequents are axiomatic. A sequent Π; Γ ∆; Σ is axiomatic if and only if Γ ∩ ∆ 6= ∅ and/or Π ∩ Σ 6= ∅. The definition of derivable sequent can be preserved for consistent and/or complete logics by changing the definition of axiomatic sequent. A sequent is gap-derivable if and only if there exists a derivation in which it is the endsequent and all initial sequents are gap-axiomatic. A sequent Π; Γ ∆; Σ is gap-axiomatic if and only if it is axiomatic and/or Γ ∩ Σ 6= ∅. A sequent is glut-derivable if and only if there exists a derivation in which it is the endsequent and all initial sequents are glut-axiomatic. A sequent Π; Γ ∆; Σ is glut-axiomatic if and only if it is axiomatic and/or Π ∩ ∆ 6= ∅. 24 Vincent Degauquier Finally, a sequent is classic-derivable if and only if there exists a derivation in which it is the endsequent and all initial sequents are classic-axiomatic. A sequent Π; Γ ∆; Σ is classic-axiomatic if and only if it is gap-axiomatic and/or glut-axiomatic. 5 Unifying logical consequence Several formulations of the redundancy of cut are possible in the sequent calculi mentioned above. Indeed, four different forms of cut are distinguishable. Only two hold for positive sequent calculus while all of them hold for classical sequent calculus. As for complete and consistent sequent calculi, they only admit one form of cut in addition to the two that hold for positive sequent calculus. These results are contained in theorems 1 and 2. Only a sketch of the proofs is given here (for details, see [3]). Theorem 1. For all formulas A: 1. if Π; Γ A, ∆; Σ and Π; Γ, A ∆; Σ are derivable, then Π; Γ ∆; Σ is derivable. 2. if Π; Γ ∆; A, Σ and Π, A; Γ ∆; Σ are derivable, then Π; Γ ∆; Σ is derivable. Proof. The proof of the first assertion proceeds by a main induction on the complexity of A. When A is an atomic formula or when A is a quantified formula of the form ∃β B or ∀β B, the proof uses a subinduction on the sum of the derivation lengths of the sequents Π; Γ A, ∆; Σ and Π; Γ, A ∆; Σ. The weakening and contraction structural properties as well as the inversion property of inference rules are presupposed as proved. The second assertion is treated symmetrically. t u Theorem 2. For all formulas A: 1. if Π; Γ ∆; A, Σ and Π; Γ, A ∆; Σ are glut-derivable, then Π; Γ ∆; Σ is glut-derivable. 2. if Π; Γ A, ∆; Σ and Π, A; Γ ∆; Σ are gap-derivable, then Π; Γ ∆; Σ is gap-derivable. Proof. The proof is similar to that of theorem 1. t u According to the position of the cut formula, four different forms of the original cut rule can be distinguished (see [5]). Π; Γ ∆; A, Σ Π, A; Γ ∆; Σ cute−e Π; Γ ∆; Σ Π; Γ A, ∆; Σ Π; Γ, A ∆; Σ cuti−i Π; Γ ∆; Σ Are True and False not Enough? 25 Π; Γ ∆; A, Σ Π; Γ, A ∆; Σ cute−i Π; Γ ∆; Σ Π; Γ A, ∆; Σ Π, A; Γ ∆; Σ cuti−e Π; Γ ∆; Σ In view of theorems 1 and 2, it is interesting to note that the cute−e and cuti−i rules preserve derivability, glut-derivability, gap-derivability and classic- derivability. By contrast, the cute−i and cuti−e rules do not preserve derivability. In addition, the cute−i rule does not preserve gap-derivability and the cuti−e rule does not preserve glut-derivability. In other words, positive sequent calculus admits only cute−e and cuti−i , while complete and consistent sequent calculi admit, in addition to these rules, the cute−i and cuti−e rules, respectively. As for classical sequent calculus, it admits the four cut rules. Using the definition of axiomatic sequent, the weakening property and the- orem 2, the following propositions can be easily proved. Proposition 4 means that Π; Γ ∆; Σ is a classic-derivable sequent if and only if Π, Γ ∆, Σ is deducible in a classical sequent calculus of the usual kind. Proposition 2. For all formulas A: 1. if Π; Γ, A ∆; Σ is glut-derivable, then Π, A; Γ ∆; Σ is glut-derivable. 2. if Π; Γ ∆; A, Σ is glut-derivable, then Π; Γ A, ∆; Σ is glut-derivable. Proposition 3. For all formulas A: 1. if Π, A; Γ ∆; Σ is gap-derivable, then Π; Γ, A ∆; Σ is gap-derivable. 2. if Π; Γ A, ∆; Σ is gap-derivable, then Π; Γ ∆; A, Σ is gap-derivable. Proposition 4. For all formulas A: 1. Π; Γ, A ∆; Σ is classic-derivable if and only if Π, A; Γ ∆; Σ is classic- derivable. 2. Π; Γ ∆; A, Σ is classic-derivable if and only if Π; Γ A, ∆; Σ is classic- derivable. These properties can be expressed using the following rules. Π, A; Γ ∆; Σ Π; Γ A, ∆; Σ *L *R Π; Γ, A ∆; Σ Π; Γ ∆; A, Σ Π; Γ, A ∆; Σ Π; Γ ∆; A, Σ )L )R Π, A; Γ ∆; Σ Π; Γ A, ∆; Σ Propositions 2 and 3 assert, respectively, the admissibility of the )L/R rules in complete sequent calculus and the admissibility of the *L/R rules in con- sistent sequent calculus. By proposition 4, each of these rules is admissible in classical sequent calculus. However, the *L/R rules do not hold for complete sequent calculus and the )L/R rules do not hold for consistent sequent calculus. Moreover, none of them are admissible in positive sequent calculus. 26 Vincent Degauquier Proposition 5. Let Π; Γ ∆; Σ be a sequent. 1. Π; Γ ∆; Σ is glut-derivable if and only if Π; Γ ∆; Σ is provable in positive sequent calculus plus the additional rule cute−i . 2. Π; Γ ∆; Σ is gap-derivable if and only if Π; Γ ∆; Σ is provable in positive sequent calculus plus the additional rule cuti−e . 3. Π; Γ ∆; Σ is classic-derivable if and only if Π; Γ ∆; Σ is provable in positive sequent calculus plus the additional rules cute−i and cuti−e . Proposition 6. Let Π; Γ ∆; Σ be a sequent. 1. Π; Γ ∆; Σ is glut-derivable if and only if Π; Γ ∆; Σ is provable in positive sequent calculus plus the additional rules )L/R . 2. Π; Γ ∆; Σ is gap-derivable if and only if Π; Γ ∆; Σ is provable in positive sequent calculus plus the additional rules *L/R . 3. Π; Γ ∆; Σ is classic-derivable if and only if Π; Γ ∆; Σ is provable in positive sequent calculus plus the additional rules )L/R and *L/R . The foregoing propositions provide two different characterizations of the no- tions of glut-derivability, gap-derivability and classic-derivability obtained from the more general notion of derivability by adding rules. Proposition 5 under- lines the crucial part played by the cut properties in characterizing the notion of logical consequence within complete and/or consistent sequent calculi. Proposi- tion 6 makes the underlying principles of completeness and consistency explicit in the definitions of glut-axiomatic, gap-axiomatic and classic-axiomatic sequent. These two characterizations of the consistent and/or complete notions of logi- cal consequence not only allow us to identify the common thread between these notions, but also allow us to better understand the relationships between the notions of cut, completeness and consistency. References 1. Avron, A.: A constructive analysis of RM. The Journal of Symbolic Logic 52(4) (1987) 939–951 2. Belnap, N.D.: A useful four-valued logic. In Dunn, J.M., Epstein, G., eds.: Modern Uses of Multiple-Valued Logic. Reidel (1977) 8–37 3. Degauquier, V.: Recherches sur la bivalence. PhD thesis, Université catholique de Louvain (2011) 4. Dunn, J.M.: Intuitive semantics for first-degree entailments and ‘coupled trees’. Philosophical Studies 29(3) (1976) 149–168 5. Gentzen, G.: Untersuchungen über das logische Schließen. I. Mathematische Zeitschrift 39(1) (1935) 176–210 6. Girard, J.Y.: Three-valued logic and cut-elimination : the actual meaning of Takeuti’s conjecture. Dissertationes Mathematicae (Rozprawy Matematyczne) 136 (1976) 1–49 7. Kleene, S.C.: Introduction to metamathematics. Van Nostrand, New York (1952) 8. Muskens, R.: On partial and paraconsistent logics. Notre Dame Journal of Formal Logic 40(3) (1999) 352–374 9. Priest, G.: The logic of paradox. Journal of Philosophical Logic 8(1) (1979) 219–241  Modeling the Suppression Task under Three-Valued L � ukasiewicz and Well-Founded Semantics Emmanuelle-Anna Dietz,� Steffen H¨ olldobler�� International Center for Computational Logic, Technische Universit¨ at Dresden D-01062 Dresden, Germany Abstract. Two three-valued approaches for modeling human condi- tional reasoning are presented. The suppression task, a study from psy- chological reasoning, formalized by Stenning and van Lambalgen, is ex- amined. It is known that the suppression task is adequately solved using logic programs under the three-valued L � ukasiewicz semantics. In this paper we examine this approach and compare it with well-founded se- mantics. We show that, by some modification, both approaches yield to identical results for a specific class of programs. 1 Introduction Three-valued logics seem to be adequate for modeling some aspects of human reasoning as shown by Stenning and van Lambalgen [1]. They analyze the sup- pression task, a well-known experiment within cognitive science. In this psy- chological study, Byrne [2] has shown that graduate students with no previous exposure to formal logic did suppress previously drawn conclusions when addi- tional information became available. Interestingly, in some instances the previ- ously drawn conclusions were valid whereas in other instances the conclusions were invalid with respect to classical two-valued logic. Consider the following example: If she has an essay to finish then she will study late in the library and She has an essay to finish. Most subjects (96%) conclude: She will study late in the library. If subjects, however, receive an additional conditional: If the library stays open she will study late in the library then only 38% of them conclude: She will study late in the library. This shows, that, although the conclusion is still correct, the conclusion is suppressed by an additional conditional. This is an excellent example for human capability to draw non-monotonic inferences. Table 1 shows the abbreviations that will be used in this paper. The participants received conditionals (A, B, C) and facts E, ¬E, L, ¬L from which they had to draw inferences. Table 2 gives an account of the findings of the first part of the suppression task. Computational approaches modeling human reasoning must be classified regard- ing cognitive adequacy. We distinguish between conceptual and inferential mea- sures. In our context, a system is conceptually adequate if it appropriately rep- � [email protected] �� [email protected] 28 Emmanuelle-Anna Dietz and Steffen H¨ olldobler 2 Emmanuelle-Anna Dietz, Steffen H¨ olldobler Table 1. The suppression task and Table 2. The drawn conclusions of the used abbreviations. experiment of Byrne [2]. A If she has an essay to finish Conditional(s) Fact Exp. Findings then she will study late in the library. A E 96% conclude L. B If she has a textbook to read A, B E 96% conclude L. then she will study late in the library. A, C E 38% conclude L. C If the library stays open A ¬E 46% conclude ¬L. she will study late in the library. A, B ¬E 4% conclude ¬L. E She has an essay to finish. A, C ¬E 63% conclude ¬L. ¬E She does not have an essay to finish. L She will study late in the library. ¬L She will not study late in the library. resents human knowledge. Inferential adequacy measures whether the compu- tations behave similarly to human reasoning. It is straightforward to see that classical two-valued logic cannot model the suppression task adequately. At least a non-monotonic operator is needed. Stenning and van Lambalgen [1] suggest that human reasoning is modeled by, firstly, reasoning towards an appropriate representation or logical form (conceptual adequacy) and, secondly, reasoning with respect to this representation (inferential adequacy). As appropriate repre- sentation to model the suppression task, Stenning and van Lambalgen propose logic programs under completion semantics based on the three-valued logic used by Fitting [3], which itself is based on the three-valued Kleene [4] logic. Un- fortunately, some technical claims made by Stenning and van Lambalgen [1] are wrong. H¨ olldobler and Kencana Ramli [5] have shown that the three-valued logic proposed by Fitting is inadequate for the suppression task. Somewhat sur- prisingly, the suppression task can be adequately modeled if the three-valued L � ukasiewicz [6] logic is used. The computational logic approach in [5, 7] models the suppression task as logic programs together with their weak completion. They show that the conclusions drawn with respect to least models correspond to the findings in [2] and con- clude that the derived logic programs under L � ukasiewicz logic are inferentially adequate for the suppression task. In this paper we examine and compare L � ukasiewicz semantics (�L semantics) with well-founded semantics. Well-founded semantics is a widely accepted approach in the field of nonmonotonic reasoning [8]. Compared to Clark’s completion [9] or stable model semantics [10], well-founded semantics behaves more intuitive for programs with positive or negative cycles [11]. Under Clark’s completion, a program with a positive cycle might not reflect the intended interpretation of the program. For instance, consider P = {l ← e ∧ ¬ab1 , ab1 ← ab2 , e ← �}. Un- der Clark’s completion we conclude l. However, if we extend P with ab2 ← ab1 , which is implied by the completion of P, we cannot conclude l anymore. This seems to be counterintuitive. Furthermore, programs containing negative cycles might not be consistent under Clark’s completion and might not have a model under stable model semantics like e.g. p ← ¬p. In the following two sections we provide the necessary definitions and explain the logic programs representing the suppression task. After that, we give the char- acterization of the semantics in consideration and point out their differences. Modeling the Suppression Task under Three-Valued Lukasiewicz and Well-Founded Semantics 29 The Suppression Task under Three-Valued Logics 3 Table 3. Truth table for three-valued logics. ¬ ∧ ∨ ←L ↔L ← K ↔S ←S �⊥ � � � � � � � � � ⊥� � ⊥ ⊥ � � ⊥ � ⊥ � U U � U U � � U � ⊥ � ⊥ � ⊥ � ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ � � � � � ⊥ U ⊥ U U U U ⊥ ⊥ U � U � U U U ⊥ ⊥ U ⊥ ⊥ U � U � ⊥ � U U U U � � U � � Section 5 shows that by some modifications both approaches yield the same results. The last section concludes. 2 Three-valued Logics Three-valued logics were introduced by L � ukasiewicz [6] and since then different interpretations about the connectives have been proposed (see e.g. [4]). In this paper, we stick to the original definition by L� ukasiewicz as it has been shown in [5, 7] that this logic adequately solves the suppression task. Table 3 gives the truth tables of three-valued conjunction, disjunction and several variants of implication and equivalence. The three-valued logics are the L � ukasiewicz logic (←L ), Kleene’s strong implication [4] (←K ), and seq3 logic [12] (←S ). The seq3 logic corresponds to the logic used under well-founded semantics [13]. The truth values of the equivalences ↔L and ↔S are obtained from those of the respec- tive implications, ←L and ←S , by conjoining them in both directions. �, ⊥, and U denote true, false, and unknown, respectively. Stenning and van Lambal- gen [1] have taken the logic {¬, ∧, ∨, ←K , ↔S } to model the suppression task. H¨olldobler and Kenana Ramli [5] show that their logic is inadequate and propose to use {¬, ∧, ∨, ←L , ↔L } which corrects their mistakes and adequately models the suppression task. 3 Preliminaries We define the necessary notations we will use throughout this paper and restrict ourselves to propositional logic as this is sufficient to solve the suppression task. 3.1 Logic Programs A logic program P is a finite set of clauses of the form A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm (1) where A is an atom and called head and A1 , . . . , An , ¬B1 , . . . , ¬Bm is called body of the clause. The body can be either a conjunction of atoms Ai with 0 ≤ i ≤ n 30 Emmanuelle-Anna Dietz and Steffen H¨ olldobler 4 Emmanuelle-Anna Dietz, Steffen H¨ olldobler and negated atoms Bj with 0 ≤ j ≤ m, where i or j is ≥ 1. � and ⊥ are special cases of atoms where a clause of the form A ← � is called positive fact and a clause of the form A ← ⊥ is called negative fact. Let AP be the set of all atoms occurring in P. An atom is not defined in P if it is not the head of any clause in P; nd(P) = {A | there is no clause C in P such that A is the head of C}. Without loss of generality, we will restrict the use of � and ⊥ in the body of the clauses on facts. A program P − is the program P without negative facts. 3.2 Interpretations and Models An interpretation I is a mapping from formulas to the set of truth values {�, ⊥, U}. With respect to a particular logic, an interpretation is represented by a pair I = �I � , I ⊥ � of disjoint sets of atoms with the understanding that all atoms mapped to � are in I � and all atoms mapped to ⊥ are in I ⊥ and vice versa. If atoms are mapped to U, they are neither in I � nor in I ⊥ . A total interpretation is an interpretation I = �I � , I ⊥ � such that AP = I � ∪ I ⊥ . An interpretation I is a model for P if I maps each clause occurring in P to �. A basic model I is a model determined according to the seq3 logic. As apparent from table 3 whenever a formula is true under the S implication it is true under the L implication and vice versa. Thus, every basic model is also a model under � ukasiewicz logic. The greatest model of P is the union of all models of P. L A well-founded model is defined based on Well-founded semantics [14], which is only defined for logic programs without negative facts. The definition of a well- founded model requires the definition of unfounded sets: U ⊆ A is an unfounded set of P with respect to I if each atom A ∈ U satisfies the following condition: For each clause A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm , (at least) one of the following holds: 1. there exists Ai ∈ I ⊥ , 1 ≤ i ≤ n, or there exists Bj ∈ I � , 1 ≤ j ≤ m. 2. there exists Ai ∈ U , 1 ≤ i ≤ n. Let I be an interpretation and P be a program without negative facts, i.e. programs P − . The operators TP , UP , and WP which determine the well-founded semantics of P, are defined as follows: – TP (I) is the set of all literals A such that there exists a clause A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm ∈ P, where each Ai is in I � and each Bj is in I ⊥ . – UP (I) is the greatest unfounded set of P with respect to I. – WP (I) = TP (I) ∪ ¬UP (I). where the greatest unfounded set UP (I) of P with respect to I is the union of all unfounded sets of P with respect to I. The negation of UP (I), ¬UP (I) contains all negated atoms of UP (I). The well-founded model of P is the least fixed point of WP (I). AL � model of a logic program P is the least fixed point of the ΦP operator under L � ukasiewicz logic. Following the definition of [1], let I be an interpretation in Modeling the Suppression Task under Three-Valued Lukasiewicz and Well-Founded Semantics 31 The Suppression Task under Three-Valued Logics 5 Table 4. Representational Form of the Suppression Task P Clauses Facts Byrne PAE l ← e ∧ ¬ab1 ab1 ← ⊥ e←� 96% L PABE l ← e ∧ ¬ab1 l ← t ∧ ¬ab2 ab1 ← ⊥ ab2 ← ⊥ e←� 96% L PACE l ← e ∧ ¬ab1 l ← o ∧ ¬ab3 ab1 ← ¬o ab3 ← ¬e e←� 38% L PAE l ← e ∧ ¬ab1 ab1 ← ⊥ e←⊥ 46% ¬L PABE l ← e ∧ ¬ab1 l ← t ∧ ¬ab2 ab1 ← ⊥ ab2 ← ⊥ e←⊥ 4% ¬L PACE l ← e ∧ ¬ab1 l ← o ∧ ¬ab3 ab1 ← ¬o ab3 ← e e←⊥ 63% ¬L ΦP (I) = �J � , J ⊥ �, where J � = {A | there exists A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm ∈ P with A1 , . . . , An ⊆ I � and B1 , . . . , Bm ⊆ I ⊥ }, ⊥ J = {A | there exists A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm ∈ P and for all A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm ∈ P there exists Ai ∈ I ⊥ or there exists Bj ∈ I � }. As shown in [5] for any P, the least fixed point of ΦP can be computed by iterating ΦP starting with the empty interpretation. 3.3 Reasoning Towards an Appropriate Logical Form Stenning and van Lambalgen [1] have argued that the first step in modeling hu- man reasoning is reasoning towards an appropriate logical form. In particular, they argue that conditionals shall not be encoded by implications straight away but rather by licenses for implications. For example, the conditional A in Ta- ble 1 should be encoded by the clause l ← e ∧ ¬ab1 , where ab1 is an abnormality predicate which expresses that something abnormal is known. In other words, l holds if e is true and nothing abnormal is known. Table 4 shows the representational form of the first six examples of the sup- pression task as modeled by Stenning and van Lambalgen.1 The last column of Table 4 shows the findings of Byrne [2]. The predicates ab1 , ab2 and ab3 represent different kinds of abnormality. For in- stance, PABE and PACE contain two clauses which yield to the same conclusion l. Both programs differ in the way that for PABE , the premise of the second clause is an alternative to the first clause and in PACE the premise of the sec- ond clause is an additional to the first clause. The difference is represented by the additional clause in PACE where ab1 is true when The library does not stay open and ab3 is true when She does not have an essay to finish. We assume that Stenning and van Lambalgen adequately model this part of the suppression task and adopt this reasoning step. 4 L � Semantics and Well-Founded Semantics In this section we give the characterizations of L � and well-founded semantics by level mappings and compare them. 1 The other 6 cases require abduction (see [7]) which is beyond the scope of this paper. 32 Emmanuelle-Anna Dietz and Steffen H¨ olldobler 6 Emmanuelle-Anna Dietz, Steffen H¨ olldobler 4.1 Level Mapping A level mapping for a program P is a function L : AP → N. A partial level mapping for P is a level mapping that may be undefined for some atoms. An I-partial level mapping for P is a partial mapping for an interpretation where the domain of L is dom(L) = I � ∪ I ⊥ . Consider the following three programs P1 = {p ← q, q ← �, q ← ¬r} P2 = {p ← p} P3 = {p ← ¬q, q ← ¬p} For instance, in P1 we have that p and q are in the domain dom(L) but r is not, because r is neither in I � nor in I ⊥ . If we want to identify some property for this program, we can define some level mapping, e.g. L(�) = 1, L(r) = 2, L(q) = 3, and L(p) = 4. This is a level mapping where the head of each clause in P1 is strictly higher than the atoms in its body. It is not possible to define such a level mapping for P2 and P3 because they contain a cycle. We have a cycle in a program if at least one atom depends on itself. We say that p depends on q if and only if p ← A1 , . . . , An , ¬B1 , . . . ¬Bm such that q = Ai or q = Bj where 1 ≤ i ≤ n and 1 ≤ j ≤ m. We say that p depends positively on q, if q = Ai and p depends negatively on q if q = Bj . Dependency is transitive, thus if p depends on q and q depends on r, then p depends on r where one negative dependency is enough to define the whole dependency as negative. Accordingly, if an atom depends positively on itself, such as in program P2 , then we call this a positive cycle and if an atom depends negatively on itself, such as in program P3 then we call this a negative cycle. By restricting the level mapping conditions we can specify these properties: P is acyclic with respect to L if for every clause A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm in P we find that L(A) > L(Ai ) for all i, 1 ≤ i ≤ n and L(A) > L(Bj ) for all j, 1 ≤ j ≤ m. P is acyclic if it is acyclic with respect to some level mapping. P1 is acyclic, whereas P2 and P3 are not. We distinguish two cases: P is stratified with respect to L if for every clause A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm in P we find that L(A) ≥ L(Ai ) for all i, 1 ≤ i ≤ n and L(A) > L(Bj ) for all j, 1 ≤ j ≤ m. P is stratified if it is stratified with respect to some level mapping [15, 16]. Programs which only have positive cycles, are stratified. P2 is stratified but P3 is not. P is tight with respect to L if for every clause A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm in P we find that L(A) > L(Ai ) for all i, 1 ≤ i ≤ n and L(A) ≥ L(Bj ) for all j, 1 ≤ j ≤ m. P is tight if it is tight with respect to some level mapping [17, 18]. Programs which only have negative cycles, are tight programs. P3 is tight but P2 is not. 4.2 L � Semantics Kenana Ramli [19] gives the following characterization of the L � semantics for a logic program. Modeling the Suppression Task under Three-Valued Lukasiewicz and Well-Founded Semantics 33 The Suppression Task under Three-Valued Logics 7 Let P be a logic program, I = �I � , I ⊥ � be a basic model of P and L be an I-partial level mapping for P. P is said to satisfy (�L) wrt I and L if for every A ∈ dom(L) one of the following conditions is satisfied: (�Li) A ∈ I � and there exists a clause A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm in P such that the following conditions hold: (�Lia) for all i with 1 ≤ i ≤ n, Ai ∈ I � and L(A) > L(Ai ) (�Lib) for all j with 1 ≤ j ≤ m, Bj ∈ I ⊥ and L(A) > L(Bj ). (�Lii) A ∈ I ⊥ and there exists a clause A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm in P and for each such clause one of the following conditions holds: (�Liia) there exists i with 1 ≤ i ≤ n, Ai ∈ I ⊥ and L(A) > L(Ai ), (�Liib) there exists j with 1 ≤ j ≤ m, Bj ∈ I � and L(A) > L(Bj ). If A ∈ dom(L) satisfies (�Li), then we say that A satisfies (�Li) wrt I and L, and similarly if A ∈ dom(L) satisfies (�Lii). H¨olldobler and Kenana Ramli [5] show that the model intersection property holds for programs under L � semantics. This property guarantees the existence of a L � model for any logic program. Theorem 1. Let P be a logic program with the L � model M . Then M is the great- est model among all models I for which there exists an I-partial level mapping L for P such that P satisfies (�L) wrt I and L. Intuitively, the level mapping that satisfies (�L) wrt to all A ∈ dom(L) is acyclic wrt �I � , ∅� and wrt �∅, I ⊥ �. 4.3 Well-Founded Semantics Hitzler and Wendt [20] give a characterization for the well-founded semantics. Let P be a logic program, I = �I � , I ⊥ � be a basic model of P and L be an I-partial level mapping for P. P is said to satisfy (WF) wrt I and L if for every A ∈ dom(L) one of the following conditions is satisfied: (WFi) A ∈ I � and there exists a clause A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm in P such that the following conditions hold: (WFia) for all i with 1 ≤ i ≤ n, Ai ∈ I � and L(A) > L(Ai ) (WFib) for all j with 1 ≤ j ≤ m, Bj ∈ I ⊥ and L(A) > L(Bj ). (WFii) A ∈ I ⊥ and for each clause A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm in P, one of the following conditions holds: (WFiia) there exists i with 1 ≤ i ≤ n, Ai ∈ I ⊥ and L(A) ≥ L(Ai ), (WFiib) there exists j with 1 ≤ j ≤ m, Bj ∈ I � and L(A) > L(Bj ). If A ∈ dom(L) satisfies (WFi), then we say that A satisfies (WFi) with respect to I and L, and similarly if A ∈ dom(L) satisfies (WFii). Every logic program has a well-founded model [8]. Theorem 2. Let P be a logic program with the well-founded model M . Then M is the greatest model among all models I for which there exists an I-partial level mapping L for P such that P satisfies (WF) wrt I and L. Intuitively, the level mapping that satisfies (WF) wrt to all A ∈ dom(L) is acyclic wrt �I � , ∅� and stratified wrt �∅, I ⊥ �. 34 Emmanuelle-Anna Dietz and Steffen H¨ olldobler 8 Emmanuelle-Anna Dietz, Steffen H¨ olldobler Table 5. Programs with corresponding L � and well-founded models P Property Possible L-mapping order L � model well-founded model P1 acyclic L(�) < L(r) < L(q) < L(p) �{p, q}, ∅� �{p, q}, {r}� P2 stratified �∅, ∅� �∅, {p, q}� P3 tight L(p) = L(q) �∅, ∅� �∅, ∅� 4.4 Properties of L � Semantics and Well-Founded Semantics The characterizations of L � semantics and well-founded semantics are different in two aspects. First, consider conditions (�Lii) and (WFii): (�Lii) A ∈ I ⊥ and there exists a clause A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm in P and for each such clause one of the following conditions holds: [...] (WFii) A ∈ I ⊥ and for each clause A ← A1 , . . . , An , ¬B1 , . . . , ¬Bm in P, one of the following conditions holds: [...] By condition (WFii) all undefined predicates are in I ⊥ whereas in L� semantics, they stay undefined. Furthermore, they differ in conditions (�Liia) and (WFiia): (�Liia) there exists i with 1 ≤ i ≤ n, Ai ∈ I ⊥ and L(A) > L(Ai ), (WFiia) there exists i with 1 ≤ i ≤ n, Ai ∈ I ⊥ and L(A) ≥ L(Ai ), In a well-founded model, all predicates which are part of a positive cycle are in I ⊥ , whereas in L� semantics these predicates stay undefined. Table 5 shows the L � and the well-founded models for P1 , P2 and P3 . In the well- founded model of P1 , r is in I ⊥ because it is an undefined predicate whereas in the L � model r stays undefined. Consider programs P2 and P3 under L � semantics. In both cases the I-partial level mapping is undefined for p and q because they are both part of a cycle. Consider an extension of P3 , P3ext = P3 ∪ {p ← �}. The L � and the well-founded models are �{p}, {q}� because P3ext satisfies (�L) and (WF) wrt (the greatest model) �{p}, {q}� and the level mapping L(�) = 0, L(p) = 1, L(q). 5 Correspondence L � Semantics and Well-Founded Semantics In the following we show how L � semantics and well-founded semantics yield the same models and recall the examples from the suppression task. 5.1 Claim There is a relation between L� semantics and well-founded semantics for tight programs. In the following, we look at programs where negative facts are only formulated when p is not the head of any other clause in P. Under L � semantics this does not restrict the expressions of our programs as by condition (�Lii), we can only conclude that p is in I ⊥ if for all clauses where p is the head of, the body is in I ⊥ . Thus p ← ⊥ would not add any more information when Modeling the Suppression Task under Three-Valued Lukasiewicz and Well-Founded Semantics 35 The Suppression Task under Three-Valued Logics 9 Table 6. Suppression Task with the corresponding L � and Well-founded models P L � Model Well-founded Model PAE �{e, l}, {ab1 }� �{e, l}, {ab1 }� PABE �{e, l}, {ab1 , ab2 }� �{e, l}, {ab1 , ab2 }� PACE �{e}, {ab3 }� �{e, ab1 }, {o, ab3 , l}� mod PACE �{e}, {ab3 }� PAE �∅, {ab1 , e, l}� �∅, {ab1 , e, l}� PABE �∅, {ab1 , ab2 , e}� �∅, {ab1 , ab2 , e, t, l}� mod PABE �∅, {ab1 , ab2 , e}� PACE �{ab3 }, {e, l}� �{ab3 }, {e, l}� there is another clause with p in the head for which the body is not in I ⊥ . For well-founded models, we can omit negative facts because they are implicit when predicates are not defined. Theorem 3. Let P be a tight logic program. We claim that the L � model of P is the well-founded model of P mod , where the modified program P mod = P − ∪{A ← ¬A | A ∈ nd(P − )}. The proof is in the appendix. 5.2 The Suppression Task Table 6 shows how the L � semantics and well-founded semantics are applied for the six cases of the suppression task. Programs PACE and PABE reflect the actual suppression of additional and alternative information and show that the mod mod corresponding L� model and well-founded model are different. PACE and PABE in the fourth and seventh row give the well-founded model of the modified programs as proposed in our claim and shows that the well-founded models are indeed the same as the corresponding L� models of the program. 6 Conclusion We investigated L� semantics and well-founded semantics for the suppression task. Both approaches have different underlying three-valued interpretations. L � semantics adequately models the suppression task, whereas well-founded seman- tics does not. However, by modifying the programs under consideration for the well-founded semantics, both compute the same adequate models. We show that both approaches yield the same results for the class of tight programs. 7 Acknowledgments The paper formalized an idea that was brought to our attention by Alexandre Miguel Pinto. Many thanks to Christoph Wernhard and Bertram Fronh¨ ofer. 36 Emmanuelle-Anna Dietz and Steffen H¨ olldobler 10 Emmanuelle-Anna Dietz, Steffen H¨ olldobler References 1. Stenning, K., van Lambalgen, M.: Human reasoning and cognitive science. Brad- ford Books. MIT Press (2008) 2. Byrne, R.M.J.: Suppressing valid inferences with conditionals. Cognition 31 (1989) 61–83 3. Fitting, M.: A Kripke-Kleene semantics for logic programs. J. Log. Program. 2 (1985) 295–312 4. Kleene, S.C.: Introduction to metamathematics. Bibl. Matematica. North-Holland, Amsterdam (1952) 5. H¨ olldobler, S., Kencana Ramli, C.D.: Logic programs under three-valued �lukasiewicz semantics. In: Proceedings of the 25th International Conference on Logic Programming. ICLP ’09, Berlin, Heidelberg, Springer-Verlag (2009) 464–478 6. L� ukasiewicz: O logice tr´ojwarto´sciowej. Ruch Filozoficzny 5 (1920) 169–171 En- glish translation: On Three-Valued Logic. In: Jan L � ukasiewicz Selected Works. (L. Borkowski, ed.), North Holland, 87-88, 1990. 7. Dietz, E.A., H¨ olldobler, S., Ragni, M.: A Computational Approach to the Sup- pression Task. to appear in Proceedings of the 34th Cognitive Science Conference (2012) 8. Van Gelder, A., Ross, K.A., Schlipf, J.S.: The well-founded semantics for general logic programs. J. ACM 38 (1991) 619–649 9. Clark, K.L.: Negation as failure. In Minker, J., ed.: Logic and Data Bases. Vol- ume 1. Plenum Press, New York, London (1978) 293–322 10. Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In Kowalski, R., Bowen, Kenneth, eds.: Proceedings of International Logic Program- ming Conference and Symposium, MIT Press (1988) 1070–1080 11. Przymusinski, T.: Well founded and stationary models of logic programs. Annals of Mathematics and Artificial Intelligence 12 (1994) 141–187 12. Gottwald, S.: A Treatise on Many-Valued Logics. Volume 9 of Studies in Logic and Computation. Research Studies Press, Baldock, UK (2001) 13. Przymusinski, T.C.: Every logic program has a natural stratification and an it- erated least fixed point model. In: Proceedings of the eighth ACM SIGACT- SIGMOD-SIGART symposium on Principles of database systems. PODS ’89, New York, NY, USA, ACM (1989) 11–21 14. Van Gelder, A., Ross, K., Schlipf, J.S.: Unfounded sets and well-founded seman- tics for general logic programs. In: Proceedings of the seventh ACM SIGACT- SIGMOD-SIGART symposium on Principles of database systems. PODS ’88, New York, NY, USA, ACM (1988) 221–230 15. Apt, K.R., Blair, H.A., Walker, A.: Foundations of deductive databases and logic programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1988) 89–148 16. Przymusinski, T.C.: Foundations of deductive databases and logic programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1988) 193–216 17. Fages, F.: Consistency of clark’s completion and existence of stable models. Meth. of Logic in CS 1 (1994) 51–60 18. Erdem, E., Lifschitz, V.: Tight logic programs. CoRR (2003) 19. Kencana Ramli, C.D.: Logic programs and three-valued consequence operators. Master’s thesis, Institute for Artificial Intelligence, Department of Computer Sci- ence, Technische Universit¨ at Dresden (2009) 20. Hitzler, P., Wendt, M.: A uniform approach to logic programming semantics. Theory and Practice of Logic Programming 5 (2005) 123–159 Modeling the Suppression Task under Three-Valued Lukasiewicz and Well-Founded Semantics 37 The Suppression Task under Three-Valued Logics 11 8 Appendix Proof of Theorem 3 � (P) if and only if A ∈ W F (P mod ) A∈L where L� (P) and W F (P mod ) are the L � model of P and the well-founded model of P mod , respectively. Both are pairs of interpretations �I � , I ⊥ �: � (P)� if and only if A ∈ W F (P mod )� and (1) A ∈ L � (P)⊥ if and only if A ∈ W F (P mod )⊥ (2) A ∈ L where L � (P)� (�L(P)⊥ ) and W F (P mod )� (W F (P mod )⊥ ) are the sets of atoms which are in I � (I ⊥ ) in the L � model of P and in the well-founded model of P mod , respectively. Proof (1) → Assume A ∈ L � (P)� . This is only the case if condition (�Li) holds. Condition (�Li) and (WFi) are the same and P ⊆ P mod , thus A ∈ W F (P mod )� . ← If A ∈ W F (P mod )� , then never because of some clause in the extension of P: {A ← ¬A}, but because of some clause in P itself. Since conditions (�Li) and (WFi) are the same and A ∈ W F (P mod )� then A ∈ L � (P)� . Proof (2) → Assume A ∈ L � (P)⊥ . This is only the case if condition (�Lii) holds. Condition (�Lii) is stricter than condition (WFii) and P ⊆ P mod , thus A ∈ W F (P mod )⊥ as well. ← (By Contraposition) Assume A �∈ L � (P)⊥ (to prove: A �∈ W F (P mod )⊥ ). Then for condition (�Lii) there are two possible cases: i there is not such a clause A ← A1 , . . . , An , ¬B1 , . . . , Bm in P. That means A is not the head of any clause: A ∈ nd(P). Thus A ← ¬A ∈ P mod , which is also the only clause in P mod with A in the head. Assume A ∈ W F (P mod )⊥ . This is only the case if condition (WFiib) holds (as the only atom in the body of the clause A ← ¬A is a negated atom) which is only the case if for each clause with A in the head there is some negated atom Bj with 1 ≤ Bj ≤ Bm occurring in the body we have that Bj ∈ W F (P mod )� and L(A) > L(Bj ). We have exactly one clause with A in the head, A ← ¬A, but then L(A) > L(A). Contradiction. ii for all clauses in P with A in the head neither condition L � iia nor L � iib hold for some clause with A in the head. Assume A ∈ W F (P mod )⊥ . Then for each clause in P with A in the head, either (WFiia) or (WFiib) holds. (a) Assume (WFiia) holds: then there exists i with 1 ≤ i ≤ n, Ai ∈ W F (P mod )� and L(A) ≥ L(Ai ). Since we restrict ourselves to tight programs, it can only be that 1 ≤ i ≤ n, Ai ∈ W F (P mod )� and L(A) > L(Ai ). Since we assume this for each clause in P mod and P ⊆ P mod (�Liia) holds for P as well and we have that A ∈ L � (P)⊥ . Contradiction. 38 Emmanuelle-Anna Dietz and Steffen H¨ olldobler 12 Emmanuelle-Anna Dietz, Steffen H¨ olldobler (b) Assume (WFiib) holds: [...]. Then (�Liib) holds for P as well and we have � (P)⊥ . Contradiction. that A ∈ L If we replace the clause A ← ¬A by the following two clauses and an addi- tional auxiliary atom e.g. A ← ¬not A, not A ← ¬A, then P mod = P ∪ {A ← ¬not A, not A ← ¬A | A ∈ nd(P)}. The proof is the same except for part [i]: i either there is not such a clause A ← A1 , . . . , An , ¬B1 , . . . , Bm in P. So we have that A is not the head of any clause and thus A ∈ nd(P). We in- troduce an additional auxiliary variable not A and two additional clauses A ← ¬not A and not A ← ¬A for P mod . These are the only two clauses in P mod with A and not A in the head, respectively. Assume A ∈ W F (P mod )⊥ . This is only the case if condition (WFiib) holds (as the only atom in the body of the clause A ← ¬ not A is a negated atom). That is not A ∈ W F (P mod )� and L(A) > L(not A). not A ∈ W F (P mod )� if (WFi) holds. That is, there exists a clause not A ← A1 , . . . An , ¬B1 , . . . , ¬Bm in P mod such that for all i with 1 ≤ i ≤ n, Ai ∈ W F (P mod )� and L(not A) > L(Ai ) and for all j with 1 ≤ j ≤ m, Bj ∈ W F (P mod )⊥ and L(not A) > L(Bj ). As we know, not A ← ¬A is the only clause with not A in the head in P mod , thus A ∈ W F (P mod )⊥ and L(not A) > L(A) have to hold. Contra- diction.  Reasoning about Rough Sets Using Three Logical Values Beata Konikowska1 and Arnon Avron2 1 Institute of Computer Science, Polish Academy of Sciences, ul. Jana Kazimierza 5, 01-248 Warsaw, Poland [email protected] 2 School of Computer Science, Tel Aviv University, Tel Aviv, Israel [email protected] Abstract. The paper presents a logic for reasoning about covering- based rough sets using three logical values: the value t corresponding to the positive region of a set, the value f — to the negative region, and the undefined value u — to the boundary region of that set. Atomic formulas of the logic represent membership of objects of the universe in rough sets, and complex formulas are built out of the atomic ones us- ing three-valued Kleene connectives. In the paper we provide a strongly sound and complete Gentzen-style sequent calculus for the logic. 1 Introduction Rough sets, developed by Pawlak in the early 1980s [18, 19], represent a simple and yet very powerful notion designed to model vague or imprecise information. Unlike Zadeh’s fuzzy sets, they are not based on any numerical measure of the degree of membership of an object in an imprecisely defined set. Instead, they employ a much more universal and versatile idea of an indiscernibility relation, which groups together objects having the same properties from the viewpoint of a certain application into disjoint equivalence classes. This concept has proved to be extremely useful in practice. Since their intro- duction in the early 1980s, rough sets have found numerous applications in areas like control of manufacturing processes [14], development of decisions tables [20], data mining [14], data analysis [21], knowledge discovery [15], and so on. They have also been the subject of an impressive body of research. Though it focused mainly on algebraic properties of rough sets, a number of logicians have also explored this area, presenting and studying various brands of logics connected with rough sets [6, 5, 7, 8, 12, 16, 17, 10, 9, 23, 24]. Over the years, the original notion of rough sets has been generalized by replacing the indiscernibility relation (representing a partition of the universe of objects) underlying Pawlak’s approach with other, less restrictive constructs. The broadest generalization are covering-based rough sets [27, 22], defined based on an arbitrary covering of the universe of objects. By now, this notion has also been examined in many papers (see e.g. [25, 26, 29]), with the main focus again on the algebraic properties of such generalized rough sets. 40 Beata Konikowska and Arnon Avron In this paper we explore the logical aspects of covering-based rough sets, employing for that purpose a three-valued logic. The motivation for using three logical values stems from the fact that, like in case of Pawlak’s rough sets, a covering-based approximation space defines three regions of any set X of objects: – positive region of X, containing all objects of the universe which certainly belong to X in the light of the information provided by the covering; – negative region of X, containing all objects which certainly do not belong to X; – boundary of X, containing all objects which cannot be said for sure to either belong or not to belong to X. Hence the most natural idea for reasoning about membership of objects in covering-based rough sets is to use a three-valued logic, with the following values: – t — meaning “certainly belongs”, and assigned to objects in the positive region of a given set; – f — meaning “certainly does not belong” and assigned to objects in the negative region of the set; and – u — meaning “not known to either belong or not”, and assigned to the boundary of the set. Such an idea was first exploited in [3] for the original rough sets based on an equivalence relation on the universe of objects. However, the logic developed there was just a simple propositional logic generated by the three-valued non- deterministic matrix (see [4, 2]), shortly: Nmatrix, which did reflected only some properties of set-theoretic operations on rough sets. Then next attempt was made in [13] for covering-based rough sets. There the semantics of the logics was based on the natural frameworks for such sets, i.e. covering-based approximations spaces. Atomic formulas of the logic represented either membership of objects of the universe in rough sets or the subordination relation3 between objects generated by the covering underlying the approxima- tion space, and complex formulas were formed out of the atomic ones using three-valued Kleene connectives. A Gentzen sequent calculus for the logic was presented, and its strong soundness was proved. However, strong completeness was only proved for the subset of the language containing formulas without set-theoretic operations on rough sets. In this paper we improve on the results of [13] by providing a strongly sound and complete Gentzen calculus for the logic of rough sets defined as in [13], but without the subordination relation. The paper is organized as follows. Section 2 presents the fundamentals of covering-based rough sets. Section 3 defines the syntax and semantics of the logic LRS examined in the paper, including satisfaction and consequence relations 3 Given a covering C of a universe U , the subordination relation generated by C is the binary relation ≺C on U such that x ≺C y ⇔ (∀C ∈ C)(y ∈ C → x ∈ C). The relation ≺C is reflexive and symmetric, and it is an equivalence relation iff C is a partition, i.e. in case of the original Pawlak’s rough sets. Reasoning about Rough Sets Using Three Logical Values 41 for formulas and sequents, Section 4 presents a strongly sound and complete Gentzen sequent calculus for LRS , and finally Section 5 presents the conclusions and outlines future work. 2 Covering-based rough sets In what follows, for any set X, by P(X) we denote the powerset of X, i.e. the set of all subsets of X, and by P + (X) — the set of all nonempty subsets of X. Definition 1. By a covering-based approximation space, or shortly approxima- tion space, we mean any ordered pair A = (U, C), where∪ U is a non-empty universe of objects, and C ⊆ P + (U ) is a covering of U , i.e. {C | C ∈ C} = U. Definition 2. For any approximation space A = (U, C): – The lower approximation of a set X ⊆ U with respect to the covering C is LC (X) = {x ∈ U | ∀C ∈ C(x ∈ C ⇒ C ⊆ X)} – The upper approximation of a set X ⊆ U with respect to the covering C is ∪ HC (X) = {C ∈ C | C ∩ X ̸= ∅} In view of the above definition, one can say that, given the approximate knowledge about objects available in the approximation space A: – LC (X) is the set of all the objects in U which certainly belong to X; – HC (X) is the set of all the objects in U which might belong to X; The above operations have the same basic properties as in case of Pawlak’s rough sets based on a partition of the universe, i.e. for any X, Y ⊆ U , we have: LC (X) ⊆ X ⊆ HC (X) HC (X ∪ Y ) = HC X ∪ HC Y LC (X ∪ Y ) ⊇ LC X ∪ LC Y LC (X ∩ Y ) = LC X ∩ LC Y HC (X ∩ Y ) ⊆ HC X ∩ HC Y (1) LC (−X) = −HC X HC (−X) = −LC X where none of the inequalities in (1) can be replaced by the equality. Following the example of Pawlak’s rough sets, with any subset of a universe U of an approximation space we can associate three regions of that universe: positive, negative and boundary, representing three basic statuses of membership of an object of the universe U in X: Definition 3. Let A = (U, C) be an approximation space, and let X ⊆ U . Then: – The positive region of X in the space A with respect to the covering C is P OSC (X) = LC (X) 42 Beata Konikowska and Arnon Avron – The negative region of X in the space A with respect to the covering C is N EGC (X) = LC (U − X) – The boundary region of X in the space A with respect to the covering C is BN DC (X) = U − (P OSC (X) ∪ N EGC (X)) Corollary 1. For any approximation space A = (U, C) and any X ⊆ U : P OSC (X) = {x ∈ U | ∀C ∈ C(x ∈ C ⇒ C ⊆ X)} N EGC (X) = {x ∈ U | ∀C ∈ C(x ∈ C ⇒ C ⊆ U − X)} (2) BN DC (X) = {x ∈ U | ∃C ∈ C(x ∈ C ∧ C ∩ X ̸= ∅ ∧ C ∩ (U − X) ̸= ∅} The regions defined as above are obviously disjoint. Moreover, we can say that, according to the approximate knowledge of the properties of objects in U pro- vided by the covering C: – The elements of P OSR (X) certainly belong to X; – The elements of N EGR (X) certainly do not belong to X; – We cannot tell if the elements of BN DR (X) belong to X or not. As a result, the most natural solution choice of a logic for reasoning about covering-based rough set is — exactly like in case of Pawlak’s rough sets — to base it on three logical values: t — true, f – false, u — unknown, corresponding to the positive, negative and the boundary region of a set, respectively. 3 Syntax and semantics of the language LRS Now we shall define the language LRS of the three-valued logic for reasoning about covering-based rough sets described in the introduction. Formulas of LRS will contain expressions representing sets of objects (built from set variables and set constants using set-theoretic operators), variables representing objects, the symbol ∈ ˆ of a three-valued binary predicate representing membership of an object in a rough set, and the logical connectives ¬, ∧, ∨ which will be interpreted as 3-valued Kleene connectives. 3.1 Syntax of LRS Definition 4. Assume that: – OV is a non-empty denumerable set of object variables; – SV is a non-empty denumerable set of set variables, – 0 and 1 are set constants The syntax of the language LRS is defined as follows: 1. The set SE of set expressions of LRS is the least set containing SV ∪ {0, 1}, and closed under the set-theoretic operators −, ∪, ∩; 2. The set of atomic formulas of LRS is ARS = {x ∈ ˆ A | x ∈ OV, A ∈ SE}; 3. The set FRS of formulas of LRS is the least set F containing ARS and closed under the connectives ¬, ∨, ∧. Reasoning about Rough Sets Using Three Logical Values 43 3.2 Semantic frameworks for LRS and interpretation of formulas The semantics of LRS is based on interpreting the formulas of LRS in semantic frameworks for that language, built on covering-based approximation spaces and including valuations of set variables and object variables. Definition 5. A semantic framework, or shortly framework, for LRS is an or- dered triple R = (A, v, w), where: – A = (U, C) is a covering-based approximation space; – v : OV → U is a valuation of object variables; – w : SV → P(U ) is a valuation of set variables and constants such that w(0) = ∅, w(1) = U . For any valuation w : SV → P(U ), by w∗ we shall denote the extension of w to SE obtained by interpreting −, ∪, ∩ as the set-theoretic operations of complement, union and intersection. In other words: w∗ (X) = w(X) for any X ∈ SV , w∗ (−A) = U − w(A) for any A ∈ SE, and w∗ (A ∪ B) = w∗ (A) ∪ w∗ (B), w∗ (A ∩ B) = w∗ (A) ∩ w∗ (B) for any A, B ∈ SE Definition 6. An interpretation of LRS in a framework R = (A, v, w), where A = (U, C), is a mapping IR : FRS → {t, f, u} defined as follows: 1. For any x, y ∈ OV and any A ∈ SE,  t if v(x) ∈ P osC (w∗ (A)) ˆ A) = f if v(x) ∈ N egC (w∗ (A)) . IR (x ∈  u if v(x) ∈ BndC (w∗ (A)) 2. For any φ, ψ ∈ F ,   t if IR (φ) = f – IR (¬φ) = f if IR (φ) = t  u if IR (φ) = u   t if either IR (φ) = t or IR (ψ) = t – IR (φ ∨ ψ) = f if IR (φ) = f and IR (ψ) = f  u otherwise   t if IR (φ) = t and IR (ψ) = t – IR (φ ∧ ψ) = f if either IR (φ) = f or IR (ψ) = f  u otherwise It can be easily seen that the interpretation IR is a well-defined mapping of the set of formulas into {t, f, u}. Indeed, as the regions of a rough set are disjoint, Point 1 provides a well-defined interpretation of atomic formulas, and the clauses for ¬, ∨, ∧ in Point 2 extend it uniquely to complex formulas. In the sequel we will drop the subscript R at IR if R is arbitrary or understood. 44 Beata Konikowska and Arnon Avron 3.3 Satisfaction and consequence relations for formulas and sequents To complete the definition of the semantics of LRS , we need to define the notions of satisfaction and the consequence relation. Since the proof system we are going to develop for LRS will be a sequent calculus, we will define both the notions for formulas as well as for sequents. Definition 7. – By a sequent we mean a structure of the form Γ ⇒ ∆, where Γ and ∆ are finite sets of formulas. The set of all sequents over the language LRS is denoted by SeqRS . – A sequent Σ ∈ SeqRS is called atomic if each formula in Σ is atomic. Depending on the specific application of rough sets, we can choose either the strong version of the three-valued semantics of LRS — with t as the only designated value, or its weak version — with two designated values: t, u, which leads to a paraconsistent logic. In this paper, we choose the strong semantics like in [3], leaving the weak version for future work, Consequently, we adopt the following definitions of satisfaction and consequence: Definition 8. 1. A formula φ ∈ FRS is satisfied by an interpretation I of LRS , in symbols I |= φ, if I(φ) = t. 2. A formula φ ∈ FRS is valid, in symbols |=RS φ, if I |= φ for any interpre- tation I of LRS . 3. A set of formulas T ⊆ FRS is satisfied by an interpretation I, in symbols I |= T , if I |= φ for all φ ∈ T . 4. A sequent Σ = (Γ ⇒ ∆) is satisfied by an interpretation I, in symbols I |= Σ, iff either I |= φ for some φ ∈ ∆, or I ̸|= ψ for some ψ ∈ Γ . 5. A sequent Σ = (Γ ⇒ ∆) is valid, in symbols |=RS Σ, if I |= Σ for any interpretation I of LRS 6. The formula consequence relation in LRS is the relation ⊢RS on P(FRS ) × FRS such that, for every T ⊂ FRS and every φ ∈ FRS , T ⊢RS φ if each interpretation I of LRS which satisfies T satisfies φ too. 7. The sequent consequence relation in LRS is the relation ⊢RS on P(SeqRS )× SeqRS such that, for every Q ⊆ SeqRS , and every Σ ∈ SeqRS , Q ⊢RS Σ iff, for any interpretation I of LRS , I |=RS Q implies I |=RS Σ. Note that the use of the same symbol for the formula and sequent consequence relations will not lead to misunderstanding, for the meaning of the symbol will always be clear from the context. 4 Proof system for the logic LRS Now we shall present a proof system for the logic LRS with the language LRS , corresponding to the consequence relation ⊢RS defined in the preceding section. The deduction formalism we use for LRS is a Gentzen-style sequent calculus. Reasoning about Rough Sets Using Three Logical Values 45 Sequent calculus CRS Axioms: (A1) φ ⇒ φ ˆ0 ⇒ (A2) x ∈ ˆ1 (A3) ⇒ x ∈ Structural rules: weakening, cut Boolean tautology rules: for any A, B ∈ SE such that A ≡ B ˆA ⇒ ∆ Γ, x ∈ ˆA Γ ⇒ ∆, x ∈ (taut − l) (taut − r) ˆB ⇒ ∆ Γ, x ∈ ˆB Γ ⇒ ∆, x ∈ Intersection rules: ˆ B, x ∈ Γ, x ∈ ˆC ⇒ ∆ ˆ B Γ ⇒ ∆, x ∈ Γ ⇒ ∆, x ∈ ˆC (∩ ⇒) (⇒ ∩) ˆ Γ, x ∈B ∩ C ⇒ ∆ ˆ Γ ⇒ ∆, x ∈B ∩ C Inference rules for Kleene connectives: ˆ −A⇒∆ Γ, x ∈ ˆ −A Γ ⇒ ∆, x ∈ ˆ ⇒) (¬ ∈ ˆ) (⇒ ¬ ∈ ˆ A) ⇒ ∆ Γ, ¬(x ∈ ˆ A) Γ ⇒ ∆, ¬(x ∈ Γ, φ ⇒ ∆ Γ ⇒ ∆, φ (¬¬ ⇒) (⇒ ¬¬) Γ, ¬¬φ ⇒ ∆ Γ ⇒ ∆, ¬¬φ Γ, φ ⇒ ∆ Γ, ψ ⇒ ∆ Γ, ⇒ ∆, φ, ψ (∨ ⇒) (⇒ ∨) Γ, φ ∨ ψ ⇒ ∆ Γ ⇒ ∆, φ ∨ ψ Γ, ¬φ, ¬ψ ⇒ ∆ Γ ⇒ ∆, ¬φ Γ ⇒ ∆, ¬ψ (¬∨ ⇒) (⇒ ¬∨) Γ, ¬(φ ∨ ψ) ⇒ ∆ Γ ⇒ ∆, ¬(φ ∨ ψ) Γ, φ, ψ ⇒ ∆ Γ ⇒ ∆, φ Γ ⇒ ∆, ψ (∧ ⇒) (⇒ ∧) Γ, φ ∧ ψ ⇒ ∆ Γ ⇒ ∆, φ ∧ ψ Γ, ¬φ ⇒ ∆ Γ, ¬ψ ⇒ ∆ Γ ⇒ ∆, ¬φ, ¬ψ (¬∧ ⇒) (⇒ ¬∧) Γ, ¬(φ ∧ ψ) ⇒ ∆ Γ ⇒ ∆, ¬(φ ∧ ψ) In all axioms and inference rules, we assume that x, y, z ∈ OV , A, B ∈ SE. Note that though the axiom φ, ¬φ is missing in the formulation of CRS, it is in fact derivable in CRS. Indeed, at the atomic level, from A1 and rule (¬ ∈⇒) we can deduce that (1) ⊢CRS x ∈ ˆ A, ¬(x ∈ ˆ A) ⇒ x ∈ ˆ A, x ∈ ˆ − A. In turn, from A1 and rule (⇒ ∩) we can obtain (2) ⊢CRS x ∈ ˆ A, x ∈ˆ − A ⇒ x ∈ (A ∩ −A). Considering that A ∩ −A ≡ 0, from rule (taut − l) we can deduce that (3) ⊢CRS x ∈ (A ∩ −A) ⇒ x ∈ ˆ 0. Applying cut, from 1), (2), (3) and Axiom A2 we conclude that ⊢CRS x ∈ ˆ A, ¬(x ∈ˆ A) ⇒ , so φ, ¬φ ⇒ holds for atomic φ. The fact that it holds for complex φ too can be shown by structural induction using the inference rules for Kleene connectives . 46 Beata Konikowska and Arnon Avron Lemma 1. 1. The axioms of the system CRS are valid. 2. For any inference rule ρ of CRS and any framework R for LRS , if the inter- pretation I of LRS in R satisfies all the premises of ρ, then I satisfies the conclusion of ρ as well. Both parts can be easily verified based on the individual clauses of the definition of I given in Definition 6. Clearly, from the above Lemma we can immediately conclude that: Corollary 2. The inference rules of CRS are strongly sound, i.e. they preserve the validity of sequents. 5 Strong soundness and completeness of the proof system To prove strong completeness of CRS, we start with simple characterization of valid single-variable atomic sequents. Definition 9. For any A, B ∈ SE, we say that: 1. A is Boolean-equivalent to B, and write A ≡ B, iff A = B is a Boolean tautology; 2. A is Boolean-included in B, and write A ⊑ B, iff A ∩ B = A is a Boolean tautology, i.e. iff A ∩ B ≡ A. Proposition 1. A sequent Σ = x ∈ ˆ A1 , . . . , x ∈ ˆ Ak ⇒ x ∈ ˆ B1 , . . . , x ∈ ˆ Bl is valid iff one of the following conditions is satisfied: (1) A1 ∩ A2 ∩ · · · ∩ Ak ≡ 0 (2) Bi ≡ 1 for some i ≤ l (3) A1 ∩ A2 ∩ · · · ∩ Ak ⊑ Bi for some i ≤ l Proof. The backward implication follows easily from the semantics of LRS . To prove the forward implication, we argue by contradiction. Assume that a sequent Σ of the form given above is such that: (I) A1 ∩ A2 ∩ · · · ∩ Ak ̸≡ 0 (II) Bi ̸≡ 1 for each i ≤ l (III) A1 ∩ A2 ∩ · · · ∩ Ak ̸⊑ Bi for each i ≤ l Define SV0 = {X ∈ SV | X occurs in Σ} SE0 = {A ∈ SE | A contains only set variables in SV0 } As SV0 is finite, SV0 = {X1 , X2 , . . . , Xn } for some n. The counter-model con- struction is based on the use of the full disjunctive normal form (DNF) of an expression in SE0 with respect to SV0 . Such a DNF is of the form Xϵ = X1ϵ1 ∩ X2ϵ2 ∩ · · · ∩ Xnϵn Reasoning about Rough Sets Using Three Logical Values 47 where ϵ = (ϵ1 , ϵ2 , . . . , ϵn ) ∈ {−1, 1}n , and Xj1 = Xj , Xj−1 = −Xj . Let A = A1 ∩ A2 ∩ · · · ∩ Ak . Then A ̸≡ 0 by (I), so we have DNF(A) = Xϵ1 ∪ Xϵ2 ∪ · · · ∪ Xϵp for some p ≥ 1, ϵ1 , · · · , ϵp ∈ {−1, 1}n . Since DNF(E) ≡ E for any E ∈ SE0 , then by (III) we get DNF(A) ̸⊑ DNF(Bi ) for each i ≤ l. Hence for each i ≤ l there is a ji ≤ p such that Xϵji does not occur in DNF(Bi ). Let us assign a unique symbol aϵ ̸∈ OV ∪ SV to any ϵ ∈ {−1, 1}n . As the universe of our counter-model R we take U = {x} ∪ {aϵ | ϵ ∈ {−1, 1}n }, and as the covering underlying the approximation space — C = {C(u) | u ∈ U }, where C(u) = {u} for u ̸= x, and C(x) = {x, aϵ1 , aϵ2 , . . . , aϵp }. The valuation of variables v is given by v(y) = x for any x ∈ OV . Finally, to define the valuation of set variables, we first define ξ(Xϵ1 ) = {x, aϵ1 } and ξ(Xϵ ) = {aϵ } for any ϵ ∈ {−1, 1}n \ {ϵ1 }. Then we put w(X) = ∅ for X ∈ SV \ SV0 , and define w on SV0 by taking ∪ w(Xj ) = {ξ(Xϵ ) | ϵ ∈ {−1, 1}n , ϵj = 1} for j = 1, 2, . . . , n (recall that SV0 = {X1 , X2 , . . . , Xn }). It is easy to check that R = ((U, C), v, w) is a well-defined semantic framework for LRS , and w∗ (A1 ∩ A2 ∩ · · · Ak ) = w∗ (X) = {x, aϵ1 , aϵ2 , . . . , aϵp } = C(x) (3) ∩k However, as w∗ (A1 ∩ A2 ∩ · · · ∩ Ak ) = r=1 w∗ (Ar ) ⊆ w∗ (Aj ) for each j ≤ k, (3) implies that C(x) ⊆ w∗ (Aj ) for any j ≤ k, Since C(x) is the only set C ∈ C such that x ∈ C, then from Corollary 1 we obtain x ∈ P OS(w∗ (Aj )) and IR |= x ∈ ˆ Aj for j = 1, 2, . . . , k. On the other hand, as Xϵji does not occur in DNF(Bi ) for any i ≤ l, then aϵji ̸∈ w∗ (DNF(Bi )) = w∗ (Bi ) for each i ≤ l, which in view of aϵji ∈ C(x) implies C(x) ̸⊆ w∗ (Bi ) for each i ≤ l. As a result, IR ̸|= x ∈ˆ Bi for i = 1, 2, . . . , l. Thus IR ̸|= Σ, which ends the proof. Since LRS has no means for expressing relationships between object variables, Proposition 1 implies a similar result for multi-variable atomic sequents: Corollary 3. An atomic sequent Σ ∈ SeqRS is valid if and only if, for some object variable x occurring in Σ, the sequent Σx obtained from Σ by deleting all formulas with variables different from x satisfies one of the conditions of Proposition 1. The proof is analogous to that of Proposition 1, with the counter-model for a sequent Σ which does not satisfy any of conditions (1),(2),(3) of that Proposition constructed by combining the individual countermodels for all single-variable subsequents of Σ, constructed exactly like in the proof of Proposition 1. From the results of the preceding section, we can easily conclude that CRS is complete for atomic sequents: Proposition 2. If an atomic sequent Σ ∈ SeqRS is valid, then it is derivable in CRS, i.e. ⊢CRS Σ. 48 Beata Konikowska and Arnon Avron Proof. For any variable x occurring in Σ, denote by Σx the atomic sequent obtained out of Σ by deleting all formulas with variables different from x. Since Σ is valid, then, by Corollary 3, there exists an x such that Σx satisfies one of the conditions (1), (2), (3) of Proposition 1. Hence, assuming that Σx = x∈ˆ A1 , . . . , x ∈ ˆ Ak ⇒ x ∈ ˆ B1 , . . . , x ∈ ˆ Bl , we have either (1) A1 ∩ A2 ∩ · · · ∩ Ak ≡ 0 or (2) Bi ≡ 1 for some i ≤ l or (3) A1 ∩ A2 ∩ · · · ∩ Ak ⊑ Bi for some i ≤ l If (1) holds, then from A1 and rule (⇒ ∩) applied k−1 times we can obtain (i) ⊢CRS x ∈ ˆ A1 , . . . , x ∈ ˆ Ak ⇒ x ∈ ˆ (A1 ∩· · ·∩Ak ). Considering that A1 ∩· · ·∩Ak ≡ 0, from rule (taut − l) and Axioms A1, A2 we get (ii) ⊢CRS x ∈ ˆ (A1 ∩ · · · ∩ Ak ) ⇒ . Applying cut to (i) and (ii), we obtain ⊢CRS x ∈ ˆ A1 , . . . , x ∈ˆ Ak ⇒ , whence ⊢CRS Σx by weakening. If (2) holds, then from Axiom A3 and rule (taut − r) we get ⊢CRS ⇒ Bi , whence ⊢CRS Σx by weakening. Finally, assume that (3) holds. By what was shown for (1), we have (i) ⊢CRS x∈ˆ A1 , . . . , x ∈ ˆ Ak ⇒ x ∈ ˆ (A1 ∩· · ·∩Ak ). For simplicity, denote A = A1 ∩· · ·∩Ak . Then A ⊑ Bi , implying A ∩ Bi ≡ A by Definition 9, whence from Axiom A1 and rule (taut − l) we get (ii) ⊢CRS x ∈ ˆA ⇒ x ∈ ˆ A ∩ Bi . In turn, by A1 and rule (∩ ⇒) we have (iii) ⊢CRS x ∈ ˆ A ∩ Bi ⇒ x ∈ ˆ Bi . Applying cut twice to (i), (ii) and (iii), we obtain ⊢CRS x ∈ ˆ A1 , . . . , x ∈ ˆ Ak ⇒ x ∈ ˆ Bi , which yields ⊢CRS Σx by weakening. Thus ⊢CRS Σx in all three cases. As Σx ⊂ Σ in the standard sense of sequent inclusion, this implies ⊢CRS Σ by weakening. Proposition 2 is the cornerstone for proving the strong completeness theorem for the logic LRS : Theorem 1. The calculus CRS is finitely strongly sound and complete for ⊢RS , i.e., for any finite set of sequents S ⊆ SeqRS and any sequent Σ ∈ SeqRS , S ⊢RS Σ iff S ⊢CRS Σ. Proof. (Sketch) As the backward implication (soundness) follows from Lemma 1 and Corollary 2, it suffices to prove the forward implication (completeness). The proof is by counter-model construction based on Proposition 2 and the maximum saturated sequent construction used e.g. in [1]. We argue by contradiction. Suppose that for a finite set of sequents S and a sequent Σ = Γ ⇒ ∆ we have S ⊢RS Σ, but Σ is not derivable from S in CRS. We shall construct a counter-model I such that I |= S but I ̸|= Σ. Denote by F (S) the set of all formulae belonging to at least one of the sides in some sequent in S, and let SV ∗ be the set of all set variables which occur either in some φ ∈ F (S) or in Σ. Since S is finite, so are F (S) and SV ∗ . Using the method shown in in [1], we can construct a sequent Γ ′ ⊆ ∆′ such that (i) Γ ⊆ Γ ′ , ∆ ⊆ ∆′ (ii) F (S) ⊆ Γ ′ ∪ ∆′ . Reasoning about Rough Sets Using Three Logical Values 49 (iii) Γ ′ ⇒ ∆′ is not derivable from S in CRS. The construction is carried out by starting with Σ, and then adding consecutively linearly ordered formulas in F (S) to either the left- or the right-hand side of the sequent constructed up to that time, depending on which option results in a sequent still not derivable from S in CRS. Such a construction is possible because if S ̸⊢CRS (Γi ⇒ ∆i ), then, for any φ ∈ F (S), we cannot have both S ⊢CRS (Γi , φ ⇒ ∆i ) and S ⊢CRS (Γi ⇒ ∆i , φ), since this would imply S ⊢CRS (Γi ⇒ ∆i ) by cut. Call a sequent saturated if it is closed under the inference rules in CRS applied backwards, whereby we assume that closure under the Boolean tautology rules (taut − l), (taut − r) is limited only to premises with the set expression A in a full disjunctive normal form with respect to the set SV ∗ . By way of example, a sequent Γ ′′ ⇒ ∆′′ is closed under rule (∨ ⇒) applied backwards iff φ ∨ ψ ⊆ Γ ′′ implies either φ ∈ Γ ′′ or ψ ∈ Γ ′′ . Let Γ ∗ ⇒ ∆∗ be the extension of Γ ′ ⇒ ∆′ to a saturated sequent which is not derivable from F (S) in CRS (is is easy to see that such a sequent exists; note that the restriction on the closure under tautology rules ensures that the closure adds only a finite number of formulas to Γ ′ ⇒ ∆′ . Then we can easily see that: (1) Γ ⊆ Γ ∗ , ∆ ⊆ ∆∗ ; (2) F (S) ⊆ Γ ∗ ∪ ∆∗ ; (3) Γ ∗ ⇒ ∆∗ is saturated and it is not derivable from S in CRS. Now let Σa = Γa ⇒ ∆a be a subsequent of Γ ∗ ⇒ ∆∗ consisting of all atomic formulas in Γ ∗ ⇒ ∆∗ . Then by (3) S ̸⊢CRS Σa , and hence also ̸⊢CRS Σa . As Σa is atomic, by Proposition 2, this implies that Σa is not valid. Accordingly, there exists a framework R for LRS and an interpretation I of LRS in R such that I ̸|= Σa . We shall prove that I is the desired counter-model for the original sequent Σ too, i.e. that: (A) I ̸|= (Γ ⇒ ∆) (B) I |= Σ for each Σ ∈ S Let us start with (A). As Γ ⊆ Γ ∗ , ∆ ⊆ ∆∗ , then in order to prove (A) it suffices to show that I ̸|= (Γ ∗ ⇒ ∆∗ ). Since the only designated value in the semantics of LRS is t and I(φ) ∈ {t, f, u} for any formula φ ∈ FRS , this means we have to prove that: I(γ) = t for any γ ∈ Γ ∗ I(δ) ∈ {f, u} for any δ ∈ ∆∗ (4) As I ̸|= Σa , then (4) holds for all atomic formulas γ ∈ Γ ∗ , δ ∈ ∆∗ . To show that it holds for complex formulas too, we prove that, for any complex formula φ, the following is true: { { t if φ ∈ Γ ∗ {f, u} if φ ∈ ∆∗ (A1) I(φ) = ∗ (A2) I(φ) ∈ f if ¬φ ∈ Γ {t, u} if ¬φ ∈ ∆∗ 50 Beata Konikowska and Arnon Avron The proof is by induction on the complexity of φ, and (A1) and (A2) are proved simultaneously, making use of the fact that Σ ∗ as a saturated sequent is closed under all rules in CRS applied backwards. To illustrate the method used, consider first the case of ξ = ¬(x ∈ ˆ A). If ξ ∈ Γ ∗ , then x ∈ ˆ − A is also in Γ ∗ , since Σ ∗ is closed under rule (¬ ∈ ˆ ⇒) applied backwards. As (4) holds for all atomic formulas and x ∈ ˆ − A is atomic, this yields I(x ∈ ˆ − A) = t. However, from Definition 6 and Corollary 1 we can easily conclude that   t iff I(x ∈ ˆ − A) = f ˆ A) = f iffI(x ∈ I(x ∈ ˆ − A) = t (5)  ˆ − A) = u u iffI(x ∈ which implies I(ξ) = I(¬(x ∈ ˆ A)) = t by Definition 6. In turn, if ξ ∈ ∆∗ , then x ∈ ˆ − A is also in ∆∗ , since Σ ∗ is closed under rule (⇒ ¬ ∈ ˆ ) applied backward. As (4) holds for x ∈ ˆ − A, then I(x ∈ ˆ − A) ∈ {f, u}, whence in view of (5) we get I(x ∈ ˆ A) ∈ {t, u}. In consequence, I(ξ) = I(¬(x ∈ ˆ A)) ∈ {f, u} by Definition 6. Thus (A1) and (A2) hold for ξ As another example, assume that (A1), (A2) hold for φ, ψ, and that ξ = φ∨ψ. If ξ ∈ Γ ∗ , then either φ ∈ Γ ∗ or ψ ∈ Γ ∗ , since Σ ∗ is closed under rule (∨ ⇒) applied backwards. As a result, by the inductive assumption on φ, ψ we have either I(φ) = t or I(ψ) = t, and consequently I(ξ) = t by Definition 6. In turn, if ξ ∈ ∆∗ , then φ, ψ ∈ ∆∗ , and I(φ), I(ψ) ∈ {f, u} by the inductive assumption, whence I(ξ) ∈ {f, u} by Definition 6, too. As a result, (A1) and (A2) hold for ξ too. The proof of other cases is similar, and is left to the reader. It remains to prove (B), i.e., to show that I |= Σ0 for each Σ0 ∈ S. So let Σ0 ∈ S. Then Σ0 = φ1 , . . . , φk ⇒ ψ1 , . . . , ψl for some integers k, l and formulas φi , ψj , i = 1, . . . , k, j = 1, . . . , l. Clearly, we cannot have both {φ1 , . . . , φk } ⊆ Γ ∗ and {ψ1 , . . . , ψl } ⊆ ∆∗ , for then Γ ∗ ⇒ ∆∗ would be derivable from Σ0 , and hence from S, by weakening. Since F (S) ⊆ Γ ∗ ∪ ∆∗ , this implies that either φi ∈ ∆∗ for some i, or ψj ∈ Γ ∗ for some j. Hence by (A1) and (A2), which we have already proved, we have either I ̸|= φi for some i, or I |= ψj for some j, which implies that I |= Σ. 6 Conclusions and future work The crucial feature of three-valued logic presented in the paper is a complete mechanism for reasoning about atomic formulas representing three-valued, rough membership of the objects of the universe in rough sets. The three values taken by the rough membership relation correspond to “crisp” membership of objects in the three basic regions of a rough set: the positive, negative and boundary one. The strong version of semantics with the single designated value t adopted in the paper amounts to identifying membership of an object x in a rough set A with its belonging to the positive region of A. However, in many applications it is advisable to identify the above membership with x belonging to either the Reasoning about Rough Sets Using Three Logical Values 51 positive region or the boundary region of A — which corresponds to taking also u as a designated value. The latter option, which leads to paraconsistent logic, will be the subject of further work. The use of connectives to form complex formulas enhances the expressive power of the language, but the Kleene 3-valued connectives used here are just one possible choice. Other interesting option, to be explored in the future, are the Lukasiewicz 3-valued connectives (including implication), and the non- deterministic connectives observing the rough set Nmatrix considered in [3]. Exploring these choices is another direction for future work. A still another is to consider a richer language which allows for expressing relationships between objects — and here the most immediate future task will be extending the results of this paper to a language featuring the subordination relation of [13]. The authors would like to thank the anonymous referees for very helpful comments on the paper, including suggestions for directions of future work — which we have included above. References 1. Avron, A., Konikowska., B. and Ben-Naim, J.: Processing Information from a Set of Sources. In: Towards Mathematical Philosophy, Series: Trends in Logic , Vol. 28, Makinson, David; Malinowski, Jacek; Wansing, Heinrich (Eds.), pp.165-186, Springer Verlag (2008) 2. Avron, A.: Logical Non-determinism as a Tool for Logical Modularity: An In- troduction. In: We Will Show Them: Essays in Honor of Dov Gabbay, Vol 1 (S. Artemov, H. Barringer, A. S. d’Avila Garcez, L. C. Lamb, and J. Woods, eds.), pp. 105–124. College Publications (2005). 3. Avron, A. and Konikowska., B.: Rough Sets and 3-valued Logics. Studia Logica, vol. 90 (1), pp. 69–92 (2008). 4. Avron, A. and Lev, I.: Non-deterministic Multiple-valued Structures. Journal of Logic and Computation 15, pp. 241–261 (2005). 5. Balbiani, P. and Vakarelov, D.: A modal Logic for Indiscernibility and Com- plementarity in Information Systems. Fundamenta Informaticae 45, pp. 173–194 (2001). 6. Banjeeri, M.: Rough sets and 3-valued Lukasiewicz logic. Fundamenta Informaticae 32, pp. 213–220 (1997). 7. Demri, S., Orlowska, E., Vakarelov, D.: Indiscernibility and complementarity relations in information systems. In: Gerbrandy, J., Marx, M., de Rijke, M., Ven- ema, Y. (eds.) JFAK: Esays dedicated to Johan van Benthem on the ocasion of his 50-th Birthday. Amsterdam University Press (1999). 8. Deneva, A. and Vakarelov, D.: Modal Logics for Local and Global Similarity Relations. Fundamenta Informaticae, vol 31, No 3,4, pp. 295–304 (1997). 9. Duentsch, I. Konikowska, B.: A multimodal logic for reasoning about comple- mentarity. Journal for Applied Non-Classical Logics, Vol. 10, No 3–4, pp. 273-302 (2000). 10. Iturrioz, L.: Rough sets and three-valued structures. In: Orlowska, E. (editor), Logic at Work: Essays Dedicated to the Memory of Helena Rasiowa. Studies in Fuzziness and Soft Computing, vol. 24, pp. 596–603, Physica-Verlag (1999). 11. Kleene, S.C.: Introduction to metamathematics, D. van Nostrad Co. (1952). 52 Beata Konikowska and Arnon Avron 12. Konikowska, B.: A logic for reasoning about relative similarity. Special Issue of Studia Logica, E. Orlowska, H. Rasiowa eds., Reasoning with incomplete informa- tion. Studia Logica 58, pp. 185–226 (1997). 13. Konikowska, B.: Three-Valued Logic for Reasoning about Covering-based Rough Sets. In: Special Volume Dedicated to the Memory of Z. Pawlak, Intelligent Systems Reference Library, Springer [to appear] (2012). 14. Lin, T.Y. and Cercone, N. (eds.): Rough sets and Data Mining. Analysis of Im- precise Data, Kluwer, Dordrecht (1997). 15. Øhrn, A., Komorowski, J., Skowron, A. and Synak, P.: The design and imple- mentation of a knowledge discovery toolkit based on rough sets — The ROSETTA system. In: Polkowski, L. and Skowron, A. (eds.), Rough Sets in Knowledge Dis- covery 1. Methodology and Applications. Physica Verlag, Heidelberg, pp. 376–399 (1998). 16. Orlowska, E.: Reasoning with Incomplete Information: Rough Set Based Infor- mation Logics. In: Proceedings of SOFTEKS Workshop on Incompleteness and Uncertainty in Information Systems, pp.16-33, (1993). 17. Pagliani, P. Rough set theory and logic-algebraic structures. In: Orlowska, E. (editor), Incomplete Information: Rough Set Analysis. Studies in Fuzziness and Soft Computing, vol. 13, pp. 109–190, Physica-Verlag (1998). 18. Pawlak, Z.: Rough Sets, Intern. J. Comp. Inform. Sci., 11, 341–356 (1982). 19. Pawlak, Z.: Rough Sets. Theoretical Aspects of Reasoning about Data. Kluwer, Dordrecht (1991). 20. Pawlak, Z.: Rough set approach to knowledge-based decision support, European Journal of Operational Research 29(3), pp. 1–10 (1997). 21. Pawlak, Z.: Rough sets theory and its applications to data analysis. Cybernetics and Systems 29, pp. 661–688 (1998). 22. Pomykala, J.A.: Approximation operations in approximation space. Bull. Pol. Acad. Sci. 35(9-10), pp. 653–662 (1987). 23. Sen J., Chakraborty, M.K.: A study of intenconnections between rough and 3- valued Lukasiewicz logics. Fundamenta Informaticae 51, 311–324, 2002. 24. Vakarelov, D.: Information Systems, Similarity Relations and Modal Logics. In: E. Orlowska (ed.) Incomplete Information: Rough Set Analysis, pp. 492-550. Studies in Fuzziness and Soft Computing, Physica-Verlag Heidelberg New York (1998). 25. Yao, Y.Y.: Relational interpretations of neighborhood operators and rough set approximation operators. Information Sciences 111 (1–4), pp. 239–259 (1998). 26. Yao, Y.Y.: On generalizing rough set theory. In: The 9th International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing (RSFDGrc) 2003. LNCS vol. 2639, pp. 44-51 (2003). 27. Zakowski, W.: On a concept of rough sets. Demonstratio Mathematica XV, 1129- 1133 (1982). 28. Zhang, Y.-L. Li, J.J. and Wu, W.-Z.: On axiomatic characterizations of three types of covering-based approximation operators. Information Sciences 180, pp. 174–187 (2010). 29. Zhu, W., Wang, F.-Y.: On three types of covering-based rough sets. IEEE Trans- actions on Knowledge and Data Engineering 19(8), pp. 1131–1144 (2007).  Doing the right things – trivalence in deontic action logic Piotr Kulicki and Robert Trypuz! John Paul II Catholic University of Lublin Abstract. Trivalence is quite natural for deontic action logic, where ac- tions are treated as good, neutral or bad. We present the ideas of trivalent deontic logic after J. Kalinowski and its realisation in a 3-valued logic of M. Fisher and two systems designed by the authors of the paper: a 4-valued logic inspired by N. Belnap’s logic of truth and information and a 3-valued logic based on nondeterministic matrices. Moreover, we com- bine Kalinowski’s idea of trivalence with deontic action logic based on boolean algebra. Keywords: deontic action logic, many-valued logic, Kalinowski’s deon- tic logic, Dunn-Belnap’s four-valued matrix Introduction Deontic logic can be seen as a formal tool for analysing rational agent’s behaviour in the context of systems of norms. Two main approaches within it can be pointed out: in one of them deontic notions, such as permission, forbiddance or obligation are attributes of situations (in the language – propositions), in the other they are attributes of actions (in the language – names). We are interested in the latter one – deontic action logic (DAL), introduced in the work of G.H. von Wright [13], which is usually treated as the beginning of modern deontic logic. The first attempt at defining the formal semantics of DAL made by J. Kali- nowski [5] has already taken the form of three-valued tables defining truth values of propositions built with deontic operators (permission, forbiddance and obli- gation) for different types of actions and negations of actions. M. Fisher [4] used a similar methodology but introduced and analysed more operations on actions, namely conjunction and disjunction. More recently a multi-valued approach to DAL appeared in the paper of A. Kouznetsov [7]. Trivalence is quite natural for deontic action logic. The three values in that context refer to actions that are respectively good, neutral or bad. This general idea needs, of course, more detailed specification to be used as a basis for a formal system. In the present paper we just point out the possible ways of using the techniques of multi-valued logic in the area of norms. A more serious study of their application would require much longer and detailed investigations. ! This research was supported by the National Science Center of Poland (DEC- 2011/01/D/HS1/04445). 53 54 Piotr Kulicki and Robert Trypuz 2 Piotr Kulicki and Robert Trypuz Although other semantic tools have also been successfully applied to DAL we believe that multi-valued semantics for that logic is worth further research. There are two main advantages of that approach (the same as of the use of many-valued techniques in other branches of logic): it is intuitively clear and produces systems with nice computational properties. We start the paper from a brief recall of Kalinowski’s ideas and Fisher’s tri-valued DAL. Then we adapt to DAL the ideas introduced into multi-valued logic in a different context: the bilattice known as F OUR (bilattice of truth and information) with the respective F OUR-valued matrices introduced by N. Belnap [2] and non-deterministic matrices introduced by A. Avron and I. Lev [1]. Finally, we study the relation between DAL, based on boolean algebra introduced by K. Segerberg in [9], and Kalinowski’s ideas. 1 Language of deontic action logic The language of DAL is defined in Backus-Naur notation in the following way: ϕ ::= α = α | O(α) | P(α) | Pw (α) | F(α) | ¬ϕ | ϕ ∧ ϕ | ϕ ∨ ϕ | ϕ → ϕ | ϕ ≡ ϕ (1) α ::= ai | 0 | 1 | α | α % α | α & α (2) where ai belongs to a finite set of basic actions Act0 , “0” is the impossible action and “1” is the universal action; “α = β” means that α is identical with β (the last three elements of the language will be used only in section 4); “O(α)” – α is obligatory; “P(α)” – α is strongly permitted (i.e. its performance is permit- ted in combination with any action); “Pw (α)” – α is weakly permitted (i.e. its performance is not forbidden);“F(α)” – α is forbidden, “α % β” – α or β (a free choice between α and β); “α & β” – α and β (parallel execution of α and β); “α” – not α (complement of α). Further, for fixed Act0 , by Act we shall understand the set of formulae defined by (2). In our considerations we understand actions as types or descriptions rather then individual events in time and space. Thus e.g. “α % β” is a description of all actions that are covered by description “α” or by description “β” (see also [8]). 2 3-valued deontic logics of Kalinowski and Fisher 2.1 Kalinowski’s deontic logic Kalinowski believed that norms like propositions are true or false. In his ap- proach norms describe relations of permission, obligation and prohibition be- tween agents and actions. Thus, if, for instance, permission holds between agent i and action α, then the norm expressing that state of affairs is true. Logical value of norms depends on moral value of actions – to fulfil norms means to do the right things. Kalinowski assumed that every action in genere is either good (g), or bad (b) or neutral (n), although actions in concreto are always Doing the right things — trivalence in deontic action logic 55 Doing the right things – trivalence in deontic action logic 3 good or bad. Good (bad) actions are such by nature and remain good (bad) in all circumstances. On the other hand neutral actions are those which in some circumstances are good and in other circumstances bad. Kalinowski expressed his philosophical intuitions concerning the meaning of deontic concepts of weak permission, obligation and prohibition by the following matrix: α Pw (α) O(α) F(α) b 0 0 1 n 1 0 0 g 1 1 0 One can see that obligatory actions are those which are always good, prohibited actions are those which are always bad and weakly permitted actions are (always) good or neutral. There is only one internal operator in Kalinowski’s logic – action complement. Each action α has its complement (or negations) α. Action negation is defined by the following matrix: αα b g nn g b A complement of a good action is bad, a complement of a bad action is good and finally a complement of a neutral action is also neutral. Kalinowski states in [6] that his theory can be enriched by other action operators such as parallel execution or indeterministic choice, but at the same time he is very sceptical about the applicability of theories more expressive than his own deontic theory. 2.2 Fisher’s trivalent matrices One of the extensions of Kalinowski’s logic is Fisher’s deontic logic. Fisher in- troduced two operators: parallel execution and indeterministic choice (see two matrixes below), which were missing in Kalinowski’s theory. &bng %b ng b bb b b b bg nbng nb ng gbgg gg gg The two operators are De Morgan duals, i.e. a%b =a&b (3) Basic actions are per se good, bad or neutral, while the deontic value of other actions, that can be described as combinations of basic actions made with the use of action operators, can be computed using the matrices. 56 Piotr Kulicki and Robert Trypuz 4 Piotr Kulicki and Robert Trypuz 3 Alternative matrix systems 3.1 4-valued deontic semantics Kalinowski stated in [6] that Fisher’s matrixes are “natural”. We find them, at least at certain points, problematic. In Fisher’s approach a combination (parallel execution) of good and bad actions is bad and free choice between such actions is good. Execution of an action that is composed of two parts of which one is good and the other is bad can be understood as a conflict of norms or values. We want to study formally different possibilities of solving such conflicts. As a first alternative for Fisher’s approach let us investigate the solution in which in such a situation a statement about what is good to do is to be made by an agent. In such a situation the action itself can be seen as neutral. That cannot be achieved with trivalent matrices with the preservation of associativity, since we would have: (g & g) & b = g & b = n and g & (g & b) = g & n = g. For that reason we take a structure inspired by Belnap’s construction con- cerning truth information, replacing them respectively by moral value and de- ontic saturation depicted in the following diagram: ' saturated deontic b g saturation ⊥ neutral bad moral value good Operator & is interpreted as supremum in the structure and operator % as infi- mum. Negation of ' is ' and negation of ⊥ is ⊥. The same definitions of the operators can be expressed by the following ma- trices: & b ⊥' g % b ⊥' g a a b b b '' b b ⊥ b ⊥ b g ⊥ b ⊥' g ⊥⊥⊥⊥⊥ ⊥⊥ ''''' ' b ⊥' g '' g ' g ' g g ⊥⊥ g g g b The interpretation of deontic atoms is defined by the following matrix: Doing the right things — trivalence in deontic action logic 57 Doing the right things – trivalence in deontic action logic 5 a Pw (a) O(a) F(a) b 0 0 1 ⊥ 1 0 0 ' 1 0 0 g 1 1 0 The matrix shows that intuitively values ⊥ and ' are treated both as neutral. Thus, in a sense, the system remains trivalent, though formally there are F OUR values that can be attached to actions. 3.2 A system based on non-deterministic matrices Another possible approach solves the problem of the conflict of norms by stat- ing that what should be done depends on situation and cannot be predicted deterministicly. We formalise it by using nondeterministic matrices. The idea of nondeterministic attachment of deontic value to actions was present in [7] but we use different content of matrix and a more elaborated formalism introduced in [1]. Definition of indeterministic matrices after Avron and Lev is as follows. – N-matrix for language L is a triple M = )V, D, O*, where: • V is a non-empty set (of truth values); • D is a non-empty proper subset of V (designated values); • O includes an n-ary function x : V n −→ 2V − ∅ for every n-ary operator x of L – Let M be N-matrix for L. An M -valuation v is a function v : FL −→ V such that for every n-ary operator x of L and every α1 , . . . , αn , v(x(α1 , . . . , αn )) ∈ x(v(α1 ), . . . , v(αn )). – A model in M is defined in a usual way. The following nondeterministic matrices define the deontic value of combined actions: aa & b n g % b n g b g b {b} {b} {b, n, g} b {b} {b, n} {b, g} nn n {b} {n} {g} n {b, n} {n} {n, g} g b g {b, n, g} {g} {g} g {b, g} {n, g} {g} The interpretation of deontic atoms is as in Kalinowski’s formalisation. The most interesting cases are those in which good and bad actions are combined with the operations of parallel execution and free choice. The result in the former case is treated as fully indeterministic. Depending on the estimation of how good is a good component of an action and how bad is its bad component one can treat such a compound action as good, neutral and bad. For the latter case we assume, as a general rule for creating the matrix, that a collection of values of two actions is a value of free choice between them. Thus a free choice between a good and a bad action cannot be neutral, as it was defined in the 4- valued system from the previous section. However, we may also use an alternative non-deterministic matrix in which value n is also possible in this case. 58 Piotr Kulicki and Robert Trypuz 6 Piotr Kulicki and Robert Trypuz 3.3 Some formulas The following formulas are tautologies in all of the systems defined in the previ- ous sections. F(α) ≡ ¬Pw (α) (4) O(α) → Pw (α) (5) O(α) ≡ ¬Pw (α) (6) Pw (α) ∧ Pw (β) → Pw (α & β) (7) Pw (α) ∧ Pw (β) → Pw (α % β) (8) Pw (α % β) → Pw (α) ∨ Pw (β) (9) In contrast the following formulas are valid respectively only in Fisher’s logic and only in the 4-valued logic: F(α) → F(α & β) (10) O(α) → Pw (α % β) (11) 4 Trivalence and deontic action logics based on boolean algebra 4.1 Fundamentals of DAL based on boolean algebra Deontic action logic based on boolean algebra was introduced by K. Segerberg in [9] and recently studied in [3, 10–12]. Fundamental axioms of DAL systems are those of Segerberg for B.O.D., i.e.: P(α % β) ≡ P(α) ∧ P(β) (12) F(α % β) ≡ F(α) ∧ F(β) (13) α = 0 ≡ F(α) ∧ P(α) (14) It is important to note that permission (prohibition) axiomatised above char- acterise permitted (prohibited) actions as always permitted (prohibited), i.e. permitted (prohibited) in combination with any action: P(α) → P(α & β) (15) F(α) → F(α & β) (16) Deontic action model for DAL is a structure M = )DAF, I*, where DAF = )E, Leg, Ill* is a deontic action frame in which E = {e1 , e2 , . . . , en } is a nonempty Doing the right things — trivalence in deontic action logic 59 Doing the right things – trivalence in deontic action logic 7 set of possible outcomes (events), Leg and Ill are subsets of E and should be un- derstood as sets of legal and illegal outcomes respectively. The basic assumption is that there is no outcome which is legal and illegal: Ill ∩ Leg = ∅ (17) I : Act −→ 2E is an interpretation function for DAF defined as follows: I(ai ) ⊆ E, for ai ∈ Act0 (18) I(0) = ∅ (19) I(1) = E (20) I(α % β) = I(α) ∪ I(β) (21) I(α & β) = I(α) ∩ I(β) (22) I(α) = E \ I(α) (23) Additionally we accept that the interpretation of every atom is a singleton: I(δ) = 1 (24) where δ is an atom of Act. A basic intuition is such that an atomic action corre- sponding to (a set with) one event/outcome is indeterministic. It is important to note two things in this place. The first one is that I(δ) is a subset of either Leg, or Ill or −Leg ∩ −Ill and the second one is that in every situation an agent’s action has only one outcome, which means in practice that what agents really do is to carry out atomic actions. The definition of an interpretation function makes it clear that every action generator is interpreted as a set of (its) possible outcomes, the impossible ac- tion has no outcomes, the universal action brings about all possible outcomes, operations “%”, “&” between actions and “ ” on a single action are interpreted as set-theoretical operations on interpretations of actions. A class of models de- fined as above will be represented by C. Satisfaction conditions for the primitive formulas of DAL in any model M ∈ C are defined as follows: M |= P(α) ⇐⇒ I(α) ⊆ Leg M |= F(α) ⇐⇒ I(α) ⊆ Ill M |= α = β ⇐⇒ I(α) = I(β) M |= ¬ϕ ⇐⇒ M 3|= ϕ M |= ϕ ∧ ψ ⇐⇒ M |= ϕ and M |= ψ Action α is strongly permitted iff all of its possible outcomes are legal. It means in practice that if α is permitted, then it is permitted in combination with any action (cf. thesis 15). The same is true for forbiddance. 60 Piotr Kulicki and Robert Trypuz 8 Piotr Kulicki and Robert Trypuz ! ! !"" "#$ %& !"" !$ !& "#$ %& !% !$ !' !( !& !" !% !# !' !( !) !"+ !" !# !* !) !"+ !* '("#$((!"'(%& Fig. 1. Five dashed line ovals illustrate Fig. 2. This model of DAL is closed in some interpretations of DAL actions. the sense that every event is either legal This model includes events which are or illegal. neither legal nor illegal. 4.2 Embedding Kalinowski’s deontic logic into DAL To embed Kalinowski’s deontic logic into DAL we need to make a few additional assumptions. First we assume that Leg and Ill are sets of good and bad events respectively. Then we need to exclude from the models the events which are neither good nor bad, since in Kalinowski’s approach each action event is either good or bad. As a result we’d like to obtain models similar to the illustrated below in figure 2. To obtain the intended result we add a new axiom to DAL which states that an action is either good or bad or has only good or bad components: P(δ) ∨ F(δ), for δ being an atom (25) Axiom 25 explicitly says that action atoms are good or bad. Additionally we assume that there are actions which are neither good nor bad, to make room for neutral ones: ¬F(1) ∧ ¬P(1) (26) Finally, we express Kalinowski’s assumption that the complement of a good action is bad: P(α) ≡ F(α) (27) The last axiom restricts models of DAL to the ones illustrated in figure 3. It also shows that “P” and “F” refer to Kalinowski’s obligation and forbiddance re- spectively. They also satisfy semantical conditions restricting obligatory actions only to the good ones and the forbidden actions only to the bad ones. It is also worth noting that each generator (and atom) in DAL satisfying all the axioms introduced above is interpreted as Leg or Ill (see figure 3). Finally, we obtain a structure similar to the one resembling Belnaps’s bilattice from section 3.1. To preserve the intuitions of boolean algebra in figure 4 we reversed the order of saturation. Doing the right things — trivalence in deontic action logic 61 Doing the right things – trivalence in deontic action logic 9 ! "#$ %& "# !! Fig. 3. Model for Kalinowski’s deontic logic E = {e1 , e2 } = Leg ∪ Ill neutral deontic Ill = {e1 } {e2 } = Leg saturation ∅ saturated bad moral value good Fig. 4. It turned out that only the impossible action ∅ is saturated. Both actions ∅ and E are neutral. Since there are only four elements in the algebra we can represent it by the following matrices. & Ill E ∅ Leg % Ill E ∅ Leg a a Ill Ill Ill ∅ ∅ Ill Ill E Ill E Ill Leg E Ill E ∅ Leg E E E E E E ∅ ∅ ∅ ∅ ∅ ∅ ∅ Ill E ∅ Leg ∅ E Leg ∅ Leg ∅ Leg Leg E E Leg Leg Leg Ill The only difference between these matrices and 4-valued matrices from sec- tion 3.1 lies in the definition of negation. There negation of ⊥ is ⊥ and negation of ' is ', here respective values – E and ∅ interchange. Kalinowski’s weak permission can be defined in the following way: PK (α) ! P(α) ∨ N(α) (28) 62 Piotr Kulicki and Robert Trypuz 10 Piotr Kulicki and Robert Trypuz where N(α) ! α = 0 ∨ ¬(P(α) ∨ F(α)) (29) Action is (syntactically) neutral (N) iff it is impossible or is neither good nor bad. Neutrality of the impossible action is assumed for the homogeneity reason. The impossible action is the only one which is at the same time good, bad and neutral. The operator defined in such a way satisfies the desired property that α is neutral iff its complement is neutral too: N(α) ≡ N(α) (30) A weakly permitted action (in Kalinowski’s sense) is thus defined as the one that is either good or neutral. a PK (a) P(a) F(a) Ill 0 0 1 E 1 0 0 ∅ 1 0 0 Leg 1 1 0 For PK the only axiom of Kalinowski’s deontic logic K1 can be proved: ¬PK (α) → PK (α) (31) One can also check that the following formula is a theorem of extended DAL: P(α) ≡ ¬PK (α) (32) Conclusions and further work We have discussed systems of deontic action logic based on three values of ac- tions: good, bad and neutral. In some of them the neutral value was divided into two. The proposed formalism was useful for discussing different approaches to conflicts of norms or values. Future works will be directed to the application of such logics for modelling agents in the context of norms. References 1. Arnon Avron and Iddo Lev. Non-deterministic multiple-valued structures. Journal of Logic and Computation, 15(3):241–261, June 2005. 2. Nuel Belnap. A useful four-valued logic. In J.M. Dunn and G. Epstein, editors, Modern uses of multiple-valued logic, pages 8–37. 1977. 3. Pablo F. Castro and T.S.E. Maibaum. Deontic action logic, atomic boolean algebra and fault-tolerance. Journal of Applied Logic, 7(4):441–466, 2009. 4. M. Fisher. A three-valued calculus for deontic logic. Theoria, 27:107–118, 1961. 5. J. Kalinowski. Theorie des propositions normativess. Studia Logica, 1:147–182, 1953. Doing the right things — trivalence in deontic action logic 63 Doing the right things – trivalence in deontic action logic 11 6. Jerzy Kalinowski. La logique des normes. Presses Universitaires de France, 1972. 7. Andrei Kouznetsov. Quasi-matrix deontic logic. In Alessio Lomuscio and Donald Nute, editors, Deontic Logic in Computer Science, volume 3065 of Lecture Notes in Computer Science, pages 191–208. Springer Berlin / Heidelberg, 2004. 8. Piotr Kulicki and Robert Trypuz. How to build a deontic action logic. In Logica 2011. To appear. 9. Krister Segerberg. A deontic logic of action. Studia Logica, 41:269–282, 1982. 10. Robert Trypuz and Piotr Kulicki. A systematics of deontic action logics based on boolean algebra. Logic and Logical Philosophy, 18:263–279, 2009. 11. Robert Trypuz and Piotr Kulicki. Towards metalogical systematisation of deontic action logics based on boolean algebra. In Proc. 10th International Conference Deontic Logic in Computer Science, volume 6181 of Lecture Notes in Computer Science. Springer, 2010. 12. Robert Trypuz and Piotr Kulicki. A norm-giver meets deontic action logic. Logic and Logical Philosophy, 20:59–72, 2011. 13. G. H. von Wright. Deontic logic. Mind, LX(237):1–15, 1951.  Trivalent Logics Arising from L-models for the Lambek Calculus with Constants Stepan Kuznetsov Moscow State University [email protected] Abstract. We consider language models for the Lambek calculus that allows empty antecedents and enrich them with constants for the empty language and for the language containing only the empty word. No com- plete calculi are known with respect to these semantics, and in this pa- per we consider several trivalent systems that arise as fragments of these models’ logics. 1 The Lambek Calculus and L-models We consider the calculus L∗ (the Lambek calculus allowing empty antecedents). This calculus is a variant of the original Lambek calculus [4] that allows empty antecedents. The set Pr = {p1 , p2 , p3 , . . . } is called the set of primitive types. Types of L∗ are built from primitive types using three binary connectives: \ (left division), / (right division), and · (multiplication); we shall denote the set of all types by Tp. Capital letters (A, B, . . . ) range over types. Capital Greek letters (except Σ) range over finite (possibly empty) sequences of types. Expressions of the form Γ → C are called sequents of L∗ . Axioms: A → A. Rules: AΠ → B (→ \) Π → A Γ B∆ → C (\ →) Π → A\B Γ Π(A \ B)∆ → C ΠA → B (→ /) Π → A Γ B∆ → C (/ →) Π → B /A Γ (B / A)Π∆ → C Π → A ∆ → B (→ ·) Γ AB∆ → C (· →) Π∆ → A · B Γ (A · B)∆ → C Π → A Γ A∆ → C (cut) Γ Π∆ → C Now let Σ be an alphabet (an arbitrary nonempty set, finite or countable). By Σ ∗ we denote the set of all words over Σ. The set Σ ∗ with the operation of word concatenation is the free monoid generated by Σ; the empty word � is the unit. Subsets of Σ ∗ are called languages over Σ. The three connectives of L∗ correspond to three natural operations on languages (M, N ⊆ Σ ∗ ): M · 66 Stepan Kuznetsov 2 Stepan Kuznetsov N � {uv | u ∈ M, v ∈ N }, M \ N � {u ∈ Σ ∗ | (∀v ∈ M ) vu ∈ N }, and N / M � {u ∈ Σ ∗ | (∀v ∈ M ) uv ∈ N } (“�” here and further means “equals by definition”). An L-model is a pair M = �Σ, w�, where Σ is an alphabet and w is a function that maps Lambek calculus types to languages over Σ, such that w(A · B) = w(A) · w(B), w(A \ B) = w(A) \ w(B), and w(B / A) = w(B) / w(A) for all A, B ∈ Tp. Obviously, w can be defined on primitive types in an arbitrary way, and then it is uniquely propagated to all types. A sequent of the form F → G is considered true in a model M (M � F → G) if w(F ) ⊆ w(G). L-models give sound and complete semantics for L, due to the following theorem: Theorem 1. A sequent F → G is provable in L∗ if and only if it is true in all L-models. This theorem is proved in [7]; its special case for the product-free frag- ment (where we keep only types without multiplication) is much easier and appears in [2]. (The notion of truth in an L-model and this theorem can be easily generalized to sequents with zero or more than one type on the left, since L∗ � F1 F2 . . . Fn → G if and only if L∗ � F1 · F2 · . . . · Fn → G; for a sequent with an empty antecedent → G its derivability is equivalent to the fact that � ∈ w(G) for any L-model M = �Σ, w�). 2 The Lambek Calculus with the Unit Lambek [5] has also introduced an extension of L with the unit constant 1. We denote the new set of types by Tp1 , and the new calculus L1 is obtained from L∗ by adding a new axiom → 1 and a new rule Γ ∆ → C (1 →). Γ 1∆ → C The set of all languages over an alphabet Σ forms a monoid with respect to the multiplication operation, and the unit of this monoid is {�}. It would be natural to define w(1) = {�}, but (see, for example, [6]) this leads to incomplete- ness: for example, the sequent (1 / p) (1 / p) → 1 / p is true in any L-model, but is not derivable in L1 . There are two possible ways to deal with this situation. The first way is to modify the notion of L-model (change the interpretation of the unit and restrict the interpretations of primitive types) — this is done in [10]. The second option, which we consider more interesting, is to extend the logic to gain completeness with respect to the existing class of L-models, with w(1) = {�}. This remains an open question; here we shall present a fragment of this logic. For any type B consider the type B,� which is B where all occurrences of any primitive type pi are replaced by pi \ 1 (one can symmetrically consider 1 / pi or even mix them). Let Tp � 1 � {B � | B ∈ Tp1 }. Consider a three-element set, say, T � {0, 1, ¯ 1} and two functions &, ⇒ : T × T → T (written in the infix form), defined by the following table: Trivalent logics arising from L-models for the Lambek calculus with constants 67 Trivalent Logics and the Lambek Calculus 3 x y x&y x ⇒ y 0 0 0 1 0 1 0 1 1 0 0 0 1 1 1 1 0 ¯ 1 0 1 ¯ 1 0 0 0 1 ¯ 1 1 0 ¯ 1 1 1 1 ¯ 1 ¯ 1 ¯ 1 ¯ 1 Table 1 The first four rows here just represent truth tables for classical conjunction and implication; the other rows extend these operations to their three-valued versions: ⇒ is the implication of Soboci´ nski’s [9] logic RM3 (a Gentzen-style calculus for it can be found in [1]), & is the contenability (fusion) operation. We shall say that a value x ∈ T is “true” if x = 1 or x = ¯ 1, and “false” if x = 0. We also introduce an ordering on T: 0 < ¯ 1 < 1. Now we define the notion of trivalent interpretation for types from Tp1 , τ : Tp1 → T. The function τ is defined in an arbitrary way on primitive types and satisfies the following conditions: τ (1) = ¯ 1, τ (A · B) = τ (A) & τ (B), and τ (A \ B) = τ (B / A) = (τ (A) ⇒ τ (B)). Theorem 2. If F, G ∈ Tp � 1 , then the following statements hold: 1. M � F → G for any L-model M if and only if τ (F ) ≤ τ (G) for any trivalent interpretation τ ; 2. M � → G for any L-model M if and only if the value τ (G) is true for any trivalent interpretation τ . As a corollary we get the result that the set T = {F1 . . . Fm → G | F1 , . . . , � 1 , and the sequent F1 . . . Fm → G is true in every L-model } is de- Fm , G ∈ Tp cidable. More precisely, it is co-NP-complete (trivalent interpretations include Boolean conjunction and implication — a complete system — therefore T is co-NP-hard due to NP-hardness of SAT; trivially, T itself is in the co-NP class). Note that another fragment, the Lambek calculus itself without the unit, is, vice versa, NP-complete [8]. Proof (of Theorem 2). It easily follows from the definitions that for any M ⊆ Σ ∗  Σ , if M = ∅;  ∗ M \{�} = {�} / M = {�}, if M = {�};   ∅ in other cases. 68 Stepan Kuznetsov 4 Stepan Kuznetsov We also consider the results of operations ·, \ and / on languages ∅, {�}, and Σ∗: M N M · N M \N N/M ∅ ∅ ∅ Σ∗ Σ∗ ∅ Σ∗ ∅ Σ∗ Σ∗ Σ∗ ∅ ∅ ∅ ∅ Σ∗ Σ∗ Σ∗ Σ∗ Σ∗ ∅ {�} ∅ Σ∗ Σ∗ {�} ∅ ∅ ∅ ∅ Σ ∗ {�} Σ∗ ∅ ∅ {�} Σ ∗ Σ∗ Σ∗ Σ∗ {�} {�} {�} {�} {�} Table 2 Statement 1 of the theorem follows from statement 2, because M � F → G iff M � → F \ G and, on the other hand, τ (F ) ≤ τ (G) iff the value τ (F \ G) = (τ (F ) ⇒ τ (G)) is true (see the table for ⇒ above). Let us prove statement 2. First we prove the implication from right to left. Let M be an L-model and let G be a type from Tp � 1 such that the value τ (G) is true for any trivalent interpretation τ . We shall prove that M � → G. Let M = �Σ, w�, and let  0, if w(pi ) = ∅;  τ (pi ) = ¯1, if w(pi ) = {�};   1 in other cases. Now, for any non-primitive subtype G� of G, since all occurrences of pi are in subtypes of the form pi \ 1, we have the following correspondence between w(G� ) and τ (G� ): w(G� ) = ∅ iff τ (G� ) = 0; w(G� ) = {ε} iff τ (G� ) = ¯1; w(G� ) = Σ ∗ � � iff τ (G ) = 1 (other values of w(G ) are impossible). For primitive types this is true by definition, and then we proceed by induction on G� (compare Table 1 and Table 2). Now, for G we have τ (G) = 1 or τ (G) = ¯ 1, therefore w(G) = Σ ∗ or w(G) = {�}, and in both cases � ∈ w(G), so M � → G. The other direction is similar. Let τ be a trivalent interpretation. Consider, say, Σ = {a, b}, and let  ∅,  if τ (pi ) = 0; w(pi ) = {�}, if τ (pi ) = ¯ 1;   ∗ Σ , if τ (pi ) = 1. Now, since � ∈ w(G), τ (G) is either 1 or ¯ 1. Trivalent logics arising from L-models for the Lambek calculus with constants 69 Trivalent Logics and the Lambek Calculus 5 We see that the considered fragment of the theory of L-models with the unit is actually a commutative trivalent logic. 3 The Lambek Calculus with the Empty Set Constant In this section we consider L-models with a special constant 0, interpreted as ∅. The set of types here is denoted by Tp0 . We introduce a new set T = {0, 1, L }, and two new operations &, ⇒ : T × T → T, defined as follows (this is the implication-conjunction fragment of the strong Kleene [3, § 64] 3-valued logic): x y x&y x ⇒ y 0 0 0 1 0 1 0 1 1 0 0 0 1 1 1 1 0 L 0 1 L 0 0 L 1 L L L L 1 L 1 L L L L Table 3 The trivalent interpretation τ is defined as in the previous section; τ (0) = 0. Now we introduce a hybrid logic L0 : we say that L0 � → G (G ∈ Tp0 ) if either τ (G) = 1 for any trivalent interpretation τ , or for any trivalent interpretation τ we have τ (G) ∈ {1, L }, and L � → G (in L-derivations 0 is considered an ordinary primitive type). We say that L0 � F1 . . . Fm → G iff L0 � → (F1 · . . . · Fm ) \ G. Intuitively, the third truth value L here means “I don’t know, ask the Lam- bek calculus”. Theorem 3. If L0 � F1 . . . Fm → G, then the sequent F1 . . . Fm → G is true in all L-models. Proof. It is sufficient to consider only sequents with empty antecedents. If L � → G (the second case in the definition of L0 , then → G is true in all L-models due to Theorem 1. Now let τ (G) = 1 for any trivalent interpretation τ . Let M = �Σ, w� be an L-model. For any pi let τ (pi ) = L . One can prove by induction that for any G� if τ (G� ) = 0, then w(G� ) = ∅, and if τ (G� ) = 1, then w(G� ) = Σ ∗ . Therefore, w(G) = Σ ∗ � �. 70 Stepan Kuznetsov 6 Stepan Kuznetsov � This is �a correctness � theorem. � Unfortunately, L0 is incomplete: L0 �� p2 · (0 \ 0) \ p1 → (0 \ 0) \ p1 , but this sequent is true in all L-models (due to the fact that for any languages N and M we have N · (Σ ∗ \ M ) ⊆ (Σ ∗ \ M )). Acknowledgments I am grateful to Prof. Mati Pentus for fruitful discussions and constant attention to my work. I am also grateful to the anonymous referees for their helpful comments and suggestions. This research was supported by the Russian Foundation for Basic Research (grants 11-01-00281-a and 12-01-00888-a), by the Presidential Council for Sup- port of Leading Research Schools (grant NSh-5593.2012.1), and by the Scientific and Technological Cooperation Programme Switzerland–Russia (STCP-CH-RU, project “Computational Proof Theory”). References 1. Avron, A.: Natural 3-valued logics — characterization and proof theory. Journal of Symbolic Logic, Vol. 56, No. 1, 276–294 (1991) 2. Buszkowski, W.: Compatibility of categorial grammar with an associated category system. Zeitschr. f¨ur Math. Logik und Grundl. der Math. 28, 229–238 (1982) 3. Kleene, S. C.: Introduction to metamathematics. D. van Nostrand Company, New York — Toronto (1952) 4. Lambek, J.: The mathematics of sentence structure. Amer. Math. Monthly, Vol. 65, No. 3, 154–170 (1958) 5. Lambek, J.: Deductive systems and categories II. Standard constructions and closed categories. Category Theory, Homology Theory and Their Applications I, ed. by P. Hilton (Proc. of the Conference held at the Seattle Research Center of the Battelle Memorial Institute, June 24–July 19, 1968; Springer Lect. Notes Math., vol. 86), 76–122. Springer, Berlin (1969) 6. Morrill, G.: Categorial Grammar: Logical Syntax, Semantics, and Processing. Ox- ford University Press, Oxford (2011) 7. Pentus, M.: Free monoid completeness of the Lambek calculus allowing empty premises. Proc. Logic Colloquium ’96, ed. by J. M. Larrazabal, D. Lascar, G. Mints (Lect. Notes Logic; vol. 12), 171–209. Springer, Berlin (1998) 8. Pentus, M.: Lambek calculus is NP-complete. Theoretical Comput. Sci., Vol. 357, No. 1–3, 186–201 (2006) 9. Soboci´nski, B.: Axiomatization of a partial system of three-value calculus of propo- sitions. Journal of Computing Systems, Vol. 1, 23–55 (1952) 10. Zvonkin, M. M.: Language models for the Lambek calculus with the unit (in Rus- sian). Term paper, Dept. of Math. Logic and Theory of Algorithms, Moscow State University (2011)  A trivalent logic that encapsulates intuitionistic and classical logic Tin Perkov Polytechnic of Zagreb, Croatia [email protected] Abstract. A third truth-value is proposed with purpose to distinguish intuitionistic valid formulas within classical validities. Keywords: trivalent logic, intuitionistic logic, Kripke semantics 1 Introduction In the classical semantics for propositional logic, we interpret propositional vari- ables by assigning a truth-value 0 or 1 to each of them. Then we extend this assignment to all well-formed formulas in a familiar way, by truth tables. If we introduce the third truth-value, say 1/2, we need to include it in truth tables, and this has been done in various ways, resulting in various systems of trivalent logic, like Lukasiewicz [8], Kleene [6], G¨odel logics [4] etc. On the other hand, even with only two truth values we can get diversity by considering semantics other then truth functional, e. g. Kripke semantics. In this way we get intuition- istic logic or, if we also enrich syntax by adding operators, modal logics and so on. In this paper, a simple example of combining three-valued logic with Kripke semantics is presented, in which classical propositional tautologies and intuition- istic validities are characterized by a correspondence with truth values. Truth value 0 is read as false, 1 as strongly true, and new truth value 1/2 is read weakly true. From the way in which semantics will be defined, it will follow that tautologies correspond to non-falsity (truth value 1 or 1/2), while intuitionistic validities correspond to the truth value 1. In Section 3 the same idea is applied to the first-order logic, using Kripke semantics for the intuitionistic predicate logic. 2 Propositional logic We work with the basic countable propositional vocabulary. Fix a countable set PROP = {p1 , p2 , . . .}. Elements of PROP are called propositional variables. Sometimes we denote them by p, q, and so on, without indices, namely in exam- ples in which only few of them occur. We denote by FORM a set of well-formed 72 Tin Perkov formulas, the smallest set that contains PROP ∪{⊥} and is closed under con- junctions, disjunctions and conditionals. That is, the syntax is given by F ::= p |⊥|F1 ∧ F2 |F1 ∨ F2 |F1 → F2 , where p ∈ PROP. We abbreviate ¬F := F → ⊥. Consider a Kripke frame F = (W, 6), where W is a non-empty set, and 6 a partial ordering on W called accessibility relation. A local assignment of truth values is a family l = {lw : w ∈ W } of functions lw : FORM → {0, 1/2, 1} such that for all w ∈ W we have: 1. if lw (p) = 1 and w 6 v, then lv (p) = 1, for all p ∈ PROP, 2. lw (⊥) = 0,   1, lw (F1 ) = lw (F2 ) = 1, 3. lw (F1 ∧ F2 ) = 0, lw (F1 ) = 0 or lw (F2 ) = 0,   1/2, otherwise,  1, lw (F1 ) = 1 or lw (F2 ) = 1, 4. lw (F1 ∨ F2 ) = 0, lw (F1 ) = lw (F2 ) = 0,  1/2, otherwise,   1, for all v > w, if lv (F1 ) = 1 then lv (F2 ) = 1,  1/2, if lw (F1 ) 6= 0 then lw (F2 ) 6= 0, and 5. lw (F1 → F2 ) =   there is v > w such that lv (F1 ) = 1 and lv (F2 ) 6= 1,  0, otherwise. From 2. and  5. we conclude:  1, for all v > w, lv (F ) 6= 1, lw (¬F ) = 1/2, there is v > w such that lv (F ) = 1, and lw (F ) = 0,  0, there is v > w such that lv (F ) = 1, and lw (F ) 6= 0. Furthermore, 1. is easily extended to all formulas by induction. We call M = (W, 6, l) a model. Clearly, M can be viewed as a Kripke model for intuitionistic logic, by putting w F if and only if lw (F ) = 1, since all clauses considering truth value 1 are exactly the same as in the definition of Kripke semantics for intuitionistic logic (see [7]). From this viewpoint, 1 is a designated truth value, while 0 and 1/2 are identified as both false. Let F ∈ FORM. We say that F is strongly valid if lw (F ) = 1 for any choice of model M = (W, 6, l), and any w ∈ W . We say that F is weakly valid if lw (F ) 6= 0, for any M and w. The following fact immediately follows from the previous remarks. Proposition 1. Let F ∈ FORM. Then F is strongly valid if and only if it is an intuitionistic validity. The truth value 1 corresponds with validities of propositional intuitionistic logic both on the local and global level, since the semantics is intentionally defined in a way that completely resembles Kripke semantics for intuitionistic logic. On the other hand, we do not have local correspondence of truth values 1 and 1/2 with classical propositional truth, namely since the statements involving truth value 0 clearly do not cover all cases of classical falsity. A trivalent logic that encapsulates intuitionistic and classical logic 73 Example 1. Let F = ({w}, {(w, w)}). Let p and q be two propositional variables and l a local assignment such that lw (p) = 1/2 and lw (q) = 0. If we consider 1/2 a designated value, then p → q is false at w in the classical sense, but lw (p → q) = 1. But in terms of validity, when we abstract away from a choice of a model, we have the result analogous to the previous proposition. Proposition 2. Let F ∈ FORM. Then F is weakly valid if and only if it is a propositional tautology. Proof. Assume F is not a tautology. Then there exists a (classical) assignment a : FORM → {0, 1} such that a(F ) = 0. Now let F = ({w}, {(w, w)}). Define a local assignment l by putting lw (p) = a(p) for all p ∈ PROP. This satisfies the clause 1. of the definition of local assignment, so l is well defined. It is easy to show by induction that lw (A) = a(A) for all A ∈ FORM. Thus lw (F ) = 0. Hence by contrapositive, a weakly valid formula is a tautology. The reverse implication follows immediately from the definition of local as- signment. t u 3 Predicate logic Let σ be a first-order vocabulary. For the sake of notational simplicity, assume σ has no function or constant symbols, so the only terms are individual variables, which we denote by x, y, z, with or without indices. We denote the set of variables, which is countable, by VAR. So, σ has finitely or countably many relation symbols which we denote by R, R1 , R2 and so on. Each relation symbol has a given arity. An atomic formula is Rx1 x2 . . . xn , where R is an n-ary relation symbol, and x1 , . . . , xn variables. We denote the set of atomic formulas by AT. By FO we denote the set of all well-formed formulas over σ, which is the smallest set containing AT ∪{⊥} that is closed under conjunctions, disjunctions, conditionals and quantifiers. In other words, the syntax is F ::= A|⊥|F1 ∧ F2 |F1 ∨ F2 |F1 → F2 |∀xF |∃xF, where A ∈ AT. As before, we abbreviate ¬F := F → ⊥. A model based on a Kripke frame F = (W, 6) is M = (W, 6, M ), where M is a family {Mw : w ∈ W } of non-empty sets, together with three-valued interpretations of relation symbols, i. e. functions Rw : Mwn → {0, 1/2, 1} for each R ∈ σ, where n is the arity of R, such that we have: 1. if w 6 v, then Mw ⊆ Mv , 2. if w 6 v and Rw (c1 , . . . , cn ) = 1, then Rv (c1 , . . . , cn ) = 1. Assigning truth values to the first-order formulas at w ∈ W depends on a val- uation of variables by elements of Mw . Note that, if w 6 v, since we have 74 Tin Perkov Mw ⊆ Mv , a is also a valuation of variables by elements of Mv . We denote by a(c/x) a valuation that assigns c to x, and agrees with a otherwise. Given a val- a uation a : VAR → Mw , an assignment at w is a function lw : FO → {0, 1/2, 1} defined as follows: a 1. lw (Rx1 . . . xn ) = Rw (a(x1 ), . . . , a(xn )) for all Rx1 . . . xn ∈ AT, a 2. lw (⊥) = 0,  a a  1, lw (F1 ) = lw (F2 ) = 1, a a a 3. lw (F1 ∧ F2 ) = 0, lw (F1 ) = 0 or lw (F2 ) = 0,  1/2,  a otherwise, a  1, lw (F1 ) = 1 or lw (F2 ) = 1, a a a 4. lw (F1 ∨ F2 ) = 0, lw (F1 ) = lw (F2 ) = 0,  1/2, otherwise,   1, for all v > w, if lva (F1 ) = 1 then lva (F2 ) = 1,  a a a 1/2, if lw (F1 ) 6= 0 then lw (F2 ) 6= 0, and 5. lw (F1 → F2 ) =   there is v > w such that l a a v (F1 ) = 1 and lv (F2 ) 6= 1,   0, otherwise,  a(c/x)  1, there is c ∈ Mw such that lw (F ) = 1, a a(c/x) 6. lw (∃xF ) = 0, for all c ∈ Mw , we have lw (F ) = 0,   1/2, otherwise,   a(c/x)  1, for all v > w and all c ∈ Mw , we have lv (F ) = 1, a a(c/x) 7. lw (∀xF ) = 0, there is c ∈ Mw such that lw (F ) = 0   1/2, otherwise, To get a standard intuitionistic Kripke model (cf. [7]) from a model M, we just need to define (classical) interpretations of relation symbols for each w ∈ W . Obviously, we interpret an n-ary relation symbol R by the relation {(c1 , . . . , cn ) : Rw (c1 , . . . , cn ) = 1}. Clearly, model and assignment are defined in a way to ensure that w a F (this denotes the intuitionistic satisfaction relation a under a valuation a) in thus defined Kripke model if and only if lw (F ) = 1. a We say that a formula F ∈ FO is strongly valid if lw (F ) = 1 for any model M = (W, 6, M ), w ∈ W and a : VAR → Mw . We say that F is weakly valid if lw (F ) 6= 0, for any M, w and a. An analogue of Proposition 1 immediately follows. Proposition 3. Let F ∈ FO. Then F is strongly valid if and only if it is an intuitionistic validity. Similarly as in the case of propositional formulas, we also establish a corre- spondence between weak validity and classical validity. Proposition 4. Let F ∈ FO. Then F is weakly valid if and only if it is a valid formula of predicate calculus. Proof. Let F be a weakly valid formula. Assume that F is not a classical validity. Then there exists a σ-structure M and an assignment a : VAR → M , where M A trivalent logic that encapsulates intuitionistic and classical logic 75 is the domain of M, such that M 6|=a F . Let F = ({w}, {(w, w)}). To define a model based on F, we only need to define Mw and a three-valued interpretation of relation symbols on Mw . Put Mw = M and for any R ∈ σ, with the arity n, define Rw (c1 , . . . , cn ) = 1 if (c1 , . . . , cn ) ∈ RM , where RM denotes the relation that interprets R in M, and Rw (c1 , . . . , cn ) = 0 otherwise. Since F is singleton, this is a well-defined model. Now, by induction we easily see that under the assignment a we have M |=a A a a if and only if lw (A) = 1, and M 6|=a A if and only if lw (A) = 0, for any A ∈ FO. a Thus lw (F ) = 0, hence F is not weakly valid, which contradicts the assumption. So, F is in fact a classical validity. For the converse, let F ∈ FO be a classical validity. It is easy to see from a the definition of lw that we can not define a model and an assignment such that a lw (F ) = 0, which proves the claim. tu 4 Concluding remarks It should be noted that Baaz and Ferm¨ uller [1] systematically combine many- valued and intuitionistic logic, namely tableau calculi for both, to obtain intu- itionistic many-valued logics. They obtain soundness and completeness results for these logics with respect to intuitionistic Kripke semantics generalized to many-valued interpretation in a somewhat similar way as in this paper. While the notion of Kripke model is essentially the same, although more general then the one presented here, semantics of connectives however differs, due to differ- ent intentions – authors of [1] develop intuitionistic semantics generalized to the many-valued context, without considering classical validities. In propositional case this has already been done by Rousseau [10], who developed sequent calcu- lus for many-valued intuitionistic logic, which was further improved by Reznik and Curmin [9]. Furthermore, it may be worthwhile to explore applying similar idea to modal logic. Indeed, the Lukasiewicz’s original idea behind introducing three-valued logic was to reason about possibility. But it has been shown that standard modal logic is not definable by any finitely many-valued logic with any truth table se- mantics (see [3]). However, B´eziau [2] considers some non-standard modal logics based on four-valued truth tables. On the other hand, one might ask if there is a Kripke-like semantics for three (or more) valued logic that would capture modality, without using modal operators in a language as symbols. Consider the basic propositional modal language with one modal operator . It should be clear that by slightly adapting the definition of local assignment from Section 2, we can characterize the truth of a formula of the form F , where F ∈ FORM, by the strong truth of F . It is not momentarily clear if we can characterize the truth of more complex modal formulas, e. g. nested boxes, by generalizing this approach somehow, but it might be worthy to explore this further. Also, W´ojcicki [11, 12] uses similar approach to define Kripke semantics for Nelson logic, that is, an extension of propositional intuitionistic logic by a con- nective ∼ called strong negation. Analogous semantics for predicate Nelson logic 76 Tin Perkov is considered by Hasuo and Kashima [5]. Roughly, semantics of negation ¬ corre- sponds to the strong truth of negation, while semantics of ∼ corresponds to weak truth of negation as presented in this paper. We leave for further consideration a question if Nelson logic can be precisely captured by multi-valued approach without using the strong negation as a symbol of a language. References 1. M. Baaz, C. G. Ferm¨ uller: Combining many-valued and intuitionistic tableaux. In: P. Miglioli et. al. (eds.) Theorem Proving with Analytic Tableaux and Related Methods, pp. 65–79. Springer (1996) 2. J. Y. B´eziau: A new four-valued approach to modal logic. Logique et Analyse, 54, 109–121 (2011) 3. J. Dugundji: Note on a property of matrices for Lewis and Langford’s calculi of propositions. Journal of Symbolic Logic, 5, 150–151 (1940) 4. K. G¨ odel: Zum intuitionistischen Aussagenkalkl. Anzeiger der Akademie der Wis- senschaftischen in Wien, 69, 65–66 (1932), English translation in: K. G¨ odel: Collected Works Vol. I, S. Feferman et al. (eds.), Oxford: Oxford University Press (1986) 5. I. Hasuo, R. Kashima: Kripke completeness of first-order constructive logics with strong negation. Logic Journal of the IGPL 11(6), 615–646 (2003) 6. S. C. Kleene: On notation for ordinal numbers. Journal of Symbolic Logic, 3, 150-155 (1938) 7. S. A. Kripke: Semantical analysis of intuitionistic logic. In: J. Crossley and M. A. E. Dummett (eds.) Formal Systems and Recursive Functions, pp. 92–130. Amsterdam: North-Holland Publishing (1965) 8. J. Lukasiewicz: O logice tr´ ojwarto´sciowej, Ruch Filozoficny, 5, 170-171 (1920), En- glish translation in: J. Lukasiewicz: Selected Works, L. Borkowski (ed.), Amsterdam: North-Holland and Warsaw: PWN. (1970) 9. E. Reznik, P. Kurmin: Intuitionistic sequent calculi for finitely many-valued logics. Logic Journal of the IGPL 9(6), 793–812 (2001) 10. G. Rousseau: Sequents in many valued logic II. Fundamenta Mathematicae, 67, 125-131 (1970) 11. R. W´ ojcicki: Lectures on Propositional Calculi. Dordrecht: Kluwer Academic Pub- lishers (1988) 12. R. W´ ojcicki: Theory of Logical Calculi. Wroclaw: Ossolineum (1984)  TCS for presuppositions J´er´emy Zehr1 and Orin Percus2 1 Institut Jean Nicod, UMR 8128, ´ Ecole Normale Suprieure, France http://www.institutnicod.org/ 2 LLING, EA 3827, Universit´e de Nantes, France http://lling.univ-nantes.fr/ Abstract. For several decades now, there have been attempts to ac- count for vagueness and presuppositions in a uniform manner. These attempts are motivated by the fact that the two phenomena have some- thing in common: the lack of a solid truth-value judgment that we find when a presuppositional statement is used in a presupposition failure sit- uation, and when a vague predicate when used to describe a borderline case. In this paper, we extend this enterprise by considering the logi- cal system named TCS3 and developed by Cobreros&al. [3] to account for vagueness. Cobreros&al. introduce two notions of truth — tolerant truth and strict truth — that allow propositions to be characterized as both true and false, or as neither true nor false. We explore to what degree this system can be applied to treat presuppositional phenomena. In particular, we use the notion of strict truth to derive the presuppo- sition associated with a statement; this way of deriving presuppositions extends naturally to complex sentences and thus leads to an account for the phenomenon of presupposition projection. Keywords: vagueness, presuppositions, presupposition projection, tol- erant truth, strict truth, trivalence, logic, semantics 1 The TCS System Cobreros&al. [3] build their system on the basis of a bivalent logic. They start from a language in which predicates may combine with every constant of the language, and where they are associated with functions that return 1 (truth) or 0. Adapting their terminology 4 , we can speak of these functions as representing the classical meaning of a predicate. The classical meanings of connectives — the standard ones — insure that, when we speak classically, all the principles of 3 T CS stands for T olerant Classical Strict. 4 We will speak of classical (or strict or tolerant) meaning, even if strictly speaking Cobreros&al.’s definitions are in terms of classical (or strict or tolerant) truth. When we speak of the classical (or strict or tolerant) meaning of a predicate P, what we mean is a function that, given the value of a constant a, yields the classical (or strict or tolerant) value of Pa. 78 J´er´emy Zehr and Orin Percus 2 J´er´emy Zehr & Orin Percus classical logic are preserved. In particular, the classical meaning of negation is such that a proposition’s negation is true iff the proposition itself is not true, so we never find that both a proposition and its negation are true. Importantly, however, classical meaning is not the only type of meaning an expression can have: there are also two other types of meaning, strict meaning and tolerant meaning. Depending on how we want to assert a statement, we can associate it with its classical, strict or tolerant meaning. Usually we speak classically, but if we want to strengthen our discourse, we will associate our statements with their strict meanings; and if we want to weaken our discourse, we will associate our statements with their tolerant meanings. We give below definitions for strict and tolerant truth and falsity, following the general lines of Cobreros&al. Note that the definitions in the case of falsity correspond to definitions of negation — to say that a proposition is tolerantly, classically or strictly false is to say that its negation is tolerantly, classically or strictly true, respectively. Definition 1 (Strict truth and falsity of a vague predicate P). P(a) is strictly true for any a if and only if P is classically true of all individuals that are sufficiently like a with respect to the measure associated with P 5 . P(a) is strictly false for any a if and only if P is classically false of all individuals that are sufficiently like a with respect to the measure associated with P. Definition 2 (Duality in TCS). A proposition is tolerantly true if and only if it is not strictly false. A proposition is tolerantly false if and only if it is not strictly true. Definition 3 (Connectives in TCS). Conjunctions of the form A & B are strictly true if and only if a is strictly true and b is strictly true. Conjunctions of the form A & B are tolerantly true if and only if a is tolerantly true and b is tolerantly true. The contributions to strict and tolerant truth of the disjunction ∨ and the condi- tional → are defined in terms of negation and conjunction in the ways familiar from classical logic. It is important to observe the dualities that we find in this system: to say that a predicate is not strictly true of an individual is to say that it is tolerantly false of her; and reciprocally, to say that a predicate is not tolerantly true of an individual is to say that it is strictly false of her. Crucially, the dual of strict truth is not strict falsity nor is the dual of tolerant truth tolerant falsity. 5 In reality, Cobreros&al. imagine that vague predicates are associated with a relation of indifference between individuals. They go no further than this. But, assuming that each vague predicate is associated with a specific scale of measurement (e.g. as Kennedy [12]), we can see this relation as holding between two individuals if the difference of their measures on the scale falls below a certain threshold of “distin- guishability”. TCS for presuppositions 79 TCS for presuppositions 3 Here is an example. Consider a context of only four people (let’s name them a, b, c and d ) who are sorted by height: a is slightly smaller than b who is slightly smaller than c who is slightly smaller than d. It’s worth noting that the relation slightly smaller is not transitive: a being slightly smaller than b and b being slightly smaller than c does not entail that a is slightly smaller than c. In fact we will assume that a is not slightly smaller than c, nor is b slightly smaller than d. Assuming that the distribution of classical truth for tall is as specified in the first line of Table 1, the distribution of classical falsity would be as in the second line. Assuming that two individuals count as sufficiently alike with respect to tallness only when one is at most slightly smaller than the other, we then have the distribution of strict truth and falsity in Table 2, and accordingly the distribution of tolerant truth and falsity in Table 3. Table 1. Classical truth and falsity of tall for a, b, c and d a b c d not true not true true true false false not false not false Table 2. Strict truth and falsity of tall for a, b, c and d a b c d not true not true not true true false not false not false not false Table 3. Tolerant truth and falsity of tall for a, b, c and d a b c d not true true true true false false false not false Notice that, in the case of b and c, tall is on the one hand neither strictly true nor strictly false, and on the other hand both tolerantly true and tolerantly 80 J´er´emy Zehr and Orin Percus 4 J´er´emy Zehr & Orin Percus false. This situation arises because of the way in which Cobreros&al. establish their dualities. In their system, for someone not to be strictly tall doesn’t mean for him to be strictly not tall; rather, it means that he’s tolerantly not tall. At the same time, when someone (like a) is not (even) tolerantly tall, this means that he’s strictly not tall (and necessarily tolerantly not tall too). These remarks suggest that the Cobreros&al. semantics can be recast in terms of a sort of modal semantics with a strictly operator — even if on their formulation there are two special kinds of meaning, tolerant and strict, their duality allows us to formulate one in terms of the other, by playing on the relative scope of the negation and a strictly operator. The aspect of Cobreros&al.’s system that interests us here is that it gives us a way of characterizing borderline cases for vague predicates — that is, cases that trigger an unclear truth-value judgment. Borderline cases are simply those for which a vague predicate yields a proposition that is neither strictly true nor strictly false — or, equivalently, cases for which the proposition is both tolerantly true and tolerantly false. Alternatively stated, a borderline case for a vague predicate is a case that leads to different strict and tolerant values for the proposition that results when we apply that predicate. Note that, the Cobreros&al. approach seems to predict that, to the extent that strict readings are natural, we should be able to judge predicates like neither − tall − nor − not − tall to be true of borderline cases for tall; likewise, to the extent that tolerant readings are natural, we should be able to judge predicates like both − tall − and − not − tall to be true of the same cases. In support of their approach, Cobreros&al. cite the results of an experiment by Alxatib&Pelletier [1], who found judgments of precisely this kind. Of related interest is the fact that, to the extent that tolerant readings are natural, the system provides an account for the sorites paradox: the paradox arises due to the tolerant way of reading the inductive premiss. Consider the following statement, meant to exemplify the kind of statement that appears as a premiss in versions of the sorites paradox. Example 1. If a man is slightly smaller than a tall man, then he is a tall man too. Strictly speaking, ( 1 ) conveys that any man who is slightly smaller than a tolerantly tall man is a strictly tall man — and this is false. But tolerantly speaking, ( 1 ) conveys that any man who is slightly smaller than a strictly tall man is a tolerantly tall man — and this is true. (To see this, suppose first that ( 1 ) should be represented as a formula of the form ∀y∀z[[P z&Ryz] → P y] - or equivalently as a conjunction of conditionals of the form [[P a&Rab] → P b] , where Rab expresses that b is slightly smaller than a. Then it suffices to observe that a conditional of the form [p → q] is strictly true if and only if the tolerant truth of p entails the strict truth of q, and that it is tolerantly true if and only if the strict truth of p entails the tolerant truth of q.6 ). With this in mind, consider 6 Here is a proof of the first claim; the proof of the second is parallel. For brevity, we abbreviate “φ is strictly true” as S[φ], “φ is not strictly true” as TCS for presuppositions 81 TCS for presuppositions 5 the tolerant reading. If a is a strictly tall man and b is slightly smaller than a, accepting the inductive premiss in a tolerant way does not lead you to conclude that b is a strictly tall man; rather you have to conclude that b is a tolerantly tall man. And if c is slightly smaller than b, then, even if this means that he’s slightly smaller than a tolerantly tall man, he is just trivially concerned by the inductive premiss if b happens not to be a strictly tall man — we don’t have to conclude that c is a strictly or tolerantly tall. This is the way the TCS system handles the sorites paradox. The “trick” is that the vague predicate in the antecedent of the conditional has to be understood in the dual way of the one in the consequent. In sum, the TCS system can be seen as a system that describes strengthening and weakening of meaning. On the one hand, there is a “classical” way of using statements on which a statement is necessarily exclusively true or false. But, on the other hand, we might wish to strengthen or weaken our way of speaking, and on these modified ways of using statements, a statement can be neither true nor false, or both true and false. 2 TCS for presuppositions 2.1 Definitions In what follows, we will explore how the TCS system might be used to treat presuppositions. More specifically, we will try to answer these two questions: i) what would we consider to be the classical, strict and tolerant meanings of presuppositional predicative objects (PPOs) 7 and sentences containing them?; ii) given the classical, strict and tolerant meanings for PPOs, can we derive the presuppositions associated with the various statements in which they appear, and more specifically, can this system account for presupposition projection? Let us start with the classical meaning of a presuppositional statement. In cases where the presupposition associated with a presuppositional statement is fulfilled, there is no debate about when the sentence is true and when it is false. For instance, take a sentence like ( 2 ), associated with the presupposition that Mary used to smoke. In cases where the presupposition is fulfilled, it is uncontroversial to say that the sentence is true if Mary does not smoke now and false otherwise. ¬S[φ] and “φ is strictly false” as S[¬φ]; similarly, we use T [φ] and T [¬φ] to talk about tolerant truth and falsity. To start with, note that it follows from Definition 2 that, for any φ, T [¬¬φ] iff T [φ] (since T [¬¬φ] iff ¬S[¬φ] and ¬S[¬φ] iff T [φ]). Now, by Definition 3, S[p → q] iff S[¬[p&¬q]]. But S[¬[p&¬q]] iff ¬T [¬¬[p&¬q]] (by Definition 2) iff ¬T [p&¬q] (by the above reasoning) iff ¬T [p] or ¬T [¬q] (by Definition 3) iff ¬T [p] or S[q] (by Definition 2). 7 We adopt the terminology of Charlow [4]. PPOs are predicates such as quit/stop X that are known to trigger the presupposition that the individual they are asserted of used to X or predicates such as know that Y that are known to trigger the presupposition that Y . The article “Presupposition” of the Stanford Encyclopedia [2] includes a list of lexical classes that can be seen as corresponding to PPOs. 82 J´er´emy Zehr and Orin Percus 6 J´er´emy Zehr & Orin Percus Example 2. Mary has stopped smoking At the same time, in cases where the presupposition is not fulfilled, there has been a controversy — ever since Russell [13] argued, contra an interpretation of Frege [9], that a presuppositional statement should be considered false when the presupposition is not fulfilled. In the spirit of Cobreros&al., we will simply imag- ine that the classical meaning of a presuppositional statement distinguishes those cases where the statement is uncontroversially true from those cases where it is not. We will represent a sentence like ( 2 ) as not − smokeused−to−smoke (M ary) and consider classical truth values to be defined as follows: Definition 4 (Classical truth of a statement Pp ). Pp (a) is classically true for any a if and only if p(a) and P (a) are both classically true. Definition 4 tells us that ( 2 ) is classically true if and only if Mary does not smoke but used to; otherwise it is classically false, given that classically a proposition’s negation is true iff the proposition itself is not. In other words, ( 2 ) is classically false not only if Mary used to smoke and has kept on smoking (in which case not−smoke(M ary) would be classically false), but also if Mary never smoked (since in this case used-to-smoke(Mary) would be classically false). In actual fact, it seems that, when people have to assign a truth value to a statement in the knowledge that its presupposition is not fulfilled — when they are forced to choose between “true” and “false” — they behave in a Russellian way and judge it false. This judgment reflects the classical truth value. Now let us turn to the strict meanings for presuppositional statements. The hallmark of a presupposition is the lack of a clear truth value judgment in cases where the presupposition is known to be unfulfilled - this is the source of the controversy we alluded to above. Now, we also find lack of a clear truth judgment when borderline cases of vague predicates are concerned, and Cobreros&al. char- acterize those statements as statements that are neither strictly true nor strictly false. This suggests to us that we should adapt Cobreros&al.’s approach in such a way that presupposition failures come out as neither strictly true nor strictly false. We can do so as follows: Definition 5 (Strict truth and falsity of a statement Pp 8 ). Pp (a) is strictly true for any a if and only if p(a) is classically true and P (a) is classically true. Pp (a) is strictly false for any a if and only if p(a) is classically true and P (a) is classically false. We will go a little further than this. In the discussion until now, we have viewed sentences as literally encoding presuppositions, and treated representa- tions like not − smokeused−to−smoke (M ary) as directly expressing the presup- position that Mary used to smoke. But another possible position is that the 8 The definition that Cobreros&al. give for the strict meaning of a vague predicate makes it stronger than its classical meaning: the truth (falsity) of a strict assertion of a vague predicate entails the truth (falsity) of its classical assertion, while the reverse is not true. Given our definitions of strict and classical meanings of a statement Pp , we observe the same relation of strength. TCS for presuppositions 83 TCS for presuppositions 7 presupposition is derived, in the following way. Our definitions already establish that a form Pp (a) is neither strictly true nor strictly false if p(a) is classically false. One might take the position that there is a “bridge principle” that derives as presuppositions of a statement P those propositions whose classical falsity would prevent P from being strictly true or false. This is what we will assume9 : Principle 1 (Presupposition and strict truth-value). Any proposition P is associated with the presupposition that S[P ] or S[¬P ]. Note that this implies that the use of a vague predicate is associated with the presupposition that we’re not talking about a borderline case; and thus that, whenever we use a vague predicate to describe a borderline case, there is a presupposition failure. We could then associate the lack of a clear truth judgment specifically with presupposition failure: Principle 2 (Lack of truth-value judgment in cases of presupposition failure). When confronted with a presupposition failure, a speaker will be un- easy giving a truth value judgment for the statement whose presupposition is unfulfilled. In sum, on our adaptation of the TCS system, simple sentences that are as- sociated with presuppositions essentially encode a stipulation about their strict meaning. The presupposition is derived from this: the presupposition that is as- sociated with a PPO is the condition that needs to be satisfied for the predication of this PPO to be either strictly true or strictly false. In this manner, Pp (a) gives rise to the presupposition that p(a) is classically true. For completeness, let us show this explicitly. (In what follows, for brevity we will write P instead of P (a) and p instead of p(a).) By Principle 1, Pp is associated with the presupposition that S[Pp ] or S[¬Pp ]. But by Definition 5, S[Pp ] iff C[p] and C[P ], while S[¬Pp ] iff C[p] and C[¬P ]. So Pp is associated with the presupposition that C[p] and either C[P ] or C[¬P ], or in other words with the presupposition that C[p] (as, for any φ, it is always the case that C[φ] or C[¬φ]). Note that the condition in which a predication of a PPO is either strictly true or strictly false is the condition in which there would be no difference in the resulting classical or strict truth value for the sentence (since the strict meaning is stronger than the classical one — see note 5). In this light, qualifying an expression as “presuppositional” can be seen as anticipating its behavior in some contexts; rather, what would be intrinsically associated with a PPO would not be a presupposition anymore but an ambiguity between its classical and its strict meaning 10 . 9 As before, we write S[φ] as an abbreviation for “φ is strictly true”. 10 This idea of associating a (regular) truth-value with an expression only when it wouldn’t give rise to different truth-judgments no matter how we interpret it — and observing a truth-value gap when different interpretations lead to different truth- judgments — is reminiscent of the idea of supervaluationism, which was originally proposed by van Fraassen [8] to account for presuppositions. Within this frame- 84 J´er´emy Zehr and Orin Percus 8 J´er´emy Zehr & Orin Percus 2.2 Judgments for simple predications Our set-up, on which PPOs are associated with a particular kind of strict mean- ing, correctly predicts the fact that we naturally judge a predication of a PPO as neither true nor false when the associated presupposition is not fulfilled. For in- stance, it correctly predicts that, given the knowledge that Mary never smoked, it is natural to judge ( 2 ) in this way — this follows from the fact, that, if Mary never smoked, the sentence is neither strictly true nor strictly false. At the same time, it also potentially allows for a judgment of falsity in this kind of situation, for the sentence is classically false. And this judgment indeed seems to be possible as well. The fact that one can say of this sentence both that it is false and that it is not false is naturally accounted for given its strict and classical meanings. A further successful prediction of the approach is that, in this same kind of sit- uation, the negative counterpart of a sentence like ( 2 ) should naturally give rise to the same neither-true-nor-false judgment. We make this prediction to the ex- tent that we would represent a sentence like ( 3 ) as ¬ not−smoke used−to−smoke (M ary), the negation of ( 2 ). To see this, notice that to say that S[¬ not−smoke used−to−smoke (M ary)] or S[¬¬not − smoke used−to−smoke (M ary)] is just to say that S[ not − smoke used−to−smoke (M ary)] or S[not − smoke used−to−smoke (M ary)] (due to Definition 2), so ( 3 ) is predicted to have the same presuppo- sition as ( 2 ), in accordance with the common wisdom concerning the negative counterparts of presuppositional statements. At the same time, our approach also potentially allows for a judgment of truth in this kind of situation, for the sentence is classically true, and this judgment seems to be possible too. Parallel to the affirmative case, the fact that one can say of this sentence both that it is true and that it is not true is naturally accounted for given its strict and classical meanings. Example 3. Mary has not stopped smoking However, a word is in order about tolerant meanings, which we have not yet discussed in connection with presuppositional phenomena. Given Definition 2, in a situation in which Mary never smoked, ( 2 ) is tolerantly true, but it would certainly be quite unnatural to judge ( 2 ) true on the basis of the knowledge that Mary never smoked. The success of this approach thus interacts with the question of how natural it is to judge a sentence true on the basis of the fact that it is tolerantly true. Perhaps it is quite unnatural in other cases as well, and in this case there is no problem for the approach we have taken to presup- positions. But note that Cobreros&al. rely on the assumption that it is natural specifically in their treatment of the sorites paradox, and in their explanation of the both-true-and-false judgments associated with vague predicates as observed by Alxatib&Pelletier. The issue clearly deserves further examination. work Fine [6] proposes that a vague expression is (super)true or (super)false if and only if, no matter how we precisify our language, its logical value would still be truth/falsity — and neither (definitely/super)true nor (definitely/super)false when its logical value depends on how we precisify our language. TCS for presuppositions 85 TCS for presuppositions 9 2.3 Presupposition projection with connectives (and, or, if ) We have adopted an approach on which the presuppositions of a statement are derived from the conditions for its strict truth and strict falsity. Since our sys- tem as it stands makes predictions about the conditions under which complex sentences are strictly true and strictly false, this means that it also makes predic- tions about the presuppositions of complex sentences. In other words, it makes predictions about the patterns of “presupposition projection” that we should find — about the ways in which the presuppositions that we associate with com- plex sentences relate to the presuppositions that we associate with the sentences that they embed. We have already seen this in the case of negation. A major challenge for theories of presuppositions is to account for presup- position projection effects in a non-stipulative way. In what follows, we review some more basic facts about presupposition projection and show to what extent our approach can account for them. Some can be accounted for without any further stipulation, and this alone seems to render our approach promising as the basis for a theory of presupposition. Others need additional stipulations. 2.4 Facts We will be concerned here with presupposition projection effects in sentences containing the connectives and, or and if — and thus in sentences that we would formalize with the connectives &, ∨ and →. For example, consider the following statements in ( 4 ) and their counterparts in ( 5 ) where the embedded clauses are reversed: Example 4. (a) Mary has stopped smoking and she buys anti-smoking patches. (b) Either Mary has stopped smoking or she doesn’t buy anti-smoking patches. (c) If Mary has stopped smoking, then she buys anti-smoking patches. Example 5. (a) Mary buys anti-smoking patches and she has stopped smoking. (b) Either Mary doesn’t buy anti-smoking patches or she has stopped smoking. (c) If Mary buys anti-smoking patches, then she has stopped smoking. All of these statements embed the proposition [she/Mary] has stopped smok- ing, which is associated with the presupposition that Mary used to smoke. But this presupposition “projects” in different ways. The statements in ( 4 ), which embed the proposition “to the left”, retain the presupposition that Mary used to smoke (we say that here the presupposition projects globally). By contrast, those in ( 5 ), which embed the proposition “to the right,” seem to presuppose that, if Mary buys anti-smoking patches, then she used to smoke (we could say that here it projects conditionally or restrictively) 11 . Adapting these sentences 11 We intend our if...then... here to be understood as material implication: presuppo- sition failure arises when Mary buys anti-smoking patches but has never smoked. 86 J´er´emy Zehr and Orin Percus 10 J´er´emy Zehr & Orin Percus to our formalism 12 , it thus seems that sentences of the form in (1) presuppose that C[p] while sentences of the form in (2) conditionalize this presupposition as below: Form 1. a. Ap &B presupposition: C[p] b. Ap ∨ B presupposition: C[p] c. Ap → B presupposition: C[p] Form 2. a. B&Ap presupposition: C[p] b. B ∨ Ap presupposition: C[p] c. B → Ap presupposition: C[p] (In support of the claim that sentences that embed the proposition “to the right” should be viewed as behaving in this way, consider the sentences in ( 6 ). Unlike the sentences in ( 5 ), these seem to be associated with no presupposition at all. This effect can be explained if the process that derives presuppositions derives for ( 6a ) — for example — the presupposition that, if Mary used to smoke, then she used to smoke. This presupposition is vacuous: it could never be false.) Example 6. a. Mary used to smoke and she has stopped smoking. b. Either Mary never smoked or she has stopped smoking. c. If Mary used to smoke, then she has stopped smoking. 2.5 TCS predictions As things stand, with no further modification, our system makes the following predictions. It correctly derives the conditional presuppositions for sentences of the form in 2 above. To see this, recall that a proposition P is associated with the presup- position that S[P ] or S[¬P ]. Below we show that in this case this amounts to the conditional presupposition we specified above. (In what follows, it is useful to recall that classical truth and falsity are defined in such a way that, for any φ, C[¬φ] iff ¬C[φ]. Moreover, we assume that B in all of the cases we discuss is associated with no presupposition, and thus that S[B] iff C[B] and S[¬B] iff C[¬B]. It is also useful to remember that it follows from Definition 2 that, for any φ, S[¬¬φ] iff S[φ].13 ) 12 In what follows, we will use Ap to represent a proposition that is associated with the presupposition that p. In other words, strict truth and falsity are determined as follows for such a proposition: Ap is strictly true iff p is classically true and A is classically true; Ap is strictly false iff p is classically true and A is classically false. 13 This is because S[¬[φ&ψ]] iff ¬T [φ&ψ] (by Definition 2) iff ¬T [φ] or ¬T [ψ] (by Definition 3) iff S[¬φ] or S[¬ψ] (by Definition 3). TCS for presuppositions 87 TCS for presuppositions 11 Proof (B&Ap is associated with the presupposition that if C(B) then C(p)). a. B&Ap is associated with the presupposition that S[B&Ap ] or S[¬[B&Ap ]]. (Principle 1) b. S[B&Ap ] iff S[B] and S[Ap ] (Definition 3) iff C[B] and C[p] and C[A] (Definition 5) c. S[¬[B&Ap ]] iff ¬T [B&Ap ] (Definition 2) iff ¬T [B] or ¬T [Ap ] (Definition 3) iff S[¬B] or S[¬Ap ] (Definition 2) iff C[¬B] or (C[p] and C[¬A]) (Definition 5) iff ¬C[B] or (C[p] and ¬C[A]) d. To say that C[B] and C[p] and C[A] or ¬C[B] or (C[p] and ¬C[A]) is to say that ¬C[B] or C[p], or in other words that if C[B] then C[p]. 14 � Proof (B ∨ Ap is associated with the presupposition that if ¬C(B) then C(p)). a. B ∨ Ap is associated with the presupposition that S[B ∨ Ap ] or S[¬[B ∨ Ap ]]. (Principle 1) b. S[B ∨ Ap ] iff S[¬[¬B&¬Ap ]] (Principle efdef:connectives) iff S[B] or S[Ap ] (Definition 2,3) iff C[B] or ( C[p] and C[A] ) (Definition 5) c. S[¬[B ∨ Ap ]] iff S[¬¬[¬B&¬Ap ]] (Principle 3) iff S[¬B&¬Ap ] (Definition 2) iff S[¬B] and S[¬Ap ] (Definition 3) iff C[¬B] and C[p] and C[¬A] (Definition 5) iff ¬C[B] and C[p] and ¬C[A] d. To say that C[B] or (C[p] and C[A]) or ¬C[B] and C[p] and ¬C[A] is to say that C[B] or C[p], or in other words that if ¬C[B] then C[p]. � Proof (B → Ap is associated with the presupposition that if C(B) then C(p)). 1. B → Ap is associated with the presupposition that S[B → Ap ] or S[¬[B → Ap ]]. (Principle 1) 2. S[B → Ap ] iff S[¬[B&¬Ap ]] (Definition 3) iff S[¬B] or S[Ap ] (Definitions 2,3) iff C[¬B] or (C[p] and C[A]) (Definition 5) iff ¬C[B] or (C[p] and C[A]) 3. S[¬[B → Ap ]] iff S[¬¬[B&¬Ap ]] (Definition 3) iff S[B&¬Ap ] (Definition 2) iff S[B] and S[¬Ap ] (Definition 3) iff C[B] and C[p] and C[¬A] (Definition 5) iff C[B] and C[p] and ¬C[A] 14 To see this, note that we intend the and and or in our metalanguage to behave like the connectives of classical logic, and the formula [[p&[q&r]] ∨ [¬p ∨ [q&¬r]]] is equivalent to [¬p ∨ q]. 88 J´er´emy Zehr and Orin Percus 12 J´er´emy Zehr & Orin Percus 4. To say that ¬C[B] or (C[p] and C[A]) or C[B] and C[p] and ¬C[A] is to say that ¬C[B] or C[p], or in other words that if C[B] then C[p]. � On the other hand, the system also incorrectly derives conditional presup- positions for sentences of the form in 1. It is obvious that it derives exactly the same presuppositions for 1a,b that it does for 2a,b, where the embedded propo- sitions are switched. This is because “&” is symmetric: for any φ, ψ, S[φ&ψ] iff S[φ&ψ] and S[¬[φ&ψ]] iff S[¬[φ&ψ]]. In the case of 1c, we will derive the same presupposition that we derive for the disjunction 2b: Proof (Ap → B is associated with the presupposition that if ¬C(B) then C(p) ). 1. Ap → B is associated with the presupposition that S[Ap → B] or S[¬[Ap → B]]. 2. S[Ap → B] iff S[¬[Ap &¬B]] iff S[¬Ap ] or S[B] iff (C[p] and ¬C[A]) or C[B] S[¬[Ap → B]] iff S[¬¬[Ap &¬B]] iff S[Ap ] and S[¬B] iff C[p] and C[A] and ¬C[B] To say that (C[p] and ¬C[A]) or C[B] or C[p] and C[A] and ¬C[B] is to say that C[p] or C[B], or in other words that if ¬C[B] then C[p]. � A possible way of getting around this problem is to supplement this system with a principle that effectively projects by brute force presuppositions associ- ated with the proposition on the left side of a connective. For example, one could supplement the definitions of strict truth and falsity with a clause that specifi- cally concerns propositions built out of connectives with a presuppositional item on the left: Definition 6 (“Incremental” strict truth and falsity). Let Pp be a proposi- tion associated with the presupposition p, Q a proposition and × any connective. Then: Pp × Q is strictly true if and only if p is classically true and P × Q is strictly true. Pp × Q is strictly false if and only if p is classically true and P × Q is strictly false. 15 This can be seen as a variant of a proposal by Fox [7] to account for presup- position projection within a trivalent (Strong Kleene) logic. (For his precise pro- posal, Fox draws his inspiration from Schlenker’s [14] pragmatically motivated 15 An anonymous reviewer complained that the need for this definition made the theory non predictive. Apparently, the reviewer felt that this definition implies that the projection behavior of a connective has to be lexically encoded. Although it is stated as a definition, one could arguably view this as a parsing principle, since it is designed to apply in full generality and full recursivity to a sequence of two propositions connected with any connective. Report to Fox [7] and Schlenker [14] for further details on this kind of implementation. TCS for presuppositions 89 TCS for presuppositions 13 approach to presupposition projection, and one could entertain alternatives to definition 6 that arrive at the same effect in a different way.) These additions to the definitions of strict truth and falsity would have no effect as far as the forms in 2 are concerned, but they would associate the forms in 1 with an additional presupposition that C[p]. The result as a whole will then be that the forms in 1 presuppose that C[p], as desired. 2.6 Comments and further extensions We just saw that, with the addition of a further order-sensitive stipulation con- cerning the strict truth and falsity of propositions formed with connectives, the TCS system derives correct presuppositions for a variety of complex sentences. Is there a reason to favor it over other kinds of approaches of presupposition projection? At least we can say the following. For one thing, a TCS system that computes strict values alongside classical values seems to handle some presuppo- sition facts more naturally than the simplest trivalent approaches that come to mind. Consider examples ( 2 ) and ( 3 ) again, and recall that they both give rise to two kinds of judgments in cases where it is known that Mary never smoked. The most natural judgment for both is a judgment of truth-valuelessness, but there is also another judgment possible, in particular when one is asked to choose between true and false: false for ( 2 ) and true for ( 3 ). Now, in order to account for the first, more natural judgment, a system that simply computes trivalent truth values would assign the sentences the third value #, but in that case it is not straightforward to account for the second kind of judgment: if, in order to account for the “false” judgment for ( 2 ), we were to say that in special circumstances a “false” judgment can correspond to #, then we would expect a “false” judgment for ( 3 ) as well, contrary to fact. By contrast, we have seen that the TCS system can account for the two kinds of judgment easily: the first concerns strict truth values, the second concerns classical truth values. The TCS system as we have presented it is also arguably immune to the kinds of criticisms that have been levelled against Heims [11] approach to presupposition projection in terms of context-change semantics. On Heims approach, there is a sense in which the aspects of a connectives semantics that are responsible for its contri- bution to presupposition projection are arbitrary and not intrinsically related to its contribution to truth conditions. On our approach, by contrast, there is a systematicity to the way in which a connective encodes its contribution to pre- supposition projection: a connectives contribution to presupposition projection derives from its strict meaning, which is related to its classical meaning. Since our TCS system for presuppositions is inspired by an account for vague- ness, and draws a connection between borderline cases and presupposition failure — the judgment of no clear truth value arises in the same way in the two cases — one might think that this approach generally predicts parallel behavior for the two kinds of predicates. In particular, one might think that it leads us to expect parallel “presupposition projection” effects. We would like to point out that, while systematically parallel behavior for the two kinds of predicates would certainly lend credence to an approach like ours, a difference in behavior could 90 J´er´emy Zehr and Orin Percus 14 J´er´emy Zehr & Orin Percus still be compatible with it: we defined strict truth and falsity differently for the two kinds of predicates in the basic cases (compare Definition 1 and Definition 5), and in principle they could also be defined differently when more complex constructions are involved. To make this remark concrete, consider a specific case where we seem not to find parallel behavior for the two kinds of predicates. Benjamin Spector points out, in work in progress, that sentences like ( 7a ) and ( 8a ) below do not seem to behave in the same way. On the one hand, when we consider Sarah to be a borderline case for tall (i.e. when we consider Sarah is tall to lack a truth value), we naturally judge ( 7a ) false if we consider Mary to be short (and thus answer “No” to ( 7b )); on the other hand, when we know that Sarah never smoked (i.e. when we consider Sarah has stopped smoking to lack a truth value), we are uneasy giving a truth judgment for ( 8a ) (or answering “Yes” or “No” to ( 8b )) even if we know that Mary began smoking at some point in the past and never gave up. Example 7. a. Sarah and Mary are both tall. b. Are both Sarah and Mary tall? Example 8. a. Sarah and Mary have both stopped smoking. b. Have both Sarah and Mary stopped smoking? Viewing things from the standpoint of our approach, it thus seems that the strict falsity of Mary is tall suffices to make ( 7a ) strictly false while the strict falsity of Mary has stopped smoking does not on its own render ( 8a ) strictly false — rather, in a sense, the presupposition associated with Sarah has stopped smoking projects. While we suspect that the factors behind this difference are complex, suppose for the sake of argument that the facts are as follows: quan- tifying over a PPO projects the presupposition “proportionally” (cf. Chemla [5], George [10]) while quantifying over a vague predicate results in a neither- true-nor-false judgment in those instances where, so to speak, one could only consider the sentence true by counting borderline cases as not being such. (So, in the case at hand where the quantifier is universal, we arrive for ( 8b ) at the presupposition that both used to smoke. We do not arrive at a neither-true-nor false judgment for ( 7a ) because counting Sarah as tall would not serve to make the sentence true.) We could derive this result if we defined strict truth and fal- sity for quantified statements differently for cases involving PPOs and for cases involving vague predicates. A sketch follows (where we assume that the logical language contains restricted quantification). It will follow from Definition 7 that a proposition of the form Qx[A(x)][P p(x)] presupposes that Qx[A(x)][p(x)] is classically true. It will follow from Definition 8 that a proposition of the form Qx[A(x)][P (x)] (where P is a vague predicate) presupposes, in effect, that the proposition is not merely true by virtue of considering P tolerantly. 16 16 For the sake of legibility, Definition 8 is formulated in terms of tolerant truth rather than strict falsity, but recall that a proposition is strictly false iff it is not tolerantly TCS for presuppositions 91 TCS for presuppositions 15 Definition 7 (Quantification with Q over a PPO Pp ). A proposition of the form Qx[A(x)][P p(x)] is strictly true if and only if Qx[A(x)][p(x)] is classically true and Qx[A(x)][P (x)] is classically true. A proposition of the form Qx[A(x)][P p(x)] is strictly false if and only if Qx[A(x)][p(x)] is classically true and Qx[A(x)][P (x)] is classically false. Definition 8 (Quantification with Q over a vague predicate P ). Let SS:A abbreviate the set of propositions { P (z) | z is a constant and A(z) is classically true } and let δQ abbreviate the proportion associated with the quan- tifier Q. A proposition of the form Qx[A(x)][P (x)] is strictly true if and only if δQ of the propositions in SP :A are strictly true. A proposition of the form Qx[A(x)][P (x)] is tolerantly true if and only if δQ of the propositions in SP :A are tolerantly true. 3 Conclusion We have suggested here that the TCS system can be adapted to account for pre- suppositional phenomena in a coherent way, rendering it a legitimate alternative to other treatments of presuppositions. Seeing the TCS system as a theory of presuppositions, one can in fact view part of this theory — the treatment of connectives — as independently motivated, given its original role in accounting for phenomena involving vague predicates. However, we have also seen that some stipulations have to be added that seem to go beyond what is needed in order to account for vagueness. Our initial motivation in extending TCS to presuppositions was the feeling that vagueness and presupposition have much in common, and more specifically the suspicion that expressions that lead to the lack of a clear truth-value judg- ment might be treated similarly by the grammar. (Which is not to imply that the lack of a truth-value judgment always arises for the same reason. We have suggested, though, that expressions that give rise to this phenomenon might have in common an essential ambiguity between two kinds of meaning.) At the same time, we touched on some tentative evidence that vague predicates and PPOs differ with respect to a detail of their “presupposition projection” behav- ior. Further empirical work will be needed to determine whether the facts really force us to different stipulations for vague predicates and for PPOs within a TCS system. We also mentioned in passing another area where the facts need to be better understood: facts concerning the naturalness of tolerant meanings in constructions involving vague predicates could have a bearing on the question of whether the same system should be used in order to treat presuppositions. true. The result of Definition 8 is thus that Qx[A(x)][P (x)] presupposes that either (i) δQ of the propositions in SP :A are strictly true; or (ii) it is not the case that δQ of the propositions in SP :A are tolerantly true. In other words, Qx[A(x)][P (x)] presupposes that, if it is the case that δQ of the propositions in SP :A are tolerantly true, then it is also the case that δQ of the propositions in SP :A are strictly true — or, put another way, that borderline cases cannot be held responsible for truth. 92 J´er´emy Zehr and Orin Percus 16 J´er´emy Zehr & Orin Percus References 1. Alxatib, S., Pelletier, J. F.: The psychology of vagueness: Borderline cases and contradictions, Mind and Language (2010) 2. Beaver, D. I., Geurt, B.: article “Presupposition”, Stanford Encyclopedia of Philos- ophy, URL http://plato.stanford.edu/entries/presupposition/ (2011) 3. Cobreros, P., Egre, P., Ripley, D., van Rooij, R., Tolerant, classical, strict, Journal of Philosophical Logic. (2011) 4. Charlow, S., ‘Strong’ predicative presuppositional objects, in Natahan Klinedinst and Daniel Rothschild (eds.), Proceedings of ESSLLI 2009 Workshop: New Direc- tions in the Theory of Presupposition. (2009) 5. Chemla, E., Similarity: Towards a Unified Account of Scalar Implicatures, Free Choice Permission and Presupposition Projection. Ms., ENS & MIT. URL http: //www.emmanuel.chemla.free.fr/Material/Chemla-SIandPres.pdf. (2008) 6. Fine, K., Vagueness, truth and logic, Synthese 30, 265-300. D. Reidel Publishing Company, Dordrecht-Itolland (1975) 7. Fox, D., Two short notes on Schlenkers theory of presupposition projection, Theo- retical Linguistics 34(3), pp. 237-252. (2008) 8. van Fraassen, B. C., Singular Terms, Truth-Value Gaps, and Free Logic, The Journal of Philosophy 63 (17), pp. 481-495. (1966) 9. Frege, G., Uber Sinn und Bedeutung, Zeitschrift fur Philosophie und philosophische Kritik, C: 25-50. English Translation: On Sense and Meaning, in McGuinness, B. (ed), Frege: collected works, Oxford: Basil Blackwell, 157-177. (1892) 10. George, B. R., Predicting Presupposition Projection: some alternatives in the strong Kleene tradition. M.A. thesis, UCLA. (2008) 11. Heim, I., On the Projection Problem for Presuppositions, in Michael Barlow, Daniel Flickinger & Michael Westcoat (eds.) Second Annual West Coast Conference on Formal Linguistics, 114-126. Stanford University. (1983) 12. Kennedy, C., Vagueness and grammar: The semantics of relative and absolute gradable predicates. in Linguistics and Philosophy, 30: 1-45. (2007) 13. Russell, B., On Denoting, Mind, 14: 479-493. (1905) 14. Schlenker, P., Local Contexts, Semantics & Pragmatics Volume 2, Article 3: 1-78, 2009. (2008)