Towards a probability theory based on Moisil logic

 In this paper a concept of probability defined on a Lukasiewicz-Moisil algebra is proposed. We take some steps in developing the theory, including an extension theorem and some results related to conditional probabilities on Lukasiewicz-Moisil algebras.     

Some convergence results in Dempster–Shafer theory

 Belief functions and basic probability assignments defined on a finite frame of discernment are given an intuitive extension in this paper. Some convergence results are then given on sets converging from above and below; also, a weakened form of one of the Borel–Cantelli lemmas is given. The paper concludes with a theorem on the Dempster–Shafer random variable.     

针对教学场景的ZFC集合论Coq形式化

离散数学是计算机类专业的基础课程之一,命题逻辑、一阶逻辑与公理集合论是其重要组成部分.教学实践表明,初学者准确理解语法、语义、推理系统等抽象概念是有一定难度的.近年来,已有一些学者开始在教学中引入交互式定理证明工具,以帮助学生构造形式化证明,更透彻地理解逻辑系统.然而,现有的定理证明器有较高上手门槛,直接使用会增加学生的学习负担.鉴于此,在Coq中开发了针对教学场景的ZFC公理集合论证明器.首先,形式化了一阶逻辑推理系统和ZFC公理集合论;之后,开发了数条自动化推理规则证明策略.学生可以在与教科书风格相同的简洁证明环境中使用自动化证明策略完成定理的形式化证明.该工具被用在了大一新生离散数学课程的教学中,没有定理证明经验的学生使用该工具可以快速完成数学归纳法和皮亚诺算术系统等定理的形式化证明,验证了该工具的实际效果.     

A Skeptic's Approach to Combining HOL and Maple

We contrast theorem provers and computer algebra systems, pointing out the advantages and disadvantages of each, and suggest a simple way to achieve a synthesis of some of the best features of both. Our method is based on the systematic separation of search for a solution and checking the solution, using a physical connection between systems. We describe the separation of proof search and checking in some detail, relating it to proof planning and to the complexity class NP, and discuss different ways of exploiting a physical link between systems. Finally, the method is illustrated by some concrete examples of computer algebra results proved formally in the HOL theorem prover with the aid of Maple.     

T-Resolution: Refinements and Model Elimination

T-resolution is a binary rule, proposed by Policriti and Schwartz in 1995 for theorem proving in first-order theories (T-theorem proving) that can be seen – at least at the ground level – as a variant of Stickel's theory resolution. In this paper we consider refinements of this rule as well as the model elimination variant of it. After a general discussion concerning our viewpoint on theorem proving in first-order theories and a brief comparison with theory resolution, the power and generality of T-resolution are emphasized by introducing suitable linear and ordered refinements, uniformly and in strict analogy with the standard resolution approach. Then a model elimination variant of T-resolution is introduced and proved to be sound and complete; some experimental results are also reported. In the last part of the paper we present two applications of T-resolution: to constraint logic programming and to modal logic.     

Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover

A few schema theorems for genetic programming (GP) have been proposed in the literature in the last few years. Since they consider schema survival and disruption only, they can only provide a lower bound for the expected value of the number of instances of a given schema at the next generation rather than an exact value. This paper presents theoretical results for GP with one-point crossover which overcome this problem. First, we give an exact formulation for the expected number of instances of a schema at the next generation in terms of microscopic quantities. Due to this formulation we are then able to provide an improved version of an earlier GP schema theorem in which some (but not all) schema creation events are accounted for. Then, we extend this result to obtain an exact formulation in terms of macroscopic quantities which makes all the mechanisms of schema creation explicit. This theorem allows the exact formulation of the notion of effective fitness in GP and opens the way to future work on GP convergence, population sizing, operator biases, and bloat, to mention only some of the possibilities.     

On two generalisations of the final value theorem: scientific relevance,first applications,and physical foundations

The present work considers two published generalisations of the Laplace-transform final value theorem (FVT) and some recently appeared applications of one of these generalisations to the fields of physical stochastic processes and Internet queueing. Physical sense of the irrational time functions, involved in the other generalisation, is one of the points of concern. The work strongly extends the conceptual frame of the references and outlines some new research directions for applications of the generalised theorem.     

Regularity of null-additive fuzzy measure on metric spaces

In this paper, we investigate the regularity of null-additive fuzzy measures on metric spaces and show that Lusin's theorem on fuzzy measure space remains valid for those fuzzy measures with null-additivity. Egoroff's theorem for fuzzy measures on metric spaces is presented. These are generalizations and improvements of the previous results obtained by others.     

On the multiple values and uniqueness of meromorphic functions on annuli

The purpose of this article is to deal with the multiple values and uniqueness of meromorphic functions on annuli. We prove a general theorem on the multiple values and uniqueness of meromorphic functions on annuli, from which an analog of Nevanlinna’s famous five-value theorem is proposed.     

An experiment with the Boyer-Moore theorem prover: A proof of Wilson's theorem

This paper describes the use of the Boyer-Moore theorem prover in mechanically generating a proof of Wilson's theorem: for any prime p, (p-1)! and p-1 are congruent modulo p. The input to the theorem prover consists of a sequence of three function definitions and forty-two propositions to be proved. The proofs generated by the system are based on a library of lemmas relating to list manipulation and number theory, including Fermat's theorem.     

The fixed point theory of unbounded non-determinism

