[PDF] [PDF] Discrete Mathematics For Computer Science - Skyline University

Chapters 1 and 8 of Mathematics for Computer Science by J H Conway, in The Book of Numbers, traces the identity to Leonhard Euler's 1748 Introductio; 



Previous PDF Next PDF





[PDF] DISCRETE MATHEMATICS FOR COMPUTER SCIENCE

Figure 4: The above arrangement of books and blocks represents two books placed on the first and last shelves, and one book on the second shelf As a sum, this 



[PDF] free pdf version - Discrete Mathematics - An Open Introduction

2 jan 2019 · is still of interest, but the intent is not to provide a solid mathematical foundation for computer science, unlike the majority of textbooks on the



[PDF] Discrete Mathematics For Computer Science - Skyline University

Chapters 1 and 8 of Mathematics for Computer Science by J H Conway, in The Book of Numbers, traces the identity to Leonhard Euler's 1748 Introductio; 



[PDF] Discrete Mathematics For Computer Science

6 mar 2014 · Chapters 1 and 8 of Mathematics for Computer Science by J H Conway, in The Book of Numbers, traces the identity to Leonhard Euler's 



[PDF] Discrete Mathematics For Computer Science wwwcepuneporg

science students taking the discrete math course Written specifically for computer science students, this unique textbook directly addresses their needs by 



[PDF] Discrete Mathematics - UNEP

central theme of this book is the connection between computing and discrete excellent introduction to discrete mathematics for computer science, software 



[PDF] Discrete Mathematics Using a Computer - xeduuy Matematica

To be sure, most discrete math textbooks incorporate some aspects applying discrete math to computing, but it usually takes the form of asking students to write 



[PDF] Mathematics for Computer Science

This story is the subject of the popular book, Fermat's Enigma by Simon Singh Induction plays a central role in discrete mathematics and computer sci- ence



DISCRETE MATHEMATICS FOR COMPUTING

These books generally cover the same broad range of topics: symbolic logic, sets , functions, induction, recursion, Boolean algebra, combinatorics, graph theory, 



[PDF] Discrete Math for Computer Science Students - KTH

Discrete Math for Computer Science Students Ken Bogart ways to mix the books up among themselves is the number of permutations of the books, namely k

[PDF] discrete mathematics for computer science

[PDF] discrete mathematics lecture notes ppt

[PDF] discrete mathematics problems and solutions pdf

[PDF] discrete mathematics solutions and answers pdf

[PDF] discrete mathematics syllabus

[PDF] discrete mathematics topics

[PDF] discrete time fourier series

[PDF] discrete time fourier transform

[PDF] discrete time fourier transform calculator

[PDF] discrete time fourier transform examples

[PDF] discrete time fourier transform pdf

[PDF] discrete time fourier transform properties

[PDF] discrete time fourier transform table

[PDF] discrimination essay titles

[PDF] discuss and exemplify roman jakobson's functions of language

Version of March 6, 2014

Notes for Part IA CST 2013/14

Discrete Mathematics

For Computer Science

Prof Marcelo Fiore

Marcelo.Fiore@cl.cam.ac.uk

- 0 -

Version of March 6, 2014

Lecture plan

Proofs

1. Preliminaries (pages 5-11) and introduction (pages 12-38).

2. Implication (pages 39-57) and bi-implication (pages 58-68).

3. Universal quantification (pages 69-77) and conjunction

(pages 78-85).

4. Existential quantification (pages 86-99).

5. Disjunction (pages 100-111) and a little arithmetic

(pages 112-127).

6. Negation (pages 128-147).

- 1 -

Version of March 6, 2014Numbers

7. Number systems (pages 148-160).

8. The division theorem and algorithm (pages 161-171) and

modular arithmetic (pages 172-178).

9. On sets (pages 179-185), the greatest common divisor

(pages 186-193), and Euclid's algorithm (pages 194-215) and theorem (pages 216-221).

10. The Extended Euclid's Algorithm (pages 222-235) and the

Diffie-Hellman cryptographic method (pages 236-240). - 2 -

Version of March 6, 2014

11. Mathematical induction: the Principle of Induction

(pages 241-259), the Principle of Induction from a basis (pages 260-264), and the Principle of Strong Induction from a basis (pages 264-286). Sets

12. Extensionality, subsets and supersets, separation, Russell's

paradox, empty set, powerset, Hasse and Venn diagrams, the powerset Boolean algebra (pages 287-313).

13. Unordered and ordered pairing, products, big unions, big

intersections, and disjoint unions (pages 314-339). - 3 -

Version of March 6, 2014

