Discrete mathematics

Discrete mathematics

Discrete Mathematics provides an introduction to some of the fundamental concepts in modern mathematics. Abundant examples help explain the principles and practices of discrete mathematics. The book intends to cover material required by readers for whom mathematics is just a tool, as well as provide...

Descripción completa

Detalles Bibliográficos
Otros Autores: Akerkar, Rajendra Author (author), Akerkar, Rupali Contributor (contributor)
Formato: Libro electrónico
Idioma:Inglés
Publicado: [Place of publication not identified] Pearson 2007
Edición:1st edition
Colección:Always learning.
Materias:
Engineering & Applied Sciences
Computer Science
Ver en Biblioteca Universitat Ramon Llull:https://discovery.url.edu/permalink/34CSUC_URL/1im36ta/alma991009627769606719
Tabla de Contenidos:
  • Cover
  • Preface
  • Contents
  • Proof Methods and Induction
  • Formal Proofs
  • Proofs and the Real World
  • Propositional Reasoning Examples
  • Direct Proof
  • Proof by Contradiction
  • Proof by Contradiction
  • Structured Proofs and Paragraph Proofs
  • Counter Examples
  • Proofs
  • False Proofs
  • Some Actual Proofs
  • Inductive Proofs
  • More Simple Induction
  • Divisibility
  • A String Example
  • Fibonacci Numbers
  • Tiling Problem
  • Geometry
  • Double Induction
  • Strong Induction
  • Blocks and Towers
  • Fibonacci Examples
  • Prime Factorization
  • Tournaments
  • Cycles
  • Locally Fair Rankings
  • Locally Fair Rankings and Number of Wins
  • Induction, Strong Induction, and Well-ordering
  • Induction vs Strong Induction
  • Well-ordering
  • Structural Induction
  • Some Recursive Definitions for Data Types
  • Inductive Proofs Based on Recursive Data Type Definitions
  • Recursively-defined Functions on Recursively-defined Data Types
  • Induction and Recursive Algorithms
  • RSA Public Key Cryptosystem
  • Fast Exponentiation
  • Greatest Common Divisor
  • Chapter 1: Symbolic Logic
  • 1.1 Introduction to Logic
  • 1.2 Boolean Expressions
  • 1.3 Construction of Boolean Expressions
  • 1.4 Meaning of Boolean Expressions
  • 1.4.1 Conjunctions
  • 1.4.2 Disjunctions
  • 1.4.3 Negations
  • 1.5 Construction of Truth Tables
  • 1.5.1 Back to Derivations
  • 1.5.2 Valuations and Truth Tables
  • 1.5.3 How Many Rows
  • 1.5.4 Making Truth Tables
  • 1.5.5 Truth Tables
  • 1.6 Logical Equivalence
  • 1.7 DeMorgan's Law
  • 1.7.1 Why Use DeMorgan's Law
  • 1.7.2 Pushing Negations Inward
  • 1.8 Why Use Logical Equivalences
  • 1.9 Tautologies and Contradictions
  • 1.10 Implication and Biconditionals
  • 1.10.1 Mental Imagery: Cause and Effect
  • 1.10.2 Relation of Biconditionals to Logical Equivalence
  • 1.10.3 Relation of Implication Biconditional.
  • 1.11 Logical Equivalences
  • 1.12 Another Equivalence
  • 1.13 Negation of Conditionals
  • 1.14 Variations on a Theme
  • 1.15 Translations
  • 1.15.1 How to Handle Translations
  • 1.16 Arguments
  • 1.16.1 Showing an Argument as Valid
  • 1.16.2 Disjunctive Addition
  • 1.16.3 Conjunctive Simplification
  • 1.16.4 Disjunctive Simplification
  • 1.16.5 Hypothetical Syllogism
  • 1.16.6 Dilemma: Proof by Division into Cases
  • 1.17 Fallacies
  • 1.17 .1 Converse Error
  • 1.17.2 Inverse Error
  • 1.18 Valid Argument with a False Conclusion
  • 1.19 Contradiction Rule
  • 1.20 Applications of Boolean Expressions
  • 1.21 Logic Gates
  • 1.21.1 AND Gates, OR Gates
  • 1.21.2 Why Not Implication Gates
  • 1.22 How to Construct Circuits
  • 1.23 How to Derive a Boolean Expression
  • 1.24 Creating a Circuit from Truth Tables
  • 1.25 Adders
  • 1.26 Predicate Calculus
  • 1.27 Boolean Formulas
  • 1.28 Understanding Quantifiers
  • 1.29 Negation of Quantifiers
  • 1.30 Vacuously True Statements
  • 1.31 Normal Forms in Propositional Logic
  • 1.32 Normal Forms in Predicate Logic
  • 1.33 The Resolution Principle
  • 1.34 Parenthesized Infix Notation and Polish Notation
  • Chapter 2: Set Theory
  • 2.1 Definitions
  • 2.2 Set Specification
  • 2.2.1 Explicit
  • 2.2.2 By Properties
  • 2.2.3 Grammar
  • 2.3 Set Operations
  • 2.3.1 Definitions
  • 2.3.2 Properties
  • 2.4 Characteristic Function
  • 2.4.1 Properties of Characteristic Function
  • 2.4.2 Computer Representation of Sets and Subsets
  • 2.5 Fuzzy Set Theory
  • 2.5.1 Introduction
  • 2.6 Basic Notions of Fuzzy Set
  • 2.6.1 The Concept of Fuzzy Subset
  • 2.6.2 The Algebra of Fuzzy Subsets
  • 2.6.3 Other Important Notions
  • 2.6.4 Fuzzy Relations
  • Chapter 3: Relations
  • 3.1 Operations on Relations
  • 3.1.1 Set Operations
  • 3.1.2 Inverse
  • 3.1.3 Composition
  • 3.1.4 Closure
  • 3.2 Computing the Transitive Closure.
  • 3.3 Equivalence Relation and Partitions
  • 3.3.1 Definitions
  • 3.3.2 Integers Modulo m
  • 3.3.3 Fast Exponentiation
  • 3.4 Partial Orders
  • 3.4.1 Definitions for Partial Orders
  • 3.4.2 Directed Acyclic Graph Definition
  • 3.4.3 Hasse Diagrams
  • 3.4.4 Partial vs Total Orders
  • 3.4.5 Topological Sorting
  • 3.4.6 Parallel Task Scheduling
  • 3.5 Ordered Pairs
  • 3.5.1 Representation of Relation
  • 3.5.2 Graph of Relation
  • 3.5.3 Composition of Relations
  • 3.5.4 Types of Relations
  • 3.5.5 Interpretation Using Digraphs
  • 3.6 Warshall's Algorithm
  • 3.7 Application of Relation
  • Chapter 4: Functions and Recursion
  • 4.1 Functions
  • 4.1.1 Terminology
  • 4.1.2 Properties
  • 4.2 Recursion
  • Chapter 5: Algebraic Structures
  • 5.1 Algebra
  • 5.1.1 Types of Homomorphism
  • 5.2 DeMorgan's Law
  • 5.2.1 Properties of Binary Operations
  • 5.2.2 Quotient Semigroup: (Factor Semigroup)
  • 5.3 Group
  • 5.3.1 Isomorphism
  • 5.4 Ring
  • 5.4.1 Subring of a Ring R
  • 5.4.2 Ring Homomorphism
  • 5.5 Polish Expressions and Their Compilation
  • 5.5.1 Polish Notation
  • 5.5.2 Conversion of Infix Expressions to Polish Notation
  • 5.6 The Communication Model and Error Correction
  • 5.7 Hamming Codes
  • 5.8 Error Recovery in Group Codes
  • Chapter 6: Graph Theory
  • 6.1 Introduction
  • 6.2 Graph Representation
  • 6.3 Topological Sort
  • 6.4 Simple Graph Propagation Algorithm
  • 6.5 Depth-First Search
  • 6.5.1 Biconnected Components
  • 6.5.2 Strongly-connected Components
  • 6.5.3 An Application
  • 6.6 Breadth-First Search
  • 6.6.1 Introduction
  • 6.6.2 Shortest Paths
  • 6.7 Shortest-Path Algorithm
  • 6.7.1 Single-source Shortest Path
  • 6.8 Directed Acyclic Graphs
  • 6.8.1 Matrix Multiplication
  • 6.8.2 Floyd-Warshall's Method
  • 6.8.3 Other Applications
  • Chapter 7: Counting
  • 7.1 A Party Problem
  • 7.1.1 Sets and the Like
  • 7.1.2 The Number of Subsets.
  • 7.1.3 Sequences
  • 7 .1.4 Permutations
  • 7.2 Induction
  • 7.2.1 The Sum of Odd Numbers
  • 7 .2.2 Subset Counting Revisited
  • 7 .2.3 More Induction Proofs
  • 7 .2.4 Counting Regions
  • 7.3 Counting Subsets
  • 7.3.1 The Number of Ordered Subsets
  • 7 .3.2 The Number of Subsets of a Given Size
  • 7 .3.3 The Binomial Theorem
  • 7 .3.4 Distributing Presents
  • 7 .3.5 Anagrams
  • 7 .3.6 Distribution of Money
  • 7.4 Pascal's Triangle
  • 7 .4.1 Identities in the Pascal Triangle
  • 7.4.2 A Bird's- Eye View at the Pascal Triangle
  • 7.5 Combinatorial Probability
  • 7.5.1 Events and Probabilities
  • 7 .5.2 Independent Repetition of an Experiment
  • 7 .5.3 The Law of Large Numbers
  • 7.6 Fibonacci Numbers
  • 7.6.1 Fibonacci's Exercise
  • 7 .6.2 Lots of Identities
  • 7 .6.3 A Formula for the Fibonacci Numbers
  • 7.7 Integers, Divisors, and Primes
  • 7. 7.1 Divisibility of Integers
  • 7.7.2 Primes and Their History
  • 7.7.3 Factorization into Primes
  • 7.7.4 Fermat's "Little" Theorem
  • 7.7.5 The Euclidean Algorithm
  • 7. 7.6 Primality Test
  • Chapter 8: Combinatorics
  • 8.1 The Pigeonhole Principle
  • 8.2 Strong Pigeonholes
  • 8.2.1 Pigeonhole Principle Examples: Weighing Balls
  • 8.3 Dilworth's Theorem
  • 8.4 Problems
  • 8.5 Sets of the Same Size: Bijections
  • 8.6 Finite Sets
  • 8.7 Inclusion-Exclusion
  • 8.8 lnfinite Sets
  • 8.9 Schroder-Bcrnstein Theorem
  • 8.10 Countable Sets
  • 8.11 The Continuum
  • 8.12 Diagonal Argwnents
  • 8.12.1 A Paradox
  • 8.13 Set Theory Revisited
  • 8.13.1 Bijections, Injections, Surjections
  • 8.13.2 Finite Cardinality
  • 8.14 Functions and Permutations
  • 8.14.1 Surjection, Injection, Bijection
  • 8.14.2 Permutation
  • Chapter 9: Automata
  • 9.1 Introduction
  • 9.1.1 Abstraction
  • 9.2 Decision Problems vs Functions
  • 9.2.1 Strings
  • 9.2.2 Operations on Strings
  • 9.2.3 Operations on Sets.
  • 9.3 Finite Automata and Regular Sets
  • 9.3.1 States and Transitions
  • 9.3.2 Finite Automata
  • 9.3.3 Semantic Actions
  • 9.3.4 A Sample Lexical Analyzer
  • 9.4 More on Regular Sets
  • 9.4.1 Some Closure Properties of Regular Sets
  • 9.4.2 The Product Construction
  • 9.5 Nondetenninistic Finite Automata
  • 9.5.1 Nondeterminism
  • 9.5.2 Nondeterministic Finite Automata
  • 9.5.3 Equivalence of DFAs and NFAs
  • 9.6 The Subset Construction
  • 9.6.1 Formal Definition of Nondeterministic Finite Automata
  • 9.6.2 The Subsets Construction: General Account
  • 9.6.3 e -Transition
  • 9.6.4 More Closure Properties
  • Chapter 10: Program Verification
  • 10.1 Introduction
  • 10.2 A Simple Example
  • 10.3 Linear Search
  • Chapter 11: Design of Algorithms
  • 11.1 Introduction
  • 11.2 Greedy Algoritluns
  • 11.2.1 Greedy Algorithms-When to Apply
  • 11.2.2 Greedy Approach for CPU Scheduling
  • 11.3 Backtracking
  • 11.4 Divide and Conquer
  • 11.4.1 Model of Divide and Conquer
  • 11.4.2 Finding the mth Smallest Element
  • 11.5 Dynamic Programming
  • 11.5.1 Shortest Path from I to l
  • Bibliography
  • Index.

Ejemplares similares