Search

This study was conducted to determine if fifth-grade students can significantly improve their use of logical analysis through a suitable instructional unit taught under ordinary classroom conditions. Concrete teaching materials were developed to familiarize students with the distinction between the valid inference patters--Modus Ponendo Ponens and Modus Tollendo Tollens (MP, MT), and the fallacious ones--Affirming the Consequent and Denying the Antecedent (AC, DA). No formal rules were taught. The experimental unit was implemented 4 to 5 times a week for 23-25 sessions, by 4 fifth-grade teachers in their ordinary classes. The teachers participated in a 12-hour pretraining workshop. A pretest/posttest, treatment/no treatment design was applied to assess resulting improvement in students' conditional reasoning ability. The sample consisted of 210 fifth-grade students in a suburban area, 104 in 4 experimental classes and 106 in 4 control classes. Experimental and control group pretest performance levels did not differ, but there was a significant difference in the posttest means. There was no significant change in the control group's pretest and posttest performance levels on any logical form, or for the experimental group's on MP and MT. However, on AC and DA the two groups' gain scores were significantly different. (MLH)

This study was designed to test the effectiveness of providing students with instruction on how to use the information contained in examples and non-examples of disjunctive concepts, and of five different instructional sequences of examples and non-examples. Students (192) enrolled in a mathematics course for prospective elementary teachers served as subjects. Subjects (90) in the experimental group received programed instruction on the use of examples and nonexamples in the learning of disjunctive concepts; controls received no comparable instruction. Experimental and control groups both consisted of five subgroups, one for each of five exemplification strategies used in teaching twelve disjunctive mathematical concepts. All teaching was by programed instruction. A 72-item test of concept attainment was constructed and used as the criterion measure. For each concept taught this instrument contained two items at each of three cognitive levels: (1) terminology, translation, recognition; (2) classification and selection of examples and non-examples; (3) analysis; synthesis, evaluation. Results indicated no difference between experimental and control groups, suggesting that subjects already knew how to use exemplary information. Overall there was no difference attributable to exemplification sequence; on level (2) items, however, a difference favoring the all examples sequence was found. (SD)

The effect of playing a logic game, Master Mind, on student learning in physics was examined in this study. An experimental group of 16 Electronics Engineering Technology students played the game during class one hour per week for seven weeks. A control group of nineteen students took the course without playing the logic game. Results showed that use of the logic game developed reasoning ability to the extent that the experimental group performed better on physics exams than the control group. Because of the abstract nature of physics, understanding requires formal operational thought, however many college students are still in the concrete operational stage. Transition into the formal stage is possible if the student encounters problems requiring formal level thought while dealing with concrete objects. The logic game used in this study provided the student with non-verbal, non-mathematical, concrete experiences with hypothesis testing and control of variables. Physics laboratory exercises are analogous to the logic game in that they also require formal level thought. Further study is recommended to verify the value of the logic game as an aid to cognitive development. (TP)

I defend the claim that knowledge of logical truths does not depend on experience, that it is a priori knowledge. In chapter I, I introduce and clarify the idea of a priori knowledge, and in chapter II, I respond to a widespread objection to it derived from Quine's critique of analyticity. In chapter III, I distinguish between two approaches to developing an account of a priori knowledge, one that ties apriority to the cognitive abilities of knowers and another that ties it to features of truths known. I motivate the second approach over the first. In chapter IV, I sketch an outline of how the second approach could lead to an account of the apriority of logical knowledge. In the final three chapters, I develop an account which follows the outline. In chapter V, I introduce the Fregean idea of logic as a study of the laws of truth which I spell out with the help of the semantic conception of truth developed by Tarski. In chapter VI, I defend an idea found in Wittgenstein's Tractatus that the signs for logical operations cannot be construed as having objects corresponding to them. The defence proceeds via a defence of Frege's Context Principle. A consequence of the Tractarian idea is that logical truths are not expressions of thought, that they are truths without a truth-condition. In the last chapter, I spell out the epistemic implications of this idea, that an understanding of truth is accompanied by knowledge of every logical truth and that any acquisition of knowledge by experience therefore presupposes logical knowledge, meaning that logical knowledge itself cannot depend on experience or any other means of learning.

In this thesis I consider and argue against various versions of the view that logical truth and necessity are identical. I criticise purely modalist accounts of logical consequence, according to which consequence is just necessary truth-preservation, and I also criticise views on which necessity is identified with some prior understanding of logical truth (as semantic validity, or substitutional validity, or as syntactic derivability). In the process I develop various systems of modal semantics in detail and investigate the logic of logical truth under various alternative hypotheses.

This work is closely tied to the metaphysical and formal work of David Lewis on modality. First, to Lewis' reduction of modality in terms of his modal realism and mature counterpart machinery. Second, to Lewis' 1968 formal account (and its subsequent developments) employing a notion of counterparthood, an account that is detachable from Lewis' full-blooded metaphysics. This work is primarily an examination of both of these accounts, as well as five other formal accounts that, inspired by Lewis' work, employ a notion of counterparthood. The thesis divides into four chapters. The first chapter presents Lewis' reduction of modality in terms of his modal realism and mature counterpart machinery. It includes a presentation of an account that I take to be a straightforward regimentation of Lewis' sketch of joint possibilities in 1986. The second chapter considers certain issues for this account. These concern existence, the combination of existence and iterated modality, and ``contingent identity". The chapter ends with a discussion of alternatives to the machinery employed by the account. The third chapter begins with a presentation and discussion of Lewis' 1968 formal account. That account employs formal machinery to deliver counterpart characterisations of natural language modal claims. First, Lewis presents a formal first-order theory, counterpart theory. Second, Lewis provides a method for translating natural language modal claims into sentences of the language of counterpart theory. This process has two steps. First, Lewis assumes a regimentation of natural language modal claims into sentences of ``the language of quantified modal logic". Second, Lewis provides a translation scheme that maps sentences of this language of quantified modal logic to sentences of the language of counterpart theory. This combination of (i) a theory and (ii) a translation scheme (that maps sentences of the language of quantified modal logic to sentences of the language of counterpart theory) generates a semantics for the language of quantified modal logic. Given this, I turn to a more foundational matter in the final part of the third chapter: comparing the usual direct model-theoretic approach and this indirect approach (presenting a theory and translation scheme) to presenting a semantics for a formal language. The fourth chapter raises issues for five formal accounts in the literature that in some way appeal to a notion of counterparthood: Hazen's 1977 stipulational semantics; Russell's 2013 counterpart semantics; Bacon's 2014 counterpart semantics; Graff Fara's 2008 relative-sameness semantics; and Meyer's 2013 counterpart account.

This dissertation is about logical consequence. The main points I will defend can be summarised as follows. First, I claim that logical consequence can be understood as truth-preservation under all interpretations of the language. There is no need to use modal notions to define consequence. In chapter one, I argue that domain-variation across different interpretations can be understood in purely interpretational terms, if we take quantifiers to be context-sensitive expressions. Secondly, I am sympathetic with a substitutional account of logical consequence, where consequence is preservation of truth under all substitutions of the non-logical vocabulary. In chapter two, I extend the substitutional account to modal logic, where the box is read as "It is substitutionally valid that". Modal logic is seen as a way for the system to reflect upon what is valid. Different readings of the box can be provided by restricting the substitutions relevant for the truth of a modal formula. In the third chapter, I argue that a theory of logical consequence ought to be self-applicable: it should apply to its own language. This is required by our use of logical consequence in philosophical logic, to express the debate between the monist and the pluralist about logical consequence, and to link our theory of what is valid with a theory of valid reasoning and justification. Finally, in the fourth chapter I suggest that a theory of interpretations of a given language will never really capture all the interpretations of that language. I extend the worry even to theories that admit absolute generality and take higher-order talk to be non-reducible to first-order talk. I argue that, regardless of the order of the theory one is speaking from, there is always an order higher that one can take as one's starting point, and at any further order up the hierarchy, more interpretations of any language become available.

This dissertation reconstructs Marx's critique of political economy from the perspective of reproduction. In doing so, the dissertation develops three main, interrelated arguments. The first is that the reproduction of capital's social relations requires various complex forms of subjection. Here, I demonstrate that both impersonal relations -specific to capital's fetish character -and non-capitalist interpersonal relations co-exist in a non-linear development, with the rise of finance capital engendering a counterintuitive return to interpersonal forms of domination. The second argument is that capitalist reproduction is formally determined by monetary circulation. When money circulates as credit money, money acquires a distinct temporality, placing future constraint on subjects. By understanding capitalist reproduction monetarily, this dissertation displaces the central contradiction of capitalism from production and wage-labour relationsto the tension between capitalist and non-capitalist forms. Consequently, production-centric accounts are shown to stem from a reductive reading of capital's logic. To address the lack of existing analysis, this dissertation develops a concept of non-capitalist elements as 'immanent externalities.' Such 'immanent externalities,' I argue, are formally necessary for reproduction to occur. Finally, the third argument is that attention to the contradiction between capitalist and non-capitalist forms and processes -internal to the reproduction process -reveals an underexamined contradiction underpinning Marx's theories of exploitation and alienation: there are two conflictual concepts of life operating in capital's reproduction, one capitalist and the other non-capitalist. The tension between capital's life process on the one hand and human life and nature on the other begets a contradiction between the possibilities for their respective reproductions. Human life and nature engender natural limits to capital's abstract forms; capitalism curtails the reproduction of natural life. This contradiction thus leads the dissertation to consider how concrete life retains an independence from capital. Accordingly, the dissertationasks how concrete life can be reproduced in independence from capital's abstractions. By elaborating these three arguments, this dissertation develops a methodological framework to grasp the logical coproduction of three significant arenas of exploitation and domination today: social reproduction, ecological degradation and the expansion of finance capital.

