The tree-based data structure of -tree for propositional formulas is introduced in an improved and optimised form. The -trees allow a compact representation for negation normal forms as well as for a number of reduction strategies in order to consider only those occurrences of literals which are relevant for the satisfiability of the input formula. These reduction strategies are divided into two subsets (meaning- and satisfiability-preserving transformations) and can be used to decrease the size of a negation normal form (...) A at (at most) quadratic cost. The reduction strategies are aimed at decreasing the number of required branchings and, therefore, these strategies allow to limit the size of the search space for the SAT problem. (shrink)

dialectical frameworks constitute a recent and powerful generalisation of Dung's argumentation frameworks, where the relationship between the arguments can be specified via Boolean formulas. Recent results have shown that this enhancement comes with the price of higher complexity compared to AFs. In fact, acceptance problems in the world of ADFs can be hard even for the third level of the polynomial hierarchy. In order to implement reasoning problems on ADFs, systems for quantified Boolean formulas thus are (...) suitable engines to be employed. In this paper we give complexity sensitive QBF encodings of ADF problems generalising recent work on QBFs for AF labellings. Our encodings provide a uniform and modular way of translating reasoning in ADFs to QBFs, that can be used as the basis for novel systems for ADF reasoning. (shrink)

Originating from work in operations research the cutting plane refutation systemCP is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial sizeCP proofs are given for the undirecteds-t connectivity principle. The subsystemsCP q ofCP, forq≥2, are shown to be polynomially equivalent toCP, thus answering problem 19 from the list of open problems of [8]. We present a normal form (...) theorem forCP 2-proofs and thereby for arbitraryCP-proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extensionCPLE +, introduced in [9] and there shown top-simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem. (shrink)

We present some algebraic tools useful to the study of the expressive power of bounded formulas in second-order arithmetic (alternatively, second-order formulas in finite models). The techniques presented here come from Boolean circuit complexity and are adapted to the context of arithmetic. The purpose of this article is to expose them to a public with interests ranging from arithmetic to finite model theory. Our exposition is self-contained.

Gaifman's normal form theorem showed that every first-order sentence of quantifier rank n is equivalent to a Boolean combination of “scattered local sentences”, where the local neighborhoods have radius at most 7n−1. This bound was improved by Lifsches and Shelah to 3×4n−1. We use Ehrenfeucht–Fraïssé type games with a “shrinking horizon” to get a spectrum of normal form theorems of the Gaifman type, depending on the rate of shrinking. This spectrum includes the result of Lifsches and Shelah, with a (...) more easily understood proof and with the bound on the radius improved to 4n−1. We also obtain bounds for a normal form theorem of Schwentick and Barthelmann. (shrink)

How can we find any satisfying assignment for a Boolean formula that has many satisfying assignments? There exists an obvious randomized algorithm for solving this problem: one can just pick an assignment at random and check the truth value of the formula for this assignment, this is iterated until a satisfying assignment occurs. Does there exist a polynomial-time deterministic algorithm that solves the same problem? This paper presents such an algorithm and shows that its worst-case running time is linear (...) when input formulas are in k-CNF and a fraction of satisfying assignments is greater than a constant. This algorithm is almost the same as the algorithm proposed by Monien and Speckenmeyer in the early 1980s for less than 2n steps 3-SAT decision.Another result of this paper is that if a formula in k-CNF has many satisfying assignments, then there exists a short satisfying assignment, i.e. an assignment of truth values to a small number of variables. The proposed algorithm yields just such a short satisfying assignment. We also show that there exist formulas in general CNF having many satisfying assignments, that have no short satisfying assignments. (shrink)

The logical calculus for SAT are not valid for MaxSAT and MinSAT because they preserve satisfiability but not the number of unsatisfied clauses. To overcome this drawback, a MaxSAT resolution rule preserving the number of unsatisfied clauses was defined in the literature. This rule is complete for MaxSAT when it is applied following a certain strategy. In this paper we first prove that the MaxSAT resolution rule also provides a complete calculus for MinSAT if it is applied following the strategy (...) proposed here. We then describe an exact variable elimination algorithm for MinSAT based on that rule. Finally, we show how the results for Boolean MinSAT can be extended to solve the MinSAT problem of the multiple-valued clausal forms known as signed conjunctive normal form formulas. (shrink)

