A computational framework for Karl Popper's logic of scientific discovery  

作　　者：Wei LI Yuefei SUI 

机构地区：[1]State Key Laboratory of Software Development Environment, Beihang University [2]Key Laboratory of Intelligent Information Processing, Institute of Computing Technology,Chinese Academy of Sciences

出　　处：《Science China(Information Sciences)》2018年第4期91-100,共10页中国科学（信息科学）（英文版）

基　　金：supported by National Basic Research Program of China(973 Program)(Grant No.2005CB321901);Open Fund of the State Key Laboratory of Software Development Environment(Grant No.SKLSDE-2010KF-06);Beijing University of Aeronautics and Astronautics

摘　　要：Belief revision is both a philosophical and logical problem. From Popper＇s logic of scientific discovery, we know that revision is ubiquitous in physics and other sciences. The AGM postulates and Rcalculus are approaches from logic, where the R-calculus is a Gentzen-type concrete belief revision operator.Because deduction is undecidable in first-order logic, we apply approximate deduction to derive an R-calculus that is computational and has finite injury. We further develop approximation algorithms for SAT problems to derive a feasible R-calculus based on the relation between deduction and satisfiability. In this manner, we provide a full spectrum of belief revision： from philosophical to feasible revision.Belief revision is both a philosophical and logical problem. From Popper＇s logic of scientific discovery, we know that revision is ubiquitous in physics and other sciences. The AGM postulates and Rcalculus are approaches from logic, where the R-calculus is a Gentzen-type concrete belief revision operator.Because deduction is undecidable in first-order logic, we apply approximate deduction to derive an R-calculus that is computational and has finite injury. We further develop approximation algorithms for SAT problems to derive a feasible R-calculus based on the relation between deduction and satisfiability. In this manner, we provide a full spectrum of belief revision： from philosophical to feasible revision.

关 键 词：belief revision logic of scientific discovery approximate deduction approximation algorithms feasible computation 

分 类 号：B812[哲学宗教—逻辑学]