Logic and theology were once spoken of together in a divine speech with which we spoke of God, even as God spoke to us, in one and the same sacred speech. Logic had been conceived as a simulation of speech in argument from the divine Logos. Yet logic has since been repeatedly separated from theology by Aristotle, Ockham, and Kant, just as often as it has been re-united by Plotinus, Cusa, and Hegel. Each separation has resulted in the successive construction of logic into more articulate forms of argument and inference. Origen of Alexandria (fl. AD 184-253/4) has contributed the first Christian theological interpretation of logic. He has, beginning in his systematic theology On First Principles, interpreted logic as a simulation of the Logos, communicated by Christ, in and through the divine hypostases of God as Trinity. And he has, in his scriptural commentaries, shown how, beginning in the 'spiritual sense', logic is virtually 'interwoven' in all the philosophical sciences, and supremely through the mystical or 'epoptic' science of theology. This 'theology of logic' announces a new way to study the subject of logic for theology. It should be doubly distinguished, on the one hand, from theoretical or philosophical logic, which asks what are the rules of logic, and on the other hand, from practical or applied logic, which asks how these rules of logic can be used to demonstrate the conclusions of any science. It thus starts with no standing presumption as to the absolute necessity of logic, but, rather and more radically, asks the prior question of the contingent grounds for our very belief in the truth of logic. It raises the most originary questions of the beginning and end of logic before any separation from theology. This discovery has, however, since been submerged and silenced, first due to the Origenist controversies, but finally due to the progressive formalization of logic in medieval and modern logic, culminating in the 'pure analytic' of mathematical logic. Once it has reduced the living spirit of speech to the dead letters of writing, and suspended this spirit in an artificial syntax, the logical can lapse into the formalization of a secular logic. Logic then tends to forget and frustrate its own formality as it signifies without speaking of its first formalization. It has thus tended to render logic a-theological, theology a-logical, and both altogether inarticulate. Yet so long as logic remains separate from God, theology can never demonstrate its conclusions, and logic may never come to know its highest truths. Origen can, as this dissertation will show, be read by a theological interpretation of logic, or a theology of logic, which asks theological questions of the fundamental assumptions of any possible form of logic. He had, in contrast to later secular, formal, and mathematical logics, shown how logic can be simulated as it is spoken in and from the higher ground of the divine Logos, and communicated by Christ in God as Trinity. We may, with Origen, begin to weave each exercise of logic through all the sciences, in this speech that may be spoken, as it ever is spoken, in one and the same sacred speech.

This thesis studies the expressive power of restricted fragments of first order logic on words with the order predicate. In particular, we consider particular instances of the following two questions. Given a regular language L, and a fragment of first order logic, can L be described by formulae in this fragment? Given two regular languages L1 and L2, and a fragment of first order logic, can we find a language L which can be described by formulae in this fragment such that L1 is a subset of L and the intersection of L2 and L is empty. The former is known as the membership problem, and the latter the separation problem. These problems are well studied in the theory of regular languages, and their solution has often relied on tools from algebra, such as finite monoids and pointlikes. We consider formulae using only two variables, a fragment known as FO2[<]. Inside this fragment, we make further restrictions regarding the alternation depth of the formula, i.e. how many times we are allowed to switch between existential and universal quantifiers along a parse tree of a formula. For languages of finite words, membership for these fragments has already been solved. We generalise these results in multiple directions. First, we solve the membership problem for the aforementioned fragments for inf-regular languages, i.e. languages consisting of both infinitely and finitely long words. This in particular solves the membership problem for omega-regular languages, i.e. those containing only infinitely long words. Our main tool is to impose algebraic conditions on the syntactic monoid: a monoid which can be computed from any major presentation of regular languages. For the lower levels, we also need to consider topological properties of the languages. The above shows that membership for inf- and omega-regular languages is decidable. However, given a language presented by an automata, calculating the syntactic monoid is generally not efficient. Our second main contribution is therefore an efficient way to decide membership for languages presented by deterministic finite automata (for regular languages) and Carton--Michel automata (for omega-regular languages). We give forbidden patterns for these fragments; that is, we specify structures which cannot be present in an automata for it to be expressible by formulae of a particular alternation depth. Finding these patterns can be done in non-deterministic logarithmic space. Together with a reduction from graph reachability, this shows that the membership problem for these fragments is NL-complete when the input is given as a deterministic finite automaton or Carton--Michel automaton. Our final main contribution is a solution to the separation and covering problem for languages consisting of finite words. We introduce conelikes as a generalisation of pointlikes for ordered monoids, and use these to solve the covering problem (which generalises separation) for the aforementioned fragments.

This thesis presents a model-theoretical analysis of some theories of linear orders in monadic and weak monadic second order logic. In particular, the pseudofinite monadic second order theory of linear order and the weak monadic second order theory of a dense linear order. The analysis of the former plays a key role in the analysis of the latter. We adopt a one-sorted first-order setup for dealing with monadic and weak monadic second order logic, which is described in full detail. In both instances the model-theoretical analysis involves presenting an axiomatisation which gives insight into non-standard models, and obtaining a model-completeness result after suitably enriching the signature. For the pseudofinite monadic second order theory of linear order, we also classify the completions using residue functions and establish a connection to the free profinite monoid on one generator using extended Stone duality. Throughout, an emphasis is placed on non-standard models of monadic and weak monadic second order theories. Towards our analysis of the weak monadic second order theory of a dense linear order, we present a definable composition theorem, inspired by Shelah's composition theorem, which is more easily applied in the case of non-standard models.