The language of standard propositional modal logic has one operator (? or ?), that can be thought of as being determined by the quantifiers ? or ?, respectively: for example, a formula of the form ?F is true at a point s just in case all the immediate successors of s verify F.This paper uses a propositional modal language with one operator determined by a generalized quantifier to discuss a simple connection between standard invariance conditions on modal formulas and (...) generalized quantifiers: the combined generalized quantifier conditions of conservativity and extension correspond to the modal condition of invariance under generated submodels, and the modal condition of invariance under bisimulations corresponds to the generalized quantifier being a Boolean combination of ? and ? (shrink)

A fundamental problem in game theory is the possibility of reaching equilibrium outcomes with undesirable properties, e.g., inefficiency. The economics literature abounds with models that attempt to modify games in order to avoid such undesirable properties, for example through the use of subsidies and taxation, or by allowing players to undergo a bargaining phase before their decision. In this paper, we consider the effect of such transformations in Boolean games with costs, where players control propositional variables that they can (...) set to true or false, and are primarily motivated to seek the satisfaction of some goal formula, while secondarily motivated to minimise the costs of their actions. We adopt preparation sets as our basic solution concept. A preparation set is a set of outcomes that contains for every player at least one best response to every outcome in the set. Prep sets are well-suited to the analysis of Boolean games, because we can naturally represent prep sets as propositional formulas, which in turn allows us to refer to prep formulas. The preference structure of Boolean games with costs makes it possible to distinguish between hard and soft prep sets. The hard prep sets of a game are sets of valuations that would be prep sets in that game no matter what the cost function of the game was. The properties defined by hard prep sets typically relate to goal-seeking behaviour, and as such these properties cannot be eliminated from games by, for example, taxation or subsidies. In contrast, soft prep sets can be eliminated by an appropriate system of incentives. Besides considering what can happen in a game by unrestricted manipulation of players’ cost function, we also investigate several mechanisms that allow groups of players to form coalitions and eliminate undesirable outcomes from the game, even when taxes or subsidies are not a possibility. (shrink)

We consider the theory Thprin of Boolean algebras with a principal ideal, the theory Thmax of Boolean algebras with a maximal ideal, the theory Thac of atomic Boolean algebras with an ideal where the supremum of the ideal exists, and the theory Thsa of atomless Boolean algebras with an ideal where the supremum of the ideal exists. First, we find elementary invariants for Thprin and Thsa. If T is a theory in a first order language and (...) α is a linear order with least element, then we let Sentalg be the Lindenbaum-Tarski algebra with respect to T, and we let intalg be the interval algebra of α. Using rank diagrams, we show that Sentalg ⋍ intalg, Sentalg ⋍ intalg ⋍ Sentalg, and Sentalg ⋍ intalg. For Thmax and Thac we use Ershov's elementary invariants of these theories. We also show that the algebra of formulas of the theory Tx of Boolean algebras with finitely many ideals is atomic. (shrink)

We consider logical expressions built on the single binary connector of implication and a finite number of literals . We prove that asymptotically, when the number of variables becomes large, all tautologies have the following simple structure: either a premise equal to the goal, or two premises which are opposite literals.

Ancient Greek mathematics developed the original feature of being deductive mathematics. This article attempts to give a explanation f or this achievement. The focus is on the use of a fixed system of linguistic formulae in Greek mathematical texts. It is shown that the structure of this system was especially adapted for the easy computation of operations of substitution on such formulae, that is, of replacing one element in a fixed formula by another, and it is further argued that such (...) operations of substitution were the main logical tool required by Greek mathematical deduction. The conclusion explains why, assuming the validity of the description above, this historical level is the best explanatory level for the phenomenon of Greek mathematical deduction. (shrink)

In terms of validity in Kripke frames, a modal formula expresses a universal monadic second-order condition. Those modal formulae which are equivalent to first-order conditions are called elementary. Modal formulae which have a certain persistence property which implies their validity in all canonical frames of modal logics axiomatized with them, and therefore their completeness, are called canonical. This is a survey of a recent and ongoing study of the class of elementary and canonical modal formulae. We summarize main ideas and (...) results, and outline further research perspectives. (shrink)

