Boolean Algebra And Automata Theory Over Boolean Algebra

Boolean algebra is an important mathematical tool used in the field of information science. It contains abundant content and is widely applied.In this thesis, we first compile some utilizable parts of Boolean algebra theory, which are the fundamental objects: the structure of Boolean algebra, the Boolean functions, the Boolean equations, and the Boolean matrices. Then we study the system of fixed-point Boolean equations. Some new results are derived as following:1. We determine the general reproductive solutions of the system of fixed-point Boolean equationsand present the necessary and sufficient conditions for it to have a singular solution [theorem 2.1~2.2].2. We prove that, when .each column of A is orthogonal, the system of fixed-point Boolean equationshas the same set of orthogonal solutions and of orthonormal solutions as the linear Boolean equationThen we reduce the total number of orthonormal solutions of the system of fixed-point Boolean equation AX = X [theorem 2.3~2.4].Automata theory is an important branch of computer science theory. It is widely applied in many fields, such as communication, detection, biology, neurology, psychology, intelligence, economy, and sociology. The research on it is closely related to the development of computer software and hardware. In this thesis, we study the non-invertible linear finite autonomous automata and derive the following new results:1. A formula is given to count the number of the nodes of everylevel in a down-oriented tree of an autonomous automaton. Then a necessary and sufficient condition is presented for the graph of an autonomous automaton to be an exact-equibranch down-oriented tree [theorem 3.2-3.3].2. Some necessary and sufficient conditions are presented for an autonomous automaton to be a circle-tree autonomous automaton [theorem 3.7~3.8].3. The graph structure of some non-invertible autonomous automata is discussed in regular space, orthogonal space, and orthonormal space respectively. Some new results are derived [theorem 3.10-3.13].Boolean ring has much distinctive difference from domain in that Boolean ring has zero divisors. The difference gives rise to great difficult in researching linear characteristic. We explore the graph structure of the autonomous automata over Boolean ring and derive the following new results:1. We determine the graph structure of a kind of exact-equibranch down-oriented-tree autonomous automata and of a kind of invertible autonomous automata [theorem 4.1 -4.4].2. We prove that one kind of invertible autonomous automata has the same graph structure as its affine autonomous automata [theorem 4.5].