V.A. Smirnov’s Results in the Field of Modern Formal Logic

This paper is a survey of V.A. Smirnovs main results in modern logic.     

Uniform Interpolation and Propositional Quantifiers in Modal Logics

We investigate uniform interpolants in propositional modal logics from the proof-theoretical point of view. Our approach is adopted from Pitts’ proof of uniform interpolationin intuitionistic propositional logic [15]. The method is based on a simulation of certain quantifiers ranging over propositional variables and uses a terminating sequent calculus for which structural rules are admissible. We shall present such a proof of the uniform interpolation theorem for normal modal logics K and T. It provides an explicit algorithm constructing the interpolants. Presented by Heinrich Wansing     

Protoalgebraic Gentzen Systems and the Cut Rule

In this paper we show that, in Gentzen systems, there is a close relation between two of the main characters in algebraic logic and proof theory respectively: protoalgebraicity and the cut rule. We give certain conditions under which a Gentzen system is protoalgebraic if and only if it possesses the cut rule. To obtain this equivalence, we limit our discussion to what we call regular sequent calculi, which are those comprising some of the structural rules and some logical rules, in a sense we make precise. We note that this restricted set of rules includes all the usual rules in the literature. We also stress the difference between the case of two-sided sequents and the case of many-sided sequents, in which more conditions are needed.     

An O(n log n)-Space Decision Procedure for the Relevance Logic B+

In previous work we gave a new proof-theoretical method for establishing upper-bounds on the space complexity of the provability problem of modal and other propositional non-classical logics. Here we extend and refine these results to give an O(n log n)-space decision procedure for the basic positive relevance logic B⁺. We compute this upper-bound by first giving a sound and complete, cut-free, labelled sequent system for B⁺, and then establishing bounds on the application of the rules of this system.     

Sequent Calculi and Decision Procedures for Weak Modal Systems

We investigate sequent calculi for the weak modal (propositional) system reduced to the equivalence rule and extensions of it up to the full Kripke system containing monotonicity, conjunction and necessitation rules. The calculi have cut elimination and we concentrate on the inversion of rules to give in each case an effective procedure which for every sequent either furnishes a proof or a finite countermodel of it. Applications to the cardinality of countermodels, the inversion of rules and the derivability of Löb rules are given.     

Complete Infinitary Type Logics

For each regular cardinal , we set up three systems of infinitary type logic, in which the length of the types and the length of the typed syntactical constructs are < . For a fixed , these three versions are, in the order of increasing strength: the local system ₍₎, the global system g₍₎ (the difference concerns the conditions on eigenvariables) and the -system ₍₎ (which has anti-selection terms or Hilbertian -terms, and no conditions on eigenvariables). A full cut elimination theorem is proved for the local systems, and about the -systems we prove that they admit cut-free proofs for sequents in the -free language common to the local and global systems. These two results follow from semantic completeness proofs. Thus every sequent provable in a global system has a cut-free proof in the corresponding -systems. It is, however, an open question whether the global systems in themselves admit cut elimination.     

Deduction chains for common knowledge

Deduction chains represent a syntactic and in a certain sense constructive method for proving completeness of a formal system. Given a formula , the deduction chains of are built up by systematically decomposing into its subformulae. In the case where is a valid formula, the decomposition yields a (usually cut-free) proof of . If is not valid, the decomposition produces a countermodel for . In the current paper, we extend this technique to a semiformal system for the Logic of Common Knowledge. The presence of fixed point constructs in this logic leads to potentially infinite-length deduction chains of a non-valid formula, in which case fairness of decomposition requires special attention. An adequate order of decomposition also plays an important role in the reconstruction of the proof of a valid formula from the set of its deduction chains.