Group Cancellation and Resolution

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.     

Lightweight relevance filtering for machine-generated resolution problems

Irrelevant clauses in resolution problems increase the search space, making proofs hard to find in a reasonable amount of processor time. Simple relevance filtering methods, based on counting symbols in clauses, improve the success rate for a variety of automatic theorem provers and with various initial settings. We have designed these techniques as part of a project to link automatic theorem provers to the interactive theorem prover Isabelle. We have tested them for problems involving thousands of clauses, which yield poor results without filtering. Our methods should be applicable to other tasks where the resolution problems are produced mechanically and where completeness is less important than achieving a high success rate with limited processor time.     

Proof Theory for Reasoning with Euler Diagrams: A Logic Translation and Normalization

Proof-theoretical notions and techniques, developed on the basis of sentential/symbolic representations of formal proofs, are applied to Euler diagrams. A translation of an Euler diagrammatic system into a natural deduction system is given, and the soundness and faithfulness of the translation are proved. Some consequences of the translation are discussed in view of the notion of free ride, which is mainly discussed in the literature of cognitive science as an account of inferential efficacy of diagrams. The translation enables us to formalize and analyze free ride in terms of proof theory. The notion of normal form of Euler diagrammatic proofs is investigated, and a normalization theorem is proved. Some consequences of the theorem are further discussed: in particular, an analysis of the structure of normal diagrammatic proofs; a diagrammatic counterpart of the usual subformula property; and a characterization of diagrammatic proofs compared with natural deduction proofs.     

Connection-Driven Inductive Theorem Proving

We present a method for integrating rippling-based rewriting into matrix-based theorem proving as a means for automating inductive specification proofs. The selection of connections in an inductive matrix proof is guided by symmetries between induction hypothesis and induction conclusion. Unification is extended by decision procedures and a rippling/reverse-rippling heuristic. Conditional substitutions are generated whenever a uniform substitution is impossible. We illustrate the integrated method by discussing several inductive proofs for the integer square root problem as well as the algorithms extracted from these proofs.     

Socratic Trees

The method of Socratic proofs (SP-method) simulates the solving of logical problem by pure questioning. An outcome of an application of the SP-method is a sequence of questions, called a Socratic transformation. Our aim is to give a method of translation of Socratic transformations into trees. We address this issue both conceptually and by providing certain algorithms. We show that the trees which correspond to successful Socratic transformations—that is, to Socratic proofs—may be regarded, after a slight modification, as Gentzen-style proofs. Thus proof-search for some Gentzen-style calculi can be performed by means of the SP-method. At the same time the method seems promising as a foundation for automated deduction.     

Das Problem der apagogischen Beweise in Bolzanos Beyträgen und seiner Wissenschaftslehre

This paper analyzes and evaluates Bolzano's remarks on the apagogic method of proof with reference to his juvenile booklet ‘Contributions to a better founded presentation of mathematics’ of 1810 and to his ‘Theory of science’ (1837). I shall try to defend the following contentions: (1) Bolzanos’ vain attempt to transform all indirect proofs into direct proofs becomes comprehensible as soon as one recognizes the following facts: (1.1) his attitude towards indirect proofs with an affirmative conclusion differs from his stance to indirect proofs with a negative conclusion; (1.2) by Bolzano's lights arguments via consequentia mirabilis only seem to be indirect. (2) Bolzano does not deny that indirect proofs can be perfect certifications (Gewissmachungen) of their conclusion; what he denies is rather that they can provide grounds for their conclusions. (2.1) They cannot do the latter, since they start from false premises and (2.2) since they make an unnecessary detour. (3) The far-reaching agreement between his early and late assessment of apagogical proofs (in the Beyträge of 1810 and the Wissenschaftslehre of 1837) is partly due to the fact that he develops his own position always against the background of Wolff's and Lambert's views.     

On the Proof Theory of the Modal mu-Calculus

We study the proof-theoretic relationship between two deductive systems for the modal mu-calculus. First we recall an infinitary system which contains an omega rule allowing to derive the truth of a greatest fixed point from the truth of each of its (infinitely many) approximations. Then we recall a second infinitary calculus which is based on non-well-founded trees. In this system proofs are finitely branching but may contain infinite branches as long as some greatest fixed point is unfolded infinitely often along every branch. The main contribution of our paper is a translation from proofs in the first system to proofs in the second system. Completeness of the second system then follows from completeness of the first, and a new proof of the finite model property also follows as a corollary. Presented by Heinrich Wansing     

