Discrete mathematics

Format:

Book

Author/Creator:

Akerkar, Rajendra, Author.

Contributor:

Akerkar, Rupali, Contributor.

Series:

Always learning.

Always Learning

Language:

English

Physical Description:

1 online resource (1 v.) : ill.

Edition:

1st edition

Place of Publication:

[Place of publication not identified] Pearson 2007

Language Note:

English

System Details:

text file

Summary:

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 a strong foundation for mathematics majors. The vital role that discrete mathematics plays in computer science is strongly emphasized as well. The book is useful for students and instructors, and also software professionals.

Contents:

Cover

Preface

Contents

Proof Methods and Induction

Formal Proofs

Proofs and the Real World

Propositional Reasoning Examples

Direct Proof

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.

Notes:

Bibliographic Level Mode of Issuance: Monograph

Includes bibliographical references.

Description based on publisher supplied metadata and other sources.

ISBN:

9789332515567

9332515565

9788131775905

8131775909

OCLC:

1024269864