We generalize and extend the class of Sahlqvist formulae in arbitrary polyadic modal languages, to the class of so called inductive formulae. To introduce them we use a representation of modal polyadic languages in a combinatorial style and thus, in particular, develop what we believe to be a better syntactic approach to elementary canonical formulae altogether. By generalizing the method of minimal valuations à la Sahlqvist–van Benthem and the topological approach of Sambin and Vaccaro we prove that all inductive formulae (...) are elementary canonical and thus extend Sahlqvist’s theorem over them. In particular, we give a simple example of an inductive formula which is not frame-equivalent to any Sahlqvist formula. Then, after a deeper analysis of the inductive formulae as set-theoretic operators in descriptive and Kripke frames, we establish a somewhat stronger model-theoretic characterization of these formulae in terms of a suitable equivalence to syntactically simpler formulae in the extension of the language with reversive modalities. Lastly, we study and characterize the elementary canonical formulae in reversive languages with nominals, where the relevant notion of persistence is with respect to discrete frames. (shrink)

Ritualistic formulae and acts pervade the political, legal, societal and religious life of the ancient world. In many instances there are striking similarities between the formulae of the Greco-Roman world and those of the Near East. Often illumination exists from one to the other. Here I wish to notice a few passages in Greek drama where I think such illumination is possible.

In terms of validity in Kripke frames, a modal formula expresses a universal monadic second-order condition. Those modal formulae which are equivalent to first-order conditions are called \emph{elementary}. Modal formulae which have a certain persistence property which implies their validity in all canonical frames of modal logics axiomatized with them, and therefore their completeness, are called \emph{canonical}. This is a survey of a recent and ongoing study of the class of elementary and canonical modal formulae. We summarize main ideas and (...) results, and outline further research perspectives. (shrink)

In this paper, we present a way to translate the metainferences of a mixed metainferential system into formulae of an extended-language system, called its associated σ-system. To do this, the σ-system will contain new operators (one for each standard), called the σ operators, which represent the notions of "belonging to a (given) standard". We first prove, in a model-theoretic way, that these translations preserve (in)validity. That is, that a metainference is valid in the base system if and only if its (...) translation is a tautology of its corresponding σ-system. We then use these results to obtain other key advantages. Most interestingly, we provide a recipe for building unlabeled sequent calculi for σ-systems. We then exemplify this with a σ-system useful for logics of the ST family, and prove soundness and completeness for it, which indirectly gives us a calculus for the metainferences of all those mixed systems. Finally, we respond to some possible objections and show how our σ-framework can shed light on the “obeying” discussion within mixed metainferential contexts. (shrink)

Isomorphism between formulae is defined with respect to categories formalizing equality of deductions in classical propositional logic and in the multiplicative fragment of classical linear propositional logic caught by proof nets. This equality is motivated by generality of deductions. Characterizations are given for pairs of isomorphic formulae, which lead to decision procedures for this isomorphism.

This article suggests a novel way to advance a current debate in the philosophy of mathematics. The debate concerns the role of diagrams and visual reasoning in proofs—which I take to concern the criteria of legitimate representation of mathematical thought. Drawing on the so-called ‘maverick’ approach to philosophy of mathematics, I turn to mathematical practice itself to adjudicate in this debate, and in particular to category theory, because there (a) diagrams obviously play a major role, and (b) category theory itself (...) addresses questions of representation and information preservation over mappings. We obtain a mathematical answer to a philosophical question: a good mathematical representation can be characterized as a category theoretic natural transformation. (shrink)

The most recent work dealing expressly with adoption in Greece is Wentzel's article in Hermes lxv , 167–76, ‘Studien über die Adoption in Griechen-land’. Her article ranges widely over the whole subject and includes a list of all the inscriptions known to her which refer to adoptions, as well as a list of the adoptive formulae found in these inscriptions. In the present article I shall deal more fully with these formulae.

This paper is about several little-known Latin funerary formulae of some interest. It is also intended as an addition to the growing literature on what are now called in English ‘support verbs’, with special focus on facio.

This article is a study of formulaic passages in the Sanskrit Avadanasataka. Alongside a preliminary discussion of work on oral studies within Buddhism, and some recourse to wider oral studies on Indian texts, the focus of this article is a two-part study of formulae and constituents of formulae. The first part of the article details formulaic sections from the Avadanasataka, from short formulae about wealthy merchants to lengthy counterparts that detail the consequences of a Buddha's smile. The second part looks (...) in detail at constituents of the formulaic passages. The passages are constructed around semantic lists, which either constitute the whole formulaic phrase or passages, or can be identified as the building blocks for the passages. To my knowledge this is the first study of semantic list-based formulae in a Sanskrit text. (shrink)