Wittgenstein on the Infinity of Primes

It is controversial whether Wittgenstein's philosophy of mathematics is of critical importance for mathematical proofs, or is only concerned with the adequate philosophical interpretation of mathematics. Wittgenstein's remarks on the infinity of prime numbers provide a helpful example which will be used to clarify this question. His antiplatonistic view of mathematics contradicts the widespread understanding of proofs as logical derivations from a set of axioms or assumptions. Wittgenstein's critique of traditional proofs of the infinity of prime numbers, specifically those of Euler and Euclid, not only offers philosophical insight but also suggests substantive improvements. A careful examination of his comments leads to a deeper understanding of what proves the infinity of primes.     

On the Proof-Theory of two Formalisations of Modal First-Order Logic

We introduce a Gentzen-style modal predicate logic and prove the cut-elimination theorem for it. This sequent calculus of cut-free proofs is chosen as a proxy to develop the proof-theory of the logics introduced in [14, 15, 4]. We present syntactic proofs for all the metatheoretical results that were proved model-theoretically in loc. cit. and moreover prove that the form of weak reflection proved in these papers is as strong as possible.     

Fool-proof proofs of God?

Summary Two claims have been explored, the first, that fool-proof proofs of the sort that there could be if there were a God like the God of Abraham, Isaac and Jacob are not to be expected, on good religious grounds (a claim I found wanting); and second, that there cannot be philosophical proofs of God which work beyond reasonable doubt.The argument that there cannot be philosophical proofs beyond a reasonable doubt is supported by an examination of some of the fundamental issues in the traditional discussions of proofs for God's existence, and by claims about the relativity of methodological rules to world-views which, I maintain, the traditional discussions indicate. I do not claim to have proved that relativity, only to have illustrated the claim that it is there.It is my further opinion, but I do not claim really to have proved it, that the failure of religious excuses for the lack of public demon strations constitutes a good reason for concluding that there is no God of the sort described as the God of Abraham, Isaac and Jacob; hence that if there is a God, it must be the God of the philosophers. However I admit that there might be sufficient hidden reasons which would offer persuasive excuses for the God of the ordinary believer.Lastly, I have made some comments about what I think is the more valuable way to view the proofs for God. Such an interpretation does justice to the otherwise baffling and continual philosophical disagreements better than rival theories. It is time we take these disagreements with utmost seriousness, and one can hardly do that while treating basic metaphysical arguments as fool-proof proofs.Readers of the literature on proofs will recognize many of the historical and current discussions on which comment is being made. To provide sources for all the comments would be not only cumbersome but impossible because they are found in so many different places and are not the property of any one in particular.     

Recognition of proofs in conditional reasoning

Relatively little is known about those who consistently produce the valid response to Modus Tollens (MT) problems. In two studies, people who responded correctly to MT problems indicated how “convinced” they were by proofs of conditional reasoning conclusions. The first experiment showed that MT competent reasoners found accurate proofs of MT reasoning more convincing than similar “proofs” of invalid reasoning. Similarly, there was a tendency for MT competent reasoners to find an initial counterfactual supposition more convincing than did people who were less competent in MT. The second experiment showed that when individuals produced the correct MT response, and found correct MT proofs to be more convincing than “bogus” proofs, they were also less likely to find the conclusions to Denying the Antecedent, or Affirming the Consequent problems valid, compared to individuals who could not discriminate between valid and bogus MT proofs. These findings are discussed in terms of both their implications for the mental logic and mental models positions, and individual differences in System 1 and System 2 reasoning.     

Explanation by induction?

Philosophers of mathematics commonly distinguish between explanatory and non-explanatory proofs. An important subclass of mathematical proofs are proofs by induction. Are they explanatory? This paper addresses the question, based on general principles about explanation. First, a recent argument for a negative answer is discussed and rebutted. Second, a case is made for a qualified positive take on the issue.     

Supporting the formal verification of mathematical texts

