Discrete mathematical structures with applications to computer science
By: J. P. Tremblay, R. Manohar.
Contributors: Manohar, R., 1925- joint author.
Series: McGraw-Hill computer science series
Publisher: McGraw-Hill
Published: 1975
Place of publication: New York
Language: eng
Number of pages: 606
Subjects: Mathematics; Electronic data processing; Machine theory
Notes: Includes bibliographies and index.
Table of contents: title: Preface
pagenum: xiii; label: 1
title: Mathematical Logic
pagenum: 1; title: Introduction
pagenum: 1; label: 1-1
title: Statements and Notation
pagenum: 2; label: 1-2
title: Connectives
pagenum: 7; label: 1-2.1
title: Negation
pagenum: 8; label: 1-2.2
title: Conjunction
pagenum: 9; label: 1-2.3
title: Disjunction
pagenum: 10; label: 1-2.4
title: Statement Formulas and Truth Tables
pagenum: 11; title: Exercises 1-2.4
pagenum: 14; label: 1-2.5
title: Logical Capabilities of Programming Languages
pagenum: 14; label: 1-2.6
title: Conditional and Biconditional
pagenum: 18; title: Exercises 1-2.6
pagenum: 22; label: 1-2.7
title: Well-formed Formulas
pagenum: 23; label: 1-2.8
title: Tautologies
pagenum: 24; title: Exercises 1-2.8
pagenum: 26; label: 1-2.9
title: Equivalence of Formulas
pagenum: 26; label: 1-2.10
title: Duality Law
pagenum: 30; label: 1-2.11
title: Tautological Implications
pagenum: 32; title: Exercises 1-2.11
pagenum: 34; label: 1-2.12
title: Formulas with Distinct Truth Tables
pagenum: 35; label: 1-2.13
title: Functionally Complete Sets of Connectives
pagenum: 37; title: Exercises 1-2.13
pagenum: 38; label: 1-2.14
title: Other Connectives
pagenum: 39; title: Exercises 1-2.14
pagenum: 41; label: 1-2.15
title: Two-state Devices and Statement Logic
pagenum: 41; title: Exercises 1-2.15
pagenum: 49; title: Exercises 1-2
pagenum: 49; label: 1-3
title: Normal Forms
pagenum: 50; label: 1-3.1
title: Disjunctive Normal Forms
pagenum: 50; label: 1-3.2
title: Conjunctive Normal Forms
pagenum: 52; label: 1-3.3
title: Principal Disjunctive Normal Forms
pagenum: 53; label: 1-3.4
title: Principal Conjunctive Normal Forms
pagenum: 56; label: 1-3.5
title: Ordering and Uniqueness of Normal Forms
pagenum: 58; title: Exercises 1-3.5
pagenum: 60; label: 1-3.6
title: Completely Parenthesized Infix Notation and Polish Notation
pagenum: 61; title: Exercises 1-3.6
pagenum: 64; label: 1-4
title: The Theory of Inference for the Statement Calculus
pagenum: 65; label: 1-4.1
title: Validity Using Truth Tables
pagenum: 66; title: Exercises 1-4.1
pagenum: 67; label: 1-4.2
title: Rules of Inference
pagenum: 68; label: 1-4.3
title: Consistency of Premises and Indirect Method of Proof
pagenum: 72; label: 1-4.4
title: Automatic Theorem Proving
pagenum: 74; title: Exercises 1-4
pagenum: 79; label: 1-5
title: The Predicate Calculus
pagenum: 79; label: 1-5.1
title: Predicates
pagenum: 80; label: 1-5.2
title: The Statement Function, Variables, and Quantifiers
pagenum: 82; label: 1-5.3
title: Predicate Formulas
pagenum: 85; label: 1-5.4
title: Free and Bound Variables
pagenum: 86; label: 1-5.5
title: The Universe of Discourse
pagenum: 88; title: Exercises 1-5
pagenum: 89; label: 1-6
title: Inference Theory of the Predicate Calculus
pagenum: 90; label: 1-6.1
title: Valid Formulas and Equivalences
pagenum: 90; label: 1-6.2
title: Some Valid Formulas over Finite Universes
pagenum: 92; label: 1-6.3
title: Special Valid Formulas Involving Quantifiers
pagenum: 94; label: 1-6.4
title: Theory of Inference for the Predicate Calculus
pagenum: 96; label: 1-6.5
title: Formulas Involving More Than One Quantifier
pagenum: 99; title: Exercises 1-6
pagenum: 101; title: Bibliography
pagenum: 102; label: 2
title: Set Theory
pagenum: 104; title: Introduction
pagenum: 104; label: 2-1
title: Basic Concepts of Set Theory
pagenum: 105; label: 2-1.1
title: Notation
pagenum: 105; label: 2-1.2
title: Inclusion and Equality of Sets
pagenum: 106; label: 2-1.3
title: The Power Set
pagenum: 109; title: Exercises 2-1.3
pagenum: 111; label: 2-1.4
title: Some Operations on Sets
pagenum: 111; title: Exercises 2-1.4
pagenum: 115; label: 2-1.5
title: Venn Diagrams
pagenum: 116; title: Exercises 2-1.5
pagenum: 118; label: 2-1.6
title: Some Basic Set Identities
pagenum: 118; label: 2-1.7
title: The Principle of Specification
pagenum: 121; label: 2-1.8
title: Ordered Pairs and n-tuples
pagenum: 122; label: 2-1.9
title: Cartesian Products
pagenum: 123; title: Exercises 2-1
pagenum: 125; label: 2-2
title: Representation of Discrete Structures
pagenum: 126; label: 2-2.1
title: Data Structures
pagenum: 126; label: 2-2.2
title: Storage Structures
pagenum: 129; label: 2-2.3
title: Sequential Allocation
pagenum: 130; label: 2-2.4
title: Pointers and Linked Allocation
pagenum: 132; label: 2-2.5
title: An Application of Bit Represented Sets
pagenum: 141; title: Exercises 2-2
pagenum: 147; label: 2-3
title: Relations and Ordering
pagenum: 148; label: 2-3.1
title: Relations
pagenum: 149; title: Exercises 2-3.1
pagenum: 153; label: 2-3.2
title: Properties of Binary Relations in a Set
pagenum: 154; title: Exercises 2-3.2
pagenum: 155; label: 2-3.3
title: Relation Matrix and the Graph of a Relation
pagenum: 156; label: 2-3.4
title: Partition and Covering of a Set
pagenum: 162; title: Exercises 2-3.4
pagenum: 164; label: 2-3.5
title: Equivalence Relations
pagenum: 164; label: 2-3.6
title: Compatibility Relations
pagenum: 171; title: Exercises 2-3.6
pagenum: 175; label: 2-3.7
title: Composition of Binary Relations
pagenum: 176; title: Exercises 2-3.7
pagenum: 182; label: 2-3.8
title: Partial Ordering
pagenum: 183; label: 2-3.9
title: Partially Ordered Set: Representation and Associated Terminology
pagenum: 186; title: Exercises 2-3.9
pagenum: 191; label: 2-4
title: Functions
pagenum: 192; label: 2-4.1
title: Definition and Introduction
pagenum: 192; title: Exercises 2-4.1
pagenum: 197; label: 2-4.2
title: Composition of Functions
pagenum: 198; label: 2-4.3
title: Inverse Functions
pagenum: 201; title: Exercises 2-4.3
pagenum: 204; label: 2-4.4
title: Binary and n-ary Operations
pagenum: 205; title: Exercises 2-4.4
pagenum: 210; label: 2-4.5
title: Characteristic Function of a Set
pagenum: 210; label: 2-4.6
title: Hashing Functions
pagenum: 212; title: Exercises 2-4.6
pagenum: 219; title: Exercises 2-4
pagenum: 219; label: 2-5
title: Natural Numbers
pagenum: 220; label: 2-5.1
title: Peano Axioms and Mathematical Induction
pagenum: 220; label: 2-5.2
title: Cardinality
pagenum: 224; title: Exercises 2-5
pagenum: 231; label: 2-6
title: Recursion
pagenum: 232; label: 2-6.1
title: Recursive Functions, Sets, and Predicates
pagenum: 232; title: Exercises 2-6.1
pagenum: 243; label: 2-6.2
title: Recursion in Programming Languages
pagenum: 243; title: Exercises 2-6
pagenum: 259; label: 2-7
title: Recursion in Mechanical Theorem Proving
pagenum: 261; title: Exercises 2-7
pagenum: 268; title: Bibliography
pagenum: 268; label: 3
title: Algebraic Structures
pagenum: 270; title: Introduction
pagenum: 270; label: 3-1
title: Algebraic Systems: Examples and General Properties
pagenum: 271; label: 3-1.1
title: Definition and Examples
pagenum: 271; label: 3-1.2
title: Some Simple Algebraic Systems and General Properties
pagenum: 274; title: Exercises 3-1
pagenum: 281; label: 3-2
title: Semigroups and Monoids
pagenum: 282; label: 3-2.1
title: Definitions and Examples
pagenum: 282; label: 3-2.2
title: Homomorphism of Semigroups and Monoids
pagenum: 287; label: 3-2.3
title: Subsemigroups and Submonoids
pagenum: 292; title: Exercises 3-2
pagenum: 294; label: 3-3
title: Grammars and Languages
pagenum: 294; label: 3-3.1
title: Discussion of Grammars
pagenum: 295; label: 3-3.2
title: Formal Definition of a Language
pagenum: 299; label: 3-3.3
title: Notions of Syntax Analysis
pagenum: 304; title: Exercises 3-3
pagenum: 308; label: 3-4
title: Polish Expressions and Their Compilation
pagenum: 309; label: 3-4.1
title: Polish Notation
pagenum: 310; label: 3-4.2
title: Conversion of Infix Expressions to Polish Notation
pagenum: 311; title: Exercises 3-4
pagenum: 318; label: 3-5
title: Groups
pagenum: 319; label: 3-5.1
title: Definitions and Examples
pagenum: 319; title: Exercises 3-5.1
pagenum: 328; label: 3-5.2
title: Subgroups and Homomorphisms
pagenum: 329; title: Exercises 3-5.2
pagenum: 333; label: 3-5.3
title: Cosets and Lagrange's Theorem
pagenum: 333; label: 3-5.4
title: Normal Subgroups
pagenum: 335; label: 3-5.5
title: Algebraic Systems with Two Binary Operations
pagenum: 341; title: Exercises 3-5.5
pagenum: 343; title: Exercises 3-5
pagenum: 344; label: 3-6
title: The Application of Residue Arithmetic to Computers
pagenum: 344; label: 3-6.1
title: Introduction to Number Systems
pagenum: 345; label: 3-6.2
title: Residue Arithmetic
pagenum: 348; title: Exercises 3-6
pagenum: 359; label: 3-7
title: Group Codes
pagenum: 359; label: 3-7.1
title: The Communication Model and Basic Notions of Error Correction
pagenum: 360; label: 3-7.2
title: Generation of Codes by Using Parity Checks
pagenum: 364; label: 3-7.3
title: Error Recovery in Group Codes
pagenum: 373; title: Exercises 3-7
pagenum: 376; title: Bibliography
pagenum: 376; label: 4
title: Lattices and Boolean Algebra
pagenum: 378; title: Introduction
pagenum: 378; label: 4-1
title: Lattices as Partially Ordered Sets
pagenum: 379; label: 4-1.1
title: Definition and Examples
pagenum: 379; title: Exercises 4-1.1
pagenum: 382; label: 4-1.2
title: Some Properties of Lattices
pagenum: 382; title: Exercises 4-1.2
pagenum: 385; label: 4-1.3
title: Lattices as Algebraic Systems
pagenum: 385; label: 4-1.4
title: Sublattices, Direct Product, and Homomorphism
pagenum: 387; title: Exercises 4-1.4
pagenum: 391; label: 4-1.5
title: Some Special Lattices
pagenum: 392; title: Exercises 4-1.5
pagenum: 397; label: 4-2
title: Boolean Algebra
pagenum: 397; label: 4-2.1
title: Definition and Examples
pagenum: 398; label: 4-2.2
title: Subalgebra, Direct Product, and Homomorphism
pagenum: 401; title: Exercises 4-2
pagenum: 405; label: 4-3
title: Boolean Functions
pagenum: 406; label: 4-3.1
title: Boolean Forms and Free Boolean Algebras
pagenum: 406; label: 4-3.2
title: Values of Boolean Expressions and Boolean Functions
pagenum: 410; title: Exercises 4-3
pagenum: 417; label: 4-4
title: Representation and Minimization of Boolean Functions
pagenum: 418; label: 4-4.1
title: Representation of Boolean Functions
pagenum: 418; label: 4-4.2
title: Minimization of Boolean Functions
pagenum: 424; title: Exercises 4-4
pagenum: 433; label: 4-5
title: Design Examples Using Boolean Algebra
pagenum: 436; title: Exercises 4-5
pagenum: 451; label: 4-6
title: Finite-state Machines
pagenum: 453; label: 4-6.1
title: Introductory Sequential Circuits
pagenum: 453; label: 4-6.2
title: Equivalence of Finite-state Machines
pagenum: 456; title: Exercises 4-6
pagenum: 465; title: Bibliography
pagenum: 466; label: 5
title: Graph Theory
pagenum: 468; title: Introduction
pagenum: 468; label: 5-1
title: Basic Concepts of Graph Theory
pagenum: 469; label: 5-1.1
title: Basic Definitions
pagenum: 469; title: Exercises 5-1.1
pagenum: 475; label: 5-1.2
title: Paths, Reachability, and Connectedness
pagenum: 476; title: Exercises 5-1.2
pagenum: 483; label: 5-1.3
title: Matrix Representation of Graphs
pagenum: 484; title: Exercises 5-1.3
pagenum: 493; label: 5-1.4
title: Trees
pagenum: 494; title: Exercises 5-1.4
pagenum: 501; label: 5-2
title: Storage Representation and Manipulation of Graphs
pagenum: 501; label: 5-2.1
title: Trees: Their Representation and Operations
pagenum: 501; label: 5-2.2
title: List Structures and Graphs
pagenum: 509; title: Exercises 5-2
pagenum: 514; label: 5-3
title: Simple Precedence Grammars
pagenum: 515; label: 5-3.1
title: Syntax Terminology
pagenum: 516; label: 5-3.2
title: A View of Parsing
pagenum: 520; label: 5-3.3
title: Notion and Use of Precedence Relations
pagenum: 523; label: 5-3.4
title: Formal Definition of Precedence Relations
pagenum: 526; label: 5-3.5
title: Parsing Algorithm for Simple Precedence Grammars
pagenum: 530; title: Exercises 5-3
pagenum: 532; label: 5-4
title: Fault Detection in Combinational Switching Circuits
pagenum: 533; label: 5-4.1
title: Faults in Combinational Circuits
pagenum: 534; label: 5-4.2
title: Notions of Fault Detection
pagenum: 535; label: 5-4.3
title: Algorithm for Generating a Fault Matrix
pagenum: 537; label: 5-4.4
title: Procedure for the Detection of Faults
pagenum: 547; title: Exercises 5-4
pagenum: 549; label: 5-5
title: PERT and Related Techniques
pagenum: 550; title: Exercises 5-5
pagenum: 555; title: Bibliography
pagenum: 555; label: 6
title: Introduction to Computability Theory
pagenum: 557; title: Introduction
pagenum: 557; label: 6-1
title: Finite-state Acceptors and Regular Grammars
pagenum: 558; title: Exercises 6-1
pagenum: 566; label: 6-2
title: Turing Machines and Partial Recursive Functions
pagenum: 566; title: Exercises 6-2
pagenum: 584; title: Bibliography
pagenum: 584; title: Appendix
pagenum: 585; title: Index
pagenum: 591