On transformations of constant depth propositional proofs

This paper studies the complexity of constant depth propositional proofs in the cedent and sequent calculus. We discuss the relationships between the size of tree-like proofs, the size of dag-like proofs, and the heights of proofs. The main result is to correct a proof construction in an earlier paper about transformations from proofs with polylogarithmic height and constantly many formulas per cedent.     

Complexity of subclasses of the intuitionistic propositional calculus

We investigate the complexity of the decision problem for subclasses of the intuitionistic propositional calculus and present upper bounds for decision procedures locating these subclasses into lower complexity classes like co-NP or polynomial time.     

Non-commutative Łukasiewicz propositional logic

The non-commutative counterpart of the well-known Łukasiewicz propositional logic is developed, in strong connection with the algebraic theory of psMV-algebras. An extension by a new unary logical connective is also considered and a stronger completeness result is proved for this system.     

Counting proofs in propositional logic

We give a procedure for counting the number of different proofs of a formula in various sorts of propositional logic. This number is either an integer (that may be 0 if the formula is not provable) or infinite. Research described in this paper is supported by Polish Ministry of Science and Higher Education grant NN206 356236.     

Separability of normalizable superintuitionistic propositional logics

The problem of separability of superintuitionistic propositional logics that are extensions of the intuitionistic propositional logic is studied. A criterion of separability of normal superintuitionistic propositional logics, as well as results concerning the completeness of their subcalculi is obtained. This criterion makes it possible to determine whether a normalizable superintuitionistic propositional logic is separable. By means of these results, the mistakes discovered by the author in the proofs of certain statements by McKay and Hosoi are corrected.Translated fromMatematicheskie Zametki, Vol. 64, No. 4, pp. 606–615, October, 1998.This research was supported by the Russian Foundation for Basic Research under grant No. 94-01-00944.     

Proof complexity of propositional default logic

Default logic is one of the most popular and successful formalisms for non-monotonic reasoning. In 2002, Bonatti and Olivetti introduced several sequent calculi for credulous and skeptical reasoning in propositional default logic. In this paper we examine these calculi from a proof-complexity perspective. In particular, we show that the calculus for credulous reasoning obeys almost the same bounds on the proof size as Gentzen??s system LK. Hence proving lower bounds for credulous reasoning will be as hard as proving lower bounds for LK. On the other hand, we show an exponential lower bound to the proof size in Bonatti and Olivetti??s enhanced calculus for skeptical default reasoning.     

A new algorithm for the propositional satisfiability problem

A new enumeration algorithm is proposed for the propositional satisfiability problem. Such algorithm is based on a hypergraph formulation of the problem. Two different implementations of the algorithm are presented together with the results of an experimentation intended to compare their performance with the performance of other known methods. The computational results obtained are quite promising.     

On the correspondence between arithmetic theories and propositional proof systems – a survey

