Handbook of Discrete and Combinatorial Mathematics

Kenneth H. Rosen

• Publisher: Chapman and Hall/CRC
• Year: 2017
• Print ISBN: 9781584887805
• eBook ISBN: 9781351644051
• Topic: Mathematics
• Subtopic: Operating Systems
• Index: Mathematics

Handbook of Discrete and Combinatorial Mathematics provides a comprehensive reference volume for mathematicians, computer scientists, engineers, as well as students and reference librarians.

The material is presented so that key information can be located and used quickly and easily. Each chapter includes a glossary. Individual topics are covered in sections and subsections within chapters, each of which is organized into clearly identifiable parts: definitions, facts, and examples.

Examples are provided to illustrate some of the key definitions, facts, and algorithms. Some curious and entertaining facts and puzzles are also included. Readers will also find an extensive collection of biographies.

This second edition is a major revision. It includes extensive additions and updates. Since the first edition appeared in 1999, many new discoveries have been made and new areas have grown in importance, which are covered in this edition.

1

FOUNDATIONS

1.1 Propositional and Predicate LogicJerrold W. Grossman

1.1.1 Propositions and Logical Operations

1.1.2 Equivalences, Identities, and Normal Forms

1.1.3 Predicate Logic

1.2 Set TheoryJerrold W. Grossman

1.2.1 Sets

1.2.2 Set Operations

1.2.3 Infinite Sets

1.2.4 Axioms for Set Theory

1.3 FunctionsJerrold W. Grossman

1.3.1 Basic Terminology for Functions

1.3.2 Computational Representation

1.3.3 Asymptotic Behavior

1.4 RelationsJohn G. Michaels

1.4.1 Binary Relations and Their Properties

1.4.2 Equivalence Relations

1.4.3 Partially Ordered Sets

1.4.4 n-Ary Relations

1.5 Proof TechniquesSusanna S. Epp

1.5.1 Rules of Inference

1.5.2 Proofs

1.5.3 Disproofs

1.5.4 Mathematical Induction

1.5.5 Diagonalization Arguments

1.6 Axiomatic Program VerificationDavid Riley

1.6.1 Assertions and Semantic Axioms

1.6.2 NOP, Assignment, and Sequencing Axioms

1.6.3 Axioms for Conditional Execution Constructs

1.6.4 Axioms for Loop Constructs

1.6.5 Axioms for Subprogram Constructs

1.7 Logic-Based Computer Programming ParadigmsMukesh Dalal

1.7.1 Logic Programming

1.7.2 Fuzzy Sets and Logic

1.7.3 Production Systems

1.7.4 Automated Reasoning

INTRODUCTION

This chapter covers material usually referred to as the foundations of mathematics, including logic, sets, and functions. In addition to covering these foundational areas, this chapter includes material that shows how these topics are applied to discrete mathematics, computer science, and electrical engineering. For example, this chapter covers methods of proof, program verification, and fuzzy reasoning.

GLOSSARY

action: a literal or a print command in a production system.

aleph-null: the cardinality ${\mathcal{N}}_0$ of the set $\mathcal{N}$ of natural numbers.

AND: the logical operator for conjunction, also written ∧.

antecedentL in a conditional proposition p → q (“if p then q”), the proposition p (“if-clause”) that precedes the arrow.

antichain: a subset of a poset in which no two elements are comparable.

antisymmetric: the property of a binary relation R that if aRb and bRa, then a = b.

argument form: a sequence of statement forms, each called a premise of the argument, followed by a statement form called a conclusion of the argument.

assertion: (or program assertion) a program comment specifying some conditions on the values of the computational variables; these conditions are supposed to hold whenever program flow reaches the location of the assertion.

asymmetric: the property of a binary relation R that if aRb, then $b\cancel{\text{R}}a$.

asymptotic: A function f is asymptotic to a function g, written f(x) ~ g(x), if f(x) ≠ 0 for sufficiently large x and ${\lim }_{x\to \infty }\frac{g\left(x\right)}{f\left(x\right)}=1$.

atom (or atomic formula): a simplest formula of predicate logic.

atomic formula: See atom.

atomic proposition: a proposition tha...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Table of Contents
• 1. FOUNDATIONS
• 2. COUNTING METHODS
• 3. SEQUENCES
• 4. NUMBER THEORY
• 5. ALGEBRAIC STRUCTURES
• 6. LINEAR ALGEBRA
• 7. DISCRETE PROBABILITY
• 8. GRAPH THEORY
• 9. TREES
• 10. NETWORKS AND FLOWS
• 11. PARTIALLY ORDERED SETS
• 12. COMBINATORIAL DESIGNS
• 13. DISCRETE AND COMPUTATIONAL GEOMETRY
• 14. CODING THEORY
• 15. CRYPTOGRAPHY
• 16. DISCRETE OPTIMIZATION
• 17. THEORETICAL COMPUTER SCIENCE
• 18. INFORMATION STRUCTURES
• 19. DATA MINING
• 20. DISCRETE BIOINFORMATICS
• BIOGRAPHIES
• INDEX