Research On Logic Operation And Its Applications In Membrane Computing

Membrane Computing is a new branch of biological computing, inspired by thestructure and function of the live cell membrane of life, and thereby it is able to abstractfrom the calculation model. Membrane Computing can also be known as the P System,the direction of the study was founded in1998by Romanian scientists Gheorghe P un,and it has rapidly developed into a field of science with great potential, and it bringsnew solution ideas to many areas of difficult issues. Due to the large amount of the cellmembranes and the very low energy consumption, the most advantage of this kind ofcomputer system is to implement calculation in a great degree of parallelism, to obtainthe far more than the traditional computer computing capacity. Some studies haveproven that this computing model can solve NP-complete problem in polynomial time.How to implement arithmetical, Boolean and relational operations is primaryproblem in a computing model. So far, there has some certain research results about theimplementation of arithmetical operations in cell-like P system. But Boolean andrelational operations attract rare attention in the researches on membrane computing. Soby studying the elementary logic operation, logic expression evaluation and the Psystem of the applications of logic operation, this paper is able to extend use of the logicoperation P system, and lay a foundation for the biological computing.The following is a brief introduction to the work of completed studied in thispaper:①According to the basic ideas and execution feature of the MembraneComputing, priority rule-based logic operations P system is designed, and it lays afoundation for the realization of the logic expression evaluation in the MembraneComputing.②According to the logic operation P system, a construction algorithm about logicexpression evaluation in the Membrane Computing is designed, and a P system isconstructed for evaluating the logic expression.③Propositional logic satisfiability problem is the known problem in the fields oftheoretical computer science and artificial intelligence, especially about the research ofa Boolean formula in conjunctive normal form (CNF) and formulated as SAT problem.So on the basis of the study mentioned above, the SAT Problem is chosen for theapplication, and two families of P systems are designed and constructed for solving SAT/All-SAT problems, one is a semi-uniform solution, and another is a uniform Psystem.④Achieved to simulation of the P system for evaluating the logic expression andsolving the SAT/All-SAT problem by using of computer and it verifies correctness.Results of this paper are to further enrich the theory that logic operations andexpression evaluation in the Membrane Computing, the SAT problem is chosen to bethe application, and it extends application of logic P System, so it is able to become thereferences that solve the other problems.