14. Relations, internal diagrams, relational composition, matrices,

directed graphs, reachability, preorders, and reflexive-transitive closure (pages 340-368).

15. Partial functions, (total) functions, bijections, andequivalence

relations and set partitions (pages 369-397).

16. Calculus of bijections, characteristic (or indicator)functions,

finite and infinite sets, surjections, and enumerability and countability (pages 398-420).

17. Choice, injections, Cantor-Bernstein-Schroeder theorem, direct

and inverse images, replacement and set-indexing, unbounded cardinality, and foundation (pages 421-449). - 4 -

Version of March 6, 2014

A Zen story

from the Introduction of

Mathematics Made Difficultby C.E. Linderholme

One of the great Zen masters had an eager disciple who never lost an opportunity to catch whatever pearls of wisdom might dropfrom the master's lips, and who followed him about constantly. One day, deferentially opening an iron gate for the old man, the disciple asked, `How may I attain enlightenment?' The ancient sage, though with- ered and feeble, could be quick, and he deftly caused the heavy gate to shut on the pupil's leg, breaking it. - 5 -

Version of March 6, 2014

What are we up to?

?Learn to read and write, and work with, mathematicalarguments. ?Doing some basic discrete mathematics. ?Getting a taste of computer science applications. - 6 -

Version of March 6, 2014

What is it that we do?

In general:

Mathematical models and methods to analyse problems that arise in computer science.

In particular:

Make and study mathematical constructions by means of definitions and theorems. We aim at understanding their properties and limitations. - 7 -

Version of March 6, 2014

Application areas

algorithmics - compilers - computability - computer aided verification computer algebra - complexity - cryptography - databases digital circuits - discrete probability - model checking - network routing - program correctness - programming languages - security semantics - type systems - 8 -

Version of March 6, 2014

Preliminaries

Complementary reading:

?Preface and Part I ofHow to Think Like a Mathematicianby

K.Houston.

- 9 -

Version of March 6, 2014

Some friendly advice

by K. Houston from the Preface of

How to Think Like a Mathematician

•It's up to you.•Be active.

•Think for yourself.•Question everything.

•Observe.•Prepare to be wrong.

•Seek to understand.•Develop your intuition.

•Collaborate.•Reflect.

- 10 -

Version of March 6, 2014

Study skills

Part I ofHow to Think Like a Mathematician

by K. Houston ?Reading mathematics ?Writing mathematics ?How to solve problems - 11 -

Version of March 6, 2014Proofs

Topics

Proofs in practice. Mathematical jargon: statement, predicate, theorem, proposition, lemma, corollary, conjecture, proof, logic, axiom, definition. Mathematical statements: implication, bi-implication, universal quantification, conjunction, existential quantification, disjunction, negation. Logical deduction: proof strategies and patterns, scratch work, logical equivalences. Proof by contradiction. Divisibility and congruences. Fermat's

Little Theorem.

- 12 -

Version of March 6, 2014

Complementary reading:

?Parts II, IV, and V ofHow to Think Like a Mathematicianby

K.Houston.

?Chapters 1 and 8 ofMathematics for Computer Scienceby

E.Lehman, F.T.Leighton, and A.R.Meyer.?

Chapter 3 ofHow to Prove itby D.J.Velleman.

Chapter II ofThe Higher Arithmeticby H. Davenport. - 13 -

Version of March 6, 2014Objectives

?To develop techniques for analysing and understandingmathematical statements.

?To be able to present logical arguments that establishmathematical statements in the form of clear proofs.

?To prove Fermat's Little Theorem, a basic result in thetheory of numbers that has many applications incomputer science; and that, in passing, will allowyou to solve the following ...

- 14 -

Version of March 6, 2014Puzzle

5pirates have accumulated a tower of

ncubes each of which con- sists of n3 golden dice, for an unknown (but presumably large) num- ber n. This treasure is put on a table around which they sit on chairs numbered from 0to

4, and they are to split it by simultaneously tak-

ing a die each with every tick of the clock provided that five ormore dice are available on the table. At the end of this process there will be rremaining dice which will go to the pirate sitting on the chair numbered r. What chair should a pirate sit on to maximise his gain? - 15 -

Version of March 6, 2014

Proofs in practice

We are interested in examining the following statement:

The product of two odd integers is odd.

This seems innocuous enough, but it is in fact full of baggage.

For instance, it presupposes that you know:

?what a statement is; ?what the integers (...,-1,0,1,...) are, and that amongst them there is a class of odd ones (...,-3,-1,1,3,...) ?what the product of two integers is, and that this is in turn aninteger. - 16 -

Version of March 6, 2014