This work considers data about the intentional nature of human cognition, and traces their consequences for debates in the philosophy and epistemology of logic, and metaphysics. The first part of this work, comprising its first three chapters, investigates the prospect of revising logic in light of de re intentionality, that is, more precisely, in light of the fact that via their cognitive abilities agents can relate to objects that do not exist. We will consider two candidate systems for logical revision, expressions of two forms of logical revisionism, and eventually motivate, from anti-exceptionalist grounds, our preference for one of them. We will start in Ch. 1 by illustrating the anti-exceptionalist methodological framework assumed in this work. Subsequently, in Ch. 2, we will discuss four classically valid principles inadequate to the data of de re intentionality, reject possible attempts, by proponents of so-called realist abstractionist theories of fiction, to deny those data, and present the system P of positive free logic. We will then go on, in Ch. 3, to illustrate the noneist programme of logical revision and a system, N^R, implementing its principles. We will thus argue from anti-exceptionalist grounds that rational theory choice is exercised by choosing N^R. The rest of the chapter is dedicated to defend a realist account about the ontological dependency of the non-existent on the existent. Ch. 4 and Ch. 5 are dedicated to refute attempts, by Timothy Williamson, to reduce disagreements about non-existent objects to cases of merely verbal disagreements. In Ch. 4, we take issue with arguments to the extent that logical disputes about `exists' are genuine only if the parties use it in deductively ways. In Ch. 5 we address his scepticism towards the dispute, about merely possible objects, between actualism and possibilism, and find it unwarranted.

This study is conceived to carry two interrelated aims. Firstly, through the lens of one of the most important-and perhaps most contested of all-theological problems, ruʾyat Allāh, I hope to bring to light the systematic character of the classical Ashʿarī school. 'Systematic' is here meant to convey the idea that the theologians under consideration built an architectonic of knowledge with comprehensive and integrated categories of understanding the world, taking in the ontology of the cosmos, its metaphysics, its logical thought structure, its semantic categories and additionally for the purposes of this study, the science of optics. Importantly, such an understanding saw these disciplines not as mutually exclusive or siloed categories but as continuous fields of inquiry that contributed towards building a complete and wholistic worldview. In constructing such a worldview, Ashʿarī thinkers did not see speculation about the world as something removed from understanding God's word as revealed in the Qur'an. Here, the importance of the science referred to as uṣūl al-fiqh as a method to interpret and understand Scripture, as well as the manner in which this science complements broader theological method, will be explored. In relation to the science of optics, the study will explore the extent to which classical-period Ashʿarīs such as Abū al-Maʿālī al-Juwaynī (d. 478/1085) and Abū al-Qāsim al-Anṣārī (d. 512/1118) were drawing from Avicenna's (d. 428/1037) theory of optics in their own objections against the Muʿtazilī extramission theory of vision. Part of this study will, therefore, also include previously unstudied aspects of the Muʿtazilī intromission theory of vision. The second aim has a methodological focus, which is to say that through the lens of ruʾyat Allāh the study will explore the logico-epistemological development of the classical Ashʿarī school, and how, through this totemic theological question (and others like it) it came to reject its earlier logical methods, thus paving the way for its subsequent move towards a more robust epistemological base in the form of Avicennan logic. The interplay between the two aims will be to show how the logico-epistemological developments ultimately came to affect the manner-and the grounds upon which-the case for ruʾyat Allāh was made by the classical Ashʿarī school. Ruʾyat Allāh is thus the anchor through which the aims of the study hope to be realized.

Background - Poetry therapy is a promising but heterogeneous and under-evidenced form of creative art therapy. Theories of change have been proffered but are modelspecific and poorly evidenced in the empirical literature. Aims - To systematically retrieve, review, and synthesise empirical literature exploring mechanisms of pan-theoretical poetry therapy, providing a united understanding of how poetry therapy operates to guide future research and practice. Methods - A systematic search of six databases yielded 161 papers. Fourteen met the inclusion criteria, spanning individual and group approaches. Mechanisms and effects were extracted and synthesised into a governing framework and logic model. Stakeholder consultation was used to validate results. Results - 25 primary mechanisms and 54 associated effects were identified. These were synthesised into logic model characterised by five core processes: Engaging, Feeling, Exploring, Connecting, and Transferring ("EFECT"). These processes were associated with multifarious benefits, impacting cognitive, emotional and behavioural domains. Conclusions - The mechanisms and effects of poetry therapy can be understood via the EFECT model. This should now be tested empirically. The model can then be used to guide a united, rigorous research programme, helping to bring poetry therapy into evidence-based policy and practice.

The initial motivating question for this thesis is what the standard of rigour in modern mathematics amounts to: what makes a proof rigorous, or fail to be rigorous? How is this judged? A new account of rigour is put forward, aiming to go some way to answering these questions. Some benefits of the norm of rigour on this account are discussed. The account is contrasted with other remarks that have been made about mathematical proof and its workings, and is tested and illustrated by considering a case study discussed in the literature. On the view put forward here one can obtain a manner of informal, rigorous mathematics founded on any of a variety of proof systems. The latter part of the thesis is concerned with the question of how we should decide which of these competing proof systems we should base our mathematics on: i.e., the question of which proof system we should take as a foundation for our mathematics. A novel answer to this question is proposed, in which the key property we should require of a proof system is that for as many different kinds of structures as possible, when the proof system allows a generalization about that kind of structure to be proved, the generalization actually holds of all real examples of that kind of structure which exist. This is the requirement of soundness of the proof system (for each kind of structure). It is argued that the best way to establish the soundness of a proof system may be by giving an interpretation of its axioms on which they are established as true. As preparation for this discussion, the thesis first investigates the logical and conceptual basis of various arithmetic concepts, with the results obtained used in the final discussion of soundness.

My thesis presents a novel argument for deflationism about truth using new research in formal truth theory. In Chapter 2 I show the inadequacy of CT− as a truth theory for nonstandard models of syntax. I develop an extended T-Schema to overcome this and prove it entails non-conservativity over arithmetic. This shows a minimally adequate purely alethic theory has powerful deductive consequences. I argue, against the conservativity argument, this is a boon for deflationism. To do this, Chapter 3 provides a novel account of which theories of truth are deflationary, namely purely logical-linguistic-semantic theories of the word ‘true’. Chapter 4 then considers which formal theories of truth are deflationary and argues deflationary theories need not be proof-theoretically conservative, semantically conservative or formally logical. Instead, taking my conception of deflationism from Chapter 4, I argue that all current axiomatic theories of truth are deflationary. In Chapter 5 I develop and explore two new axiomatic theories of truth and argue for one’s adequacy as a formal theory of truth. Chapter 6 provides a new philosophical position, deflationary alethic pluralism, which I argue shows even a simple deflationary theory of truth can capture the philosophical and linguistic benefits of a powerful pluralist theory of truth. I conclude in Chapter 7 that, taken together, these results imply the adequacy of, and provide support for, deflationism about truth. This has important ramifications for those who seek truths. It tells us that theoreticians need not be concerned with metaphysical or epistemic features of truth, particularly those which could conflict with their practice. Further, philosophers using the notion of truth to phrase their theory do not incur additional commitments by doing so. With a deflationary conception of truth, troubling aspects of truth are removed from focus, leaving theoreticians free to pursue the truths of their particular domain.

Axiomatization and Incompleteness in Arithmetic and Set Theory Wesley Duncan Wrigley I argue that are (at least) two distinct kinds of mathematical incompleteness. Part A of the thesis discusses Gödelian incompleteness, while Part B is concerned with set-theoretic incompleteness. Both parts are concerned with the philosophical justification of reflection principles and other axiomatic devices which can be used to reduce incompleteness, and in particular with the justification of such devices from the philosophical standpoint of Kurt Gödel. In Part A I consider Gödel's disjunctive argument. In chapter 1, I argue that the non-mechanical mind considered by Gödel is best modelled by a theory constructed using the transfinite iterated application of a soundness reflection principle to PA. I argue that Feferman's completeness theorem shows this account of the mind to be incompatible with some elementary assumptions in the epistemology of arithmetic. In chapter 2, these considerations are developed into a positive argument for the existence of absolutely undecidable arithmetical propositions. The consequences for the indefinite extensibility of the concept natural number are then discussed. I argue that properly understood, Feferman's theorem refutes Dummett's position in the debate. I begin part Part B in chapter 3, by reconstructing a version of Gödel's platonism, called conceptual platonism. I then examine how such a position relates to various means of reducing set-theoretic incompleteness. In chapter 4 I argue that there is some prospect for this position of effecting a limited reduction in incompleteness by means of reflection principles justified by mathematical intuition. However, such priniciples are incompatible with Gödel's commitment to platonism about properties of properties of sets. In chapter 5 I argue that conceptual platonism does not lend support to the view that a substantial reduction in incompleteness can be effected by large cardinal axioms justified using extrinsic methods analogous to the principles of theory choice in natural science. This undercuts the traditional justification for many large cardinal axioms, so I end with a sketch of how conceptual platonism could be modified to rehabilitate the large cardinals program.

The question of whether there is a logic that characterises polynomial-time is arguably the most important open question in finite model theory. The study of extensions of fixed-point logic are of central importance to this question. It was shown by Anderson and Dawar that fixed-point logic with counting (FPC) has the same expressive power as uniform families of symmetric circuits over a basis with threshold functions. In this thesis we prove a far-reaching generalisation of their result and establish an analogous circuit characterisation for each from a broad range of extensions of fixed-point logic. In order to do so we fist develop a very general framework for defining and studying extensions of fixed-point logics, which we call generalised operators. These operators generalise Lindström quantifiers as well as the counting and rank operators used to define FPC and fixed-point logic with rank (FPR). We also show that in order to define a symmetric circuit model that goes beyond FPC we need to consider circuits with gates that are allowed to compute non-symmetric functions. In order to do so we develop a far more general framework for studying circuits. We also show that key notions, such as the notion of a symmetric circuit, can be analogously defined in this more general framework. The characterisation of FPC in terms of symmetric circuits, and the treatment of circuits generally, relies heavily on the assumption that the gates in the circuit compute symmetric functions. We develop a broad range of new techniques and approaches in order to study these more general symmetric circuit models. As a corollary of our main result we establish a circuit characterisation of FPR. We also show that the question of whether there is a logic that characterises polynomial-time can be understood as a question about the symmetry property of circuits. We lastly propose a number of new approaches that might exploit this new-found connection between circuit complexity and descriptive complexity.

This thesis is concerned with intersections between poetry and prayer, in printed texts attributed to Edmund Spenser and Lancelot Andrewes. It takes as a starting point the pervasiveness of Ramism at Pembroke College Cambridge during these two writers’ overlapping years spent there as undergraduates, proposing that Ramist ideologies of the short and efficient, the organised, the hierarchical, the one-size-fits-all diagrammatic text, offer new ways of understanding the pedagogical aspirations—and the formal mechanisms—of Andrewes’s literary homiletics and Spenser’s religious allegories. I will be preoccupied above all by poetic economies of page space and prayer time: in representations of large in small, or the extraordinary in the ordinary, and the anxieties and humilities involved in such inadequate accommodated ‘insteads’. Chapter one examines printed English versions of Andrewes’s Preces Privatae, reading its mise-en-page as reminiscent of Ramist logic books, and beginning to establish an early modern context of instrumental ‘diagrammatic reading’ by taking a particular interest in the work of curly braces as a ‘didactic technology’ which both performs and instructs prayer on the printed page. Chapter two considers Spenser’s Fowre Hymnes as devotional poems. Read diagrammatically, by their complicated poetic hierarchies and chronologies these self-sacred parodies enact a thinking-through of the theological cruxes of the Incarnation and its meditative contemplation in the broken gift-cycle of prayerful thanksgiving. Chapter three uses grammatical anaphors and abridgements in Andrewes’s Passion sermons and the Pattern of Catechistical Doctrine to derive a theory of accommodated reading based on metaphorical sizes and imaginary dimensions. My final chapter reads the ballad-stanza ‘Arguments’ with which Spenser prolepsises and summarises every Canto in The Faerie Queene as recognisably generic paratexts with analogies in the Geneva Bible, Thomas Speght’s 1598 collected Chaucer, printed plays, and the Sternhold-Hopkins psalter. Short, simple, and economical, the four-line Arguments seem at first a very different poetical space from the Spenserian stanza—but on closer reading, they demand an investment in the dimensions of printed language and the spaces and syntax of its storytelling which fits persuasively with the wider poetics of The Faerie Queene and with its narrative structures.

Constraint problems are a powerful framework in which many common combinatorial problems can be expressed. Examples include graph colouring problems, Boolean satisfaction, graph cut problems, systems of equations, and many more. One typically distinguishes between constraint satisfaction problems (CSPs), which model strictly decision problems, and so-called valued constraint satisfaction problems (VCSPs), which also include optimisation problems. A key open problem in this field is the long-standing dichotomy conjecture by Feder and Vardi. It claims that CSPs only fall into two categories: Those that are NP-complete, and those that are solvable in polynomial time. This stands in contrast to Ladner's theorem, which, assuming P$\neq$NP, guarantees the existence of problems that are neither NP-complete, nor in P, making CSPs an exceptional class of problems. While the Feder-Vardi conjecture is proven to be true in a number of special cases, it is still open in the general setting. (Recent claims affirming the conjecture are not considered here, as they have not been peer-reviewed yet.) In this thesis, we approach the complexity of constraint problems from a descriptive complexity perspective. Namely, instead of studying the computational resources necessary to solve certain constraint problems, we consider the expressive power necessary to define these problems in a logic. We obtain several results in this direction. For instance, we show that Schaefer's dichotomy result for the case of CSPs over the Boolean domain can be framed as a definability result: Either a CSP is definable in fixed-point logic with rank (FPR), or it is NP-hard. Furthermore, we show that a dichotomy exists also in the general case. For VCSPs over arbitrary domains, we show that a VCSP is either definable in fixed-point logic with counting (FPC), or it is not definable in infinitary logic with counting. We show that these definability dichotomies also have algorithmic implications. In particular, using our results on the definability of VCSPs, we prove a dichotomy on the number of levels in the Lasserre hierarchy necessary to obtain an exact solution: For a finite-valued VCSP, either it is solved by the first level of the hierarchy, or one needs $\Omega(n)$ levels. Finally, we explore how other methods from finite model theory can be useful in the context of constraint problems. We consider pebble games for finite variable logics in this context, and expose new connections between CSPs, pebble games, and homomorphism preservation results.

There now exists an abundant collection of conjectures and results, of various complexities, regarding the diophantine properties of Shimura varieties. Two central such statements are the Andre-Oort and Zilber-Pink Conjectures, the first of which is known in many cases, while the second is known in very few cases indeed. The motivating result for much of this document is the modular case of the Andre-Oort Conjecture, which is a theorem of Pila. It is most commonly viewed as a statement about the simplest kind of Shimura varieties, namely modular curves. Here, we tend instead to view it as a statement about the properties of the classical modular j-function. It states, given a complex algebraic variety V, that V contains only finitely many maximal special subvarieties, where a special variety is one which arises from the arithmetic behaviour of the j-function in a certain natural way. The central question of this thesis is the following: what happens if in such statements we replace the j-function with some other kind of modular function; one which is less well-behaved in one way or another? Such modular functions are naturally called nonclassical modular functions. This question, as we shall see, can be studied using techniques of o-minimality and point-counting, but some interesting new features arise and must be dealt with. After laying out some of the classical theory, we go on to describe two particular types of nonclassical modular function: almost holomorphic modular functions and quasimodular functions (which arise naturally from the derivatives of the j-function). We go on to prove some results about the diophantine properties of these functions, including several natural Andre-Oort-type theorems, then conclude by discussing some bigger-picture questions (such as the potential for nonclassical variants of, say, Zilber-Pink) and some directions for future research in this area.

Querying a database to retrieve an answer, telling a robot to perform an action, or teaching a computer to play a game are tasks requiring communication with machines in a language interpretable by them. Semantic parsing is the task of converting human language to a machine interpretable language. While human languages are sequential in nature with latent structures, machine interpretable languages are formal with explicit structures. The computational linguistics community have created several treebanks to understand the formal syntactic structures of human languages. In this thesis, we use these to obtain formal meaning representations of languages, and learn computational models to convert these meaning representations to the target machine representation. Our goal is to evaluate if existing treebank syntactic representations are useful for semantic parsing. Existing semantic parsing methods mainly learn domain-specific grammars which can parse human languages to machine representation directly. We deviate from this trend and make use of general-purpose syntactic grammar to help in semantic parsing. We use two syntactic representations: Combinatory Categorial Grammar (CCG) and dependency syntax. CCG has a well established theory on deriving meaning representations from its syntactic derivations. But there are no CCG treebanks for many languages since these are difficult to annotate. In contrast, dependencies are easy to annotate and have many treebanks. However, dependencies do not have a well established theory for deriving meaning representations. In this thesis, we propose novel theories for deriving meaning representations from dependencies. Our evaluation task is question answering on a knowledge base. Given a question, our goal is to answer it on the knowledge base by converting the question to an executable query. We use Freebase, the knowledge source behind Google’s search engine, as our knowledge base. Freebase contains millions of real world facts represented in a graphical format. Inspired from the Freebase structure, we formulate semantic parsing as a graph matching problem, i.e., given a natural language sentence, we convert it into a graph structure from the meaning representation obtained from syntax, and find the subgraph of Freebase that best matches the natural language graph. Our experiments on Free917, WebQuestions and GraphQuestions semantic parsing datasets conclude that general-purpose syntax is more useful for semantic parsing than induced task-specific syntax and syntax-agnostic representations.

We introduce subatomic logic, a new methodology where by looking inside of atoms we are able to represent a wide variety of proof systems in such a way that every rule is an instance of a single, regular, linear rule scheme. We show the generality of the subatomic approach by presenting how it can be applied to several different systems with very different expressivity. In this thesis we use subatomic logic to study two normalisation procedures: cut-elimination and decomposition. In particular, we study cut-elimination by characterising a whole class of substructural logics and giving a generalised cut-elimination procedure for them, and we study decomposition by providing generalised rewriting rules for derivations that we can then apply to decompose derivations and to eliminate cycles.

Bertrand Russell's works on logic, despite his reputation as a founder of mathematical logic, appear unnecessarily metaphysical and even naïve to contemporary logicians and philosophers. He offered several accounts of logic whilst pursuing the goal of logicism, the view of mathematics as reducible to logic. In their attempts to explain why those accounts look naïve nowadays, many commentators have sought one or another simple philosophical doctrine which can characterise his conception of logic. Instead of thus assuming a coherent theme underlying his works on logic, I propose to understand them as a shift from a conception of logic towards another. By looking into books, papers and manuscripts which he wrote during the period from 1898 to 1918, I argue that he inherited an antique, metaphysical conception of logic from his idealist predecessors and, through his attempts to replace some idealistic features of the conception with his realist alternatives, he became more sympathetic to—though never fully convinced of—a linguistic conception of logic, which was proposed by some of his contemporary logicians and has been widely accepted since then.

Frege wanted to show that arithmetical truths are logical by proving them from purely logical basic laws. But how do we know that these basic laws are logical? Frege uses generality and undeniability to make a prima facie case for logicality—if a truth is general and undeniable, then it's likely logical. I argue that Frege could, did, and had to make a deeper case for why we're right in recognizing his basic laws as logical. Implicit in his work is a view of logical laws as epistemically analytic—his arguments for his basic laws serve to elicit a reflective awareness of the fact that understanding them is sufficient for recognizing them to be true. This view both fits with Frege's comments concerning the connection between logic, truth, and normativity, and serves to explain why and in what sense he took logic to be general and conceptually undeniable. In my view, semantics must play a distinctive role in any rational reconstruction of Frege's case for logicality—the aforementioned “reflective awareness” must be an explicit appreciation of how the truth of formulas expressing Frege's laws follows quickly from his stipulations governing terms which figure in those formulas. Opposing this view is the elucidatory interpretation of Thomas Ricketts, Warren Goldfarb, and Joan Weiner, which holds that Frege's arguments for his basic laws can't be taken at face value, and must serve the merely elucidatory purpose of easing us into the language. Another reading is the correctness interpretation of Richard Heck and Jason Stanley, which holds that Frege's primary purpose in his arguments is justifying the claim that Frege's axioms, qua formulas, are true. I argue against both of these interpretations, and in doing so clarify the role and limits of semantics in Frege's enterprise.

We examine how logical reasoning in the two-variable guarded fragment with counting quantifiers can be integrated with databases in the presence of certain integrity constraints, called path-functional dependencies. In more detail, we establish that the problems of satisfiability and finite satisfiability for the two-variable guarded fragment with counting quantifiers, a database, and binary path-functional dependencies are EXPTIME-complete; we also establish that the data complexity of these problems is NP-complete. We establish that query answering for the above fragment (with a database and binary path-functional dependencies) is 2-EXPTIME-complete with respect to arbitrary models, and provide a 2-EXPTIME upper bound for finite models. Finally, we establish that the data complexity of query answering is coNP-complete, both with respect to arbitrary and finite models.

In this thesis we study Ax-Schanuel type inequalities for abstract differential equations. A motivating example is the exponential differential equation. The Ax-Schanuel theorem states positivity of a predimension defined on its solutions. The notion of a predimension was introduced by Hrushovski in his work from the 1990s where he uses an amalgamation-with-predimension technique to refute Zilber's Trichotomy Conjecture. In the differential setting one can carry out a similar construction with the predimension given by Ax-Schanuel. In this way one constructs a limit structure whose theory turns out to be precisely the first-order theory of the exponential differential equation (this analysis is due to Kirby (for semiabelian varieties) and Crampin, and it is based on Zilber's work on pseudo-exponentiation). One says in this case that the inequality is adequate. Thus, by an Ax-Schanuel type inequality we mean a predimension inequality for a differential equation. Our main question is to understand for which differential equations one can find an adequate predimension inequality. We show that this can be done for linear differential equations with constant coefficients by generalising the Ax-Schanuel theorem. Further, the question turns out to be closely related to the problem of recovering the differential structure in reducts of differentially closed fields where we keep the field structure (which is quite an interesting problem in its own right). So we explore that question and establish some criteria for recovering the derivation of the field. We also show (under some assumptions) that when the derivation is definable in a reduct then the latter cannot satisfy a non-trivial adequate predimension inequality. Another example of a predimension inequality is the analogue of Ax-Schanuel for the differential equation of the modular j-function due to Pila and Tsimerman. We carry out a Hrushovski construction with that predimension and give an axiomatisation of the first-order theory of the strong Fraïssé limit. It will be the theory of the differential equation of j under the assumption of adequacy of the predimension. We also show that if a similar predimension inequality (not necessarily adequate) is known for a differential equation then the fibres of the latter have interesting model theoretic properties such as strong minimality and geometric triviality. This, in particular, gives a new proof for a theorem of Freitag and Scanlon stating that the differential equation of j defines a trivial strongly minimal set.

Mathematical logic and theoretical computer science are the mathematical studies of logic and computation, respectively, which largely correspond to each other notably by the Curry-Howard isomorphism. However, logic and computation have been captured mainly syntactically, which may be criticized as conceptually unclear and mathematically cumbersome. For this point, the field of semantics has been developed, i.e., its main aim is to explain logic and computation by mathematical and in particular syntax-independent concepts. However, logic and computation have not yet been completely captured semantically, where a main obstacle lies in the point that proofs and programs are central in these fields, and they are dynamic, intensional concepts, but mainstream mathematics has been concerned mainly with static, extensional objects such as sets and functions, lacking in dynamic, intensional structures. Motivated by this foundational problem, the present thesis is written for the aim of establishing mathematically rigorous, syntax-independent, conceptually natural semantics of some central aspects of logic and computation, particularly their dynamics and intensionality, that have not been captured very well from a conceptual or mathematical viewpoint, for which our primary goal is to obtain a deeper understanding of logic and computation. Specifically, the thesis is concerned with concepts such as proof-normalization in logic (or reduction in computation), higher-order computability, and predicates in logic (or dependent types in computation). Our approach is based on mathematical structures developed in the field of game semantics for they are mathematically rigorous, syntax-independent, conceptually natural and exible enough to model various kinds of logic and computation in a systematic manner; also, they have a good potential to capture dynamics and intensionality of logic and computation. More concretely, we generalize, for each concept mentioned above, an existing variant of games to capture the concept, where each case is confirmed by a certain soundness or sometimes completeness theorem. Since each of the generalizations is orthogonal to one another, we may combine them into a single framework that provides a unified view on these developments. As technical achievements of the thesis, many of the generalizations give the first game-semantic interpretations of the corresponding concepts, for which we have introduced a number of novel mathematical structures and proved their properties. Also, conceptually, our games give dynamic, intensional semantics that explains various concepts and phenomena in a natural, intuitive yet mathematically precise manner, e.g., normalization of reduction, Π-, Σ- and Id-types as well as universes in Martin-Lof type theory, incompatibility of Σ-types and classical reasoning, and nonconstructivity of Univalence Axiom in homotopy type theory. Last but not least, since our mathematical structures capture logic and computation more completely, well beyond conventional game semantics, one of their implications would be the semantics-first-view: Logic and computation may be understood abstractly and syntax-independently as mathematics, viz., games, rather than as syntactic entities to be analyzed by various semantics, which is our intention behind the title of the thesis. In particular, our game-semantic approach enables an analytic study of logic and computation, as opposed to more standard synthetic ones such as categorical semantics, in the sense that it reduces the two concepts to the highly primitive notions of '(dialogical) arguments' between prover and refuter mathematicians, and '(computational) processes' between a computational agent and an environment, respectively, giving a deeper understanding of the very notion of logic and computation. The former can be seen particularly as a unity of proof theory and model theory: It gives a syntax-independent formulation of proofs that is also a computational description of models (by which we mean what formal languages refer to in a loose sense), namely strategies, where provability and validity of a formula simply coincide as the existence of a winning strategy on the corresponding game. By this unity, the central questions of soundness and completeness in logic just disappear. Furthermore, consistency of the logic which our games and strategies embody is immediate. These points demonstrate certain technical advantages (in addition to the conceptual naturality mentioned above) of our game-semantic approach to logic.

This thesis comprises three main chapters-each comprising one relatively standalone paper. The unifying theme is fragmentalism about truth, which is the view that the predicate 'true' either expresses distinct concepts or expresses distinct properties. In Chapter 1, I provide a formal development of alethic pluralism. Pluralism is the view that there are distinct truth properties associated with distinct domains of subject matter, where a truth property satisfies certain truth-characterizing principles. On behalf of pluralists, I propose an account of logic and semantics that shows how they can answer central conceptual and logical challenges for their view. In Chapter 2, I motivate and develop a modal account of propositions on the basis of an iterative conception of propositions, where the modality is logico-mathematical. The modal account of propositions takes the conception to motivate an inherently potential hierarchy of propositions. I show that the account helps provide satisfying solutions to the intensional paradoxes of Russell-Myhill, Kaplan, and Prior. In Chapter 3, I propose that 'true' is polysemous. I suggest that 'true' is initially polysemous between correspondence truth and disquotational truth, and further polysemous between the meanings corresponding to the subconcepts of the concept truth generated by the indefinite extensibility of that concept. I show that the proposal provides satisfying solutions to the semantic paradoxes.

Description logics (DLs) are knowledge representation formalisms with numerous applications and well-understood model-theoretic semantics and computational properties. SRIQ is a DL that provides the logical underpinning for the semantic web language OWL 2, which is the W3C standard for knowledge representation on the web. A central component of most DL applications is an efficient and scalable reasoner, which provides services such as consistency testing and classification. Despite major advances in DL reasoning algorithms over the last decade, however, ontologies are still encountered in practice that cannot be handled by existing DL reasoners. Consequence-based calculi are a family of reasoning techniques for DLs. Such calculi have proved very effective in practice and enjoy a number of desirable theoretical properties. Up to now, however, they were proposed for either Horn DLs (which do not support disjunctive reasoning), or for DLs without cardinality constraints. In this thesis we present a novel consequence-based algorithm for TBox reasoning in SRIQ - a DL that supports both disjunctions and cardinality constraints. Combining the two features is non-trivial since the intermediate consequences that need to be derived during reasoning cannot be captured using DLs themselves. Furthermore, cardinality constraints require reasoning over equality, which we handle using the framework of ordered paramodulation - a state-of-the-art method for equational theorem proving. We thus obtain a calculus that can handle an expressive DL, while still enjoying all the favourable properties of existing consequence-based algorithms, namely optimal worst-case complexity, one-pass classification, and pay-as-you-go behaviour. To evaluate the practicability of our calculus, we implemented it in Sequoia - a new DL reasoning system. Empirical results show substantial robustness improvements over well-established algorithms and implementations, and performance competitive with closely related work.

Plato describes a way of reasoning that comprises two complementary operations, collection and division. Collection unifies many into one while division divides one into many. In other words, while collection brings together many parts into a whole, division divides a whole into many parts. While Plato goes into some detail in his observations on collection and division, several questions remain unanswered. More specifically, the means by which collection and division operate, their product, and their relation to deductive and non-deductive reasoning are uncertain. The purpose of this study is to shed light on collection and division by defending the following thesis: collection and division define logical frameworks that underlie both deductive and non-deductive reasoning. Chapter 1 will introduce collection and division by reviewing recent literature, defining key terms, and discussing illustrations of collection and division in the dialogues. Chapter 2 will explain how collection and division define logical frameworks through three operations: seeing, naming, and placing. These operations will be discussed in terms of their relations to reasoning about wholes and parts. Chapter 3 will present four models for interpreting the logical structures that are produced by collection and division. It will present the argument that collection and division define non-hierarchical structures of overlapping parts. Chapter 4 will present the argument that collection and division define whole-part relations that underlie deductive reasoning on the one hand, and the formulation of definitions in dialogues such as the Sophist and the Statesman on the other. Chapter 5 will explore the relation between collection and division and non-deductive reasoning. It will present the argument that Meno’s definition of virtue and Euthyphro’s definition of piety are formulated using collection and division. Chapter 6 will provide a summary of key points from the preceding chapters and discuss unanswered questions and avenues for future research.

In the last 30 years there has been growing interest in and a greater appreciation of the unique contributions that medieval authors have made to the history of logic. In this thesis, we compare and contrast the modal logics of Robert Kilwardby and John Buridan and explore how their two conceptions of modality relate to and differ from modern notions of modal logic. We develop formal reconstructions of both authors' logics, making use of a number of different formal techniques. In the case of Robert Kilwardby we show that using his distinction between per se and per accidens modalities, he is able to provide a consistent interpretation of the apodictic fragment of Aristotle's modal syllogism and that, by generalising this distinction to hypothetical construction, he can develop an account of connexive logic. In the case of John Buridan we show that his modal logic is a natural extension of the usual Kripke-style possible worlds semantics, and that this modal logic can be shown to be sound and complete relative to a proof-theoretic formalisation of Buridan's treatment of the expository syllogism.

Things could have been different, but could it also have been different what things there are? It is natural to think so, since I could have failed to be born, and it is natural to think that I would then not have been anything. But what about entities like propositions, properties and relations? Had I not been anything, would there have been the property of being me? In this thesis, I formally develop and assess views according to which it is both contingent what individuals there are and contingent what propositions, properties and relations there are. I end up rejecting these views, and conclude that even if it is contingent what individuals there are, it is necessary what propositions, properties and relations there are. Call the view that it is contingent what individuals there are first-order contingentism, and the view that it is contingent what propositions, properties and relations there are higher-order contingentism. I bring together the three major contributions to the literature on higher-order contingentism, which have been developed largely independently of each other, by Kit Fine, Robert Stalnaker, and Timothy Williamson. I show that a version of Stalnaker's approach to higher-order contingentism was already explored in much more technical detail by Fine, and that it stands up well to the major challenges against higher-order contingentism posed by Williamson. I further show that once a mistake in Stalnaker's development is corrected, each of his models of contingently existing propositions corresponds to the propositional fragment of one of Fine's more general models of contingently existing propositions, properties and relations, and vice versa. I also show that Stalnaker's theory of contingently existing propositions is in tension with his own theory of counterfactuals, but not with one of the main competing theories, proposed by David Lewis. Finally, I connect higher-order contingentism to expressive power arguments against first-order contingentism. I argue that there are intelligible distinctions we draw with talk about "possible things", such as the claim that there are uncountably many possible stars. Since first-order contingentists hold that there are no possible stars apart from the actual stars, they face the challenge of paraphrasing such talk. I show that even in an infinitary higher-order modal logic, the claim that there are uncountably many possible stars can only be paraphrased if higher-order contingentism is false. I therefore conclude that even if first-order contingentism is true, higher-order contingentism is false.

This work is an investigation into the notion of truth. More specifically, this thesis deals with how to account for the main features of truth, with the interaction between truth and fundamental linguistic elements such as connectives and quantifiers, and with the analysis and the solution of truth-theoretic paradoxes. In the introductory Chapter 1, I describe and justify the approach to truth I adopt here, giving some general coordinates to contextualize my work. In Part I, I examine some theories of truth that fall under the chosen approach. In Chapter 2, I discuss a famous theory of truth developed by Saul Kripke. Some difficulties of Kripke's theory led several authors, notably Hartry Field, to emphasize the importance of a well-behaved conditional connective in conjunction with a Kripkean treatment of truth. I articulate this idea in a research agenda, which I call Field's program, giving some conditions for its realizability. In Chapter 3, I analyze the main theory of truth proposed by Field to equip Kripke's theory with a well-behaved conditional, and I give a novel analysis of its shortcomings. Field's theory is remarkably successful but is technically and intuitively very complex, and it is unclear whether Field's conditional is a plausible candidate for a philosophically useful conditional. Moreover, Field's treatment of "determinate truth" and his handling of many kinds of paradoxes is not fully satisfactory. In Part II, I develop some new theories that capture the main aspects of the notion of truth and, at the same time, give a philosophically interesting meaning to connectives and quantifiers - in particular, they yield a strong and conceptually significant conditional. The theory proposed in Chapter 4 extends the inductive methods employed in Kripke's theory, showing how to adapt them to non-monotonic connectives as well. There, I also develop and defend a new, theoretically fruitful notion of gappiness. The theory proposed in Chapter 5 (and discussed further in Chapter 6), instead, employs some graph-theoretic intuitions and tools to provide a new model-theoretic construction. The resulting theory, I argue, provides a nice framework to account for the interaction between truth, connectives, and quantifiers, and it is flexible enough to be applicable to several interpretations of the logical vocabulary. Some new technical results are established with this theory as well, concerning the interplay between every Lukasiewicz semantics and some interpretations of the truth predicate, and concerning the handling of determinate truth. Finally, the theory developed in Chapter 5 provides articulate and telling solutions to truth-theoretical paradoxes.

A fundamental component of theoretical computer science is the application of logic. Logic provides the formalisms by which we can model and reason about computational questions, and novel computational features provide new directions for the development of logic. From this perspective, the unusual features of quantum computation present both challenges and opportunities for computer science. Our existing logical techniques must be extended and adapted to appropriately model quantum phenomena, stimulating many new theoretical developments. At the same time, tools developed with quantum applications in mind often prove effective in other areas of logic and computer science. In this thesis we explore logical aspects of this fruitful source of ideas, with category theory as our unifying framework. Inspired by the success of diagrammatic techniques in quantum foundations, we begin by demonstrating the effectiveness of string diagrams for practical calculations in category theory. We proceed by example, developing graphical formulations of the definitions and proofs of many topics in elementary category theory, such as adjunctions, monads, distributive laws, representable functors and limits and colimits. We contend that these tools are particularly suitable for calculations in the field of coalgebra, and continue to demonstrate the use of string diagrams in the remainder of the thesis. Our coalgebraic studies commence in chapter 3, in which we present an elementary formulation of a representation result for the unitary transformations, following work developed in a fibrational setting in [Abramsky, 2010]. That paper raises the question of what a suitable "fibred coalgebraic logic" would be. This question is the starting point for our work in chapter 5, in which we introduce a parameterized, duality based frame- work for coalgebraic logic. We show sufficient conditions under which dual adjunctions and equivalences can be lifted to fibrations of (co)algebras. We also prove that the semantics of these logics satisfy certain "institution conditions" providing harmony between syntactic and semantic transformations. We conclude by studying the impact of parameterization on another logical aspect of coalgebras, in which certain fibrations of predicates can be seen as generalized invariants. Our focus is on the lifting of coalgebra structure along a fibration from the base category to an associated total category of predicates. We show that given a suitable parameterized generalization of the usual liftings of signature functors, this induces a "fibration of fibrations" capturing the relationship between the two different axes of variation.

Ontological database management systems are a powerful tool that combine traditional database techniques with ontological reasoning methods. In this setting, a classical extensional database is enriched with an ontology, or a set of logical assertions, that describe how new, intensional knowledge can be derived from the extensional data. Conjunctive queries are therefore answered against this combined knowledge base of extensional and intensional data. Many languages that represent ontologies have been introduced in the literature. In this thesis we will focus on existential rules (also called tuple-generating dependencies or Datalog± rules), and three established languages in this area, namely guarded-based rules, sticky rules and weakly-acyclic rules. The main goal of the thesis is to enrich these languages with non-deterministic constructs (i.e. disjunctions) and investigate the complexity of the answering conjunctive queries under these extended languages. As is common in the literature, we will distinguish between combined complexity, where the database, the ontology and the query are considered as input, and data complexity, where only the database is considered as input. The latter case is relevant in practice, as usually the ontology and the query can be considered as fixed, and are usually much smaller than the database itself. After giving appropriate definitions to extend the considered languages to disjunctive existential rules, we establish a series of complexity results, completing the complexity picture for each of the above languages, and four different query languages: arbitrary conjunctive queries, bounded (hyper-)treewidth queries, acyclic queries and atomic queries. For the guarded-based languages, we show a strong 2EXPTIME lower bound for general queries that holds even for fixed ontologies, and establishes 2EXPTIME-completeness of the query answering problem in this case. For acyclic queries, the complexity can be reduced to EXPTIME, if the predicate arity is bounded, and the problem even becomes tractable for certain restricted languages, if only atomic queries are used. For ontologies represented by sticky disjunctive rules, we show that the problem becomes undecidable, even in the case of data complexity and atomic queries. Finally, for weakly-acyclic rules, we show that the complexity increases from 2EXPTIME to coN2EXPTIME in general, and from tractable to coNP in case of the data complexity, independent of which query language is used. After answering the open complexity questions, we investigate applications and relevant consequences of our results for description logics and give two generic complexity statements, respectively, for acyclic and general conjunctive query answering over description logic knowledge bases. These generic results allow for an easy determination of the complexity of this reasoning task, based on the expressivity of the considered description logic.

Philosophical enquiry on the notion of truth has traditionally involved the identification of a class of objects to which truth is ascribed. At the same time, formal investigations are often required when the notion of truth is at issue: semantic paradoxes force in fact philosophers to shape their arguments in a precise way. Objects of truth, in formal context, are always reduced to other, more manageable objects that mimic their structural properties such as numbers or sets. This form of reduction renders the distinction between linguistic or syntactic objects, to which truth is usually applied, and their mathematical counterparts opaque, at least from the point of view of the theory of truth. In informal metatheoretic discussion, in fact, they are clearly different entities. In this thesis we focus on an alternative way of constructing axiomatic theories of truth in which syntactic objects and mathematical objects belong to different universes. A brief introduction tries to situate the proposed theories in the context of different investigations on axiomatic truth. Chapter 2 is devoted to the discussion of historical and more theoretical motivations behind the proposed alternative. Chapter 3 will present the syntactic koinè spoken by our theories. Morphological categories of the object language and logical concepts concerning the object theory will be formalised in a recent axiomatisation of hereditarily finite sets. In Chapter 4 we finally introduce theories of truth with a built-in syntactic theory and examine some of their consequences. We briefly focus on disquotational truth, then consider compositional axioms for truth. Chapter 5 investigates a possible application of the setting just introduced: a realisation of the all-present interaction, in metamathematical practice, between informal metatheoretic claims and their (suitably chosen) coded counterparts. In the final chapter, after a brief characterisation of the key doctrines of the delflationary conception of truth, we evaluate the impact that the theories of truth studied in this work can have on the debate on the so-called conservativeness argument, which tries to match the alleged insubstantiality of the notion of truth, advocated by deflationists, with the deductive power of deflationary acceptable theories of truth.

There have been recent explosions of interest in two fields: Madhyamaka-Pyrrhonism parallels and Pyrrhonism itself, which seems to have been misunderstood and therefore neglected by the West for the same reasons and in the same ways that Madhyamaka traditionally has often been by the West and the East. Among these recent studies are several demonstrating that grounding in Madhyamaka, for example, reveals and illuminates the import and insights of Pyrrhonean arguments. Furthermore it has been suggested that of all European schools of philosophy Pyrrhonism is the one closest to Buddhism, and especially to Madhyamaka. Indeed Pyrrho is recorded to have studied with philosophers in Taxila, one of the first places where Madhyamaka later flourished, and the place where the founder of Madhyamaka, Nāgārjuna, may have received hitherto concealed texts which became the foundation for his school. In this dissertation I explore just how similar these two philosophical projects were. I systematically treat all the arguments in the Pyrrhonist redactor Sextus Empiricus’ Outlines of Pyrrhonism and Against Dogmatists and compare them to the most similar arguments available in the Madhyamaka treatises and related texts. On this basis, I ask whether the Pyrrhonists and the Buddhists would satisfy each other’s self-identifying criteria, or what characteristics would disqualify either or both in the other’s eyes. I also ask what questions arise from the linguistic and historical evidence for interactions between the Pyrrhonist school and the Madhyamaka school, and how sure we can be of the answers. Did Pyrrho learn Buddhism in Taxila? Was Nāgārjuna a Pyrrhonist? Finally I bring the insights of the living commentarial tradition of Madhyamaka to bear on current scholarly controversies in the field of Sextan Pyrrhonism, and apply the subtleties of interpretation of the latter which have developed in recent scholarship to Madhyamaka and its various difficulties of interpretation, to scrutinize each school under the illumination of the other. With this hopefully illuminated view, I address for example whether Sextus was consistent, whether living Pyrrhonism implies apraxia, whether Pyrrhonism is philosophy at all, and whether Madhyamaka is actually nihilism.

This thesis deals with the problem of technical product configuration: Connect individual components conforming to a component catalogue in order to meet a given objective while respecting certain constraints. Solving such configuration problems is one of the major success stories of applied AI research: In industrial environments they support the configuration of complex products and, compared to manual processes, help to reduce error rates and increase throughput. Practical applications are nowadays ubiquitous and range from configurable cars to the configuration of telephone communication switching units. In the classical definition of a configuration problem the number of components to be used is fixed while in practice, however, the number of components needed is often not easily stated beforehand. Existing knowledge representation (KR) formalisms expressive enough to deal with this dynamic aspect of configuration require that explicit bounds on all generated components are given as well as extensive knowledge about the underlying solving algorithms. To date there is still a lack of high-level KR tools being able to cope with these demands. In this work we present LoCo, a fragment of classical first order logic that has been carefully tailored for expressing technical product configuration problems. The core feature of LoCo is that the number of components used in configurations does not have to be finitely bounded explicitly, but instead is bounded implicitly through the axioms. We identify configurations with models of the logic; hence, configuration finding becomes model finding. LoCo serves as a high-level representation language which allows the modelling of general configuration problems in an intuitive and declarative way without the need of having knowledge about underlying solving algorithms; in fact, the specification gets automatically translated into low-level executable code. LoCo allows translations into different target languages. We present the language, related algorithms and complexity results as well as a prototypical implementation via answer-set programming.

Logic, it is said, is normative - logic tells us something about how we ought to think or reason. However, it's not clear why we should think logically, or which rules or which theory we are meant to follow. In the following chapters, I provide a novel view of logical normativity which aims to answer these vexing questions. I defend the view that logical normativity can be understood on the basis of a conception of logic according to which its laws are fundamentally descriptive, what I call the 'laws of truth' conception of logic. But I also defend the view that logical normativity can be understood on the basis of a conception of logic according to which its laws are fundamentally prescriptive, what I call the 'laws of thought' conception of logic. The resulting view is what I call 'logical normativity dualism', the idea that logic is normative in both of these distinct yet complementary ways.In Chapter 1, I address some of the fundamental issues of logical normativity by uncovering the deep distinction between the laws of truth and laws of thought conceptions of logic. I employ the figure of the logical alien as it appears in the work of Gottlob Frege in order to draw out these alternative conceptions, showing that ultimately Frege's view presumes the laws of truth conception, but differently from Frege, Kant and the later Wittgenstein's conception of logic characterizes the logical laws as explicit prescriptions for how we ought to reason. I conclude that the contemporary literature on logical normativity has been shaped primarily by Frege's laws of truth conception of logic, but that we should return to a Kantian view in order to get a complete picture of logical normativity.In Chapter 2, I present 'constitutive normativism', an explication of the normativity of logic based in the laws of thought conception of logic, and I defend it against a number of pressing objections. Constitutive normativism posits the evaluative, wide scope 'in spirit' normative requirement on deductive propositional reasoning that it should avoid certain combinations of attitudes which violate modus ponens and universal instantiation. I also argue that Gilbert Harman's well-known objections to logical normativity about belief revision, excessive cognitive demands, and triviality, can be handled by constitutive normativism. I conclude by defending constitutive normativism against some objections to the general strategy of constitutivism as a way to explain the categorical authority of norms.In the second half of my dissertation, I develop and employ the logical normativity dualism framework to address some standing problems in the philosophy of logic. One key upshot which I discuss in Chapter 3 is that constitutive normativism can help solve a recent problem for Quinean, anti-exceptionalist views of logic, what is called the Adoption Problem. I explain that the Adoption Problem poses a problem for the Quinean view because we aren't able to reason in accordance with our preferred theory without using modus ponens and universal instantiation, regardless of whether either inference rule is valid in our preferred theory. But by embracing a plurality of conceptions of logic - taking on both the laws of truth and laws of thought conceptions of logic - we can distinguish between kinds of logical rules which make inquiry possible and those which we inquire into, and thereby save the Quinean view.In Chapter 4, I complete the picture of logical normativity dualism by developing and defending an evidentialist explication of logical normativity on the basis of the laws of truth conception of logic. I demonstrate that the two logical normativities, constitutive normativism and what I call 'evidential reasons normativism', complement each other rather than conflict. I also draw on the developments of the previous chapters to demonstrate that the supposed incompatibility between logical pluralism and logical normativity doesn't carry over to my view.

A central goal of modern model theory is to classify and understand first-order structures through studying the combinatorial properties of their definable sets, Conversely, model-theoretic properties can shed light on the behavior of interesting families of sets, such as semialgebraic families, which happen to be definable in well-behaved structures. This dissertation studies one such model-theoretic property, distality, as it manifests in the combinatorics of definable sets, and in continuous logic, where definable sets are generalized to real-valued functions.In Chapter 2, we calculate explicit bounds on the sizes of distal cell decompositions for definable sets in a variety of distal structures. These lead to incidence combinatorics bounds in exponential-polynomial and p-adic settings. In Chapter 3 and Chapter 4, we develop a theory of distality in continuous logic. This begins with a study of the combinatorics of NIP metric structures, building on earlier work by Ben Yaacov and results from statistical learning theory. We also develop a theory of generically stable Keisler measures in continuous logic, allowing us to generalize combinatorial statements from just pertaining to finite counting measures. We then generalize many definitions of distal structures to the continuous logic context, showing that under an NIP assumption, they are all equivalent. These allow us to study distal metric structures through the perspectives of indiscernible sequences, strong honest definitions, distal cell decompositions, Keisler measures, and an analytic regularity lemma. Finally in Chapter 5, joint work with Itaï Ben Yaacov, we present examples of distal metric structures that are unique to continuous logic, including real closed metric valued fields and dual linear continua.

This dissertation investigates Baire measurable, measurable, and Borel labeling problems in descriptive combinatorics on Borel graphs that are tree-like or grid-like, and also on graphs that have certain expansion behavior.Chapter 2 introduces a framework for applying the determinacy method to prove impossibility results in Borel combinatorics to labeling problems on tree-like graphs and hypergraphs. It also establishes a generalized method of round elimination to prove analogous impossibility results in the theory distributed algorithms and shows that these two methods both naturally apply to the same class of sinkless coloring problems. Chapter 3 provides a proof that the set of games for which a certain player has a winning strategy in a Borel family of games in Baire measurable. This result is used in the previous chapter in the determinacy arguments. This result is proven by classical methods, but it is also shown how the result follows from and fits into the theory of universally Baire sets of reals. Chapter 4 contains joint work with Felix Weilacher and Anton Bernshteyn to find a locally checkable labeling problem on two dimensional grids which can always be solved μ-measurably on any Borel grid for any Borel probability measure μ, but cannot always be solved Baire measurably. Chapter 5 contains joint work with Alexander Kastner to prove that free Borel actions of non-amenable groups admit Baire measurable perfect matchings. Chapter 6 proves an expander mixing lemma for probability measure preserving graphs and uses this result to obtain a simpler construction of an edge-colored highly mixing graph from the descriptive combinatorics literature.

The everything as a service concept enables dynamic resource provisions to be seen and delivered as services. Their proliferation nowadays leads to the creation of new value-added services composed of several sub-services in a pre-specified manner, known as service workflows. The use of service workflow appears in various domains, ranging from the basic interactions found in several e-commerce and several online interactions to the complex ones such as Virtual Organizations, Grids, and Cloud Computing. However, the dynamic nature in open environments makes a workflow constantly changing, to be adaptable to the change of new circumstances. How to determine suitable services has becomes a very important challenge. Requirements from both workflow owners and service providers play a significant role in the process of service acquisition, composition, and interoperations. From the workflow owner viewpoint, requirements can specify properties of services to be acquired for tasks in a workflow. On the other hand, requirements from service providers affect trust-based decision in workflow participation. The lack of formal languages to specify these requirements poses difficulties in the success of service collaborations in a workflow. It impedes: (1) workflow scalability that tends to be limited within a certain set of trusted domains; (2) dynamicity when each service acts in an autonomous and unpredictable manner where any change might affect existing requirements; and (3) inconsistency in dealing with the disparate representations of requirements, causing high overhead for compliance checking. This thesis focuses on developing a framework to overcome, or at least alleviate, these problems. It situates in inter-disciplinary areas including logics, workflow modelling, specification languages, trust management, decision support system, and compliance checking. Two core elements are proposed: (1) a formal logic-based requirement specification language, namely Trust Specification (TS), such that the requirements can be formally and uniformly expressed; and (2) compliance checking algorithms to automatically check for the compliance of requirements in service workflows. It is worth noting that this thesis contains some proofs of logic extension, workflow modelling, specification language, and compliance checking algorithms. These might raise a concern to people focusing deep on one particular area such as logics, or workflow modelling who might overlook the essence of the work, for example (1) the application of a formal specification language to the exclusive characteristics of service workflows, and (2) bridging the gap of the high level languages such as trust management down to the lower logic-based ones. The first contribution of the framework is to allow requirements to be independently and consistently expressed by each party where the workflow participation decision and acquisition are subject to the compliance of requirements. To increase scalability in large-scale interoperations, the second contribution centres on automatic compliance checking where TS language and compliance checking algorithms are two key components. The last contribution focuses on dynamicity. The framework allows each party to modify existing requirements and the compliance checking would be automatically activated to check for further compliance. As a result, it is anticipated that the solution will encourage the proliferation of service provisions and consumption over the Internet.

This dissertation shows that satisfiability procedures are abstract interpreters. This insight provides a unified view of program analysis and satisfiability solving and enables technology transfer between the two fields. The framework underlying these developments provides systematic recipes that show how intuition from satisfiability solvers can be lifted to program analyzers, how approximation techniques from program analyzers can be integrated into satisfiability procedures and how program analyzers and satisfiability solvers can be combined. Based on this work, we have developed new tools for checking program correctness and for solving satisfiability of quantifier-free first-order formulas. These tools outperform existing approaches. We introduce abstract satisfaction, an algebraic framework for applying abstract interpre- tation to obtain sound, but potentially incomplete satisfiability procedures. The framework allows the operation of satisfiability procedures to be understood in terms of fixed point computations involving deduction and abduction transformers on lattices. It also enables satisfiability solving and program correctness to be viewed as the same algebraic problem. Using abstract satisfaction, we show that a number of satisfiability procedures can be understood as abstract interpreters, including Boolean constraint propagation, the dpll and cdcl algorithms, St ̊almarck’s procedure, the dpll(t) framework and solvers based on congruence closure and the Bellman-Ford algorithm. Our work leads to a novel understand- ing of satisfiability architectures as refinement procedures for abstract analyses and allows us to relate these procedures to independent developments in program analysis. We use this perspective to develop Abstract Conflict-Driven Clause Learning (acdcl), a rigorous, lattice-based generalization of cdcl, the central algorithm of modern satisfiability research. The acdcl framework provides a solution to the open problem of lifting cdcl to new prob- lem domains and can be instantiated over many lattices that occur in practice. We provide soundness and completeness arguments for acdcl that apply to all such instantiations. We evaluate the effectiveness of acdcl by investigating two practical instantiations: fp-acdcl, a satisfiability procedure for the first-order theory of floating point arithmetic, and cdfpl, an interval-based program analyzer that uses cdcl-style learning to improve the precision of a program analysis. fp-acdcl is faster than competing approaches in 80% of our benchmarks and it is faster by more than an order of magnitude in 60% of the benchmarks. Out of 33 safe programs, cdfpl proves 16 more programs correct than a mature interval analysis tool and can conclusively determine the presence of errors in 24 unsafe benchmarks. Compared to bounded model checking, cdfpl is on average at least 260 times faster on our benchmark set.

Logical deduction and abstraction from detail are fundamental, yet distinct aspects of reasoning about programs. This dissertation shows that the combination of logic and abstract interpretation enables a unified and simple treatment of several theoretical and practical topics which encompass the model theory of temporal logics, the analysis of satisfiability solvers, and the construction of Craig interpolants. In each case, the combination of logic and abstract interpretation leads to more general results, simpler proofs, and a unification of ideas from seemingly disparate fields. The first contribution of this dissertation is a framework for combining temporal logics and abstraction. Chapter 3 introduces trace algebras, a new lattice-based semantics for linear and branching time logics. A new representation theorem shows that trace algebras precisely capture the standard trace-based semantics of temporal logics. We prove additional representation theorems to show how structures that have been independently discovered in static program analysis, model checking, and algebraic modal logic, can be derived from trace algebras by abstract interpretation. The second contribution of this dissertation is a framework for proving when two lattice-based algebras satisfy the same logical properties. Chapter 5 introduces functions called subsumption and bisubsumption and shows that these functions characterise logical equivalence of two algebras. We also characterise subsumption and bisubsumption using fixed points and finitary logics. We prove a representation theorem and apply it to derive the transition system analogues of subsumption and bisubsumption. These analogues strictly generalise the well studied notions of simulation and bisimulation. Our fixed point characterisations also provide a technique to construct property preserving abstractions. The third contribution of this dissertation is abstract satisfaction, an abstract interpretation framework for the design and analysis of satisfiability procedures. We show that formula satisfiability has several different fixed point characterisations, and that satisfiability procedures can be understood as abstract interpreters. Our main result is that the propagation routine in modern sat solvers is a greatest fixed point computation involving abstract transformers, and that clause learning is an abstract transformer for a form of negation. The final contribution of this dissertation is an abstract interpretation based analysis of algorithms for constructing Craig interpolants. We identify and analyse a lattice of interpolant constructions. Our main result is that existing algorithms are two of three optimal abstractions of this lattice. A second new result we derive in this framework is that the lattice of interpolation algorithms can be ordered by logical strength, so that there is a strongest and a weakest possible construction.

Description Logics form a family of powerful ontology languages widely used by academics and industry experts to capture and intelligently manage knowledge about the world. A key advantage of Description Logics is their amenability to automated reasoning that enables the deduction of knowledge that has not been explicitly stated. However, in order to ensure decidability of automated reasoning algorithms, suitable restrictions are usually enforced on the shape of structures that are expressible using Description Logics. As a consequence, Description Logics fall short of expressive power when it comes to representing cyclic structures, which abound in life sciences and other disciplines. The objective of this thesis is to explore ontology languages that are better suited for the representation of structured objects. It is suggested that an alternative approach which relies on nonmonotonic existential rules can provide a promising candidate for modelling such domains. To this end, we have built a comprehensive theoretical and practical framework for the representation of structured entities along with a surface syntax designed to allow the creation of ontological descriptions in an intuitive way. Our formalism is based on nonmonotonic existential rules and exhibits a favourable balance between expressive power and computational as well as empirical tractability. In order to ensure decidability of reasoning, we introduce a number of acyclicity criteria that strictly generalise many of the existing ones. We also present a novel stratification condition that properly extends `classical' stratification and allows for capturing both definitional and conditional aspects of complex structures. The applicability of our formalism is supported by a prototypical implementation, which is based on an off-the-shelf answer set solver and is tested over a realistic knowledge base. Our experimental results demonstrate improvement of up to three orders of magnitude in comparison with previous evaluation efforts and also expose numerous modelling errors of a manually curated biochemical knowledge base. Overall, we believe that our work lays the practical and theoretical foundations of an ontology language that is well-suited for the representation of structured objects. From a modelling point of view, our approach could stimulate the adoption of a different and expressive reasoning paradigm for which robustly engineered mature reasoners are available; it could thus pave the way for the representation of a broader spectrum of knowledge. At the same time, our theoretical contributions reveal useful insights into logic-based knowledge representation and reasoning. Therefore, our results should be of value to ontology engineers and knowledge representation researchers alike.

