We reconstruct Frege’s treatment of certain deducibility problems posed by Boole. It turns out that in his formalization and solution of Boole’s problems Frege anticipates the idea of propositional resolution.

We show that Smullyan's analytic tableaux cannot p-simulate the truth-tables. We identify the cause of this computational breakdown and relate it to an underlying semantic difficulty which is common to the whole tradition originating in Gentzen's sequent calculus, namely the dissonance between cut-free proofs and the Principle of Bivalence. Finally we discuss some ways in which this principle can be built into a tableau-like method without affecting its analytic nature.

In this paper we investigate the problem of testing the coherence of an assessment of conditional probability following a purely logical setting. In particular we will prove that the coherence of an assessment of conditional probability χ can be characterized by means of the logical consistency of a suitable theory T χ defined on the modal-fuzzy logic FP k (RŁΔ) built up over the many-valued logic RŁΔ. Such modal-fuzzy logic was previously introduced in Flaminio (Lecture Notes in Computer Science, vol. (...) 3571, 2005) in order to treat conditional probability by means of a list of simple probabilities following the well known (smart) ideas exposed by Halpern (Proceedings of the eighth conference on theoretical aspects of rationality and knowledge, pp 17–30, 2001) and by Coletti and Scozzafava (Trends Logic 15, 2002). Roughly speaking, such logic is obtained by adding to the language of RŁΔ a list of k modalities for “probably” and axioms reflecting the properties of simple probability measures. Moreover we prove that the satisfiability problem for modal formulas of FP k (RŁΔ) is NP-complete. Finally, as main result of this paper, we prove FP k (RŁΔ) in order to prove that the problem of establishing the coherence of rational assessments of conditional probability is NP-complete. (shrink)

The authors present the main ideas of the computer-assisted proof of Mischaikow and Mrozek that chaos is really present in the Lorenz equations. Methodological consequences of this proof are examined. It is shown that numerical calculations can constitute an essential part of mathematical proof not only in the discrete mathematics but also in the mathematics of continua.

A new type of formalization of classical first-order logic with equality is introduced on the basis of the sequent calculus. It serves to justify the claim that equality is a logical constant characterised by well-behaved rules satisfying properties usually regarded as essential. The main feature of this approach is the application of sequents built not only from formulae but also from terms. Two variants of sequent calculus are examined, a structural and a logical one. The former is defined in accordance (...) with Dos̆en’s criteria for logical constants. The latter is a standard Gentzen’s sequent calculus and satisfies Hacking’s criteria for logicality, including cut elimination. It is also shown that provided rules are harmonious in the sense advocated by Gratzl and Orlandelli. (shrink)

We describe the foundations of a system for rule-based programming which integrates two powerful mechanisms: matching with context variables, sequence variables, and regular constraints for their matching values; and strategic programming with labeled rules. The system is called ρLog, and is built on top of the pattern matching and rule-based programming capabilities of Mathematica.

We show the completeness of a Hilbert-style system LK defined by M. Valiev involving the knowledge operator K dedicated to the reasoning with incomplete information. The completeness proof uses a variant of Makinson's canonical model construction. Furthermore we prove that the theoremhood problem for LK is co-NP-complete, using techniques similar to those used to prove that the satisfiability problem for propositional S5 is NP-complete.

Tautology elimination rule was successfully applied in automated deduction and recently considered in the framework of sequent calculi where it is provably equivalent to cut rule. In this paper we focus on the advantages of proving admissibility of tautology elimination rule instead of cut for sequent calculi. It seems that one may find simpler proofs of admissibility for tautology elimination than for cut admissibility. Moreover, one may prove its admissibility for some calculi where constructive proofs of cut admissibility fail. As (...) an illustration we present a cut-free sequent calculus for S5 based on tableau system of Fitting and prove admissibility of tautology elimination rule for it. (shrink)

This paper is an attempt at providing a systematic presentation of Quantified Modal Logics . We present a set of modular, uniform, normalizing, sound and complete labelled sequent calculi for all QMLs whose frame properties can be expressed as a finite set of first-order sentences with equality. We first present CQK, a calculus for the logic QK, and then we extend it to any such logic QL. Each calculus, called CQL, is modular , uniform , normalizing and Kripke-sound and complete (...) for QL. We improve on the existing literature on the subject by extending the class of logics for which such a presentation is given, and by giving a new proof of soundness and completeness. (shrink)

In trying to control various aspects concerning utterance production in multi-party human–computer dialogue, argumentative considerations play an important part, particularly in choosing appropriate lexical units so that we fine-tune the degree of persuasion that each utterance has. A preliminary step in this endeavor is the ability to place an ordering relation between semantic forms (that are due to be realized as utterances, by the machine), concerning their persuasion strength, with respect to certain (explicit or implicit) conclusions. Thus, in this article, (...) we propose a mechanism for assessing utterances, in terms of their argumentative force. The framework designed conflates insights from Asher and Lascarides’ SDRT (“Segmented Discourse Representation Theory”), and from Anscombre and Ducrot’s AT (“Argumentation Theory”). These mechanisms are included in a language generation component of a multi-party dialogue system for book reservation applications (i.e., a “virtual librarian”), and thus evaluated via typical human–machine conversations. (shrink)

We add a limited but useful form of quantification to Coalition Logic, a popular formalism for reasoning about cooperation in game-like multi-agent systems. The basic constructs of Quantified Coalition Logic (QCL) allow us to express such properties as "every coalition satisfying property P can achieve φ" and "there exists a coalition C satisfying property P such that C can achieve φ". We give an axiomatisation of QCL, and show that while it is no more expressive than Coalition Logic, it is (...) nevertheless exponentially more succinct. The complexity of QCL model checking for symbolic and explicit state representations is shown to be no worse than that of Coalition Logic, and satisfiability for QCL is shown to be no worse than satisfiability for Coalition Logic. We illustrate the formalism by showing how to succinctly specify such social choice mechanisms as majority voting, which in Coalition Logic require specifications that are exponentially long in the number of agents. (shrink)

This book provides a detailed exposition of one of the most practical and popular methods of proving theorems in logic, called Natural Deduction. It is presented both historically and systematically. Also some combinations with other known proof methods are explored. The initial part of the book deals with Classical Logic, whereas the rest is concerned with systems for several forms of Modal Logics, one of the most important branches of modern logic, which has wide applicability.

We add a limited but useful form of quantification to Coalition Logic, a popular formalism for reasoning about cooperation in game-like multi-agent systems. The basic constructs of Quantified Coalition Logic (QCL) allow us to express such properties as “every coalition satisfying property P can achieve φ” and “there exists a coalition C satisfying property P such that C can achieve φ”. We give an axiomatisation of QCL, and show that while it is no more expressive than Coalition Logic, it is (...) nevertheless exponentially more succinct. The complexity of QCL model checking for symbolic and explicit state representations is shown to be no worse than that of Coalition Logic, and satisfiability for QCL is shown to be no worse than satisfiability for Coalition Logic. We illustrate the formalism by showing how to succinctly specify such social choice mechanisms as majority voting, which in Coalition Logic require specifications that are exponentially long in the number of agents. (shrink)

In Schwichtenberg, Schwichtenberg fine-tuned Tait’s technique so as to provide a simplified version of Gentzen’s original cut-elimination procedure for first-order classical logic. In this note we show that, limited to the case of classical propositional logic, the Tait–Schwichtenberg algorithm allows for a further simplification. The procedure offered here is implemented on Kleene’s sequent system G4. The specific formulation of the logical rules for G4 allows us to provide bounds on the height of cut-free proofs just in terms of the logical (...) complexity of their end-sequent. (shrink)