The formal verification of mathematical texts is one of the most interesting applications for computer systems. In fact, we argue that the expert language of mathematics is the natural choice for achieving efficient mathematician–machine interaction. Our empirical approach, the analysis of carefully authored textbook proofs, forces us to focus on the language and the reasoning pattern that mathematician use when presenting proofs to colleagues and students. Enabling a machine to understand and follow such language and argumentation is seen to be the key to usable and acceptable math assistant systems. In this paper, we first perform an analysis of three textbook proofs by hand; we then describe a computational framework that aims at mechanising such an analysis. The resulting proof-of-concept implementation is capable of processing simple textbook proofs and constitutes promising steps towards a natural mathematician–machine interface for proof development and verification.     

Strategic Construction of Fitch-style Proofs

Symlog is a system for learning symbolic logic by computer that allows students to interactively construct proofs in Fitch-style natural deduction. On request, Symlog can provide guidance and advice to help a student narrow the gap between goal theorem and premises. To effectively implement this capability, the program was equipped with a theorem prover that constructs proofs using the same methods and techniques the students are being taught. This paper discusses some of the aspects of the theorem prover's design, including its set of proof-construction strategies, its unification algorithm as well as some of the tradeoffs between efficiency and pedagogy.     

Strategic Maneuvering in Mathematical Proofs

This paper explores applications of concepts from argumentation theory to mathematical proofs. Note is taken of the various contexts in which proofs occur and of the various objectives they may serve. Examples of strategic maneuvering are discussed when surveying, in proofs, the four stages of argumentation distinguished by pragma-dialectics. Derailments of strategies (fallacies) are seen to encompass more than logical fallacies and to occur both in alleged proofs that are completely out of bounds and in alleged proofs that are at least mathematical arguments. These considerations lead to a dialectical and rhetorical view of proofs.

Defining answer classes using resolution refutation

Resolution theorem proving provides a useful paradigm for the exploration of question answering. A partition of the clauses generated during resolution refutation based on their syntactic structure is presented. The three classes comprising this partition correspond to semantically intuitive types of answers. This work encompasses and expands upon previous work on question answering in a theorem proving paradigm, which began with the association of answers with proofs. A complete, formal definition of what is meant by answer in the context of resolution theorem proving is presented. In this context, clauses that are relevant are all identified as answers, where relevance is determined with respect to a question and knowledge base: any clause descended from the clause form of a negated question is deemed relevant. This definition of relevance is not in and of itself novel; rather, it is the way in which the set of relevant clauses is partitioned that provides the key to interpreting clauses as answers. The three answer classes identified are: specific, generic, and hypothetical. These classes are formally distinguished by the way in which literals in a clause share variables, with class membership based on a property termed the closure of variable sharing of a literal. The results presented provide a foundation for further work by establishing a context-independent logical pragmatics of question answering.     

An Operational Logic of Proofs with Positive and Negative Information

The logic of proofs was introduced by Artemov in order to analize the formalization of the concept of proof rather than the concept of provability. In this context, some operations on proofs play a very important role. In this paper, we investigate some very natural operations, paying attention not only to positive information, but also to negative information (i.e. information saying that something cannot be a proof). We give a formalization for a fragment of such a logic of proofs, and we prove that our fragment is complete and decidable.     

On Different Intuitionistic Calculi and Embeddings from Int to S4

In this paper, we compare several cut-free sequent systems for propositional intuitionistic logic Intwith respect to polynomial simulations. Such calculi can be divided into two classes, namely single-succedent calculi (like Gentzen's LJ) and multi-succedent calculi. We show that the latter allow for more compact proofs than the former. Moreover, for some classes of formulae, the same is true if proofs in single-succedent calculi are directed acyclic graphs (dags) instead of trees. Additionally, we investigate the effect of weakening rules on the structure and length of dag proofs.The second topic of this paper is the effect of different embeddings from Int to S4. We select two different embeddings from the literature and show that translated (propositional) intuitionistic formulae have sometimes exponentially shorter minimal proofs in a cut-free Gentzen system for S4than the original formula in a cut-free single-succedent Gentzen system for Int. Moreover, the length and the structure of proofs of translated formulae crucially depend on the chosen embedding.