Böcker av George Tourlakis

This book is ideal for a first or second year discrete mathematics course for mathematics, engineering, and computer science majors. The author has extensively class-tested early conceptions of the book over the years and supplements mathematical arguments with informal discussions to aid readers in understanding the presented topics. ¿Safe¿ ¿ that is, paradox-free ¿ informal set theory is introduced following on the heels of Russell¿s Paradox as well as the topics of finite, countable, and uncountable sets with an exposition and use of Cantor¿s diagonalisation technique. Predicate logic ¿for the user¿ is introduced along with axioms and rules and extensive examples. Partial orders and the minimal condition are studied in detail with the latter shown to be equivalent to the induction principle. Mathematical induction is illustrated with several examples and is followed by a thorough exposition of inductive definitions of functions and sets. Techniques for solving recurrence relations including generating functions, the O- and o-notations, and trees are provided. Over 200 end of chapter exercises are included to further aid in the understanding and applications of discrete mathematics.

This survey of computability theory offers the techniques and tools that computer scientists (as well as mathematicians and philosophers studying the mathematical foundations of computing) need to mathematically analyze computational processes and investigate the theoretical limitations of computing. Beginning with an introduction to the mathematisation of ¿mechanical process¿ using URM programs, this textbook explains basic theory such as primitive recursive functions and predicates and sequence-coding, partial recursive functions and predicates, and loop programs. Advanced chapters cover the Ackerman function, Tarski¿s theorem on the non-representability of truth, Goedel¿s incompleteness and Rosser¿s incompleteness theorems, two short proofs of the incompleteness theorem that are based on Lob's deliverability conditions, Church¿s thesis, the second recursion theorem and applications, a provably recursive universal function for the primitive recursive functions, Oraclecomputations and various classes of computable functionals, the Arithmetical hierarchy, Turing reducibility and Turing degrees and the priority method, a thorough exposition of various versions of the first recursive theorem, Blum¿s complexity, Hierarchies of primitive recursive functions, and a machine-independent characterisation of Cobham's feasibly computable functions.