logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 4: 042101(2018) https://doi.org/10.1007/s11432-017-9199-8

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

More info
  • ReceivedFeb 21, 2017
  • AcceptedJun 19, 2017
  • PublishedFeb 6, 2018

Abstract

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 $R$-calculus 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.


References

[1] Popper K. The Logic of Scientific Discovery. New York: Routledge, 1959. Google Scholar

[2] Popper K. Conjectures and Refutations. London: Routledge, 1963. Google Scholar

[3] Gärdenfors P, Rott H. Belief revision. In: Handbook of Logic in Artificial Intelligence and Logic Programming: Vol.4: Epistemic and Temporal Reasoning. Oxford: Oxford Science Publications, 1995. 35--132. Google Scholar

[4] Alchourrón C E, G?rdenfors P, Makinson D. On the logic of theory change: Partial meet contraction and revision functions. J symb log, 1985, 50: 510-530 CrossRef Google Scholar

[5] Bochman A. A foundational theory of belief and belief change. Artificial Intelligence, 1999, 108: 309-352 CrossRef Google Scholar

[6] Fermé E, Hansson S O. AGM 25 Years. J Philos Logic, 2011, 40: 295-331 CrossRef Google Scholar

[7] Friedman N, Halpern J Y. Belief revision: a critique. J Logic Language Inf, 1999, 8: 401-420 CrossRef Google Scholar

[8] Darwiche A, Pearl J. On the logic of iterated belief revision. Artificial Intelligence, 1997, 89: 1-29 CrossRef Google Scholar

[9] Li W. R-Calculus: An Inference System for Belief Revision. Comput J, 2007, 50: 378-390 CrossRef Google Scholar

[10] Friedberg R M. TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944). Proc Natl Acad Sci USA, 1957, 43: 236-238 CrossRef Google Scholar

[11] Muchnik A A. On the separability of recursively enumerable sets (in Russian). Dokl Akad Nauk SSSR, 1956, 109: 29--32. Google Scholar

[12] Rogers H. Theory of Recursive Functions and Effective Computability. Cambridge: the MIT Press, 1987. Google Scholar

[13] Soare R I. Recursively Enumerable Sets and Degrees, a Study of Computable Functions and Computably Generated Sets. Berlin: Springer-Verlag, 1987. Google Scholar

[14] Takeuti G. Proof theory. In: Handbook of Mathematical Logic. Amsterdam: North-Holland. 1987. Google Scholar

[15] Li W, Sui Y F. The R-calculus and the finite injury priority method. In: Proceedings of IEEE International Conference on Robotics & Automation, Singapore, 2017. 2329--2335. Google Scholar

[16] Asano T. Approximation algorithms for MAX SAT: Yannakakis vs. Goemans-Williamson. In: Proceedings of the 5th Israel Symposium on Theory of Computing and Systems, Ramat-Gan, 1997. 24--37. Google Scholar

[17] Battiti R, Protasi M. Approximate algorithms and heuristics for MAXSAT. In: Handbook of Combinatorial Optimization. Boston: Springer, 1998. 77--148. Google Scholar

[18] Hochbaum D S. Approximation Algorithms for NP-Hard Problems. Boston: PWS Publishing Company, 1997. Google Scholar

[19] Katsuno H, Mendelzon A O. Propositional knowledge base revision and minimal change. Artificial Intelligence, 1991, 52: 263-294 CrossRef Google Scholar

[20] Li W, Sui Y F, Sun M Y. The sound and complete R-calculus for revising propositional theories. Sci China Inf Sci, 2015, 58: 092101. Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1