Rogowski Lukasz, Sosík Petr
Research Institute of the IT4Innovations Centre of Excellence, Faculty of Philosophy and Science, Silesian University in Opava, 74601 Opava, Czech Republic ; Department of Math and Computer Science, University of Lodz, 90238 Łódź, Poland.
Research Institute of the IT4Innovations Centre of Excellence, Faculty of Philosophy and Science, Silesian University in Opava, 74601 Opava, Czech Republic.
ScientificWorldJournal. 2014;2014:834237. doi: 10.1155/2014/834237. Epub 2014 Jul 3.
We present a DNA-based implementation of reaction system with molecules encoding elements of the propositional logic, that is, propositions and formulas. The protocol can perform inference steps using, for example, modus ponens and modus tollens rules and de Morgan's laws. The set of the implemented operations allows for inference of formulas using the laws of natural deduction. The system can also detect whether a certain proposition a can be deduced from the basic facts and given rules. The whole protocol is fully autonomous; that is, after introducing the initial set of molecules, no human assistance is needed. Only one restriction enzyme is used throughout the inference process. Unlike some other similar implementations, our improved design allows representing simultaneously a fact a and its negation ~a, including special reactions to detect the inconsistency, that is, a simultaneous occurrence of a fact and its negation. An analysis of correctness, completeness, and complexity is included.
我们展示了一种基于DNA的反应系统实现方式，其中分子编码命题逻辑的元素，即命题和公式。该协议可以使用例如肯定前件式、否定后件式规则和德摩根定律来执行推理步骤。所实现的操作集允许使用自然演绎法则来推断公式。该系统还可以检测是否可以从基本事实和给定规则中推导出某个命题a。整个协议是完全自主的；也就是说，在引入初始分子集之后，无需人工协助。在整个推理过程中仅使用一种限制酶。与其他一些类似的实现方式不同，我们改进后的设计允许同时表示事实a及其否定~a，包括用于检测不一致性的特殊反应，即事实与其否定的同时出现。文中还包括了正确性、完整性和复杂性分析。
