CONTENTS CHAPTER 11 Properties of the Integers 264 11.1 Introduction 264 11.2 Order and Inequalities,Absolute Value 265 11.3 Mathematical Induction 266 11.4 Division Algorithm 267 11.5 Divisibility,Primes 269 11.6 Greatest Common Divisor,Euclidean Algorithm 270 11.7 Fundamental Theorem of Arithmetic 273 11.8 Congruence Relation 274 11.9 Congruence Equations 278 Solved Problems 283 Supplementary Problems 299 CHAPTER 12 Languages,Automata,Grammars 303 12.1 Introduction 303 12.2 Alphabet,Words,Free Semigroup 303 12.3 Languages 304 12.4 Regular Expressions,Regular Languages 305 12.5 Finite State Automata 306 12,6 Grammars 310 Solved Problems 314 Supplementary Problems 319 CHAPTER 13 Finite State Machines and Turing Machines 323 13.1 Introduction 323 13.2 Finite State Machines 323 13.3 Godel Numbers 326 13.4 Turing Machines 326 13.5 Computable Functions 330 Solved Problems 331 Supplementary Problems 334 CHAPTER 14 Ordered Sets and Lattices 337 14.1 Introduction 337 14.2 Ordered Sets 337 14.3 Hasse Diagrams of Partially Ordered Sets 340 14.4 Consistent Enumeration 342 14.5 Supremum and Infimum 342 14.6 Isomorphic (Similar)Ordered Sets 344 14.7 Well-Ordered Sets 344 14.8 Lattices 346 14.9 Bounded Lattices 348 14.10 Distributive Lattices 349 14.11 Complements,Complemented Lattices 350 Solved Problems Supplementary Problems 360x CONTENTS CHAPTER 11 Properties of the Integers 264 11.1 Introduction 264 11.2 Order and Inequalities, Absolute Value 265 11.3 Mathematical Induction 266 11.4 Division Algorithm 267 11.5 Divisibility, Primes 269 11.6 Greatest Common Divisor, Euclidean Algorithm 270 11.7 Fundamental Theorem of Arithmetic 273 11.8 Congruence Relation 274 11.9 Congruence Equations 278 Solved Problems 283 Supplementary Problems 299 CHAPTER 12 Languages, Automata, Grammars 303 12.1 Introduction 303 12.2 Alphabet, Words, Free Semigroup 303 12.3 Languages 304 12.4 Regular Expressions, Regular Languages 305 12.5 Finite State Automata 306 12.6 Grammars 310 Solved Problems 314 Supplementary Problems 319 CHAPTER 13 Finite State Machines and Turing Machines 323 13.1 Introduction 323 13.2 Finite State Machines 323 13.3 Gödel Numbers 326 13.4 Turing Machines 326 13.5 Computable Functions 330 Solved Problems 331 Supplementary Problems 334 CHAPTER 14 Ordered Sets and Lattices 337 14.1 Introduction 337 14.2 Ordered Sets 337 14.3 Hasse Diagrams of Partially Ordered Sets 340 14.4 Consistent Enumeration 342 14.5 Supremum and Infimum 342 14.6 Isomorphic (Similar) Ordered Sets 344 14.7 Well-Ordered Sets 344 14.8 Lattices 346 14.9 Bounded Lattices 348 14.10 Distributive Lattices 349 14.11 Complements, Complemented Lattices 350 Solved Problems 351 Supplementary Problems 360