经典命题逻辑的Boole语义理论

以有限Boole代数作为赋值域建立了经典命题逻辑的一种新的语义理论;证明了命题逻辑公式为重言式当且仅当该命题的每个赋值都等于Boole代数的最大元;在这种新语义理论中提出了公式的B-度实概念,研究了B-真度的基本性质。     

On a sequential model of the algebra of finite-valued logic

We consider basic postulates for an interpretation of the algebra of finite-valued logic in which prepositional variables are interpreted as variables whose values are sequences. We obtain an analytic representation of the operations of two-valued logic for a class of recursive sequences—generalized arithmetic progressions. We exhibit certain generalizations, modifications, and applications of the proposed model.Translated fromMatematicheskie Metody i Fiziko-Mekhanicheskie Polya, Issue 32, 1990, pp. 14–17.     

The logic of π1-conservativity

We show that the modal prepositional logicILM (interpretability logic with Montagna's principle), which has been shown sound and complete as the interpretability logic of Peano arithmetic PA (by Berarducci and Savrukov), is sound and complete as the logic of ₁-conservativity over eachbE ₁-sound axiomatized theory containingI ₁ (PA with induction restricted tobE ₁-formulas). Furthermore, we extend this result to a systemILMR obtained fromILM by adding witness comparisons in the style of Guaspari's and Solovay's logicR (this will be done in a separate continuation of the present paper).     

Local computation in linear logic

This work deals with the exponential fragment of Girard's linear logic ([3]) without the contraction rule, a logical system which has a natural relation with the direct logic ([10], [7]). A new sequent calculus for this logic is presented in order to remove the weakening rule and recover its behavior via a special treatment of the propositional constants, so that the process of cut-elimination can be performed using only “local” reductions. Hence a typed calculus, which admits only local rewriting rules, can be introduced in a natural manner. Its main properties — normalizability and confluence — has been investigated; moreover this calculus has been proved to satisfy a Curry-Howard isomorphism ([6]) with respect to the logical system in question. MSC: 03B40, 03F05.     

Interpolation by a Game

We introduce a notion of a real game (a generalisation of the Karchmer-Wigderson game (cf. [3]) and of real communication complexity, and relate this complexity to the size of monotone real formulas and circuits. We give an exponential lower bound for tree-like monotone protocols (defined in [4, Definition 2.2]) of small real communication complexity solving the monotone communication complexity problem associated with the bipartite perfect matching problem. This work is motivated by a research in interpolation theorems for prepositional logic (by a problem posed in [5, Section 8], in particular). Our main objective is to extend the communication complexity approach of [4, 5] to a wider class of proof systems. In this direction we obtain an effective interpolation in a form of a protocol of small real communication complexity. Together with the above mentioned lower bound for tree-like protocols this yields as a corollary a lower bound on the number of steps for particular semantic derivations of Hall's theorem (these include tree-like cutting planes proofs for which an exponential lower bound was demonstrated in [2]).     

Logics that define their own semantics

The capability of logical systems to express their own satisfaction relation is a key issue in mathematical logic. Our notion of self definability is based on encodings of pairs of the type (structure, formula) into single structures wherein the two components can be clearly distinguished. Hence, the ambiguity between structures and formulas, forming the basis for many classical results, is avoided. We restrict ourselves to countable, regular, logics over finite vocabularies. Our main theorem states that self definability, in this framework, is equivalent to the existence of complete problems under quantifier free reductions. Whereas this holds true for arbitrary structures, we focus on examples from Finite Model Theory. Here, the theorem sheds a new light on nesting hierarchies for certain generalized quantifiers. They can be interpreted as failure of self definability in the according extensions of first order logic. As a further application we study the possibility of the existence of recursive logics for PTIME. We restate a result of Dawar concluding from recursive logics to complete problems. We show that for the model checking Turing machines associated with a recursive logic, it makes no difference whether or not they may use built in clocks. Received: 7 February 1997     

A formalization of Sambins's normalization for GL

Sambin [6] proved the normalization theorem (Hauptsatz) for GL, the modal logic of provability, in a sequent calculus version called by him GLS. His proof does not take into account the concept of reduction, commonly used in normalization proofs. Bellini [1], on the other hand, gave a normalization proof for GL using reductions. Indeed, Sambin's proof is a decision procedure which builds cut-free proofs. In this work we formalize this procedure as a recursive function and prove its recursiveness in an arithmetically formalizable way, concluding that the normalization of GL can be formalized in PA. MSC: 03F05, 03B35, 03B45.     

Harmony in Multiple-Conclusion Natural-Deduction

The paper studies the extension of harmony and stability, major themes in proof-theoretic semantics, from single-conclusion natural-deduction systems to multiple-conclusions natural-deduction, independently of classical logic. An extension of the method of obtaining harmoniously-induced general elimination rules from given introduction rules is suggested, taking into account sub-structurality. Finally, the reductions and expansions of the multiple-conclusions natural-deduction representation of classical logic are formulated.     

Normalizable linear orders and generic computations in finite models

Numerous results about capturing complexity classes of queries by means of logical languages work for ordered structures only, and deal with non-generic, or order-dependent, queries. Recent attempts to improve the situation by characterizing wide classes of finite models where linear order is definable by certain simple means have not been very promising, as certain commonly believed conjectures were recently refuted (Dawar's Conjecture). We take on another approach that has to do with normalization of a given order (rather than with defining a linear order from scratch). To this end, we show that normalizability of linear order is a strictly weaker condition than definability (say, in the least fixpoint logic), and still allows for extending Immerman-Vardi-style results to generic queries. It seems to be the weakest such condition. We then conjecture that linear order is normalizable in the least fixpoint logic for any finitely axiomatizable class of rigid structures. Truth of this conjecture, which is a strengthened version of Stolboushkin's conjecture, would have the same practical implications as Dawar's Conjecture. Finally, we suggest a series of reductions of the two conjectures to specialized classes of graphs, which we believe should simplify further work. Received: 13 July 1996     

基础R0-代数的性质及在L*系统中的应用

研究了王国俊教授建立的模糊命题演算的形式演绎系统L^*和与之在语义上相关的R₀-代数,提出了基础R₀-代数的观点并讨论了其中的一些性质,在将L^*系统中的推演证明转化为相应的R₀-代数中的代数运算方面作了一些尝试,作为它的一个应用,证明了L^*系统中的模糊演绎定理。     

Logic for abstract hoop twist-structures

In this paper, we introduce and study a logic that corresponds to abstract hoop twist-structures and present some results on this logic. We prove the local deductive theorem for this logic and show that this logic is algebraizable with respect to the quasi-variety of abstract hoop twist-structures.     

常微分方程解的存在唯一性定理教学研究

探讨了常微分方程初值问题解的存在唯一性定理教学策略.为便于教学和有利于学生理解并掌握其思想方法,对定理证明过程的表述作了命题化处理,给出了Picard逐步逼近法的应用实例,提出了教学讨论与知识拓展的一些有益内容.     

Logic optimality for multi-objective optimization

Pareto dominance is one of the most basic concepts in multi-objective optimization. However, it is inefficient when the number of objectives is large because in this case it leads to an unmanageable number of Pareto solutions. In order to solve this problem, a new concept of logic dominance is defined by considering the number of improved objectives and the quantity of improvement simultaneously, where probabilistic logic is applied to measure the quantity of improvement. Based on logic dominance, the corresponding logic nondominated solution is defined as a feasible solution which is not dominated by other ones based on this new relationship, and it is proved that each logic nondominated solution is also a Pareto solution. Essentially, logic dominance is an extension of Pareto dominance. Since there are already several extensions for Pareto dominance, some comparisons are given in terms of numerical examples, which indicates that logic dominance is more efficient. As an application of logic dominance, a house choice problem with five objectives is considered.     

Logic and Natural Selection

Is logic, feasibly, a product of natural selection? In this paper we treat this question as dependent upon the prior question of where logic is founded. After excluding other possibilities, we conclude that logic resides in our language, in the shape of inferential rules governing the logical vocabulary of the language. This means that knowledge of (the laws of) logic is inseparable from the possession of the logical constants they govern. In this sense, logic may be seen as a product of natural selection: the emergence of logic requires the development of creatures who can wield structured languages of a specific complexity, and who are capable of putting the languages to use within specific discursive practices.     

Axiomatizing first order consequences in inclusion logic

Inclusion logic is a variant of dependence logic that was shown to have the same expressive power as positive greatest fixed-point logic. Inclusion logic is not axiomatisable in full, but its first order consequences can be axiomatized. In this paper, we provide such an explicit partial axiomatization by introducing a system of natural deduction for inclusion logic that is sound and complete for first order consequences in inclusion logic.     

Characterizing Belnap's Logic via De Morgan's Laws

The aim of this paper is technically to study Belnap's four-valued sentential logic (see [2]). First, we obtain a Gentzen-style axiomatization of this logic that contains no structural rules while all they are still admissible in the Gentzen system what is proved with using some algebraic tools. Further, the mentioned logic is proved to be the least closure operator on the set of {Λ, V, ?}-formulas satisfying Tarski's conditions for classical conjunction and disjunction together with De Morgan's laws for negation. It is also proved that Belnap's logic is the only sentential logic satisfying the above-mentioned conditions together with Anderson-Belnap's Variable-Sharing Property. Finally, we obtain a finite Hilbert-style axiomatization of this logic. As a consequence, we obtain a finite Hilbert-style axiomatization of Priest's logic of paradox (see [12]).     

A topological characterization of consistency of logic theories in propositional logic

The main purpose of this note is to characterize consistency of logic theories in propositional logic by means of topological concept. Based on the concepts of truth degree of formulas and similarity degree between formulas the concept of logic metric space has been proposed by the first author. It is proved in this note that a closed logic theory Γ is consistent if and only if it contains no interior point in the logic metric space. Moreover the relationship between logic closedness and topological closedness of a logic theory Γ is discussed. Finally, the concept of full divergency is also characterized by means of the topological concept of density. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Optimal procedures for the discrete time/cost trade-off problem in project networks

We describe two algorithms, based on dynamic programming logic, for optimally solving the discrete time/cost trade-off problem (DTCTP) in deterministic activity-on-arc networks of the CPM type, where the duration of each activity is a discrete, nonincreasing function of the amount of a single nonrenewable resource committed to it. The first algorithm is based on a procedure proposed by Bein, Kamburowski and Stallmann for finding the minimal number of reductions necessary to transform a general network to a series-parallel network. The second algorithm minimizes the estimated number of possibilities that need to be considered during the solution procedure. Both procedures have been programmed in C and tested on a large set of representative networks to give a good indication of their performance, and indicate the circumstances in which either algorithm performs best.     

Possibilistic nested logic programs and strong equivalence

In this paper, the class of possibilistic nested logic programs is introduced. These possibilistic logic programs allow us to use nested expressions in the bodies and heads of their rules. By considering a possibilistic nested logic program as a possibilistic theory, a construction of a possibilistic logic programing semantics based on answer sets for nested logic programs and the proof theory of possibilistic logic is defined. In order to define a general method for computing the possibilistic answer sets of a possibilistic nested program, the idea of equivalence between possibilistic nested programs is explored. By considering properties of equivalence between possibilistic programs, a process of transforming a possibilistic nested logic program into a possibilistic disjunctive logic program is defined. Given that our approach is an extension of answer set programming, we also explore the concept of strong equivalence between possibilistic nested logic programs. To this end, we introduce the concept of poss SE-models. Therefore, we show that two possibilistic nested logic programs are strong equivalents whenever they have the same poss SE-models.The expressiveness of the possibilistic nested logic programs is illustrated by a scenario from the medical domain. In particular, we exemplify how possibilistic nested logic programs are expressive enough for capturing medical guidelines which are pervaded by vagueness and qualitative information.