More precisely put, we may write:

Ifmandnare odd integers then so ism·n.

which further presupposes that you know: ?what variables are; ?what if ...then ... statements are, and how one goes about proving them; ?that the symbol "

·" is commonly used to denote the product

operation. - 17 -

Version of March 6, 2014

Even more precisely, we should write

For all integersmandn, ifmandnare odd then so

ism·n. which now additionally presupposes that you know: ?what for all ... statements are, and how one goes about proving them. Thus, in trying to understand and then prove the above statement, we are assuming quite a lot of mathematical jargon that one needs to learn and practice with to make it a useful, and in fact verypow- erful, tool. - 18 -

Version of March 6, 2014

Some mathematical jargon

Statement

A sentence that is either true or false - but not both.

Example 1

eiπ+1=0

Non-example

`This statement is false' - 19 -

Version of March 6, 2014

THEOREMOFTHEDAY

Euler"s IdentityWithτandethemathematicalconstants

τ=2π=6.2831853071 7958647692 5286766559 0057683943 3879875021 1641949889 1846156328 1257241799 7256069650 6842341359...ande=2.7182818284 5904523536 0287471352 6624977572 4709369995 9574966967 6277240766 3035354759 4571382178 5251664274...

(thefirst100 placesofdecimalbeing given),and usingi to denote⎷ -1,wehave e iτ/2+1=0.

Squaring bothsidesofeiτ/2=-1 giveseiτ=1,encodingthedefiningfact thatτradiansmeasuresonefullcircumference.The calculationcan

be confirmedexplicitly usingthe evaluation ofez,foranycomplex numberz,asaninfinitesum:ez=1+z+z2/2!+z3/3!+z4/4!+....The

even powersofi=⎷ -1alternatebetween 1and-1,whiletheodd powersalternatebetweeniand-i,soweget twoseparatesums,onewith

i"s(theimaginary part)and onewithout(therealpart).Bothconvergerapidlyas showninthetwo plotsabove: therealpart to 1,theimaginary

to 0.Inthelimitequalityisattained,eiτ=1+0×i,whenceeτi=1.Thevalueofeiτ/2may be confirmedinthesameway.

Combiningasitdoesthesixmostfundamentalconstantsofmathematics:0, 1, 2,i,τande,theidentityhasanairofmagic.J.H.Conway,in

TheBookofNumbers

Weblink:

Further reading:

From www.theoremoftheday.org byRobinWhitty.Thisfilehosted by

LondonSouthBankUniversity

- 20 -

Version of March 6, 2014Predicate

A statement whose truth depends on the value of one or more variables.

Example 2

1. ` eix=cosx+isinx

