Online research in philosophy

In this paper we describe an improvement of Smullyan's analytic tableau method for the propositional calculus-Improved Parent Clash Restricted (IPCR) tableau-and show that it is equivalent to SL-resolution in complexity.

The revised edition contains a new chapter which provides an elegant description of the semantics. The various classes of lambda calculus models are described in a uniform manner. Some didactical improvements have been made to this edition. An example of a simple model is given and then the general theory (of categorical models) is developed. Indications are given of those parts of the book which can be used to form a coherent course.

In this paper, we propose a game semantics for the (associative) Lambek calculus . Compared to the implicational fragment of intuitionistic propositional calculus, the semantics deals with two features of the logic: absence of structural rules, as well as directionality of implication. We investigate the impact of these variations of the logic on its game semantics.

In this chapter, I produce counterexamples to Presuppositional Epistemic Contextualism (PEC), a view about the semantics of ‘knowledge’-ascriptions that I have argued for elsewhere. According to PEC, the semantic content of the predicate ‘know’ at a context C is partly determined by the speakers’ pragmatic presuppositions at C. The problem for the view that I shall be concerned with here arises from the fact that pragmatic presuppositions are sometimes known to be true by the speakers who make them: hence the Problem of Known Presuppositions. After discussing several unsuccessful ways to solve the problem, I propose the addition of a new Lewisian rule of proper ignoring to the semantics of PEC--namely, the Rule of Evidence-Based Ignoring. If the proposed account succeeds, the Problem of Known Presuppositions has a straightforward solution within the framework of PEC.

In this paper, I will argue for a new account of presuppositions which is based on double indexing as well as minimal representational contexts providing antecedent material for anaphoric presuppositions, rather than notions of context defined in terms of the interlocutors’ pragmatic presuppositions or the information accumulated from the preceding discourse. This account applies in particular to new phenomena concerning the presupposition of quantifier domains. But it is also intended to be an account of presuppositions in general. The account differs from the Satisfaction Theory and the Binding Theory of presuppositions in that it can be viewed as a conservative extension of traditional static semantics and in that it does not involve the notion of pragmatic presupposition.

This paper presents a formulation and completeness proof of the resolution-type calculi for the first order fragment of Girard's linear logic by a general method which provides the general scheme of transforming a cutfree Gentzen-type system into a resolution type system, preserving the structure of derivations. This is a direct extension of the method introduced by Maslov for classical predicate logic. Ideas of the author and Zamov are used to avoid skolomization. Completeness of strategies is first established for the Gentzen-type system, and then transferred to resolution. The propositional resolution system was implemented by T. Tammet.

We prove that the problem of determining the minimum propositional proof length is NP- hard to approximate within a factor of 2 log 1 - o(1) n . These results are very robust in that they hold for almost all natural proof systems, including: Frege systems, extended Frege systems, resolution, Horn resolution, the polynomial calculus, the sequent calculus, the cut-free sequent calculus, as well as the polynomial calculus. Our hardness of approximation results usually apply to proof length measured either by number of symbols or by number of inferences, for tree-like or dag-like proofs. We introduce the Monotone Minimum (Circuit) Satisfying Assignment problem and reduce it to the problems of approximation of the length of proofs.

We establish a connection between the geometric methods developed in the combinatorial theory of small cancellation and the propositional resolution calculus. We define a precise correspondence between resolution proofs in logic and diagrams in small cancellation theory, and as a consequence, we derive that a resolution proof is a 2-dimensional process. The isoperimetric function defined on diagrams corresponds to the length of resolution proofs.

We investigate several approaches to resolution based automated theoremproving in classical higher-order logic (based on Church's simply typed-calculus) and discuss their requirements with respect to Henkincompleteness and full extensionality. In particular we focus on Andrews'higher-order resolution (Andrews 1971), Huet's constrained resolution (Huet1972), higher-order E-resolution, and extensional higher-order resolution(Benzmüller and Kohlhase 1997). With the help of examples we illustratethe parallels and differences of the extensionality treatment of these approachesand demonstrate that extensional higher-order resolution is the sole approach thatcan completely avoid additional extensionality axioms.