This thesis is a detailed examination of the logico-semantic system propounded by the English philosopher and theologian William of Ockham (c.1287 – c.1347). It provides a reinterpretation of Ockham's account of mental content and mental-language semantics, as well as of his theory of consequential goodness. It does so from the standpoint of an inferentialist theory of meaning, in rejection of previous attempts made from the standpoint of internalist and externalist theories of mental content. Chapter 1 ('The Scientic Status of Logic') provides an account of Ockham's understanding of logic as a rational, practical, ostensive science. Chapter 2 ('The Received Interpretation') presents and casts doubt upon the arguments put forward by the defenders of both externalist and internalist construals of Ockham's semantic theory. Chapter 3 ('An Inferentialist Construal') presents the central tenets of a inferentialist theory of meaning. In order to show how Ockham's system can be understood within such a semantic paradigm, we will have to set out at least three things. First, Chapter 4 ('Ockham's Propositionalism') argues that the mature Ockham actually embraced a propositionalist theory of meaning. Second, Chapter 5 ('Obligationes and the Normativity of Asserting') seeks to prove that such a theory of meaning can only be properly understood against the normative background provided by his theory of obligationes. Finally, Chapter 6 ('Consequences') argues that Ockham's theory of consequential goodness is materialist, not formalist. That is to say, that the goodness of a certain kind of consequence ultimately depends upon the meaning of its propositional parts, rather than upon its structure. It is then shown that all remaining kinds of consequences (syllogisms included) are to understood with respect to these material inferences. The main sources of this research are Ockham's Ordinatio, his Summa logicae, and his Quodlibeta septem. As regards the inferentialist theory of meaning, Robert Brandom's Making it Explicit (1994) and Wilfrid Sellars 'Inference and Meaning' (1953) were essential to this research.