The purpose of this paper is to survey the correspondence between bounded arithmetic and propositional proof systems. In addition, it also contains some new results which have appeared as an extended abstract in the proceedings of the conference TAMC 2008 [11]. Bounded arithmetic is closely related to propositional proof systems; this relation has found many fruitful applications. The aim of this paper is to explain and develop the general correspondence between propositional proof systems and arithmetic theories, as introduced by Krají?ek and Pudlák [46]. Instead of focusing on the relation between particular proof systems and theories, we favour a general axiomatic approach to this correspondence. In the course of the development we particularly highlight the role played by logical closure properties of propositional proof systems, thereby obtaining a characterization of extensions of EF in terms of a simple combination of these closure properties (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A simple propositional S5 tableau system

We give a sound and weakly complete propositional S5 tableau system of a particularly simple sort, having an easy completeness proof. It sheds light on why the satisfiability problem for S5 is less complex than that for most other propositional modal logics. We believe the system remains complete when appropriate quantifier rules are added. If so, it would allow us to get partway to an interpolation theorem for first-order S5, a theorem that is known to fail in general.     

Simple characterization of functionally complete one‐element sets of propositional connectives

A set of propositional connectives is said to be functionally complete if all propositional formulae can be expressed using only connectives from that set. In this paper we give sufficient and necessary conditions for a one‐element set of propositional connectives to be functionally complete. These conditions provide a simple and elegant characterization of functionally complete one‐element sets of propositional connectives (of arbitrary arity). (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Quantification over propositional formulas in probability logic: decidability issues

A language for reasoning about probability is generalized by adding quantifiers over propositional formulas to the language. Then relevant decidability issues are considered. In particular, the results presented demonstrate that a rather weak fragment of the new language has an undecidable validity problem. On the other hand, it is stated that a restricted version of the validity problem is decidable for ∀∃-sentences.     

A coding method for a sequent calculus of propositional logic

The paper deals with a coding method for a sequent calculus of the propositional logic. The method is based on the sequent calculus. It allows us to determine if a formula is derivable in the calculus without constructing a derivation tree. The main advantage of the coding method is its compactness in comparison with derivation trees of the sequent calculus. The coding method can be used as a decision procedure for the propositional logic.     

Classification of derivable propositional formulas

This article considers questions connected with the derivability of propositional formulas under restrictions on the length of the derivation. A classification is proposed for formulas with minimum derivation length.Translated from Matematicheskie Zametki, Vol. 11, No. 2, pp. 165–174, February, 1972.     

On the recognition of the tautological nature of propositional formulas

A formal language whose propositions express (in some sense) the properties of propositional formulas is described in the paper. For a certain subset of propositions of this language it is proved that each of them defines a class of propositional formulas, on which it is possible to recognize the tautological nature in a time polynomially dependent on the formula's length.Translated fromZapiski Nauchnykh Seminarov Leningradskogo Matematicheskogo, Otdeleniyaim. V. A.Steklova Akad.Nauk SSSR, Vol. 60, pp. 197–206,1976. Result announced December 4, 1974.     

A proof-search procedure for intuitionistic propositional logic

A sequent root-first proof-search procedure for intuitionistic propositional logic is presented. The procedure is obtained from modified intuitionistic multi-succedent and classical sequent calculi, making use of Glivenko’s Theorem. We prove that a sequent is derivable in a standard intuitionistic multi-succedent calculus if and only if the corresponding prefixed-sequent is derivable in the procedure.     

Fuzzy propositional logics

Fuzzy logic $\text{L}$_∞9 considered in connection with fuzzy sets theory, is a special theory, is a special many valued logic with truth-value sets [0, 1], which has been studied already by Lukasiewicz. We consider also his versions $\text{L}$_m for m ? 2 with finite truth-value sets. In all cases we add two further propositional connectives, one conjunction and one disjunction. For these logics we give a list of tautologies, consider relations between their sets of tautologies, prove their compactness, and mention some further results.     

Another look at graph coloring via propositional satisfiability

This paper studies the solution of graph coloring problems by encoding into propositional satisfiability problems. The study covers three kinds of satisfiability solvers, based on postorder reasoning (e.g., grasp, chaff), preorder reasoning (e.g., 2cl, 2clsEq), and back-chaining (modoc). The study evaluates three encodings, one of them believed to be new. Some new symmetry-breaking methods, specific to coloring, are used to reduce the redundancy of solutions. A by-product of this research is an implemented lower-bound technique that has shown improved lower bounds for the chromatic numbers of the long-standing unsolved random graphs known as DSJC125.5 and DSJC125.9. Independent-set analysis shows that the chromatic numbers of DSJC125.5 and DSJC125.9 are at least 18 and 40, respectively, but satisfiability encoding was able to demonstrate only that the chromatic numbers are at least 13 and 38, respectively, within available time and space.     

Algorithms for propositional model counting

We present algorithms for the propositional model counting problem #SAT. The algorithms utilize tree decompositions of certain graphs associated with the given CNF formula; in particular we consider primal, dual, and incidence graphs. We describe the algorithms coherently for a direct comparison and with sufficient detail for making an actual implementation reasonably easy. We discuss several aspects of the algorithms including worst-case time and space requirements.     

Combinatorics of first order structures and propositional proof systems

We define the notion of a combinatorics of a first order structure, and a relation of covering between first order structures and propositional proof systems. Namely, a first order structure M combinatorially satisfies an L-sentence iff holds in all L-structures definable in M. The combinatorics Comb(M) of M is the set of all sentences combinatorially satisfied in M. Structure M covers a propositional proof system P iff M combinatorially satisfies all for which the associated sequence of propositional formulas _n, encoding that holds in L-structures of size n, have polynomial size P-proofs. That is, Comb(M) contains all feasibly verifiable in P. Finding M that covers P but does not combinatorially satisfy thus gives a super polynomial lower bound for the size of P-proofs of _n. We show that any proof system admits a class of structures covering it; these structures are expansions of models of bounded arithmetic. We also give, using structures covering proof systems R^*(log) and PC, new lower bounds for these systems that are not apparently amenable to other known methods. We define new type of propositional proof systems based on a combinatorics of (a class of) structures.Partially supported by grant # A 101 99 01 of the Academy of Sciences of the Czech Republic and by project LN00A056 of The Ministry of Education of the Czech Republic.Also member of the Institute for Theoretical Computer Science of the Charles University. A part of this work was done while visiting the Mathematical Institute, Oxford.