The paper is intended to provide a full-scale defence of the infamous Barcan Formulae. Not only do I put forth some arguments, both semantic and metaphysical, against recent criticism; I also take pains at supplying some rationale in favour of the formal semantics underlying the Formulae, namely Possibilist quantification. Such a task is carried out through an argument for Compositional Nihilism, according to which nothing but mereological simples ever exists, and consequently through an informal sketch of the metaphysics of possible (...) worlds grounded upon Compositional Nihilism. The paper closes by surveying the main reasons why the account championed here isn’t defective with respect to other possibilist accounts of existence and modality presently on stage. (shrink)

The Lorentz-formulae are deduced from three factual statements the physical meaning of which is explained in terms of operations with clocks, light-signals and measuring rods. These statements are: (1) The time-length of a process is invariant. (2) The velocity of light is the same in all inertial systems. (3) The velocity of light is independent of the source. It is also shown that these statements can be deduced from the Lorentz-formulae. They are the physical content of the latter. The principle (...) of relativity and the light-principle together, however, contain more physical meaning than the Lorentz-formulae. Operational definitions are given for all relevant concepts. (shrink)

Another sort of thing resembles works of art in combining existence, message and a kind of presentation, namely, symbols. Hence it seems reasonable to take works of art as symbols. And yet works of art are a special kind of symbol, because in them presentation has a double function. All symbols directly present their meaning; indeed the essential function of symbols is to serve as vehicles for conveying us into the immediate presence of what they mean. But works of art (...) have a second presentational mode of functioning. They also present themselves; and this is true both for abstract and for representational art. (shrink)

Although it is not younger than other areas of non-classical logic, paraconsistent logic has received full recognition only in recent years, largely due to the work of, among others, Newton da Costa, Graham Priest, Diderik Batens, and Jerzy Perzanowski. A logical system Λ is paraconsistent if there is a set of Λ-formulas Δ ∪ {A} such that in Λ one may derive from Δ both A and its negation, and the deductive closure of Δ with respect to Λ is (...) different from the set of all formulas. If from Δ one may derive a formula and its negation, Δ is said to be syntactically inconsistent. But is every syntactically inconsistent set of formulas contradictory? In classical logic and many non-classical logics, every syntactically inconsistent set is unsatisfiable, that is, semantically inconsistent. If contradictoriness means semantical inconsistency, there is, up to logical equivalence, only one contradiction. In paraconsistent logics, there are usually many non-equivalent formulas representing the semantically unique contradiction in a non-paraconsistent logic. So when is a formula the contradiction of another formula, and, moreover, how does the notion of contradiction relate to the notions of contrariety and negation? (shrink)

Related Works: Part I: Michael Zakharyaschev. Canonical Formulas for $K4$. Part I: Basic Results. J. Symbolic Logic, Volume 57, Issue 4 , 1377--1402. Project Euclid: euclid.jsl/1183744119 Part III: Michael Zakharyaschev. Canonical Formulas for K4. Part III: The Finite Model Property. J. Symbolic Logic, Volume 62, Issue 3 , 950--975. Project Euclid: euclid.jsl/1183745306.

Kant's formulae ought to effectively produce the same result when applied to the moral validity of any particular maxim; further, no valid maxim produces contradictory results when applied against Kant's Universal Law and Humanity formulae. Where one uses all formulae in the assessment of a maxim, one gains a more complete understanding of the moral law, thereby bridging principles of reason with intuition within the agent who has undertaken to evaluate the morality of a particular action. These formulae command without (...) regard to any particular interests, but are instead unconditional; further, these formulae effectively limit choice of action and therefore give rise to duty. Kant implies that the structure of all maxims requires different formulae of the same moral law, i.e., all maxims have a ‘form’ and a ‘matter’, which prompt reconfiguring of the categorical imperative into different formulae in order to test the morality of a maxim. (shrink)

Satisfaction or contentment is deficient in our intelligent world, for entropy is at its prodigality accompanying the egoistic human mind. The lesser beings are content with what is provided, seem more beholden of being created, rather than the selfish unsatisfied human, whose desire to gain has no limit leaving the body unsatisfied to deteriorate thy own soul and its existence and of the others. The cause of entropy is human intelligence and the falsified superiority of human consciousness that leaves the (...) body unsatisfied and the soul to writhe; for it creates a resistance in the flow of consciousness that makes the human loose its value of life and all that resides within. Egoism enhances superiority promotes an indestructible feeling; denies consciousness that flows within and across the system; a loss of revere to the cosmic bridge of consciousness that links the body, mind and soul to the universe. Satisfaction can be gotten when one clearly differentiates the subjectivity from the objectivity of consciousness; for the subjectivity of consciousness cannot be taken for granted over its trailing objectivity that ceaselessly deceives. (shrink)