2. `the function

fis differentiable' - 21 -

Version of March 6, 2014Theorem

A very important true statement.

Proposition

A less important but nonetheless interesting true statement. Lemma A true statement used in proving other true statements.

Corollary

A true statement that is a simple deduction from a theorem or proposition.

Example 3

1. Fermat's Last Theorem

2. The Pumping Lemma

- 22 -

Version of March 6, 2014

THEOREMOFTHEDAY

Fermat"sLastTheoremIfx,y,zand n areintegers satisfying x n+yn=zn,

It iseasytoseethatwe canassumethatall theintegersinthetheoremarepositive.Sothefollowingisalegitimate,but totally different,way

ofassertingthetheorem:wetake aballatrandomfromUrnA; thenreplaceitandtake a2nd ballatrandom.DothesameforUrnB.The

probabilitythatbothAballsareblue,fortheurns shown here,is5

7×5

7.TheprobabilitythatbothBballsarethesame colour (both blueorboth

red)is(4

7)2+(3

7)2.NowthePythagoreantriple52=32+42tellsusthat theprobabilitiesare equal:25

49=9
49+16

49.What ifwe choosen>2 balls

withreplacement?Canwe againfilleach oftheurnswithNballs,redand blue,sothat takingnwithreplacementwillgive equalprobabilities?

Fermat"sLastTheoremsays:onlyinthetrivialcasewhere all theballsinUrnAareblue(whichincludes,vacuously,thepossibilitythatN=0.)

Another,muchmoreprofoundrestatement: ifan+bn,forn>2and positiveintegersaandb,isagainann-th powerofanintegerthenthe

elliptic curvey2=x(x-an)(x+bn),knownastheFreycurve,cannotbemodular (isnotarationalmap ofamodularcurve).Soit isenoughto

provetheTaniyama-Shimura-Weilconjecture:allrationalelliptic curvesaremodular.

Fermat"sinnocentstatementwasfamouslyleftunprovedwhenhediedin 1665andwasthelastofhisunproved'theorems"tobesettledtrueorfalse,hencethe name.Thenon-modularityoftheFreycurvewasestablishedinthe1980sbythesuccessiveeffortsofGerhardFrey,Jean-PierreSerre andKenRibet.TheTaniyama-Shimura-Weilconjecturewasat thetimethoughttobe'inaccessible"butthetechnicalvirtuosity(nottomentionthecourageandstamina)ofAndrewWilesresolvedthe'semistable"case,whichwasenoughtosettleFermat"sassertion.HisworkwasextendedtoafullproofofTaniyama-Shimura-Weilduringthelate90sbyChristopheBreuil,BrianConrad,FredDiamondandRichardTaylor.

Weblink:

Further reading:

Fermat"sLastTheorem

Created byRobinWhittyfor

www.theoremoftheday.org - 23 -

Version of March 6, 2014

THEOREMOFTHEDAY

xy izisalso aword ofL.

automaton(DFA)whose edgesarelabelledfromΣ.Aboveleft,suchaDFAis shown,whichrecognisesthelanguage consisting ofallpositive

multiplesof7,writtenin basetwo.Thenumber95×7=665=29+27+24+23+20isexpressedin base2as1010011001.Togetherwith

anyleadingzeros,thesedigits,readleft toright,willcausethe edgesoftheDFAto betraversedfromtheinitialstate(heavy verticalarrow)to

anacceptingstate(coincidentallythesamestate,markedwithadouble circle),as showninthetablebelowtheDFA.Noticethat thebracketed

partofthetable correspondstoa cycleintheDFAandthismay occurzero ormoretimeswithoutaffectingthestring"srecognition.Thisisthe

ideabehindthepumpinglemma,inwhichp,the'pumpinglength",may betakento bethenumberofstatesoftheDFA.

SoaDFAcan besmartenoughtorecognisemultiplesofaparticularprimenumber.But itcannotbesmartenoughrecognise allprimenumbers,

evenexpressedinunarynotation(2=aa,3=aaa,5=aaaaa,etc).Theproof,aboveright,typifiesthe application ofthepumpinglemmain

disproofsof regularity:assume arecognisingDFAexistsandexhibitawordwhich,when'pumped"mustfalloutsidetherecognisedlanguage.

Weblink:

(anddon"tmiss

Further reading:

ModelsofComputation andFormalLanguages

Created byRobinWhittyfor

www.theoremoftheday.org - 24 -

Version of March 6, 2014Conjecture

A statement believed to be true, but for which we have no proof.Example 4

1. Goldbach's Conjecture

2. The Riemann Hypothesis

3. Schanuel's Conjecture

- 25 -

Version of March 6, 2014

Proof Logical explanation of why a statement is true; a method for establishing truth. Logic The study of methods and principles used to distinguish good (correct) from bad (incorrect) reasoning.

Example 5

1. Classical predicate logic

2. Hoare logic

3. Temporal logic

- 26 -

Version of March 6, 2014

Axiom

A basic assumption about a mathematical situation.Axioms can be considered facts that do not need to beproved (just to get us going in a subject) or they can beused in definitions.

Example 6

1. Euclidean Geometry

2. Riemannian Geometry

3. Hyperbolic Geometry

- 27 -

Version of March 6, 2014Definition

An explanation of the mathematical meaning of a word (or phrase).The word (or phrase) is generally defined in terms of prop-erties.

Warning

:It is vitally important that you can recall definitions precisely. A common problem is not to be able to advance in some problem because the definition of a word is unknown. - 28 -

Version of March 6, 2014

Definition, theorem, intuition, proof

in practice

Definition 7An integer is said to be

odd whenever it is of the form

2·i+1

for some (necessarily unique) integer i.

Proposition 8For all integers

m and n, if m and nare odd then so is m·n - 29 -

Version of March 6, 2014

Intuition:

- 30 -

Version of March 6, 2014

YOUR PROOF OFProposition 8 (on page 29):

- 31 -

Version of March 6, 2014

MY PROOF OFProposition 8 (on page 29): Let

m and n be arbitrary odd integers. Thus, m=2·i+1 and n=2·j+1 for some integers iand j. Hence, we have that m·n=2·k+1 for k=2·i·j+i+j , showing that m·n is indeed odd. - 32 -

Version of March 6, 2014

Warning

:Though the scratch work m=2·i+1 n=2·j+1 m·n= (2·i+1)·(2·j+1) =4·i·j+2·i+2·j+1 =2·(2·i·j+i+j) +1quotesdbs_dbs21.pdfusesText_27