计算机科学的数学结构：离散数学及其应用

版权申诉

163 浏览量更新于2024-07-21 收藏 11.16MB PDF 举报

"Mathematical Structures for Computer Science" 是一本由Judith L Gersting编写的关于离散数学及其应用的书籍，适用于计算机科学领域的学习和研究。这本书是第七版，由W.H. Freeman and Company出版，属于Macmillan Higher Education Company的一部分。书中涵盖了数学建模、计算机网络和计算机视觉等主题。正文：离散数学是计算机科学的基础，它是研究非连续对象（如整数、集合、图和逻辑）的数学分支。在"Mathematical Structures for Computer Science"中，作者Judith L. Gersting深入浅出地介绍了这些概念，帮助读者建立起坚实的数学基础，这对于理解和解决计算机科学中的问题至关重要。本书的主要内容可能包括以下几个方面： 1. **逻辑基础**：书中会介绍形式逻辑的基本概念，如命题逻辑、谓词逻辑以及蕴含、等价和推理规则，这些都是编程语言设计和形式验证的基础。 2. **集合论**：集合是所有数学结构的基础，学习集合的基本操作、子集、并集、交集和幂集等内容，有助于理解数据结构和算法的设计。 3. **图论**：图是计算机科学中用于表示关系和网络的通用工具，书里可能会涵盖图的基本概念、路径、环、树、图的遍历和最短路径算法等。 4. **组合数学**：包括排列、组合、二项式定理、帕斯卡定律等，这些在分析算法复杂性和计算可能性时非常有用。 5. **数论**：讨论整数的性质，如整除性、最大公约数、最小公倍数，以及欧几里得算法，这些对于密码学和编码理论等领域有重要应用。 6. **代数结构**：介绍群、环、域等基本的代数系统，它们在计算机科学的抽象数据类型和程序设计中扮演着角色。 7. **形式语言与自动机理论**：涉及正则表达式、有限状态自动机、上下文无关文法，这些在编译器设计和形式语法分析中至关重要。 8. **计算理论**：可能包含图灵机模型、计算复杂性理论和停机问题，这是理解计算能力极限的基础。 9. **概率论与统计**：虽然标签没有明确提及，但概率和统计知识在计算机科学的许多领域，如机器学习、数据挖掘和人工智能中不可或缺。 Gersting的这本书旨在将复杂的数学概念与实际计算机科学问题相结合，通过实例和练习帮助读者掌握这些概念，并将它们应用到实际问题中。它不仅适合大学计算机科学专业的学生，也适合任何希望加深对计算机科学底层原理理解的从业者。

Preface xv

for a proof, the complete proof is given. Otherwise, the answer is just

the answer, not necessarily the solution. A Student Solutions Manual with

solutions for odd-numbered exercises from the book is available from the

Web site at www.whfreeman.com/gersting. The student manual also in-

cludes two sample tests per chapter. A complete Solutions Manual is avail-

able to instructors from the publisher.

• Many new exercises have been added, particularly with an eye toward

pairing odd-numbered exercises with similar even-numbered exercises.

• Of course, student learning aids such as chapter objectives, practice prob-

lems, reminders, section reviews, and chapter reviews remain.

WEB SITE

Online Study Guide

A Web site for the book may be found at www.whfreeman.com/gersting. The Web

pages contain representative new example problems (not contained in the text) for

many of the end-of-section Techniques. Each Technique that has a corresponding

Web page example is marked with the icon

Each example on the Web rst states the problem. Then succeeding pages

develop the solution, much as the student would be expected to write it. As the stu-

dent navigates the pages, the solution unfolds step-by-step. A compressed audio

le is also part of each Web page after the initial problem statement. The audio le

contains a rst-person stream-of-consciousness thought process about that step of

the solution—why it occurred to the narrator to try this, why it looked promising,

what knowledge was being called on to suggest that this step should come next,

and so on. The point is, students see perfect and complete worked-out proofs in

the textbook and often see them performed by the instructor. Yet when a student

goes home and tries to produce such a solution by himself or herself, he or she is

unsure where to start or how to think about the problem or how to see any pat-

tern to enable a guess as to what to do next. Consequently the student gives up in

frustration. The purpose of the audio narration is to share the “secret picture” that

mathematicians use to solve problems.

To access the problems, after you go to www.whfreeman.com/gersting, select

a chapter section, then select a sample problem and follow its step-by-step process

with the “Next” button.

PowerPoint Slides

Instructors who visit the web site will also have access to PowerPoint slides

accompanying each section of the text.

xvi Preface

ACKNOWLEDGMENTS

My thanks to the reviewers of this addition, as well to reviewers of earlier edi-

tions, all of whose help is greatly appreciated.

Elizabeth Adams, James Madison University

Kemal Akkaya, Southern Illinois University

Charles Ashbacher, Mount Mercy College

Barnabas Bede, DigiPen Institute of Technology

Terry J. Bridgeman, Colorado School of Mines

David Casperson, University of Northern British Columbia

