Discrete Structures, Logic, and Computability

by Hein, James L.

• ISBN13: 9780763718435
• ISBN10: 0763718432
• Edition: 2nd
• Format: Hardcover
• Copyright: 2001-10-10
• Publisher: Jones & Bartlett Learning

Summary

This book introduces the beginning computer science student to some of the fundamental ideas and techniques used by computer scientists today, focusing on discrete structures, logic, and computability.

Table of Contents

Elementary Notions and Notations	1	(73)
A Proof Primer	2	(11)
Logical Statements	2	(3)
Something to Talk About	5	(1)
Proof Techniques	6	(6)
Exercises	12	(1)
Sets	13	(22)
Definition of a Set	13	(5)
Operations on Sets	18	(8)
Counting Finite Sets	26	(3)
Bags (Multisets)	29	(1)
Sets Should Not Be Too Complicated	30	(1)
Exercises	31	(4)
Ordered Structures	35	(20)
Tuples	35	(4)
Lists	39	(2)
Strings and Languages	41	(5)
Relations	46	(3)
Counting Tuples	49	(3)
Exercises	52	(3)
Graphs and Trees	55	(17)
Definition of a Graph	55	(4)
Paths and Graphs	59	(2)
Graph Traversals	61	(2)
Trees	63	(5)
Spanning Trees	68	(2)
Exercises	70	(2)
Chapter Summary	72	(1)
Facts about Functions	73	(54)
Definitions and Examples	74	(17)
Definition of a Function	74	(5)
Some Useful Functions	79	(8)
Partial Functions	87	(1)
Exercises	88	(3)
Constructing Functions	91	(9)
Composition of Functions	91	(5)
The Map Function	96	(2)
Exercises	98	(2)
Properties of Functions	100	(15)
Injections and Surjections	100	(2)
Bijections and Inverses	102	(3)
The Pigeonhole Principle	105	(1)
Simple Ciphers	106	(3)
Hash Functions	109	(2)
Exercises	111	(4)
Countability	115	(10)
Comparing the Size of Sets	115	(1)
Sets that Are Countable	116	(3)
Diagonalization	119	(2)
Limits on Computability	121	(3)
Exercises	124	(1)
Chapter Summary	125	(2)
Construction Techniques	127	(66)
Inductively Defined Sets	128	(17)
Numbers	129	(3)
Strings	132	(2)
Lists	134	(4)
Binary Trees	138	(2)
Cartesian Products of Sets	140	(2)
Exercises	142	(3)
Recursive Functions and Procedures	145	(28)
Numbers	146	(4)
Strings	150	(3)
Lists	153	(6)
Binary Trees	159	(4)
Two More Problems	163	(2)
Infinite Sequences	165	(3)
Exercises	168	(5)
Grammars	173	(18)
Recalling an English Grammar	173	(1)
Structure of Grammars	174	(3)
Derivations	177	(4)
Constructing Grammars	181	(5)
Meaning and Ambiguity	186	(2)
Exercises	188	(3)
Chapter Summary	191	(2)
Equivalence, Order, and Inductive Proof	193	(80)
Properties of Binary Relations	194	(19)
Composition of Relations	195	(4)
Closures	199	(5)
Path Problems	204	(5)
Exercises	209	(4)
Equivalence Relations	213	(19)
Definition and Examples	214	(4)
Equivalence Classes	218	(1)
Partitions	219	(6)
Generating Equivalence Relations	225	(4)
Exercises	229	(3)
Order Relations	232	(21)
Partial Orders	233	(6)
Topological Sorting	239	(3)
Well-Founded Orders	242	(8)
Ordinal Numbers	250	(1)
Exercises	251	(2)
Inductive Proof	253	(19)
Proof by Mathematical Induction	253	(6)
Proof by Well-Founded Induction	259	(2)
A Variety of Examples	261	(6)
Exercises	267	(5)
Chapter Summary	272	(1)
Analysis Techniques	273	(72)
Analyzing Algorithms	274	(7)
Worst-Case Running Time	274	(3)
Decision Trees	277	(4)
Exercises	281	(1)
Finding Closed Forms	281	(8)
Closed Forms for Sums	282	(5)
Exercises	287	(2)
Counting and Discrete Probability	289	(23)
Permutations (Order Is Important)	289	(4)
Combinations (Order Is Not Important)	293	(5)
Discrete Probability	298	(11)
Exercises	309	(3)
Solving Recurrences	312	(22)
Solving Simple Recurrences	313	(6)
Generating Functions	319	(13)
Exercises	332	(2)
Comparing Rates of Growth	334	(8)
Big Theta	334	(4)
Little Oh	338	(1)
Big Oh and Big Omega	339	(2)
Exercises	341	(1)
Chapter Summary	342	(3)
Elementary Logic	345	(52)
How Do We Reason?	346	(2)
What Is a Calculus?	347	(1)
How Can We Tell Whether Something Is a Proof?	348	(1)
Propositional Calculus	348	(21)
Well-Formed Formulas and Semantics	349	(4)
Equivalence	353	(5)
Truth Functions and Normal Forms	358	(7)
Complete Sets of Connectives	365	(2)
Exercises	367	(2)
Formal Reasoning	369	(15)
Inference Rules	370	(2)
Formal Proof	372	(8)
Proof Notes	380	(1)
Exercises	381	(3)
Formal Axiom Systems	384	(10)
An Example Axiom System	384	(7)
Other Axiom Systems	391	(1)
Exercises	392	(2)
Chapter Summary	394	(3)
Predicate Logic	397	(60)
First-Order Predicate Calculus	397	(19)
Predicates and Quantifiers	398	(4)
Well-Formed Formulas	402	(2)
Semantics and Interpretations	404	(5)
Validity	409	(4)
The Validity Problem	413	(1)
Exercises	413	(3)
Equivalent Formulas	416	(16)
Equivalence	416	(8)
Normal Forms	424	(3)
Formalizing English Sentences	427	(2)
Summary	429	(1)
Exercises	430	(2)
Formal Proofs in Predicate Calculus	432	(24)
Universal Instantiation	433	(4)
Existential Generalization (EG)	437	(1)
Existential Instantiation (EI)	438	(2)
Universal Generalization (UG)	440	(3)
Examples of Formal Proofs	443	(7)
Summary of Quantifier Proof Rules	450	(1)
Exercises	451	(5)
Chapter Summary	456	(1)
Applied Logic	457	(48)
Equality	458	(8)
Describing Equality	458	(6)
Extending Equals for Equals	464	(1)
Exercises	465	(1)
Program Correctness	466	(25)
Imperative Program Correctness	467	(11)
Array Assignment	478	(4)
Termination	482	(4)
Exercises	486	(5)
Higher-Order Logics	491	(12)
Classifying Higher-Order Logics	492	(4)
Semantics	496	(2)
Higher-Order Reasoning	498	(3)
Exercises	501	(2)
Chapter Summary	503	(2)
Computational Logic	505	(52)
Automatic Reasoning	505	(28)
Clauses and Clausal Forms	506	(6)
Resolution for Propositions	512	(2)
Substitution and Unification	514	(7)
Resolution: The General Case	521	(5)
Theorem Proving with Resolution	526	(3)
Remarks	529	(1)
Exercises	530	(3)
Logic Programming	533	(22)
Family Trees	534	(2)
Definition of a Logic Program	536	(1)
Resolution and Logic Programming	537	(12)
Logic Programming Techniques	549	(4)
Exercises	553	(2)
Chapter Summary	555	(2)
Algebraic Structures and Techniques	557	(76)
What Is an Algebra?	558	(14)
Definition of an Algebra	560	(2)
Concrete Versus Abstract	562	(2)
Working in Algebras	564	(6)
Exercises	570	(2)
Boolean Algebra	572	(13)
Simplifying Boolean Expressions	574	(4)
Digital Circuits	578	(5)
Exercises	583	(2)
Abstract Data Types as Algebras	585	(16)
Natural Numbers	585	(4)
Lists and Strings	589	(3)
Stacks and Queues	592	(4)
Binary Trees and Priority Queues	596	(3)
Exercises	599	(2)
Computational Algebras	601	(12)
Relational Algebras	601	(6)
Functional Algebras	607	(4)
Exercises	611	(2)
Other Algebraic Ideas	613	(19)
Congruence	613	(3)
Cryptology: The RSA Algorithm	616	(5)
Subalgebras	621	(2)
Morphisms	623	(6)
Exercises	629	(3)
Chapter Summary	632	(1)
Regular Languages and Finite Automata	633	(64)
Regular Languages	634	(8)
Regular Expressions	635	(3)
The Algebra of Regular Expressions	638	(2)
Exercises	640	(2)
Finite Automata	642	(24)
Deterministic Finite Automata	642	(4)
Nondeterministic Finite Automata	646	(2)
Transforming Regular Expressions into Finite Automata	648	(2)
Transforming Finite Automata into Regular Expressions	650	(5)
Finite Automata as Output Devices	655	(3)
Representing and Executing Finite Automata	658	(6)
Exercises	664	(2)
Constructing Efficient Finite Automata	666	(17)
Another Regular Expression to NFA Algorithm	667	(2)
Transforming an NFA into a DFA	669	(6)
Minimum-State DFAs	675	(6)
Exercises	681	(2)
Regular Language Topics	683	(12)
Regular Grammars	684	(5)
Properties of Regular Languages	689	(4)
Exercises	693	(2)
Chapter Summary	695	(2)
Context-Free Languages and Pushdown Automata	697	(60)
Context-Free Languages	697	(3)
Exercises	700	(1)
Pushdown Automata	700	(17)
Equivalent Forms of Acceptance	703	(4)
Context-Free Grammars and Pushdown Automata	707	(5)
Representing and Executing Pushdown Automata	712	(3)
Exercises	715	(2)
Parsing Techniques	717	(29)
LL(k) Parsing	717	(14)
LR(k) Parsing	731	(13)
Exercises	744	(2)
Context-Free Language Topics	746	(10)
Transforming Grammars	746	(5)
Properties of Context-Free Languages	751	(4)
Exercises	755	(1)
Chapter Summary	756	(1)
Turing Machines and Equivalent Models	757	(34)
Turing Machines	757	(17)
Definition of a Turing Machine	758	(4)
Turing Machines with Output	762	(3)
Alternative Definitions	765	(4)
A Universal Turing Machine	769	(4)
Exercises	773	(1)
The Church-Turing Thesis	774	(15)
Equivalence of Computational Models	775	(1)
A Simple Programming Language	776	(2)
Recursive Functions	778	(3)
Machines That Transform Strings	781	(6)
Exercises	787	(2)
Chapter Summary	789	(2)
Computational Notions	791	(36)
Computability	791	(12)
Effective Enumerations	792	(3)
The Halting Problem	795	(1)
The Total Problem	796	(2)
Other Problems	798	(4)
Exercises	802	(1)
A Hierarchy of Languages	803	(5)
The Languages	803	(4)
Summary	807	(1)
Exercises	807	(1)
Complexity Classes	808	(17)
The Class P	809	(1)
The Class NP	810	(1)
The Class PSPACE	811	(2)
Intractable Problems	813	(2)
Completeness	815	(6)
Formal Complexity Theory	821	(3)
Exercises	824	(1)
Chapter Summary	825	(2)
Answers to Selected Exercises	827	(88)
Bibliography	915	(6)
Greek Alphabet	921	(2)
Symbol Glossary	923	(6)
Index	929