This paper presents a fixed point theorem for the infinite traces model of CSP. Unlike any other model of CSP, there is no complete partial order over the infinite traces model whose fixed point theory agrees with the operational semantics (A. W. Roscoe, Oxford University Computing Laboratory Technical Monograph PRG-67, 1988). This arises from the introduction of unbounded non-determinism. However, the subset of pre-deterministic processes, that is those which describe the behaviour of a process on some run of its implementation, do form a subset for which the usual order is complete. By requiring that each CSP operator has a monotonic implementation which preserves pre-determinism, it is possible to show that all CSP operators have a least fixed point. In effect, it is the requirement that all operators have a methodical implementation.The author carried out the research for this paper on the Espirit Genesis project at the Programming Research Group, Oxford University.     

基于事件逻辑的改进Needham-Schroeder协议安全性证明

安全协议是现代网络安全的基础,密码协议的安全性证明是一个挑战性的问题。事件逻辑是一种描述分布式系统中状态迁移的形式化方法,用于刻画安全协议的形式化描述,是定理证明的基础。用事件序语言、事件类和一个表示随机数、密钥、签名和密文的原子类,给出身份认证协议可以被形式化定义和强认证性证明理论。利用该理论对增加时间戳的Needham-Schroeder协议安全性进行证明,证明改进的Needham-Schroeder协议是安全的。此理论适用于类似复杂协议形式化分析与验证。     

A development of possibility theory

It is proposed to use a model of experiment with two measures (of possibility and necessity) to describe fuzzy events. A theorem on the continuation of measure to a Boolean is proved. The basic dual properties of measures are considered. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 115–123, November–December 2007.     

A note on the conditional probability on product MV algebras

 A conditional probability (state) of an element from a product MV algebra with respect to a product MV valued observable is formulated and a version of the martingale convergence theorem is proved.     

小波神经网络逼近能力及Thau 定理推广

首先提出神经元数目有限的小波神经网络对一大类Ｌｉｐｓｃｈｉｔｚ函数的逼近能力定理;然后对Ｔｈａｕ定理进行推广,得到几个实用性较强的推广定理;最后通过构造一种基于推广Ｔｈａｕ定理的小波神经网络非线性观测器,展示出该逼近定理的应用前景。     

Representing lattices using many-valued relations

This paper provides a representation theorem of lattices using many-valued relations. We show that any many-valued relation can be associated to a unique lattice which is a meet-sublattice of a product of chains. Conversely, to any lattice we can associate a many-valued relation such that its associated lattice is isomorphic to the initial one. Thereby, we obtain a representation theorem of lattices using many-valued relations. Moreover, since several many-valued relations might have the same associated lattice, we give a characterization of the minimal many-valued relation that can be associated to a lattice. We then sketch a polynomial time algorithm which computes such a minimal relation from either a lattice or an arbitrary relation. This representation presents several advantages: it is smaller than the usual binary representation; all known reconstruction algorithms working on binary relation can be used without loss of efficiency; it can be used by existing data mining processes.     

Logical foundations for representing object-oriented systems

Abstract

Object-oriented programming languages are designed for computing or simulating the behaviour of interacting objects, but their encapsulated contexts and procedural methods are not well suited to non-procedural techniques in theorem provers, optimizers, and automated design and analysis tools. Logic is the non-procedural system par excellence, but the predicate calculus notation for logic is awkward for representing and reasoning about encapsulated contexts. Conceptual graphs are a graphic system of logic that is better suited to O-O systems. First, they explicitly represent the contexts that are ignored or obscured in predicate calculus. Second, Peirce's rules of inference for reasoning with graphs are explicitly formulated in terms of contexts and the conditions for importing and exporting information from contexts. This article describes the context mechanisms of conceptual graphs, the rules of inference for reasoning with the graphs, and their use as a design language for object-oriented systems.     

D-homomorphisms and atomic σ-complete boolean D-posets

We study observables as σ-D-homomorphisms defined on Boolean D-posets of subsets into a Boolean D-poset. We show that given an atomic σ-complete Boolean D-poset ? with the countable set of atoms there exist a σ-complete Boolean D-poset of subsets ? and a σ-D-homomorphism h from ? onto ?, more precisely we can choose ? = ?(?), which gives an analogy of the Loomis–Sikorski representation theorem for Boolean σ-algebras. We show also that any atomic σ-complete Boolean D-poset with the countable set of atoms is the range of a σ-homomorphism defined on a σ-complete Boolean D-poset of fuzzy sets which gives another type of the Loomis–Sikorski theorem.     

Coq Formalization of ZFC Set Theory for Teaching Scenarios

Discrete mathematics is a foundation course for computer-related majors, and propositional logic, first-order logic, and the axiomatic set theory are important parts of this course. Teaching practice shows that beginners find it difficult to accurately understand abstract concepts, such as syntax, semantics, and reasoning system. In recent years, some scholars have begun introducing interactive theorem provers into teaching to help students construct formal proofs so that they can understand logic systems more thoroughly. However, directly employing the existing theorem provers will increase students'' learning burden since these tools have a high threshold for getting started with them. To address this problem, we develop a prover for the Zermelo-Fraenkel set theory with the axiom of Choice (ZFC) in Coq for teaching scenarios. Specifically, the first-order logical reasoning system and the axiomatic set theory ZFC are formalized, and several automated proof tactics specific to reasoning rules are then developed. Students can utilize these automated proof tactics to construct formal proofs of theorems in a textbook-style concise proving environment. This tool has been introduced into the teaching of the course of discrete mathematics for freshmen. Students with no prior theorem-proving experience can quickly construct formal proofs of theorems including mathematical induction and Peano arithmetic with this tool, which verifies the practical effectiveness of this tool.