### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# DISCRETE STRUCTURES II CS 251

PSU

GPA 3.91

### View Full Document

## 22

## 0

## Popular in Course

## Popular in ComputerScienence

This 39 page Class Notes was uploaded by Orrin Rutherford on Wednesday September 2, 2015. The Class Notes belongs to CS 251 at Portland State University taught by Staff in Fall. Since its upload, it has received 22 views. For similar materials see /class/168295/cs-251-portland-state-university in ComputerScienence at Portland State University.

## Reviews for DISCRETE STRUCTURES II

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/02/15

Errata for Discrete Structures Logic and Computability Second Edition This is the errata of Discrete Structures Logic and Computability Second Edition The errata corrects typos errors and clarifies some of the exposition Note The brackets that precede each item indicate the printings in Which the errata occur Preface 1 Page V line 13 Move the question Can the problem be solved by a computer program onto a line by itself like the other four questions 1 Page V lines 18 to 22 The left margin of this paragraph should line up with the text above it Also don39t indent the first line Contents 1 Page x line 3 Delete an from Recalling an English Grammar 1 Page xiii line 1 Insert U1 after Universal Instantiation Chapter 1 1 Page 7 line 8 Replace 25 by 27 so the list looks like quot6 11 18 27 38 51quot 1 2 Page 8 line 10 The italic contrapositve is misspelled and should be contraposttwe 1 2 Page 14 lines 10 to 12 Delete this paragraph of two sentences An important characteristic occurrences of the letter L 1 2 Page 14 lines 3 to 6 Replace these four lines with the following text It follows from the definition of equality that there is no particular order or arrangement of the elements in a set For example since u g h and h u g have the same elements we have Ln g h h u g It also follows that there are no repeated occurrences of elements in a set For example since h u g h and h u g have the same elements we have h u g h in u g So h u g h u g h and h u g are different representations of the same set 1 2 Page 22 line 12 In Example 114 replace x E N with x E Z 1 Page 31 line 15 Exercise 2c should have 9 included in the set so it looks like quot1 4 9 16 25 36 49 64quot 1 Page 31 line 5 Exercise 6e should be blue color 1 Page 44 line 5 Insert space between uppercase lambda and or In other words replace quotAorquot with quotA orquot 1 Page 45 line 7 Delete space between Q and ie replace quotQ quot with girl 1 2 Page 46 line 4 Change ternary operation on to ternary relation on 1 2 Page 50 line 8 The third line of the displayed equations is missing an absolute value brace I at the right end In other words replace I a c d with a c d5 1 Page 53 line 15 Change Exercise 11c from a b c 1 b to a b c a Chapter 2 1 2 Page 80 line 4 Change divisiors to divisors 1 2 Page 87 line 13 5 lines below the box Replace the two sentences At this point we re stuck for an exact answer But we can make an estimate With the single sentence Now we can easily estimate the value of the expresson 1 Page 88 line 12 Change Exercise 6c from 15 mod 12 to 12 mod 15 1 Page 88 line 12 Change Exercise 6d from 15 mod 12 to 21 mod 15 1 2 Page 90 line 9 In exercise 20c change ab mod n to 1 mod n ab mod n 1 2 Page 96 line 12 Change a comma to a decimal point Change mapfloor 1 5 to mapfloor 15 1 2 Page 97 line 16 3rd line above quotend examplequot There is a missing left parenthesis Change 2 maplt0 0 1 1 2 2 to maplt0 0 1 1 2 2 1 2 Page 99 line 16 last line of exercise 6 Replace five binary With four binary 1 Page 100 line 11 Change Proofs to boldface With no color 1 2 Page 101 line 10 Change f35 f3 to f35 f36 1 2 Page 104 line 16 In the equation change nq1 nq2 to nq1 r12 1 2 Page 106 line 4 Replace how wrap With how to wrap 1 2 Page 107 line 3 Replace the sentences ls f a bij ection Yes because f has type N26 gt N26 With the following sentence It follows from 26 that f is a bijection of type N26 gt N26 1 2 Page 107 line 16 Replace abut with about 1 2 Page 107 line 4 Change quotM Aquot to quotA M 1 2 Page 107 line 1 Change quot3x 5 mod 26quot to quot3x 15 mod 26 1 2 Page 108 line 3 Change quot9x 7 mod 26quot to quot9x 21 mod 26quot 1 2 Page 111 line 16 Change g n 1 to gcdg n 1 1 Page 113 line 2 In Exercise 10 change 0 to 26 to 0 to 25 1 2 Page 114 line 17 In Exercise 13 change N7 to N8 1 Page 115 line 3 In Exercise 20 change 16 to prove to 19 to prove 1 Page 117 line 10 Replace Therefore fs is with Therefore fS is 1 2 Page 124 line 8 In Exercise 1a replace 5 100 by S 98 1 Page 124 line 1 Delete the period to the right of the first right brace Chapter 3 1 2 Page 131 line 3 from bottom of example There is a missing equals sign The line should look like the following 1 0 U 0 Q U 0 0 1 2 Page 136 line 8 Replace of this with of these 1 2 Page 141 line 12 Change the sentence by adding a phrase at the end so the sentence reads as follows So the area A can be described as the following set ofpoints where a b E N and f N gt N 1 Page 143 line 5 In Exercise 6e replace n E N with m n E N 1 2 Page 147 line 12 Replace f0 1 With f0 0 1 2 Page 150 line 10 Replace popular With the popular 1 2 Page 155 line 13 Replace difinition With definition 1 2 Page 156 line 5 In the right side of the equation replace 1 With 2 1 2 Page 166 line 9 Replace is is With it is 1 Page 168 line 4 In Exercise 4c replace the line With the following line quotc fk n gcd1 n gcd2 n gcdk n for k gt 0quot 1 Page 180 line 15 The letter M should be italic 1 Page 180 lines 1 1 13 and 14 These lines contain the symbols gt or gt Remove the space in each occurrence to obtain gt or gt and insert a space to the right of each or For example replace quotgt wquot With quotgt wquot 1 Page 181 line 7 Replace quotgt ayquot With quotgt ayquot 1 Page 181 line 9 Replace quotgt abyquot With quotgt ayyquot 1 2 Page 189 line 13 In Exercise 4b replace n E N With m n E N 1 2 Page 191 line 8 In Exercise 15b change b gt b I bB to B gt b I bB Chapter 4 1 2 Page 197 line 1 In the title of box 41 replace the word Relation With its plural Relations 1 2 Page 203 lines 3 and 4 Replace the sentence For example ifR a a b b a b a c then Std NR a a b b a b a C b a C a with the sentence For example if R a a b b c c a b b c then you can verify that stR tsR 1 2 Page 219 line 5 Replace proptery with property 1 2 Page 226 line 16 Replace might a set with might be a set 1 Page 228 line 3 4 and 15 Decrease the space to the right of the union symbol ie center the union symbol between its two arguments 1 2 Page 229 line 7 In last line of example replace treee with tree 1 2 Page 238 several lines The symbol Q in five places on this page for rational numbers is the wrong font It should be the same font as introduced on page 15 The same problem occurs on page 569 1 2 Page 243 line 19 Remove the period at the end of the quoted question 1 2 Page 247 line 9 Insert the phrase if no two elements are defined in terms of each other at the end the first sentence So the new first sentence should read It s easy to make an inductively defined set into a wellfounded set if no two elements are defined in terms of each other 1 2 Page 255 line 10 Replace natural numbers n with natural numbers n 2 1 1 Page 268 line 16 Exercise 10a should be blue color 1 2 Page 269 line 9 Replace 22b with 22a and 22b 1 2 Page 269 line 10 Replace l lt gt with L lt gt Chapter 5 1 Page 282 line 8 Change Summation Fact to Summation Facts 1 Page 282 line 4 In 52a Change 2 to i 1 11 1 Page 282 line 2 In 52c change the lower limit of the summation from i1 t0i 0 1 Page 286 lines 7 and 8 Replace sentence and phrase There are no operations for n 0 If n gt 0 then there are n 1 addition operations and with the following phrase There are n addition operations and 1 Page 286 line 9 Replace operations for n gt 0 is given by with quotoperations is given byquot 1 Page 286 lines 11 12 and 13 Replace these three displayed lines with the following three lines 7 n012n n2 n n 2 r723n 2 1 Page 286 line 15 Replace 494 with 495 1 Page 294 line 13 In box 58 the term at the right end of the equation contains the term n r in the denominator It should be n r Here is the proper equation with the correct term on the right Pn r n C n r H H n r 1 Page 298 line 9 Replace quotbe bit trickyquot with quotbe a bit trickyquot 1 2 Page 308 line 10 Replace Frst with First 1 Page 311 line 7 In exercise 15 replace home after 6 pm with home by 6 pm 1 Page 311 line 10 In exercise 18c change quotwith four of to quotwith four or five of 1 2 Page 319 line 6 Replace closed from with closed form n a 1 2 Page 322 line 2 In the first summation change ULon to an4xn 1 2 Page 322 line 3 Change the lower limit in the first summation from n 0 to n 2 so the line looks like the following I n x 52 anilx 62a izx quot2 quot2 1 2 Page 323 line 11 Change the minus between the two expressions to a plus so that the line looks like the following 1 ut into form i 1 2x 1 3x p 1quot 1 2 Page 327 line 17 Change from 1 to k 1 to from 1 to n 1 Chapter 6 1 2 Page 350 line 14 On the line Punctuation symbols eliminate the period and eliminate the space before the comma 1 2 Page 353 line 3 start counting above the gure Change spelling of contraditions as contradictions 1 2 Page 355 line 8 Replace to old with to the old 1 Page 354 below quotFigure 65quot In quotBasic Equivalences 61quot move 61 to the right margin 1 Page 368 line 14 In Exercise 10c replace quot B quot with quotB quot so the formula becomes quotA v B A A gt Bquot 1 2 Page 370 line 2 Replace required and we ll discuss them next with required inference rules and aXioms We ll discuss them next 1 2 Page 372 line 3 Replace quotthe way we reason informallyquot with quotthe natural way that we reasonquot 1 Page 372 line 1 Replace quotallows us provequot with quotallows us to provequot 1 Page 386 lines 8 to 13 the six line proof Delete the 4th line of the proof and replace the last two lines as follows 4 A gtB gtA gtB 23MP 5 A gt B 1 4 MP So the result should be the following five line proof 1 Proof of A gt B Induction 2 Proof of A gt B gt Bk Induction 3 A gt B gt B gt A gt Bi gt A gt B Axiom 2 4 A gtBi gtA gtBk 2 3MP 5 A gt Bk 1 4 MP 1 2 Page 388 line 10 in Example 618 Replace QED 1 3 CP With QED In other words delete 1 3 CP 1 2 Page 390 line 1 Replace A gt B W with A gt B 2 WV Chapter 7 1 2 Page 402 line 11 On the line Punctuation symbols eliminate the space before the comma and add a comma followed by a quoted comma at the end of the line ie change to 1 2 Page 405 line 6 After the sentence The expression xt is called a substitution insert the following new sentences We should note that in Chapter 9 we ll say that xt is a binding and a set of bindings with certain properties is a substitution But for now it s convenient to just call xt a substitution 1 2 Page 405 line 10 Change Wx y to Wxy 1 Page 410 lines 14 to 18 the paragraph beginning with quotIndirect approachquot Add some white space after the end of this paragraph in the same way that there is white space above and below the quotDirect approachquot paragraph 1 Page 410 line 1 Add the following sentence to the end of the paragraph quotThe proofs of 72a 72d are left as exercisesquot 1 Page 412 line 13 second line of proof Replace quotvariable of Wquot with quotvariable in a wff Wquot 1 2 Page 413 lines 1 to 4 Replace these four lines with the following sentence The proof of part 2 is similar to that of part 1 and we ll leave it as an exercise QED 1 Page 416 line 11 Do not indent the beginning paragraph of Section 72 1 Page 417 line 14 Replace quotpqa qb falsequot with the following quotpa pb true and qa qb falsequot 1 Page 418 line 12 Replace quot p0 A p1quot with quot p0 v p1quot so that the line looks like the following quot5 P0 V P1 V P2 V quotP3quot 1 Page 420 line 3 Replace the phrase quotthe following equivalence to distribute an existential quantifer over disjunctionquot with the phrase quotthe following equivalencesquot 1 Page 420 lines 1 and 2 Replace the twoline box with the following threeline box Distributing the Quantifiers 77 a 396 x v qx E 3xpx v 396 qx b Vx x A qx E prx A Vx qx 1 Page 421 line 1 Replace quotProofquot with quotProof of 77aquot 1 Page 421 line 4 Insert the following sentence after line 4 Proof of 77b Use the fact that Vx px A qx E 396 px v qx and then apply 77a QED 1 Page 423 line 1 Delete the quot quot from this formula So the line should be as follows E C A 3xAx 1 2 Page 424 lines 12 to 15 Replace the text A wff Wis in prenex normal form if all its quantifiers are on the left of the expression In other words a preneX normal form looks like the following leI ann M WITH A wff Wis in prenex normal form if it has the following form W lel ann M 1 Page 425 line 5 Replace quotCz y gt Vw Awquot with quotCz y v Vw Awquot so that the line looks like the following quota V2 Ely Ax A Bz gt Cz y v Vw Aw 74quot 1 2 Page 427 line 8 There are two occurrences of 33 on this line Delete the rightmost one ie replace Ely Cz y with Ely Cz y 1 Page 429 line 14 fomula 7 in the box of equivalences Add quot77quot at the right margin of this line In other words the last line in the box should be as follows 7 Vx Ax A Bx E Vx Ax A Vx Bx 77 1 Page 430 Exercise 3 Make replacements in each of the four parts as follows In 3a replace quotuse 77aquot with quotuse 710aquot In 3b replace quotuse 77bquot with quotuse 710bquot In 3c replace quotuse 77bquot with quotuse 710bquot In 3d replace quotuse 77bquot with quotuse 710bquot 1 2 Page 433 lines 5 to 7 Replace the sentence We say that the term t is free to replace x in Wx if either no variable of t occurs bound to a quantifier in Wx or 96 does not occur free within the scope of a quantifier in Wx WITH We say that a term t is free to replace x in Wx if for each variable oft that occurs bound to a quantifier in Wx 96 does not occur free within the scope of the quantifier 1 2 Page 436 line 3 Replace use same wff with use the wff 1 2 Page 437 line 1 1 The title of the box needs EG so that the line becomes Existential Generalization Rule EG 716 1 2 Page 437 lines 2 to 4 Delete the phrase This means as always that we must be able to write the wff in the form Wx for some variable x and attach the rest of the phrase to the end of the preceding sentence Then add the following new sentence In other words we must have Wt Wx xt With these changes the Usage Note at the bottom of page 437 should look like the following There is a kind of forwardbackward reasoning to keep in mind when using the EG rule Ifwe want to apply EG to a wff then we must be able to write the wff in the form Wt for some term t such that Wt is obtained from Wx by replacing all free occurrences of xby t In other words we must have Wt Wxxt Once this is done we check to see whether tis free to replace x in Wx 1 2 Page 439 line 13 Replace quot2 Proposed EI rule with quot1 Proposed EI rule 1 2 Page 439 line 14 Replace quot3 Proposed EI rule with quot2 Proposed EI rule 1 2 Page 439 line 15 Replace quot4 5 Conjquot With quot3 4 Conj 1 2 Page 439 line 8 The title of the box needs El so that the line becomes Existential Instantiation Rule El 717 1 Page 440 line 6 Replace quotSince y does not occur in Aquot With quotSince y does not occur in P A 396 Wx or Aquot 1 2 Page 441 line 16 On line 5 of the proof replace 3 EG With 4 EG 1 Page 442 lines 19 and 20 Replace the sentence in box 719 With the following sentence Conditional Proof Rule CP 719 IfA is a premise in a proof of B then there is a proof ofA gt B that does not use A as a premise 1 Page 442 line 18 to page 443 line 14 Replace the entire proof with the following proof Proof Let W1 Wn B be a proof of B that contains A as a premise We ll show by induction that for each k in the interval 1 S k S n there is a proof ofA gt Wk that does not use A as a premise Since B 2 Wu the result will be proved For the case k 1 the argument is the same as that given in the proof of the CP rule for propositional calculus Let k gt 1 and assume that for each i lt k there is a proof of A gt that does not use A as a premise If Wk is not inferred by a quantifier rule then the argument in the proof of the CP rule for propositional calculus constructs a proof ofA gt Wk that does not use A as a premise The construction also guarantees that the premises needed in the proof ofA gt Wk are the premises other than A that are needed in the original proof of Wk Suppose that Wk is inferred by a quantifier rule from W where i lt k First notice that if A is not needed to prove Wi then A is not needed to prove Wk So we can remove A from the given proof of Wk Now add the valid wff Wk gt A gt Wk to the proof and then use MP to infer A gt Wk This gives us a proof of A gt Wk that does not use A as a premise Second notice from the proof of the El rule 717 that for any proof that uses El there is an alternative proof that does not use El So we can assume that A is needed in the proof of and El is not used in the given proof If infers Wk by UG then Wk 2 Vx Wi where x is not free in any premise needed to prove So x is not free in A Induction gives a proof ofA gt that does not use A as a premise and x is not free in any premise needed to prove A gt So we can use UG to infer Vx A gt Since 96 is not free in A it follows from 712a that Vx A gt gt A gt Vx is valid Now use MP to infer A gt Vx So we have a proof ofA gt Wk that does not use A as premise If infers Wk by Ul then there is a wff Cx such that Vx C96 and Wk 2 Ct where t is free to replace x in Cx The proof of the U1 rule tells us that Vx Cx gt Ct is valid Induction gives a proof ofA gt Vx Cx that does not use A as a premise Now use HS to infer A gt Ct So we have a proof ofA gt Wk that does not use A as premise If infers Wk by EG then there is a wff Cx such that Ct and Wk 2 3x Cx where t is free to replace x in Cx The proof of the EG rule tells us that Ct gt 396 Cx is valid By induction there is a proof ofA gt Ct that does not use A as a premise Now use HS to inferA gt 396 Cx So we have a proof of A gt Wk that does not use A as premise QED 1 Page 448 Example 729 Replace the entire content of this example with the following lines We ll give a proof of the validity of the following wff Vx Ax v Vx Bx gt Vx Ax v Bx Proof 1 Vx Ax v Vx Bx P 2 Vx Ax P 3 Ax 2 U1 4 Ax v Bx 3 Add 5 Vx Ax v Bx 4 UG 6 Vx Ax gt Vx Ax v Bx 2 5 CP 7 Vx Bx P 8 Bx 7 U1 9 Ax v Bx 8 Add 10 Vx Ax v Bx 9 UG 11 Vx Bx gt Vx Ax v Bx 7 10 CP 12 Vx Ax v Bx 1 6 11 CD QEDl 12 CP 1 Page 449 line 14 In Example 731 replace the sentence quotThe converse of the wff in Example 729 is the following wffquot with quotSuppose we39re given the following wffquot 1 Page 451 line 6 Add quotEGquot after quotExistential Generalization Rulequot 1 Page 454 line 14 Exercise 9 Insert the boldface subtitle Equivalences before Exercise 9 1 Page 454 line 11 In exercise 11 put a comma at end of the line that contains the formula quotA quot Chapter 8 1 2 Page 461 line 6 Change letters t u and 0 denote to letters tand u denote 1 2 Page 461 line 3 Change the rightmost to gt so that the right portion of the line looks like POL tk gt PU1 Mk 1 Page 462 lines 1 to 5 and page 463 lines 1 to 4 In Example 83 the lines of the proof numbered 1 through 9 should have the formulas indented So the proof should look like the following Proof 1 xxx P 2 x x EA 3 xx xx x 12EE 4 x x x x x x AssociatiVity 5 x x x x x 3 4 TransitiVity 6 x x 0 Property of 7 x 0 0 5 6 EE 8 x x 0 Property of 0 9 x 0 7 8 TransitiVity 10 xxx gtx0 19CP 11 Vxxxx gtx0 10 UG QED 1 Page 462 lines 1 to 4 On each of these lines remove the space between the negative sign and x In other words replace quot xquot with quot xquot 1 2 Page 464 lines 5 and 6 Replace the two lines 4 xlty gt xSy 13 CP QED with the single line QED 1 3 CP 1 2 Page 464 lines 10 and 11 Replace the two lines 4 xlty gt xSy 13 CP QED with the single line QED 1 3 CP 1 2 Page 466 line 13 Exercise 8b Replace that that with that 1 2 Page 469 line 1 In the display for 811 remove the comma at the end of the numerator in the rightmost expression 1 Page 472 lines 5 and 2 On each of these lines remove the space between the negative sign and x In other words replace quot xquot with quot xquot 1 Page 473 line 2 Remove the space between the negative sign and x In other words replace quot xquot with quot xquot 1 2 Page 476 lines 10 and 11 Replace quota 2 0 A b gt 0quot with quota gt 0 A b 2 0 1 Page 477 line 8 Replace quot11 14 IPquot with quot12 14 IPquot 1 Page 477 line 3 Replace quotConseq Compquot with quotComp Conseqquot 1 Page 477 lines 1 to 18 It looks as though the lines numbered 7 to 21 should be moved left a bit so that the line numbers align with the line numbers numbered 1 to 6 1 Page 490 lines 9 to 12 In exercise 19 the left ends of the four displayed lines should be aligned 1 Page 495 line 13 Remove the space between S and comma ie replace HS 1 HS 1 2 Page 500 line 3 Change indivdual to individual Chapter 9 1 Page 509 line 12 Remove space between quotCquot and quot361 xk yquot 1 Page 509 line 8 Replace quotAd1 dk equot with quotCdl dk equot 1 Page 509 line 6 Replace quotAd1 dk equot with quotCdl dk equot 1 2 Page 511 line 4 Change pavq to pa v q 1 Page 516 lines 21 and 22 On the last two lines of Example 96 remove the space between fy and comma and between fb and comma 1 2 Page 516 line 21 Remove redundant parentheses Change 17 Jay Z a U p x y z a a 1 2 Page 517 line 11 Change unifer to unifier 1 2 Page 518 line 2 Change in the numerator to in any numerator 1 Page 520 line 5 Replace the sentence quotEither a most general unifier or a statement that the pair is not unifiablequot with quotEither a most general unifier of A and B or a statement that they are not unifiablequot 1 2 Page 522 line 10 Replace the first word of the second sentence Let with Since there could be additional occurrences of N in C B we ll let 1 Page 527 line 13 On line 2 of the proof replace quotpv wquot with quot pv wquot In other words the line should look like quot2 puvvquotpvwvpuw P39 1 Page 527 line 16 On line 5 of the proof replace quotpv xquot with quot pv xquot In other words the line should look like quot5 px v v pv x 1 2 R Ltx wx quot 1 Page 527 line 18 On line 7 of the proof replace quot4 7 R quot with quot4 6 R quot 1 Page 531 line 7 Remove the space between Band 0 In other words replace quot0 a with quot60 19 1 Page 536 lines 1 7 and 10 On each of these three lines there is a double word Replace quotunifier unifierquot With quotunifierquot 1 2 Page 538 line 1 Replace there a proof With there is a proof 1 Page 543 line 7 Replace quotgrandparent of aquot With quotgrandparent of cquot 1 Page 549 line 8 Change the title of Example 923 from quotTransitive Closurequot to quotAcyclic Transitive Closurequot 1 Page 549 lines 7 to 5 Delete the sentence quotSo we39ll discussof a binary relationquot 1 Page 549 line 5 Replace the phrase quotbinary relation r andquot With the phrase quotbinary relation r Whose graph is acyclic ie there are no cycles andquot Chapter 10 1 Page 560 line 10 Change quotRecall thatquot With quotNote thatquot 1 2 Page 569 several lines The symbol Q in three places on this page for rational numbers is the wrong font It should be the same font as introduced on page 15 The same problem occurs on page 238 1 2 Page 571 lines 20 to 24 In each of the parts a b c and d remove the phrase for 0 1 Page 572 line 2 Reduce the length of the overbar quotquot to about quotquot 1 Page 573 line 13 Replace the missing right parenthesis In other words replace quotdo it lastquot With quotdo it lastquot 1 2 Page 581 line 10 Replace Hz with quotXYZ 1 2 Page 581 line 10 Replace X72 With XYZ 20 1 2 Page 584 line 12 Exercise 5f Replace this exercise with the following f xy 2X y7 x 2 1 2 Page 584 line 8 Exercise 9 Replace a b with E 1 Page 586 line 1 Remove space between sx and comma 1 Page 587 line 3 Remove space between ss0 and comma 1 Page 587 line 4 Remove space between 30 and comma 1 Page 587 line 10 Remove space between sx and comma 1 Page 587 line 16 Remove space between sx and comma 1 Page 587 line 16 Remove space between mult0 4 and comma 1 Page 587 lines 19 to 23 On each of these lines there is a comma with too much preceding space Remove it 1 Page 587 line 3 Remove space between px and comma 1 Page 587 line 1 Remove space between px and comma 1 Page 589 line 10 Remove space between succx and comma 1 Page 589 line 12 Remove space between succx and comma 1 Page 589 line 16 Remove space between predx and comma 1 2 Page 593 line 15 Replace Then b and c are with Then c and b are 1 2 Page 593 line 14 Replace Finally a and b c are with Finally b c and a are 1 2 Page 593 line 1 Replace the arguments a and b with z and y so that the equation becomes the following evalop pushz pushy stk pushvaly Op 2 stk 1 Page 601 lines 4 and 5 On each of these lines remove space between px 21 and comma 1 2 Page 602 Figure 1011 Change Classooms to Classrooms 1 2 Page 604 Figure 1012 In the left figure the word Satelllite should be spelled Satellite 1 2 Page 605 line 13 Replace projectjoinRooms Schedule Dept Course Section With projectselectjoinRooms Schedule Computer Yes Dept Course Section 1 Page 608 line 18 Replace the missing right parenthesis In other words replace quotGg g hlquot wit quot with quotGg f g hquot 1 Page 608 line 13 Add the statement quoteg 2 a b c bquot to the end of this line so that the line becomes the following quot1 2 selectors eg 2 a b c bquot 1 Page 611 lines 5 and 6 In Exercises 1d and 1e change projects to project 1 Page 614 line 13 Replace quotklquot With quotklnquot In other words this line should look like the following quotac 2 bd bl kd klnnquot 1 2 Page 619 line 4 Replace choose d 19 With choose d 23 1 2 Page 619 lines 6 and 7 Replace Which becomes 19e mod 221 1 Since gcd19 221 1 With Which becomes 23e mod 192 1 Since gcd23 192 1 1 2 Page 619 line 8 Replace 1 19e 2213 With 1 23g 1923 1 2 Page 619 line 9 Replace gcd19 221 With gcd23 192 22 1 2 Page 619 lines 11 to 15 Replace these five lines with the following three lines 192223 3988 2328 3927 8711 1 2 Page 619 line 17 Replace the fifth equation with the third equation 1 2 Page 619 line 18 Replace 2 5 7 and 12 with 7 and 8 1 2 Page 619 lines 19 to 27 Replace these nine lines with the following five lines 1 8 71 2 8 23 8 2 1 8 3 23 1 2 192 23 8 3 23 1 23251923 1 2 Page 619 lines 28 to 37 ie lines 10 to 1 Replace these last ten lines of the example with the following lines Therefore 1 23 39 25 mod 192 But we can t choose e to be 25 because e must be positive This is no problem because we can add any multiple of 192 to 25 For example let e 192 25 167 We ll verify that this value of e works de mod 192 23 39167 mod 192 23 39192 25 mod 192 23 39192 mod 192 23 39 25 mod 192 mod 192 0 1 mod 192 1 Therefore the public key is e n 167 192 and the private key dis 23 Chapter 11 1 2 Page 649 line 1 Delete the phrase into a DFA or an NFA from the sentence 23 1 2 Page 659 line 5 Replace useful represent with useful to represent 1 Page 661 line 17 Put space around quotquot so the quotHeadTailquot is changed to quotHead Tailquot 1 Page 661 line 20 Remove space between quotquot and quotaquot so the line looks like quotlt accepta a a b quot 1 Page 663 line 2 Put space around quotquot so the quotHeadTailquot is changed to quotHead Tailquot 1 Page 664 line 3 Remove space between quotquot and quotaquot and remove space between quotquot and quotquot so the line looks like quotlt accepta b a aquot 1 Page 678 line 13 Reduce space between quotEquot and quotquot 1 Page 689 line 9 Replace quotto the final statequot with quotto a final statequot 1 Page 690 line 5 The letter quotZquot should be italic quotzquot 1 2 Page 690 line pumping lemma box Delete the phrase over the alphabet A from the first sentence 1 2 Page 690 line pumping lemma box In the second sentence replace the phrase such that for any string 3 E L where I sl 2 In there exist strings x y z E 14 where y 95 A such that s xyz lxyl S m and xykz E L for all k 2 0 with the phrase such that for any string 3 E L with Isl 2 In there exist strings x y and 2 such that s nyz y A lxyl S m and xykz E Lfor all k 2 0 1 Page 693 line 14 Exercise 1h Remove the space between quotquot and quotquot 1 Page 693 line 6 Exercise 3b Replace quotofquot with quotthat isquot Chapter 12 24 1 Page 698 line 9 There is a missing A in quotS gt I aSbquot The expression should look like quotS gt A I aSbquot 1 Page 699 line 8 Change quotwith the productionquot to quotwith the two productionsquot 1 Page 707 line 8 Remove extra space in quotA to obtain quotAquot 1 Page 713 line 13 Replace quotquot by quotquot in quotpathk at X Yquot to obtain quotpathk a tX Yquot 1 Page 715 line 12 Change the misspelled subtitle Pushdowm Automata to Pushdown Automata 1 Page 719 line 16 Replace quotgt aAbquot with quotgt aABquot 1 Page 729 line 6 Remove space between quotwquot and quotquot 1 Page 732 line 2 Remove space between quotbquot and quotquot 1 Page 738 in Figure 122 The rows labeled 3 and 9 have larger height than the others All rows of the table should be the same height 1 Page 743 line 9 Replace quotpush statejquot with quotpush a and statejquot 1 Page 745 line 11In exercise 6b insert space between quotaSBquot and quot I quot 1 Page 746 line 1 Center the union symbol quotUquot between the two sets 1 Page 746 line 7 Replace quotabquot with quotabbquot so that the line looks like the following quotB gt aBbb I abbquot 1 Page 749 line 10 Remove the period after quotATAquot Chapter 13 1 Page 772 lines 8 16 19 20 22 and 23 On these lines put a space on either side of each occurrence of quotquot For example change quotHeadTailquot to 25 quotHead Tailquot 1 2 Page 778 line 6 Replace quotthe thequot with quotthequot 1 2 Page 779 line 5 of box in Figure 133 Delete the comma at the end of addx 0 x 1 2 Page 779 line 3 Change spelling of compostion to composition 1 2 Page 780 line 5 of Example 1312 Replace quotnotEqx y 1 0quot with quotnotEqx y 1 0quot 1 Page 780 line 12 Inpart 3 ofExample 1312 replace quotfx y miny with quotfx y minzquot 1 2 Page 782 line 10 Replace number in with number is in 12 Page 784 lines 4 and 5 Delete the sentence quotSo a Post algorithm computes a function from 14 to Aquot 12 Page 784 lines 7 Replace the sentence quotA variable Xoccurs in s if and only if X occurs in t with the sentence If a variable X occurs in t then X must also occur in s 12 Page 784 lines 16 and 17 Delete the two sentences on these two lines Any nondeterministic Post algorithm can be rewritten as a deterministic Post algorithm So no additional power is obtained by nondeterminism 1 Page 788 line 12 In Exercise 3c replace quotfx y minyquot with quotfx y minzquot 1 Page 788 line 12 In Exercise 3d replace quotfx y minyquot with quotfx y minzquot Chapter 14 1 2 Page 797 line 18 Replace that when given nproduces with that when given nproduces 1 2 Page 799 line 12 Sentence preceding the box 148 Replace Here s 10th problem with Here s the 10th problem 26 1 2 Page 800 line 10 Replace f with the function symbol f 1 Page 801 lines 7 to 10 Replace the sentences and phrase quotFor any given n we can modify Tas follows Replace the Halt state by a state that looks to the right for an empty cell and when it is found it writes a 1 Then it uses n 1 more states to write n 1 more Is and then halts The modified machinequot with the following sentences and phrase quotFor any given n construct a new machine that starts with an empty tape and uses n states to write n 1 s onto the tape Then it transfers to the start state of T The new machinequot 1 Page 803 line 13 In exercise 6 replace quotstate where noquot with quotstate that noquot 1 Page 812 line 10 Replace quotVx Ely x v yquot with quotVx Ely x v yquot 1 Page 812 line 4 Replace quotVx Ely x v yquot with quotVx Ely x v yquot 1 Page 812 line 3 Replace quot32quot with quotV2quot 1 Page 825 line 7 Replace the phrase quottheorem that states NSPACEmi C DSPACEn2iquot with quottheorem stating that NSPACEmi C DSPACEmZi for i 2 1quot Answers to Selected Exercises 1 Page 827 line 8 In answer 3c replace 9 is odd but not prime Therefore the statement is false with The statement is true 27 1 Page 828 line 10 In answer 1e replace California Nevada Idaho Washington with M I S P R V E 1 Page 830 line 4 In answer 5a insert 3 between the 2 and 4 so that the answer looks like quot24 60 2 3 4 6 12quot 1 2 Page 830 lines 12 and 13 Change answer 10e to x A or 31sn or M1ltm or 31snu1 um where sk E L and uk E M 1 2 Page 830 line 21 In answer 13c replace the answer x I 96 None None E Borders for some x with x I x y None E Borders for some y 1 Page 834 line 1 In answer 9e italicize the n in fn 1 Page 834 line 10 In answer 2c replace gf5 5 with gf5 0 2 1 Page 839 line 9 In answer 2e replace x 12 with 5 1 1 Page 839 line 15 In answer 6a replace axb E S with axe E S 1 Page 840 lines 20 to 23 answer 3 Delete this entire answer and replace it with the following answer 3 For 39 makeTreelt lt3 2 4 makeTreeinsert3 lt lt2 4 makeTreeinsert2 insert3 lt 4 makeTreeinsert4 insert2 insert3 lt lt insert4 insert2 insert3 lt For 310 makeTreelt lt3 2 4 insert3 makeTreelt lt2 4 insert3 insert2 makeTreelt 4 insert3 insert2 insert4 makeTreelt insert3 insert2 insert4 lt 1 Page 840 line 15 In answer 4c replace the entire line with the following answer f1 n gcd1 n and fk n fk 1 n gcdk n 1 Page 841 line 3 Replace answer 7e with the following answer 28 f0 k 0 and fn k catfn 1 k 1 Page 843 line 16 In answer 1a replace All with Re exive symmetric transitive In answer 1c replace All with Re exive symmetric transitive In answer 1e replace All with Re exive symmetric transitive In answer 1g replace Transitive with Irre eXive transitive 1 Page 845 line 4 In answer 5a replace 5k n I k E N with 6k n l k E N 1 Page 846 line 13 In the graph for answer 3b delete the vertical line between 1 c and 1 Page 848 line 7 In answer 2i replace for n 1 with for n 2 1 2 Page 848 line 10 In answer 3a replace n 1 with n 0 1 2 Page 848 line 7 In answer 3a add 2 FltnD2 1 to the end of the line so the line looks like 2 sz 1 F Fn3 1 Fltn12 1 1 2 Page 848 line 6 In answer 3c replace For m n 0 0 the equation becomes 0 0 0 Assume wit Since the equation contains the term Fm1 we must have m 2 1 For n 0 or n 1 the equation holds for any m 2 1 Let n 2 2 and assume 1 2 Page 848 lines 1 2 and 3 In answer 3c replace the four occurrences of Fm1 on these three lines with qu 1 2 Page 850 line 21 In answer 13 replace Since gcdx y gcdx y x by 21b with Since gcdx y gcdy x gcdx y x by 21a and 21b 1 2 Page 851 line 21 In answer 20 remove a closing parens In other words replace 2 cata catx y z with 2 cata catx y z 1 2 Page 851 line 22 Misspelling Change defintion to definition 1 Page 853 line 1 In answer 1c replace the term 333 with 332 1 2 Page 853 line 4 In answer 2e replace 96 with xi 29 1 Page 853 lines 14 and 15 Replace answer 8a with the following 3 5 2k 3 where k ceilingn2 1 This sum has the value k 1 k 3 k 22 1 ceilingn2 12 1 1 2 Page 854 line 2 Change answer 9 from Either floorn2 1 or ceilingn2 1 to Either floorn2 or ceilingn2 1 Page 854 line 11 Change answer 13a from 052 to 021 1 Page 854 line 15 Change answer 18a from C49 6 to 1C49 6 1 Page 854 lines 16 to 24 Replace answer 18c with the following answer 0 C6 5C43 1 C6 4 C43 2C49 6 To obtain the answer notice that there are C49 6 6element subsets ofa 49element set Now suppose that 1 b c d e f is the winning set of numbers First we ll count all the 6 element sets that contain exactly five winners To do this notice that there are C6 5 5element subsets of 1 b c d e To each of these 5element subsets we add a nonwinner from the set 1 49 1 b c d e Since there are 43 2 C431 nonwinners it follows that there are C6 5 C43 1 sets of 6 numbers that contain exactly five winners Next we ll count the 6 element sets that contain exactly four winners To do this notice that there are C6 4 4element subsets of 1 b c d e To each of these 4element subsets we add two nonwinners from the set 1 49 1 b c d e Since there are C43 2 possible pairs of nonwinners it follows that there are C6 4 C43 2 sets of six numbers that contain exactly four winners So the probability of choosing either four or five of the six winning numbers is given by C6 5C43 1 C6 4C43 2C49 6 1 Page 857 lines 1 to 3 Replace answer 10c with the following CAVBA A gtB E AVBA AVBE AVBVAVB E AA BVAVBE AVAVBA BVAVB 2 true v IB A true VA Etrue Atruestrue 2 Page 857 line 2 In answer 10c replace true v B with true v B 1 2 Page 860 line 7 In answer to exercise 6a insert the new line 7 false 6 T and replace QED 1 2 6 IF with QED 1 2 7 IF 30 1 2 Page 860 line 14 In answer to exercise 6c insert the new line 7 false 6 T and replace QED 1 2 6 IP with QED 1 2 7 IP 1 2 Page 860 line 11 In answer to exercise 6e insert the new line 9 false 8 T and replace QED 1 2 8 IP with QED 1 2 9 IP 1 2 Page 860 line 1 In answer to exercise 6g insert the new line 10 false 9 T and replace QED 1 2 3 9 IP with QED 1 2 3 10 IP 1 2 Page 861 line 11 In answer to exercise 7c insert the new line 8 false 7 T and replace QED 1 2 3 7 IP with QED 1 2 3 8 IP 1 2 Page 861 line 1 In answer to exercise 7e insert the new line 10 false 9 T and replace QED 1 2 9 IP with QED 1 2 10 IP 1 2 Page 862 line 13 In answer to exercise 7g insert the new line 13 false 12 T and replace QED 1 2 3 4 12 IP with QED 1 2 3 4 13 IP 1 2 Page 862 lines 10 11 and 12 In answer to exercise 7i replace the the three lines 8 A gt C 3 4 7 IP 9 B gtA gtC 28CP QED 1 9 CP with the following four lines 8 false 7 T 9 A gt C 3 4 8 IP 10 B gtA gtC 29 CP QED 1 10 CP 1 Page 862 line 2 In answer to exercise 7k on line 8 replace 31 quotA AB gt C39with quotA gt Bv Cquot 1 2 Page 862 lines 1 and 2 In answer to exercise 7k replace the two lines 8 A gt B v C 23 7IP QED 1 8 CP with the following three lines 8 false 7 T 9 A gtBVC 238IP QED 1 9 CP 1 2 Page 863 line 14 In answer to exercise 9a insert the new line 12 false 11 T and replace QED 1 2 3 4 11 IP with QED 1 2 3 4121P 1 2 Page 863 line 3 In answer to exercise 10a on line 11 replace quotA A A with quotA v A 1 Page 865 line 5 In answer 2c replace quotx E 0 1quot with quoty E 0 1quot 1 Page 865 line 9 In answer 12g replace quotconsequent is truequot with quotconsequent is falsequot 1 2 Page 866 line 6 Insert the following sentence at the beginning of the answer for to Exercise 1 Section 72 between 1 and a For each part we ll assume that I is an interpretation with domain D 1 2 Page 866 lines 6 and 4 On each of these two lines replace true for domain D with true for I 1 2 Page 866 line 5 to page 867 line 6 On these lines replace all occurrences there are eight of them of true for D with true for I 1 Page 868 line 2 In the answer to exercise 8e replace quot Vxquot with quotVx Vyquot so the line looks like the following quote Vx Vy Bx A Ex y gt Wyquot 1 2 Page 869 line 1 In answer to exercise 7c insert the new line 9 false 8 T and replace QED 1 2 8 IP with 32 QED 1 2 9 IP 1 2 Page 872 line 11 In the first part of answer 9c insert the new line 11 false 10 T and replace QED 1 2 10 IP with QED 1 2 11 IP 1 2 Page 872 line 15 In the second part of answer 9c insert the new line 11 false 10 T and replace QED 1 2 10 IP with QED 1 2 11 IP 1 2 Page 876 line 15 in answer to 9 Replace 5 EG with 4 EG 1 2 Page 879 line 6 in answer to 9 Replace is equivalent to with is implied by 1 2 Page 880 line 18 in answer to 140 Replace 2 Simp with 5 Simp 1 2 Page 880 line 24 in answer to 140 Replace 2 4 with 2 4 8 1 2 Page 881 line 15 in answer to 160 Replace so we have fs fx is nonzero with so we have fs ft E N Since 96 is nonzero 1 2 Page 881 line 21 in answer to 17a Replace ft x with ft y 1 2 Page 881 line 22 in answer to 17a Replace ft y with ft x 1 Page 883 line 12 In answer to exercise 5 replace quot Ry Zquot with ll RC3 xquot 1 Page 883 line 11 ChangequotTquot to italic 1 2 Page 884 line 4 In answer to 10a replace Axiom 3 with Axiom 4 1 2 Page 894 line 8 In answer 8a replace gggx with fffx 1 2 Page 897 lines 14 to 19 Align so that there is equal space on either side of the equal symbol quot2quot 1 Page 907 line 13 In answer to 9 replace quotB gt abquot with quotB gt abbquot 33 1 Page 907 line 11 In answer to 9 replace quotneed threequot with quotneed twoquot 1 2 Page 912 line 9 In answer to 2a replace quotm0nus1 lessx yquot with quotmonus1 greaterx y Bibliography N0 Errata Greek Alphabet N0 Errata Symbol Glossary 1 Page 927 line 6 Change quot578quot to quot758quot so that the line looks like quoti a b Lj Turing machine instruction 758quot Then move the line down the page so that it becomes line 4 ie so that it sits between the line that contains 739 and the line that contains 781 Index 1 2 Page 935 first column Insert the new entry Horn clause 537 1 2 Page 939 second column line 9 Add page 151 to the entry so it should be Prefix of a string 151 245 1 Page 943 second column lines 1 and 2 Delete these last two entries pushdown automaton 701 and Turing machine 758 766 34 Other Fit and Finish Notes 1 Pages 640 to 642 Exercises In several exercises the letters of the parts are not aligned on the period For example in Exercise 2 on page 640 notice the jagged alignment of the letters quotaquot to quotfquot This is also the case in Exercises 1 2 4 5 6 8 9 and 10 See also page 465 Exercise 4 1 Page 648 Figure 114 Some arrows have minor overlaps or gaps with circles This is also the case for the arrow in the diagram at the bottom of page 648 the arrow overlaps one circle and doesn39t touch the other circle This is also the case with some other graphs eg pages 643 649 650 653 654 656 657 658 659 664 665 666 674 676 681 687 702 703 705 707 731 760 902 Discrete Structures CS 251 Lecture 7 Examplles Section 81 Chapter 8 Applied Logic 0 Can we formalize things that we talk about For example 1 When we reason we geometry we make assumptions about points and lines 2 When we reason about automobiles we make certain assumptions about how they work First order predicate calculus formalization of a subjectfirstorder theoryI 81 Equality 1 Study how the fundamental notion of equality can become part of first order theory 2 Study basic properties that are common to all equah es Equality How can we describe the idea of equality of expressions in a firstorder theory One way to start is to say the following wff is valid Vx x x The symbol is just the infix form of an equality predicate eg we could pick a predicate say e and let ex y mean x equals y To reason with equality we need some properties

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.