Explore the vast range of titles available.

Residuated basic logic (RBL) is the logic of residuated basic algebras, which constitutes a conservative extension of basic propositional logic (BPL). The basic implication is a residual of a non-associative binary operator in RBL. The conservativity is shown by relational semantics. A Gentzen-style sequent calculus GRBL, which is an extension of the distributive full non-associative Lambek calculus, is established for residuated basic logic. The calculus GRBL admits the mix-elimination, subformula, and disjunction properties. Moreover, the class of all residuated basic algebras has the finite embeddability property. The consequence relation of GRBL is decidable.

\"Satisfiability (SAT) related topics have attracted researchers from various disciplines: logic, applied areas such as planning, scheduling, operations research and combinatorial optimization, but also theoretical issues on the theme of complexity and much more, they all are connected through SAT. My personal interest in SAT stems from actual solving: The increase in power of modern SAT solvers over the past 15 years has been phenomenal. It has become the key enabling technology in automated verification of both computer hardware and software. Bounded Model Checking (BMC) of computer hardware is now probably the most widely used model checking technique. The counterexamples that it finds are just satisfying instances of a Boolean formula obtained by unwinding to some fixed depth a sequential circuit and its specification in linear temporal logic. Extending model checking to software verification is a much more difficult problem on the frontier of current research. One promising approach for languages like C with finite word-length integers is to use the same idea as in BMC but with a decision procedure for the theory of bit-vectors instead of SAT. All decision procedures for bit-vectors that I am familiar with ultimately make use of a fast SAT solver to handle complex formulas. Decision procedures for more complicated theories, like linear real and integer arithmetic, are also used in program verification. Most of them use powerful SAT solvers in an essential way. Clearly, efficient SAT solving is a key technology for 21st century computer science. I expect this collection of papers on all theoretical and practical aspects of SAT solving will be extremely useful to both students and researchers and will lead to many further advances in the field.\"--Edmund Clarke (FORE Systems University Professor of Computer Science and Professor of Electrical and Computer Engineering at Carnegie Mellon University, winner of the 2007 A.M. Turing Award).

A definition of complexity based on logic functions, which are widely used as compact descriptions of rules in diverse fields of contemporary science was explored. Detailed numerical analysis shows that (i) logic complexity is effective in discriminating between classes of functions commonly employed in modeling contexts; (ii) it extends the notion of canalization, used in the study of genetic regulation, to a more general and detailed measure; (iii) it is tightly linked to the resilience of a function's output to noise affecting its inputs. Its utility was demonstrated by measuring it in empirical data on gene regulation. Logic complexity is exceptionally low in these systems, and the asymmetry between “on” and “off” states in the data correlates with the complexity in a non‐null way. A model of random Boolean networks clarifies this trend and indicates a common hierarchical architecture in the three systems. © 2016 Wiley Periodicals, Inc. Complexity 21: 397–408, 2016

It is known that there is a sound and faithful translation of the full intuitionistic propositional calculus into the atomic polymorphic system Fat, a predicative calculus with only two connectives: the conditional and the second-order universal quantifier. The faithfulness of the embedding was established quite recently via a model-theoretic argument based in Kripke structures. In this paper we present a purely proof-theoretic proof of faithfulness. As an application, we give a purely proof-theoretic proof of the disjunction property of the intuitionistic propositional logic in which commuting conversions are not needed.

We show that there is a purely proof-theoretic proof of the Rasiowa-Harrop disjunction property for the full intuitionistic propositional calculus (IPC), via natural deduction, in which commuting conversions are not needed. Such proof is based on a sound and faithful embedding of IPC into an atomic polymorphic system. This result strengthens a homologous result for the disjunction property of IPC (presented in a recent paper co-authored with Fernando Ferreira) and answers a question then posed by Pierluigi Minari.

While many books have been written about Bertrand Russell's philosophy and some on his logic, I. Grattan-Guinness has written the first comprehensive history of the mathematical background, content, and impact of the mathematical logic and philosophy of mathematics that Russell developed with A. N. Whitehead in theirPrincipia mathematica (1910-1913). This definitive history of a critical period in mathematics includes detailed accounts of the two principal influences upon Russell around 1900: the set theory of Cantor and the mathematical logic of Peano and his followers. Substantial surveys are provided of many related topics and figures of the late nineteenth century: the foundations of mathematical analysis under Weierstrass; the creation of algebraic logic by De Morgan, Boole, Peirce, Schröder, and Jevons; the contributions of Dedekind and Frege; the phenomenology of Husserl; and the proof theory of Hilbert. The many-sided story of the reception is recorded up to 1940, including the rise of logic in Poland and the impact on Vienna Circle philosophers Carnap and Gödel. A strong American theme runs though the story, beginning with the mathematician E. H. Moore and the philosopher Josiah Royce, and stretching through the emergence of Church and Quine, and the 1930s immigration of Carnap and GödeI. Grattan-Guinness draws on around fifty manuscript collections, including the Russell Archives, as well as many original reviews. The bibliography comprises around 1,900 items, bringing to light a wealth of primary materials. Written for mathematicians, logicians, historians, and philosophers--especially those interested in the historical interaction between these disciplines--this authoritative account tells an important story from its most neglected point of view. Whitehead and Russell hoped to show that (much of) mathematics was expressible within their logic; they failed in various ways, but no definitive alternative position emerged then or since.

An original result about Hilbert Positive Propositional Calculus introduced in [11] is proven. That is, it is shown that the pseudo-canonical formulae of that calculus (and hence also the canonical ones, see [17]) are a subset of the classical tautologies.

This article analyzes the two wise girls puzzle, which is a simpler variant of the so-called three wise men puzzle, with some proof-theoretic tools. We formulate the puzzle in an epistemic logic. Our chief assumption is that the reasoning ability of each player of the puzzle is equivalent to what is described by the epistemic logic. We will interpret the behaviors of the players in the puzzle in terms of unprovability of certain statements. The proof-theoretic tools we employ are consequences of a meta-theorem, known as the cut elimination theorem.

The propositionalμ-calculus can be divided into two categories, global model checking algorithm and local model checking algorithm. Both of them aim at reducing time complexity and space complexity effectively. This paper analyzes the computing process of alternating fixpoint nested in detail and designsan efficient local model checking algorithm based on the propositional μ-calculus by a group of partial ordered relation, and its time complexity is O(d2(dn)d/2+2) (d is the depth of fixpoint nesting, n is the maximum of number of nodes), space complexity is O(d(dn)d/2). As far as we know, up till now, the best local model checking algorithm whose index of time complexity is d. In this paper, the index for time complexity of this algorithm is reduced from d to d/2. It is more efficient than algorithms of previous research.Keywords: model checking, propositional mu-calculus, computational complexity, fixpoint, partitioned dependency graph

In this paper we shall prove that certain subvarieties of the variety of S-algebras (Heyting algebras with successor) has amalgamation. This result together with an appropriate version of Theorem 1 of [L. L. Maksimova, Craig's theorem in superintuitionistic logics and amalgamable varieties of pseudo-boolean algebras, Algebra i Logika, 16(6):643-681, 1977] allows us to show interpolation in the calculus IPC S (n), associated with these varieties. We use that every algebra in any of the varieties of S-algebras studied in this work has a canonical extension, to show completeness of the calculus IPC S (n) with respect to appropriate Kripke models.