Related Works: Part I: Michael Zakharyaschev. Canonical Formulas for $K4$. Part I: Basic Results. J. Symbolic Logic, Volume 57, Issue 4 , 1377--1402. Project Euclid: euclid.jsl/1183744119 Part II: Michael Zakharyaschev. Canonical Formulas for K4. Part II: Cofinal Subframe Logics. J. Symbolic Logic, Volume 61, Issue 2 , 421--449. Project Euclid: euclid.jsl/1183745008.

We present a sound and complete tableau calculus for the class of regular grammar logics. Our tableau rules use a special feature called automaton-labelled formulae, which are similar to formulae of automaton propositional dynamic logic. Our calculus is cut-free and has the analytic superformula property so it gives a decision procedure. We show that the known EXPTIME upper bound for regular grammar logics can be obtained using our tableau calculus. We also give an effective Craig interpolation lemma for regular grammar (...) logics using our calculus. (shrink)

There are several areas in applied logic where deletion from databases is involved in one way or another:Belief contraction Triggers of the form ‘If condition then remove A’, which are extensively used in database management systemsResource considerations as in relevance and linear logics, where addition or removal of resource can affect provabilityFree logic and the like, where existence and non-existence of individuals affects quantification.All of these areas have certain logical difficulties relating to the removal of elements. This paper points out (...) the difficulties and offers a comprehensive logical model. (shrink)

Periodic orbit quantization requires an analytic continuation of non-convergent semiclassical trace formulae. We propose two different methods for semiclassical quantization. The first method is based upon the harmonic inversion of semiclassical recurrence functions. A band-limited periodic orbit signal is obtained by analytical frequency windowing of the periodic orbit sum. The frequencies of the periodic orbit signal are the semiclassical eigenvalues, and are determined by either linear predictor, Padé approximant, or signal diagonalization. The second method is based upon the direct application (...) of the Padé approximant to the periodic orbit sum. The Padé approximant allows the resummation of the, typically exponentially, divergent periodic orbit terms. Both techniques do not depend on the existence of a symbolic dynamics, and can be applied to bound as well as to open systems. Numerical results are presented for two different systems with chaotic and regular classical dynamics, viz. the three-disk scattering system and the circle billiard. (shrink)

It is and has been widely assumed, e.g., in Hintikka and Hintikka, that the logical theory available from Wittgenstein’s Tractatus Logico-Philosophicus affords a foundation for the conventional logic represented in standard formulations of classical propositional, first-order predicate, and perhaps higher-order formal systems. The present article is a detailed attempt at a mathematical demonstration, or as much demonstration as the sources will allow, that this assumption is false by contemporary lights and according to a preferred account of argument validity. When Wittgenstein’s (...) description of the forms of propositions or Sätze in the 5-numbered remarks and Remark 6 is given a close reconstruction, one sees that no Tractarian proposition is logically equivalent to a simple universally or existentially quantified formula of first-order predicate logic. Therefore, although Wittgenstein employs the sign ∀—or, in his notation—occasionally in explanations and illustrations, e.g., 4.0411 and 5.1311, when it comes to logic, the sign ∀ should receive in Tractatus a semantical treatment that is nonstandard. En route to that result, we show that the hierarchy of variables–and, hence, of propositions–defined at 5.501 incorporates the expressive power of finitary classical propositional logic. Also, when constructed over a first-order language for arithmetic, formulae corresponding to the specification of 5.501 pick out all and only arithmetic sets of numbers. Consequently, Wittgenstein’s hierarchy of iterated N-propositions–as described in vide Remark 6–does not collapse: at any level k, one finds propositions at k + 1 or above that are not logically equivalent to any proposition formed at k or below. (shrink)

We propose a generalization of Sahlqvist formulas to polyadic modal languages by representing such languages in a combinatorial PDL style and thus, in particular, developing what we believe to be the right syntactic approach to Sahlqvist formulas at all. The class of polyadic Sahlqvist formulas PSF defined here expands essentially the so far known one. We prove first-order definability and canonicity for the class PSF.

We present a search engine for mathematical formulae. The MathWebSearch system harvests the web for content representations (currently MathML and OpenMath) of formulae and indexes them with substitution tree indexing, a technique originally developed for accessing intermediate results in automated theorem provers. For querying, we present a generic language extension approach that allows constructing queries by minimally annotating existing representations. First experiments show that this architecture results in a scalable application.