Algebraic logic. Transl. from the Russian by Robert H. Silverman (Q1075292)

Here is a very readable introduction into applied algebraic logic at the intuitive and problem-solving level. The author, a student of the logician P. S. Novikov, has used the book successfully in seminars at the Pedagogical Institute in Moscow. However, a better title for the book would have been: Applied Algebraic Logic through Problem-Solving. The 12 chapters cover a broad range of interesting topics such as: normal forms of logical functions, duality, monotone logical functions, Post's Theorem, functionally closed classes, networks, contact networks (but no Quine Theory), probabilistic logics, multi-valued logics, and simple predicate logics. Each chapter is presented in the form of several problems, followed by hints to solve most of the problems, followed by more detailed solutions to most of the problems. Indeed, overall, there are more than 300 graded problems, with more than 200 hints at solutions and approximately 260 fairly complete solutions. No attempt has been made to exploit the stochastic framework of probabilistic logics to develop reliability results for non-relay circuits such as occur in electron tube, transistor, or VLSI logical designs. Optimization problems for switching circuits are treated in great depth, but there are no discussions on estimates of the complexity of problems which mention either NP-completeness or polynomial-time complexity. The book will be especially useful to members of problem-solving seminars interested in sharpening their skills in basic logic.