Adrienne Decker, SUNY Buffalo

Steve Donaldson, Samford University

Mordechai S. Goodman, Dominican University

Michael A. Gray, American University

Jerrold R. Griggs, University of South Carolina

Joseph Hobart, Okanagan College

Mark Jacobson, University of Northern Iowa

Lisa A. Jamba, University of Northern Florida

Tim Lin, Cal Poly

David Lugenbuhl, Western Carolina University

Damian Lyons, Fordham University

Mariana Maris, Arizona State University

Mikel D. Petty, University of Alabama in Huntsville

Amar Raheja, Cal Poly

J. Ben Schafer, University of Northern Iowa

Ali Shaykhian, Florida Institute of Technology

Shunichi Toida, Old Dominion University

William J. Weber, Southeast Missouri State University

Eric Westlund, Luther University

Hua Yan, Borough of Manhattan Community College

Yu Zhang, Texas A&M Corpus Christi

The folks at W.H. Freeman were very helpful in shepherding this edition

to completion, especially Penny Hull (veteran of many previous editions), Terri

Ward, Roland Cheyney, Liam Ferguson, Georgia Lee Hadler, and Vicki Tomaselli.

Thanks to Russell Kackley for the audio les on the Web site.

My deepest thanks go to my husband, John, ever my most ardent supporter

and dearest friend.

NOTE TO THE STUDENT

As you go through this book, you’ll encounter many new terms and new ideas.

Try reading with pencil and paper at hand and work the Practice problems as you

encounter them. They are intended to reinforce or clarify some new terminology

or method just introduced; answers are given at the back of the book. Pay atten-

tion also to the Reminders that point out common pitfalls or provide helpful hints.

Be sure to visit the Web site at www.whfreeman.com/gersting for detailed,

worked-out solutions to additional example problems tied to the Techniques in

each section. The Web site solutions are accompanied by audio les that explain

each step. A Student Solutions Manual with solutions for odd-numbered exercises

from the book is available from the Web site. The student manual also includes two

sample tests per chapter.

You may nd at rst that the thought processes required to solve the exercises

in the book are new and difcult. Your biggest attribute for success will be persever-

ance. Here’s what I tell my students: “If you do not see at rst how to solve a problem,

don’t give up, think about it some more; be sure you understand all the terminology

used in the problem, play with some ideas. If no approach presents itself, let it be

and think about it again later. Repeat this process for days on end. When you nally

wake up in the middle of the night with an idea, you’ll know you are putting in the

right amount of effort for this course.” Mathematical results don’t spring fully formed

from the foreheads of mathematical geniuses; well, maybe from mathematical ge-

niuses, but for the rest of us, it takes work, patience, false starts, and perseverance.

Enjoy the experience!

CHAPTER OBJECTIVES

After studying this chapter, you will be able to:

• Use the formal symbols of propositional logic.

• Find the truth value of an expression in propositional logic.

• Construct formal proofs in propositional logic, and use such proofs to deter-

mine the validity of English language arguments.

• Use the formal symbols of predicate logic.

• Find the truth value in some interpretation of an expression in predicate logic.

• Use predicate logic to represent English language sentences.

• Construct formal proofs in predicate logic, and use such proofs to determine

the validity of English language arguments.

• Understand how the programming language Prolog is built on predicate logic.

• Mathematically prove the correctness of programs that use assignment state-

ments and conditional statements.

You have been selected to serve on jury duty for a criminal case. The attorney for the

defense argues as follows:

If my client is guilty, then the knife was in the drawer. Either the knife was not in the

drawer or Jason Pritchard saw the knife. If the knife was not there on October 10,

it follows that Jason Pritchard did not see the knife. Furthermore, if the knife was

there on October 10, then the knife was in the drawer and also the hammer was in

the barn. But we all know that the hammer was not in the barn. Therefore, ladies

and gentlemen of the jury, my client is innocent.

Question: Is the attorney’s argument sound? How should you vote?

It’s much easier to answer this question if the argument is recast in the notation

of formal logic. Formal logic strips away confusing verbiage and allows us to

concentrate on the underlying reasoning being applied. In fact, formal logic—the

subject of this chapter—provides the foundation for the organized, careful method

of thinking that characterizes any reasoned activity—a criminal investigation, a

scientic experiment, a sociological study. In addition, formal logic has direct

applications in computer science. The last two sections of this chapter explore

a programming language based on logic and the use of formal logic to verify

the correctness of computer programs. Also, circuit logic (the logic governing

Formal Logic

Chapter

2 Formal Logic

computer circuitry) is a direct analog of the statement logic of this chapter. We

will study circuit logic in Chapter 8.

SECTION 1.1 STATEMENTS, SYMBOLIC REPRESENTATION,

ANDTAUTOLOGIES

Formal logic can represent the statements we use in English to communicate facts

or information. A statement (or proposition) is a sentence that is either true or

false.

EXAMPLE 1 Consider the following:

a. Ten is less than seven.

b. Cheyenne is the capital of Wyoming.

c. She is very talented.

d. There are life forms on other planets in the universe.

Sentence (a) is a statement because it is false. Sentence (b) is a statement because

it is true. Sentence (c) is neither true nor false because “she” is not specied; there-

fore (c) is not a statement. Sentence (d) is a statement because it is either true or

false; we do not have to be able to decide which.

Connectives and Truth Values

In English, simple statements are combined with connecting words like and to

make more interesting compound statements. The truth value of a compound

statement depends on the truth values of its components and which connecting

words are used. If we combine the two true statement, “Elephants are big,” and,

“Baseballs are round,” we would consider the resulting statement, “Elephants are

big and baseballs are round,” to be true. In this book, as in many logic books,

capital letters near the beginning of the alphabet, such as A, B, and C, are used to

represent statements and are called statement letters; the symbol

` is a logical

connective representing and. We agree, then, that if A is true and B is true, A

` B

(read “A and B”) should be considered true.

PRACTICE 1

a. If A is true and B is false, what truth value would you assign to A ` B?

b. If A is false and B is true, what truth value would you assign to A

` B?

c. If A and B are both false, what truth value would you assign to A

` B?

The expression A

` B is called the conjunction of A and B, and A and B are

called the conjuncts of this expression. Table 1.1 summarizes the truth value of

` B for all possible truth values of the conjuncts A and B. Each row of the table

Answers to practice problems are in the back of the text.

Section 1.1 Statements, Symbolic Representation, andTautologies 3

represents a particular truth value assignment to the statement let-

ters, and the resulting truth value for the compound expression is

shown.

Another connective is the word or, denoted by the symbol

. The

expression A

B (read “A or B”) is called the disjunction of A and B,

and A and B are called the disjuncts of this expression. If A and B are

both true, then A

B would be considered true, giving the rst line

of the truth table for disjunction (Table 1.2).

TABLE 1.2

A B A

T T T

T F

F T

F F

TABLE 1.1

A B A

` B

T T T

T F F

F T F

F F F

PRACTICE 2 Use your understanding of the word or to complete the truth table for disjunction,

Table 1.2.

Statements may be combined in the form “if statement 1, then statement 2.” If

A denotes statement 1 and B denotes statement 2, the compound statement would

be denoted by A S B (read “A implies B”). The logical connective here is implica-

tion, and it conveys the meaning that the truth of A implies or leads to the truth of

B. In the implication A S B, A stands for the antecedent statement and B stands

for the consequent statement.

The truth table for implication is less obvious than that for conjunction or

disjunction. To understand its denition, let’s suppose your friend remarks, “If I

pass my economics test, then I’ll go to the movie Friday.” If your friend passes the

test and goes to the movie, the remark was true. If your friend passes the test but

doesn’t go to the movie, the remark was false. If your friend doesn’t pass the test,

then—whether he or she goes to the movie or not—you could not claim that the

remark was false. You would probably want to give the benet of the doubt and say

that the statement was true. By convention, A S B is considered true if A is false,

regardless of the truth value of B.

PRACTICE 3 Summarize this discussion by writing the truth table for A S B.

TABLE 1.3

A B A S B B S A (A S B)

` (B S A)

T T T T T

T F F T F

F T T F F

F F T T T

The equivalence connective is symbolized by 4. Unlike conjunction,

disjunction, and implication, the equivalence connective is not really a funda-

mental connective but a convenient shortcut. The expression A 4 B stands for

(A S B)

` (B S A). We can write the truth table for equivalence by constructing,

one piece at a time, a table for (A S B)

` (B S A), as in Table 1.3. From this truth

table, A 4 B is true exactly when A and B have the same truth value.

The connectives we’ve seen so far are called binary connectives because

they join two expressions together to produce a third expression. Now let’s consider

a unary connective, a connective acting on one expression to produce a second

剩余985页未读，继续阅读

soahCChaos

粉丝: 0
资源: 4

计算机科学的数学结构：离散数学及其应用

yolov5s nnie.zip

基于uni-app+uview-ui开发的校园云打印系统微信小程序项目源码+文档说明

使用Java写的一个简易的贪吃蛇小游戏.zip

计算机网络概述.docx

数学建模学习资料 姜启源数学模型课件 M06 稳定性模型 共46页.pptx

【IEA-2024研报】到2030年满足中国电力系统灵活性需求（英）.pdf

游戏账号交易小程序 微信小程序+SSM毕业设计 源码+数据库+论文+启动教程.zip

结合 Swin Transformer 的小物体检测算法用于茶芽检测.zip

有关如何在您自己的网站的任何位置添加 Google 一键注册的演示.zip

java毕设项目之基于SpringBoot的德百商城停车场管理系统(源码+说明文档+mysql).zip

最新资源

数学建模学习资料姜启源数学模型课件 M06 稳定性模型共46页.pptx

游戏账号交易小程序微信小程序+SSM毕业设计源码+数据库+论文+启动教程.zip