DISCRETE MATH FOR CS
DISCRETE MATH FOR CS CS 3653
Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Ms. Bridie Kohler on Sunday November 1, 2015. The Class Notes belongs to CS 3653 at Oklahoma State University taught by Staff in Fall. Since its upload, it has received 19 views. For similar materials see /class/232838/cs-3653-oklahoma-state-university in ComputerScienence at Oklahoma State University.
Reviews for DISCRETE MATH FOR CS
Report this Material
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: 11/01/15
Lecture 13 Mathematical Induction Cont d Example 5 Knowing that J5 is irrational prove that wallaHm nl39s P pn 1s 1rrat10na1 Vnel23 1 Basis step P2 l 2 J5 is irrational so p2 is true 2 Assumption Assume pn is true ie Pn lll nl s is irrational 3 Induction Prove pnl is true need to show that Pnl lll n1 1 s is irrational Pnllll 1Pn n1 139 Note 1 Pn is irrational OSU cs 3653 Fall 2002 Lecture 13 1 T Menhaj OSU CS 3653 Fall 2002 Why Prove by contradiction Assume 1 P01 is rational Therefore 1 Pn1 for some qr e Z qr relatively prime r But this cannot be true since Thus Pn1 1 r q I V Pn is irrational Therefore 1 P01 is irrational Now shoW1 Pn is irrational Prove by contraction Assume J 1 Pn is rational Therefore 1Pn1 for some qr e Z qr relatively prime r 2 2 r zq which is rational r 2 1Pn 4 21311 V contradiction Back to the initial assumption of J5 is irrational Check if J5 is irrational Prove by contradiction Assume it is rational Therefore Lecture 132 T Menhaj J5 1 for some qr e Z qr relatively prime r 2 2q 23q22r23q2m meZ r Knowing that q and r are relatively prime we have q2mmeZq24m22r23r2m23 r 23 s e Z This says that q and r are not relatively prime Contradiction Example 6 Prove that the set of instructions given below does not represent an algorithm X9 while x3 x x 3 endwhile Proof need to show that the above instructions never terminates To do so let pnit does not stop after n iterations OSU CS 3653 Fall 2002 Lecture 133 T Menhaj 1 Basis step pl after first iteration X becomes m 2 J5 2J3 3 It will not stop on iteration l 2 Assume that pn is true it won t stop after n iterations P Prove that pn1 is true it won t stop after n1 iterations Because pn is true after n iterations X is still different from three39 X 3 and indeed because X is initially 9 Xl becomes 2J3 and X becomes after a few iterations less than 339 Hence at the n1th iteration X becomes m 39 this equals 3 iff X6 but we know that X is less than 339 s0 m cannot be 3 and these set of instructions does not terminate after n1 iterations meaning that pn1 is true OSU CS 3653 Fall 2002 Lecture 134 T Menhaj Example 7 Prove that 2quot gt n 1 Vn 2 211 6 N Let pn the statement Pn2 gtn1 1 Basis step P222 4 gt 2 1 3 so p2 is true 2 Assume pn is true Pn2quot gt n 1 Vn 2 211 6 N 3 Prove pn1 is true or prove that 2quot1 gt n 1 1 2quot1 2 2quot gt 2 n 1 by the assumption now show 2n 1gtn 11 2n1n11 nn2gtn2 sincenZZ Therefore 239 1 22quot gt2n1gtn2n11 2quot gtn 1 1 hence pn1 is true OSU CS 3653 Fall 2002 Lecture 135 T Menhaj Example 8 Show that Z 0 n il Letpm mow fl 1 Basis step Knowing that 3P0 z gtxx z 39 l and oamz oa az H o x This says thatp1 andp2 are true 2 Assume thatp c is true for all 1 k S n ie id k Pk l l 0 Vk12n i1 3 Prove that pn1 is true show that if n1 Pn 1 e H il Proof OSU CS 3653 Fall 2002 Lecture 136 T Menhaj formal fog 11 11 L from p2 o x am ij ax n1 171 aw o m L iil from assumption This says that pn1 is true Example 9 ProvePn S ixij S iinJn l il il il Let pn denote the proposition that PmziinJsliaJsiin n l is true i Basis First we show that p2 is true 2 2 2 2m s s Ema 1 il il il ELXIJLxZJSLx1x2JSLx1JLxZJ2 l OSU CS 3653 Fall 2002 Lecture 137 T Menhaj DenoteXi inJil2 ampy 2x X to write LXIJLx2JLX1y1JLX2yZJX1X2 sX1X2 Ly1y2JLX1y1Xzy2JLx1x2J Notethatyi lt13y1y2 lt2 amp Ly1y2JS13 LXIx2JX1X2Ly1y2JSX1X2lLx1JLx2Jl Therefore Lx1JLxZJ s Lxl x2J ngIJLx2J21 Orp2 is true 2 Assume thatpn is true ie Pn ziinJ SLanxiJ SiinJn l il il il 3 Prove that pn1 is also true pn 1ELMJSLEMJSEinJnl l Proof OSU CS 3653 Fall 2002 Lecture 138 T Menhaj n1 n 24 xixnlj j H H from p2 i Mm n from pn that is Z i 1 1 l 1 1 ixii xnuisiixi xn1jgiiiejLxMjn4l This says that pn1 is true OSU CS 3653 Fall 2002 Lecture 139 T Menhaj Example 10 Find summation S112233nn Sn iin il n 1 2 3 4 5 6 Sn 1 5 23 119 719 5039 S S n 5 48 51739 6042 70083 7171 n1 2 6 24 120 720 5040 It is reasonable to compare S with n1 and guess Sn n1 1 7 Check for n27 S7 Z i i 40319 and 71 40320 11 Now we need to prove it Denote pn Sn 2 equals n1I and proceed as follows 1 1 Basis step S1 Ziil 2 1 3 p1 is true 11 2Assumpti0n pn is true ie Sn Ziinll 11 OSU CS 3653 Fall 2002 Lecture 1310 T Menhaj 3 Inductive Step Show that pn1 is true or prove that n1 SW Z z39 n2 l 11 Proof Sn1 3514 iinlnl a 21 21 Byassumption SM n1 1n1n1n1n11 1 n1n2 l n2 1 Example 11 Prove n2 2 2n 1 n 34 Denote pn Pn n2 2 2n 1 is true v n 34 1 Basis P332 223192 7 sop3 is true 2 Assumption pn is true39 n2 2 2n 1 3 Inductive step show that pn1 is true39 need to show that n12 2211 1 1 Proof n 12 n2 2n122nl2nl By assumption Z4n2 22n2nl22nll3939 OSU CS 3653 Fall 2002 Lecture 1311 T Menhaj Example 12 prove 2quot 2112 n 4 5 Denote pn 39 Pn 2quot 2 n2 is true p A Basis P4 24 2 42 16 216p4 is true N Assumepn is true 2quot 2 11211 45 U Prove pn1 is true 2quot12n 12n 45 239 1 22quot 22112 2 112 211 1 2 n 12 By assumption and exmple 113939 n1 Example 13 Prove that 7391 2111 12 2n n pn 2H 21 n 12 is true 1 1 21 p11s true I 2 Assume pn is true39 211 2111 12 3 Prove that pn1 is true39 need to show that n1 21 22 Proof OSU CS 3653 Fall 2002 Lecture 1312 T Menhaj nl2 n1nln 2 22 2 v From Assumption quotTtla n1 72 LVn 12 Example 14 Prove Pn 3quot 7quot 2is divisible by 8 nl2 Denote pn 39 8 divides Pn nl2 1 Basis P13171 2 8 171 Sl 8true 2 Assume pn is true Pn 3quot 7quot 2 is divisible by 8 nl2 3 Provepn1 is true Proof Pnl 3 1 7 1 2 33quot 77quot 2 By assumption 83quot 7quot 2 E 3quot 7quot 2 2 Sq 3 33quot 7quot 2 47quot 1 38q47quot 1 To show 8 divides Pn1 we need to show 2 l 7quot 1V 12 This will be proved in the next example OSU cs 3653 Fall 2002 Lecture 13 13 T Menhaj Example 15 Show that 217quot 1V 152 Denote p01 2 divides7quot 1 is trueVn 12 1 Basis step p1 is true because 2 divides 71 2 Assumption pn is true ie 2 divides 7quot 1 is trueVn 12 3 Inductive step prove pn1 is true 7quot1177quot 1 67quot 7quot1 2 HQ H J divisible by 2 By assumption Divisible by 2 2 divides 7 1 l OSU CS 3653 Fall 2002 Lecture 1314 T Menhaj Example 16 By experimenting with small values of n guess a formula for the given sum 1 l l quot l2 23 nnl Then use induction to verify your formula 1 nnl n1 quot l quot l l quot l quot l Swim1El ml ll lml Leta n n n1 n n lelZll illl ll 1 i1 1 F2 J j2 J j2 J quot1 l n nl nl Verification quot l n Let nS euals p quot ii1 q n1 1 Basis step OSU CS 3653 Fall 2002 Lecture 1315 T Menhaj 514 12 11 L1 2 2 Sop1 is true quot 1 n 2 Assume n 1strueS p quot ii1 n1 3 Inductive step Prove pn1 is true quot1 1 n1 Sn1Z i1ii1 n11 Proof H 111 n1n2 LM n1 n1n2 n1n2 n22n1 n12 n1n2 n1n2 n1 n1 sincZ 1 n 11 From assumption OSU CS 3653 Fall 2002 Lecture 1316 T Menhaj Lecture 17 Graph Theory Introduction Graph Theory Modeled by theory of nite set and binary relation an extension of the theory of binary relations on a nite set Illustrative Examples Example 1 Product Principle successive tasks T 1 TI in niways 139Im Total number of different possible activities is n OSU CS 3653 Fall 2002 Lecture 171 T Menhaj Example 2 A ow chart to nd Pnm Initialization Plk0 Y N P Pgtlt n 17 k k k1 Example 3 Let A B 2345678910l112 Illustrate the Divisibility relation D alb on A by B by a graph OSU CS 3653 Fall 2002 Lecture 172 T Menhaj Example 4 Ascending orders S10151512611 OSU CS 3653 Fall 2002 Lecture 173 T Menhaj Directed Graph A More Challenging Example The con guration in below is given The goal is to obtain the following con guration A move consists of shifting one of the adjacent cells containing a number into the empty cell To develop a general approach using graph theory you need to de ne a state and adjacent states A state is OSU CS 3653 Fall 2002 Lecture 174 T Menhaj de ned as one con guration of cells and adjacent states are two states obtained from each other in a single move The graph is shown below d a E9 1 Lecture 175 H I OSU CS 3653 Fall 2002 T Menhaj Therefore it is possible to Win39 the shortest ones take four moves As easily seen problems dealing with nite set of objects and binary relations can be formulated represented by a graphical diagram of objects that properly contain information like circuit diagrams ow charts road maps trees this is the essence to the theory of graphs OSU CS 3653 Fall 2002 Lecture 176 T Menhaj History Graphs date back to the eighteenth century 1736 when the mathematician Leonard Euler introduced the KOnigsberg Kaliningrad in Russia bridge Problem Seven bridges connecting two islands amp the banks of a river Find a path that crosses each bridge exactly once and ends at the starting position mnk Graphical representation of Konigberg Problem OSU CS 3653 Fall 2002 Lecture 177 T Menhaj Graph theory became much more popular since the 1920s because of its Widespread applications in many various elds in science and engineering such as chemistry computer science electrical engineering and economics Multigraph undirected graph it consists of nodes vertices and edges lines connecting the vertices Basic terminology Definition An undirected graph G consists of a set of nodes vertices N and a set of edges arcs A such that each arc aEA is associated with an unordered pair of nodes a 111112 or a 112111 111112 6 N 112111 an arc between n1 and n2 OSU CS 3653 Fall 2002 Lecture 178 T Menhaj Abstractly you may de ne an undirected graph by a pair G 2 NA For the K6nigberg Problem G ag gwij ym hw yw N A N 7 a nite set A 7 a antire eXive symmetric relation on N Notation nodes as dots or circles arcs as lines Example 5 G N A N3325 OSU CS 3653 Fall 2002 Lecture 179 T Menhaj 2 3 Relation R a b E R if a and b have a prime factor greater than one in common A directed graph G is de ned as a pair N A st V0614 there is an ordered pair 711712 if there is a unique aeA associated with the ordered pair of nodes aquotp 71 this denotes the arc from m to 112 Notes 1 An arc edge in a graph that is associated with the pair of nodes 11 and n2is said to be incident on m and ng and m and n2are called incident on a m and n2are said to be adjacent nodes 2 Isolated node is a node if there is no arc incident with it OSU CS 3653 Fall 2002 Lecture 1710 T Menhaj In a directed graph with arc aquot1quotz n1 7 is called initial node n is called terminal node aquotpquotz is incident from m and incident into 112 Notes 1 A directed graph has arcs indicated by arrows 2 G N A A 7 irre eXive antisymmetric relation on N 3 Distinct arcs can be associated with the same node Such arcs are called parallel arcs edges See a3 and as below a3 5 I O OSU CS 3653 Fall 2002 Lecture 1711 T Menhaj An arc incident on a single node is called a loop such as node n3 with edge a4 above A node like n5 which is not an incident on any arc is called an isolated node Another View A digraph G consists of two sets Nn i12 and Aai12 together with a function fAgtNgtltN fltnn1this says that Where the arcs go For a graph the function fangtn1 Example 6 a3 quot5 quot O quot3 a5 a1 a2 a4 quot2 a a1 32 fa WM quot1 OSU CS 3653 Fall 2002 Lecture 1712 T Menhaj This View does still make sense even ifN or A is in nite Example 7 It is a directed graph digraph G N A N 13618 A 11 13 16 118 33 36 318 66 618 1818 Obviously G represents a binary relation R N represents the set and the arcs represent the relation itself ie 16 is an edge from node 1 to node 6 iff16 E R for relation R OSU CS 3653 Fall 2002 Lecture 1713 T Menhaj on N The relation R here is divisor a b 6 SR a l b E b aq q 6 ER HR is re exive then there is a loop at every node R is symmetric if there is an arc from a to b there is a corresponding edge from b to a Therefore a symmetric relation may be represented by a graph instead of a digraph Adjacent vertices For graph G N A n1 and nj are adjacent if ni nj 6 A For digraph either ni nj 6 A or nj ni E A Example 8 N P1 P2 P3 P4 be papers in a book Let A P1 P2 P1 P4 P3 P4 P4 P2 P2 P3 P3 P2 be a binary relation on N such that P1 P2 6 A means that the material in paper 1 refers to that of paper 2 The graph G N A is shown below P1 P3 P2 OSU CS 3653 Fall 2002 Lecture 1714 T Menhaj Example 9 In an under 12 soccer tournament there are 5 teams N1 12345 Let A1 12 14 34 42 23 32 be a relation on N1 such that a b E A means that team a beats team b in the soccer match between them The graph G1 N1 A1 is given below Isomorphism Two graphs are called isomorphic if there eXists a onetoone correspondence between their nodes and between their arcs edges so that incidents are preserved That is there is an arc between two nodes in a graph G iff there is a corresponding arc between the corresponding nodes in G the other graph OSU CS 3653 Fall 2002 Lecture 1715 T Menhaj Example 9 G N A N 21 the 16 f gah A a e a b b c c g c d d a e h f e g f h g G is isomorphic to G N A N 12141618 A 15 12 23 37 34 41 58 65 76 87 OSU CS 3653 Fall 2002 Lecture 1716 T Menhaj A graph with neither loops nor parallel arcs is called a simple graph Complete graph A complete graph on m nodes denoted Cm is a simple graph with m nodes in which there is an edge between each pair of distinct nodes Complete graph C4 OSU CS 3653 Fall 2002 Lecture 1717 T Menhaj A graph G 2 NA is bipartite if there exists subsets N1 and N2 either N1 or N2 may be empty of N such that N1 0 N 2 Q and N1 U N 2 N and each arc in A is incident on one node in N1 and one node in N2 Example 10 H1 n3 n2 n4 115 N1 n1anzNz 71397149715 Also the complete graph C1 on one node is bipartite OSU CS 3653 Fall 2002 Lecture 1718 T Menhaj Definition The complete bipartite graph on n and m nodes Cm is the simple graph in which there is an arc between each pair ofnodes n1 amp n2 n1 6 N1 amp n2 6 N2 OSU CS 3653 Fall 2002 Lecture 1719 T Menhaj Precedence Relation Ordering or hierarchy of the set operators l Inverse Compliment 2f Intersection 3U Union Difference Union and difference have the same precedence and are evaluated left to right if found consecutively Examples ABC ABC AUB CEAUB C AUB CiAUB C AUB E DDEUFEAUB E DDEUF The Principle of Duality Identity is preserved if we replace 1 Uby and byU 2 Q by Universal Set S and S by 0 Examples AU AcgtA SA ZUASCgtZDAQ AUB C A ltgtA BUCUSA CS 3653 Fall 2002 Lecture 21 T Menhaj Cartesian Product Given Aaiiel BbjjeJ May form a new set whose elements are all possible ordered pairs of ai and b I CAxBcija baieAieIbjeBjeJ 17 Visualization B A A AgtltB a A J AgtltB 7E BgtltA Note Order of elements is important Example Given set A A x B John Red Green Blue A X B RedJohnRedGeorgeRedJack GreenJohnGreenGeorgeGreenJack BlueJohnBlueGeorgeBlueJack Therefore Note that GeorgeGreen g Agtlt B as order is important CS 3653 Fall 2002 Lecture 22 T Menhaj Generalization of Cartesian Product Let C ck 39s Agtlt Bx C aibjck at b jck is a 3tuple Note that 134 i 3 1 4 abc def iffa 2d ec f or more generally a1an b1bn iffai 51 v2 1n How about n gtoo The in nite tuple a1a2a3 is called a sequence CS 3653 Fall 2002 Lecture 23 T Menhaj Relations Binary Relations A relation on A amp Bis any subset of the Cartesian Product A X B Example lt lets de ne lessthan using the concept of Relations Let A B R Q quotless thanquot Q xy Jay E Rx lty Note xay E Q lt3 x lty also x7y QCgtx2y Divisibility 2 divides 4 meaning that 224 de ne divisibility using the concept of relations AB123N abltgtbqa qu DababampAampbqaquA Note abeD3 qu baq CS 3653 Fall 2002 Lecture 24 T Menhaj Properties of a Relation 1 Re exivity A relation Q on A X Ais re exive if x x e Q Vx e A Examples of re exive relations 1 g 2 2 3 Stated mathematically for 3 Let AR the relation E x y xy e R x g y Since Vx e Rx g xE is re exive 2 Symmetry A relation Q on A is symmetric if for any x and y in A such thatxy e Q 3 yx e Q Examples of symmetric relations 1 also re exive 2 sibling 3 cousin Stated mathematically for Exyxya MGR E is symmetric Another example consider CS 3653 Fall 2002 Lecture 25 T Menhaj A 2 power set of the set 12349 Q quotone common elementquot QCBCnB 7 Q CampBeA Q is symmetric since CB 6 Q gt B C e Q 3 Transitivity A relation is Q is transitive if for any x y z e A such that xyeQand yzeQgtxzeQ Note if xy 0r yz the condition of transitivity is automatically met Examples of transitive relationships lt gt S 2 C are all transitive 7 7 7 Other relations x to y X an object is in nitely close to think location in 3 dimensions CS 3653 Fall 2002 Lecture 26 T Menhaj Equivalence Q is called an equivalence relation if it is re exive symmetric and transitive Example Consider A abCdef The set B 08bf represents one partition of A The relation Q on A is de ned by xyeQltgtEBeB s1 xeBampyeB This relation Q on A becomes aaacaecacc Q ceeaeceebb bafafaffabdad Q is re exive symmetric and transitive Q is an equivalence relation Why In general we can easily prove that if the set B represents a partition of A the relation Q de ned above is an equivalence relation on A Equivalence Class Let Q be an equivalence relation on a set A For each a in A let a E x E A x a E These sets are called the equivalence classes of A by the relation Q CS 3653 Fall 2002 Lecture 27 T Menhaj Note the set B E a e A is a partition of A Why We must show that every element in A belongs to exactly one element of B or ifxeAampxeanbthen ab Let a e A Since 616E Q 3 a E a This says that every element of A belongs to at least one element of B Now suppose that the pair a b is in Q and proceed as 0113 EQ and letxea gtxae Q gt Transitivity xb e Q gt xe b gt a g By the same argument may show that b g a and conclude that a bl Now assume that X e A and X e am b gt MOE Q amp xiE Q gt xax b13 fromabove a bl Example The following relation on 513530 is given Qltaagtabgtmaxed I Q is an equivalence relation and a dabc 2 Cr CS 3653 Fall 2002 Lecture 28 T Menhaj Example Mathematically state the equivalence has the same remainder when divided by 3 on A 1 234 56 789 Let de ne the relation Q on A as Q xy 3 devides x y Vxampy EA 0 3 0 gt 3 devides XX for any x e A gt Q is refeleXive Xy3q gty x 23 q Vxy e A gtQ is symmetric Xy3q and yz3q gt Xz3 qq gt Q is transitive Hence Q is an equivalence relation on A Equivalence Classes 1 xeAl 3 divides X l l47 2 x 6 Al 3 divides X2 258 3 xe Al 3 divides X 3 3 6 9 These three sets partition A since A 1 up u3 and they are pairwise disjoint CS 3653 Fall 2002 Lecture 29 T Menhaj Transitive Closure The transitive closure of a relation Q on A is T Q onA Q39 TQ E xy iffEl a sequence x x1x2xn st xixl1e Q sz 212n 1 Example Let the relation Q be the immediate positive integer number after a positive number This is mathematically formulated as QnmnampmeNnml Find Q TQ Claim Q quot lt quot Why Q xyxampyeNyltx knowing that Xy 2d 6 NZ setx1 xx2 x lxn x d2y ndl and xixi1eQ CS 3653 Fall 2002 Lecture 210 T Menhaj Composition Relations R amp Q R C A X B Q C B X C o is the symbol for composition Let L R 0 Q Then L C A X C and Laca 6 Ac 6 C St Elb e B with ab e R and 190 6 Q Given DCNXN DababeNabltgtbaqqu And Qquot quot then DoQ mneD ampnreQgtm nampn rgtm r DoQQ CS 3653 Fall 2002 Lecture 211 T Menhaj Preimage Let the relation Q on A by B is given Q C A XB Image ofa in B is QabeBabeQ aeA Similarly the preimage of b in B is Q 1baeAabeQ beB Example For divisibility relation D ab may have 193beN3beDcgtb3qqu D 148 a EN a 48 eDcgt 48aqq EN all factors of 48 CS 3653 Fall 2002 Lecture 212 T Menhaj Directed Graph A visual representation of binary relations Finite Sets A and B are given An Bm A aii12nB b jzlyzyuum For a given relation 05 la 6 A35 6 B Q C AXE draw a dot for each element of AuB and an arrow from a to b for each a b in Q Example Let A B 23456789101112 Draw directed graph of divisibility relation D ab on A by B CS 3653 Fall 2002 Lecture 213 T Menhaj Antisymmetry A relation Q on A is called antisymmetric if for all 61 e A if 6119 6 Q and a 7 b then 1961 91 Q Example The relation Q quot 39 on A 123 2 12233 is antisymmetric Is it symmetric Yes Conclusion Antisymmetry is not the opposite negation of symmetry Nonsymmetry Q is nonsymmetric if it is not symmetric It means that there are some pairs at least one pair such that cub 6 Q 3 196 Q Partial Order A relation Q on A is called partial order if it is re exive antisymmetric and transitive Example Q quot 3 quot CS 3653 Fall 2002 Lecture 214 T Menhaj Lecture 15 Mathematical Logic Cont d Generalization let p1pz39 pn be les that are the premises of an argument and let q be an le that is the conclusion Then P1 Pu q is valid iff gukq 1 is a tautology Note An argument is valid if its conclusion is true provided that the premises are assumed true If 1 is a tautology then q must be true for all truth values of atomic propositions that make the premises true this says that the argument is valid Conversely assuming that the argument is valid q must be true when all premises are true But if OSU CS 3653 Fall 2002 Lecture 151 T Menhaj any of the premises is false then 1 is true from the de nition of implication Therefore 1 is true for any values ofits atoms namely it is a tautology Tautologies Test the validity of arguments Example 1 Paq qas therefore p a s This argument is valid iffthe le PMWWHWS is true for all values ofits p q and s OSU CS 3653 Fall 2002 Lecture 152 T Menhaj m m m quotC HHHHmmHHt Q Q peqqes p T ui ui ui ui H H H H quotc ui ui H H ui ui H H 4 ui H ui H ui H ui H H H w H H H w H t H H ui H ui ui ui H H H H ui H ui H t HHHHHHHHIO Tautology Example 2 Prove that 39 39P 9 P is a tautology P W p2 pw nHU e P T F T T F T F T By induction we can easily prove that n ifnis even p p Hp ifn is odd OSU CS 3653 Fall 2002 Lecture 153 T Menhaj Example 3 Prove or disprove the following argument is valid P99 q or p gtqAq gtp P Proof p q paq paqq le T T T T T T F F F T F T T T F F F T F T So it is not a valid argument Example 4 Prove or disprove that theorem P gtIr r gts gtp OSU CS 3653 Fall 2002 Lecture 154 Not a Tautology T Menhaj 16 qu rgts pgtqr S qr r TTTT T TTTF T TTFTF TTFF F TFTTF TFTF F TFFTF TFFF F FTTT T FTTF T FTFTF FTFFF FFTTF FFTF F FFFTF FFFF F OSU T Menhaj Lecture 155 CS 3653 Fall 2002 Note If p the conclusion is T for each row Where all the premises are true then the theorem is true which is the case here De nition PX statement involving the variable X and a set D P is called the propositional function Wrt D if VX E D PX is a proposition D is the domain of discourse of the propositional function P PX by itself is neither true nor false PX represents a class of propositions each of which is either true or false Predicate Logic To make more nondeclarative and yet compleX propositions expressing the properties of the objectives Definition The statement for every X PX VX PX is called a universally quanti ed statement V is called the universal quantifrer The statement VX PX is true if PX is true for every X in D the domain of discourse OSU CS 3653 Fall 2002 Lecture 156 T Menhaj The statement for some X PX E EIX PX is called an eXistentially quanti ed statement El is called an eXistential quanti er The statement EIX PX is true if PX is true for at least one X in D This EIX PX statement is false if PX is false for every X in D V is read for every for all or for any El is read for some for at least one there eXists an X such that EXample 5 The statement for every X 2X is even Where X e Z is a universally quanti ed statement This is a true statement Example 6 Predicate quanti ers V 3 V bOXes 3 one ball 2 for every bOXes there is one ball 0 O 0 CS 3653 Fall 2002 Lecture 157 T Menhaj OSU 3 one ball V boxes there is one ball for all boxes 0 Example 7 Let px xx2 XE Z What is the truth of each of the following propositions 1 Vx px Sol n It says that Whether each integer equals its square39 obviously it is false if x2 then x24 that is not 2 2 3x such that px This is true because if xl then x2l Example 8 What is the negation of Vx px ie 1 W Sol n Ifa predicate px is not true for all x there exists some x st px is false then px is true for some x We say OSU CS 3653 Fall 2002 Lecture 158 T Menhaj lvx PXEVX Px is the same as 3x SI px 2 What is the negation of 3y Qy ie3y Qy Similarly we say that for a proposition Qy 3y Qy is the same as Vy Generalized Demorgan s Laws for Logic a VX PX E EIX PX b ax PX a VX 430 Example 9 pX 2X2 2 gt 1 X is a real number Show that for some real no X pX is false VX E 93 pX 2X22S1VX e an X 6 SR 3 X2 Z 0 x2 2 2 2 2x2 2 s 1 OSU CS 3653 Fall 2002 Lecture 159 T Menhaj Summary 1 To prove VX PX is true we have to show that PX is true for every X in the domain of discourse D 2 To prove that the universally quanti ed statement VX PX is false nd one value counterexample in D for which PX is false 3 To prove EIX PX is false show that VX PX for every X in D PX is false OSU CS 3653 Fall 2002 Lecture 1510 T Menhaj Deduction The reasoning process that leads from premises to a conclusion is called a deductive mechanism deduction Again we should note the distinction between validity and truth something is true is different from something is valid It is said that an argument is valid or the deduction mechanism is valid if the truth of the conclusion follows from the truth of the premises No even number is a multiple of 3 6 is an even number therefore 6 is not a multiple of 3 This deduction process or reasoning is valid though its conclusion we know is false therefore valid means logically correct Note It is not true that a valid deduction mechanism based on false premises necessarily leads to a false conclusion No even number is a multiple of 3 8 is an even number OSU CS 3653 Fall 2002 Lecture 1511 T Menhaj therefore 8 is not a multiple of 3 Note that the conclusion is true So about a valid reasoning it is important to remember that Whenever its premises are true its conclusion must be true Example 10 Premise m is an odd number Conclusion m2 is an odd number Proof m 2k 1 k e Z m2 2k12 22k2 2k1 Even number lodd number Therefore this is a valid argument noting that of course the premise may or may not be true for a given m An invalid argument is one in which the conclusion may be false even ifits premises are true OSU CS 3653 Fall 2002 Lecture 1512 T Menhaj Proofs A proof is nothing but an argument it establishes the truth of a theorem so we may conclude that logic is a tool for the analysis of proofs OSU CS 3653 Fall 2002 Note Generally speaking a mathematical system or aXiomatic system has aXioms de nitions and unde ned terms lAXioms are assumed to be true 2 De nitions are used to produce new terms concepts in terms of the eXisting ones 3 Theorems are derived within a system A theorem is indeed a proposition that one tries to prove it is true A corollary is viewed as a theorem that follows immediately from a given theorem Lecture 1513 T Menhaj A lemma is also a theorem that is used to prove another theorem that is of our concern Theorems are of the form V X1 Xn lfpX1 Xn then qX1 Xn This statement is true provided that the conditional proposition if pX1Xn then qX1Xn is true for all X1 Xn in the domain of discourse Direct Proof Prove directly qX1 Xn is true by assuming that pX1Xn is true and using pX1Xn as well as other axioms de nitions and previously derived theorems Example 11 For all real numbers a1 a2 a3 a4 and x lfa mina1 a2 andxltathenxlta1 andxlta2 Indirect proof proof by contradiction OSU CS 3653 Fall 2002 Lecture 1514 T Menhaj Motivation pgtq5pA qgtr r Why p q r paq pmq rA r pA qarA r T T T T F F T T T F T F F T T F T F T F F T F F F T F F F T T T F F T F T F T F F T F F T T F F T F F F T F F T So in indirect proofs I assume that the hypothesis p is true and that the conclusion q is false 2 then use p and q as well as other axioms de nitions and previously derived theorems to derive a contradiction39 a proposition of the form r r OSU CS 3653 Fall 2002 Lecture 1515 T Menhaj Example 12 VXy E 93 if p xy22then eitherXZ l oryZ 1 Proof by Contradiction Assume that the conclusion is wrong ie X lt l and y lt 1 this implies that X y lt 2 E p this says that the hypothesis p is false so we end with p p contradiction or we start from q and arrive at p q 9 p Valid and Invalid Arguments Argument p1 the error is in subroutine l or subroutine 2 p2 the error is a numerical error p3 subroutine 1 has no numerical error Therefore the error is in subroutine 2 This is a deductive argument reasoning OSU CS 3653 Fall 2002 Lecture 1516 T Menhaj A deductive argument is any argument with the form OSU CS 3653 Fall 2002 If p1 and p2 andand pn then q This argument is called valid if the conclusion follows from the hypotheses premises that is if p1 and p2 and and pH are true then q must also be true Note The conclusion is granted Whenever the hypotheses are granted39 the argument is valid because of its form not because of its content Example 13 Find Whether the argument pgtq p therefore q is valid39 ifp is true but q is false the p q cannot be true39 thus a contradiction eXists Lecture 1517 T Menhaj Example 14 p 9 q 1 therefore p Is this a valid argument No look at the third row in the truth table above p q and q are true but p is false Or assume that the conclusion p is wrong from the fourth row in the table q must be false contradiction OSU CS 3653 Fall 2002 Lecture 1518 T Menhaj Algorithms Definition A stepbystep characterization of a method of solving a given problem how to perform a certain task precisely Note Algorithm 2 Function 2 System 2 I 0 Some important considerations 1 Unique yet correct solution 2 How robust is the solution How accurate is the solution Some important properties Completeness a Finite set of actions precisely speci ed algorithm terminates after nitely many instructions execute b Each action followed by a unique successor action OSU CS 3653 Fall 2002 Lecture 81 T Menhaj c The initial action must be unique this leads to uniqueness of the intermediate results of each step of execution In short An algorithm is a nite set of instructions OSU CS 3653 Fall 2002 Lecture 82 T Menhaj Example 1 Given three numbers m n p Write a program that nds the minimum number OSU CS 3653 Fall 2002 Lecture 83 T Menhaj Example 2 LetIEDleDo Find 1I1 1E3E2E1Eo ie 1982F0983 1999F1000 Computer understands i digits from 0 to 9 N how to add 1 to digits 01 8 3 basic mathematical notation Flowchart CS 3653 Fall 2002 Lecture 84 T Menhaj It is easily seen that an algorithm presents a stepby step procedure for executing a sequence of operations to solve a problem Pseudocode int4 AddOneD3 int E4 int i for i0ilt2i ifDi9 Ei0 ifi2 E31 else EiDi1 Whi1ei2 i EiDi return E OSU CS 3653 Fall 2002 Lecture 85 T Menhaj What is pseudocode o It resembles the actual code oflanguages such as Fortran and C o It is code with the properties of precision structure and universality Pseudocode for minXyz inputs Xyz output m minXyZ int m if yltX then mX else my if zltm then mz return m Example IfI use qmin479l 186 q becomes 4 OSU CS 3653 Fall 2002 Lecture 86 T Menhaj Functions De nition A special kind of relation Given relation Q c A X B Q xay l x E Ay 63 Note Domain Q x E A l xy E Qf0r somey E B If FA B Which is a relation also to be a function the domain ofF must equal A amp ifxy amp xy are in F then we must have yy Summary A function FA B is a relation fromA to B with the following properties 1 The domain ofF is A 2 IfxyEF amp xy39EF3yy39 OSU CS 3653 Fall 2002 Lecture 87 T Menhaj Example 3 A 111112113 B 12345 F Ya1anz2n33 Is F a function Domain FDomF 111112 n3 A xay E F ampxy1E F 3y y1 this is obvious since each element in A goes to just one element in B RangeF yEBl xeAxy F uzac3 Note A sequence is a special type of function OSU CS 3653 Fall 2002 Lecture 88 T Menhaj Example 4 Al2345 Bn1nzn3 F ln12nz3n3 lsF a function No Why DmnaoL23 A Example 5 An33L BW mmL F 11111n3 2n23n3 IsF afunction No Why 1 goes to n1 amp n3 Violating the second condition because for each X in DomF there must be just one Y in RangeF suchthat xyeFyFx OSU CS 3653 Fall 2002 Lecture 89 T Menhaj See the Prime Algorithm LxJ the largest integer not gtx or the largest integer X Examples LSAJ 5 L59J 5 L023 2 0 L SlJ 6 LSJ 5 Is a function Yes f R gt Z l Domf R Range 2 2 Jay E f amp xy E f 3y y because for any x there is exactly one largest integer in Z that is not bigger than x This function is called the floor function The same is for the ceiling function x the smallest integer not lt X ie the smallest integer Z X OSU CS 3653 Fall 2002 Lecture 810 T Menhaj 4311 413141 2311 0514 212 Domd R Ranged Z Note xl LxJL er LxJ xEZ 34 3L 34J1 T M W 2 lt OSU CS 3653 Fall 2002 Lecture 811 T Menhaj Example 6 Mod modulo function f N X N N n mod m fnmp c n mqp cpn Jm m neN meN pEN This is nothing but a remainder function 7mod27LJ27 32l 7mod87 LJ87 087 Application Pseudorandom numbers Computers are used to simulate random behavior using some programs they generate numbers that appear random are called pseudorandom numbers These numbers are not truly random that s Why they are called pseudorandom because if you know the program generating them you may predict what number will be immediately follows OSU CS 3653 Fall 2002 Lecture 812 The method frequently employed for producing the pseudorandom numbers requires four integers and uses the following generic equation 2quot aozn71almodp ZSaO lt17 OSLIl ltp0Ssltp where p is the modulus and s is the seed number Steps l 20 Z S 2 zquot aozw1 0 mod p Assume that pll 0109 a17 s739 the sequence of pseudorandom numbers becomes The sequence of numbers will repeat In practice large values are used for p and do like do 11 1726371 These values generate a sequence of 263 l integers before repeating a value see the following figure seed number7 OSU CS 3653 Fall 2002 Lecture 813 T Menhaj Pseudorandom numbers Some commonly used functions 1 Exponentials f N X R gt H fxax aEN Properties 1 axay 201 2 ax gt xquot it grows faster that X ne N if agt1 ie gt0 agt1 OSU CS 3653 Fall 2002 Lecture 814 T Menhaj m 85 mu 5 mquot L022x mquot 0 2x I rf 5 m Logx4 a m quot5 m 8 1 W W 5 5 Lin 15 b 6 x OSU CS 3653 Fall 2002 Lecture 815 T Menhaj Lecture 9 Algorithms cont d Logarithms ll R y 10gbx by x 13 gt1 3 is the quotbasequot Traditional base10 Example 1 10g4162 y10g4l63164y3y2 10g2163162y3y4 Log2x 10gbl lzby3y20 bgtl OSU CS 3653 Fall 2002 Lecture 91 T Menhaj Flogbx 2 biz Properties 1 blog 2 x 10gb by y Proof Let logbxc xbc Letbczzszzx 2 logxy logx logy OSU CS 3653 Fall 2002 Lecture 92 T Menhaj 3 logx alogx 4 loga x 0gb x log a l 511mlogx 00 llm 0 X900 00 x De nition A function f from A to B fA B is said to be onetoone injective if for all y in B Vy E B there is at most one X in A El X E A with fXy 3 ifxx39EA ampfxfx393xx39 Example f R ll x20 xlt0 fxl xl OSU CS 3653 Fall 2002 Lecture 93 T Menhaj This function is not onetoone inj ective Examples y 3 x 6 5K Injective y Sinx x 6 5R Not injective 7T 7139 y Sm XE Injective De nition Onto surjectivef A B f is called onto B or surjective ifits range is B OSU CS 3653 Fall 2002 Lecture 94 T Menhaj The function f A BA nlnzn3n4B 123 f n11nz2n33n41 is onto B Examples fiN X91991 fx3x Onto on positive real numbers f07z 91 fxsinx Not onto on real line f0gt e0gt1lgt fxsinx0nt0 on 01 f9a711 fxsinxOnto on ll not oneto one De nition A function which is both onetoone injective and onto surjective is called a bijective or onetoone correspondence For example f R R y 2x is a bij ective function OSU CS 3653 Fall 2002 Lecture 95 T Menhaj Examples f3 gt al 1gt1lgt flx5mx bijective Sinx 2 fi0 11 fxsinxNot bijective Sinx Note If f is bijective we can de ne f l B gtA f 1yx wherefxy OSU CS 3653 Fall 2002 Lecture 96 T Menhaj Let A nln2n3B 123 f A gt B f n121n22n33 f is bijective39 f 1 B gt A fil 12nl2n23n3 Example Inversefx 3X isf 1x log3 x That is for each y in positive real numbers y 65W f71 Y is the logaIithm to the base 3 of y The inverse of exponential function is the logaIithm function OSU CS 3653 Fall 2002 Lecture 97 T Menhaj Polynomials R R y Pnx Zaixi n E N i0 a0 a1x anxquotan 0 ai scoef cients f g variable parameters y 131x a0 alx E apao linear polynomial See the following figure for 00 1 611 05 ySX1 How about n0 y Pox a0 with range of just go Thus P0X is not onto OSU CS 3653 Fall 2002 Lecture 98 T Menhaj Definition Composition of two functions fog fA gtBgB gtC rangefgdomaing hzgofA gtC hxgfx Note f 1fx xf f 400 y f R gt R fx sinx g R gt R gx tanhx g of R gt R gfx tanhsinx For more read sections 03 04 OSU CS 3653 Fall 2002 Lecture 99 T Menhaj Back to Algorithms Main Components of a Pseudocode 1 Assignment variablelt eXpression or variableeXpression xa replace the current value of X by the value of a Common assignment operators gtlt 2 ifthen structure if condition then actionl else action2 endif 3 for structure for kk0 to kf actions kk0kk0l kkf end for OSU CS 3653 Fall 2002 Lecture 910 T Menhaj 4 While structure While condition actions endwhile also known as repeat until contition Example nd the minimum number in X1X2 Xn Input The sequence of numbers amp their length n Output y the minimum number function yminXn Xarray of size 1 to n yX1 i2 while iltn if ygtXi then yXi end function zminl0252 455 2 z 10 OSU CS 3653 Fall 2002 Lecture 911 T Menhaj This use of While can be rewritten as a for loop as well function yminXn Xarray of size 1 to n yX1 for i2 to n if ygtXi then yXi end if endfor end function Question do we need to prove y contains the minimum of XlX2 Xn Yes39 Proof By induction on n 1 Basis after completing the for loop for i2 the number in y is the minimum of Xl and X2 2 Assumption assume the statement is true for im the number in X is the minimum of Xl Xm 3 Induction step the for loop iteration for iml y will contain the minimum of OSU CS 3653 Fall 2002 Lecture 912 T Menhaj XmlampXl Xm minimum of Xl XmXml Time complexity I the time it takes to compare two numbers Xi amp Xil Tthe total timenl I Note we may have two different algorithms for a given problem with different time complexities OSU CS 3653 Fall 2002 Lecture 913 T Menhaj Prime numbers n e Nn gt1 is a prime number if it is divisible only by l amp itself like l237111317 but 468910 are not function Tprimen if ngt2 then if 2 divides n Tfalse retum endif while kltn 2 and T if k divides n then Tfalse end if kk2 endwhile endfunction Tp1ime l 7 print T Ttrue Note k divides n k mod n0 stsan k OSU CS 3653 Fall 2002 Lecture 914 T Menhaj Example Find the smallest prime number gt n n e Nl function xsmallprimen xnl while primeX false xXl endwhile print X end function OSU CS 3653 Fall 2002 Lecture 915 T Menhaj The Euclidean algorithm It is used to nd the greatest common divisor of two integers Facts alb c Elqu st bzaq a 0 then gcdab a ie gcd4124 since 412 Let dbe Namp both not zero Among all integers that divide both a amp b there is a largest divisor called the greatest common divisor gcd of a amp b Divisors of 15 13515 Divisors of 35 15735 common divisors 15 gcd5355 OSU CS 3653 Fall 2002 Lecture 916 T Menhaj Note if c is a common divisor of a amp b then claib and l acq amp bcq then aibqiq 0 N ifcla then clab abcq b cq1q1 qb U Let baqr rremainder 0Srlta and let 0 be a common divisor of a amp b acq amp bcq then claq amp clbaq cclr So 0 is a common divisor of a and r The converse is also true if c is a common divisor a amp r so is the common divisor a amp b Therefore gcdabgcdar gcd3515 35lS25 gcd3515gcd1555 15530 gcd155gcd505 Note gcda0 a ae Z OSU CS 3653 Fall 2002 Lecture 917 T Menhaj gcd0 00 Now let r0b r1a r2r r0r1q2r2 gcdm r1 gcdr1 r2 if r2 0 divide r1 by r2 to obtain r1r2q3r3 0Sr3ltr2 gcdr1r2gcdr2r3 continue this procedure eventually some r1 will be zero ie rn0 gcdr0r1gcdr1r2 gcdrn10rn1 Since r1gtr2gtr3gt the greatest common divisor is rm OSU CS 3653 Fall 2002 Lecture 918 T Menhaj gcd algorithm Input 01 b 2 0 function cgcda b r0maxab r1minab while r1 is not 0 q oornd I 7041 VI 702 7391 r1r end while C 7390 print c end function Find gcd30590 30590335 9035220 3520115 201515 15530 gcd30590gcd9035gcd3520 gcd2015gcd155gcd505 305615 90165 OSU CS 3653 Fall 2002 Lecture 919 T Menhaj Lecture 10 Algorithms cont d Recursive Algorithm Example n llquot i n nl Original problem Find n Decompose it into simpler subproblems Find nl n20l The solutions ofthese simplier problems are combined to solve the original one Algorithm Input n function Nfactoria1n if nlt0 then Nl else Nnfactoria1n 1 end if endfunction Definition A recursive function is a function that invokes OSU CS 3653 Fall 2002 Lecture 101 T Menhaj itself A recursive algorithm is an algorithm that contains a recursive function Note there must be some situations in which the recursive algorithm does not invoke itself Bases Cases The values for which the algorithm does not call itself Recursive algorithm for gcd problem Input a b e 2 both nonzero function N gcdirecp l amaxAyBy Alternatively if AgtB then aA bB else aB bA bmmAB endif if b0 then Na else ra mod bE a iglb Ngcdirecbr endif endfunction OSU CS 3653 Fall 2002 Lecture 102 T Menhaj Example Consider the equation xk 5xk l2xk 2 Letx0 l x11 x2 0571 021 03 x3 0503 0271 7005 x4 0570050203 00353939xkZg osu CS 3653 Fall 2002 Lecture 103 T Menhaj Algorithm for Xk Function xdi eqa b If a0 and 130 then x0 return Endif x05a02b ba ax Fdz eqm b endfunction OSU CS 3653 Fall 2002 Lecture 104 T Menhaj Algorithmic language Syntax and Semantics 11 Assignmen LHSRHS LHS stands for Left Hand Side RHS stands for Right Hand Side LHS is a variable RHS is a mathematical eXpresssion Examples a2 a2 sint4 c0st a2 a 12 Selection lfPl then q1 q2qn endif OSU CS 3653 Fall 2002 Lecture 105 T Menhaj ifpl then qlq2qn else qnlqm endif if pl then pl p2 then ql pn then qn else qnl endif 13 Iteration 0 13 OSU CS 3653 Fall 2002 for ii0dif i i0 i0d i02dif Instructions endfor repeat ifp then eXit p is a logical expression endrepeat Lecture 106 T Menhaj This is the same as repeat until p endrepeat IO information Inputa quotx or Reada quotx Outputa quotx or Displaya quotx or Printa quotx or Writea quotx OSU CS 3653 Fall 2002 Lecture 107 T Menhaj Example Write an algorithm to calculate ex Fact 2 xk 1x x2 x3 function yeXpX n0 sl fnl if Xlt0 then tX endif yX repeat until tlt10A6 SSy nnl fnnfn tlfnXAn yt if tlt0 then tt endif endrepeat endfunction OSU CS 3653 Fall 2002 Lecture 108 T Menhaj Algorithm for polynomial evaluation function ypolyx n a0 to n y0 for 139 0 to n za 1 for j1 toi 22 x endfor yyz endfor endfunction check Let 112 a i0 ya0 139I ya0a1x i2 ya0a1xa2xA2 OSU CS 3653 Fall 2002 Lecture 109 T Menhaj Number of additions 3 Number of multiplications 3 OSU CS 3653 Fall 2002 Lecture 1010 T Menhaj What if we rewrite ya0alXa2XA2 as ya0lXa1la2lX Number of additions 2 Number of multiplications 2 So this new algorithm is more ef cient Code function ypoly1 x aI to nn ya0 sI for F1 to n ss x yyazs endfor endfunction OSU CS 3653 Fall 2002 Lecture 1011 T Menhaj Note In general the rst algorithm requires n1 additions amp 12111 nnl2 multiplications The second algorithm requires n additions and n multiplications OSU CS 3653 Fall 2002 Lecture 1012 T Menhaj Discrete Mathematics Lecture 1 Meaning and Motivation A kind of mathematics we as user designer programmer strongly need to know to communicate with computers It includes set theory relations and functions vectors and matrices probability graphs and trees mathematical logic and induction Applications Circuit Design requires Boolean Algebra Expert Systems AI requires Sets and Logic Knowledge Base requires Relations and functions and so many others CS 3653 Fall 2002 Lecture 11 T Menhaj Preliminaries Set Theory Foundation of the entire Modern Mathematics 39 Mathematically speaking there is no de nition for set and element because of the circular definition ie the concept to be defined used in the definition The best conventional de nition of a set may be stated as Set An unordered Collection unique of elements possessing some common property Examples1John Apple Pen 0 078 2 Coin Experiment S heads tails De ning sets in terms of the properties of their elements Aall integers from 2t020 1 Rule Method 2 Tabular Method 1279 The objects are called elements Upper case letter denotes sets and lower case letters denotes the elements CS 3653 Fall 2002 Lecture 12 T Menhaj NE012 ZE 2 1012 QEb 0abeZ Q Eqquqgt0 N123 Finite Set Finite Numbers of Elements equivalent to 12n for some n in natural numbers 0 Empty Set E contains no elements 0 Infinite Set Infinite no of Elements XSet of all natural Numbers Countable Set A finite denumerable or empty set Infinity many elements can be counted elements have 1to 1 correspondence with the positive integers CS 3653 Fall 2002 Lecture 13 T Menhaj Cardinality No of elements Noo 12nneNln Equivalent Sets Two sets A and B are equivalent if there is 1to 1 correspondence between them Subset A is a said to be the subset of B if every element ofA is in B ie A E B o For any Set S with n elements 11 elements there are 2quot possible subsets of S CS 3653 Fall 2002 Lecture 14 T Menhaj Inductive Paradigm Proof Let n 0 S implies that the only subset is Q For n1 Ss subsets are S and Q It can also be proved for others Recursive Paradigm Sn 2 a set with n elements 2 12n Nn no of subsets of Sn Discussed in the class N n 1 2N Recursive Equation Universal Set S Largest set Contains all elements Set Operations A E B gt AequalsBiff ACB amp BCA CS 3653 Fall 2002 Lecture 15 T Menhaj Complement of A Z Set of elements of S not contained in A Union All elements belonging to A or B or Both 3 AUB Intersection Those elements which are common to both A A B S 39Disjoint SetiTwo sets with no common mutually exclusive element A 13 lt1 and B CS 3653 Fall 2002 Lecture 16 T Menhaj Differencez AB All elements of A that not in B A BA A BA BUB A An uBnZAuB An3 Notes If AgB then AngngnBzA IngBampBgCthenAgC AUB BUA amp AnB BnA Commutative AUB UC AUB u C AUBU C A BmC AmBmCA B MC 3ASSOCIat1Ve AUBmC AmBuBmC Distributive CS 3653 Fall 2002 Lecture 17 T Menhaj Example 5 x0 s x 10 XEER A A Z 0 1 2 3 4 5 6 7 8 9 1 AB B A B AUB quot B B Zmosxslq im0gxlt3amp0ltxg1q A Bx3SxS7 AUBxleS9 A Bxl x 3 Notation qA AuAlj HUAH Agm A An CS 3653 Fall 2002 Lecture 18 T Menhaj Partitions A partition of S is a collection A A1A2Am of subsets of A1A2Am of S with the following property Ai AjCD i jUAS A1 A6 il nPartition An npartition of A consists of a sequence of sets Ai i12 n such that A CA Ai A 01 ms and UAZ 2A il Given A and B a 2partition ofB is BBmAuBmg Why BB SB ltAUZgtB AUB Z Note If A is a subset of S knowing that A Zc1gt amp AUAS Hence A2 is a partition of S CS 3653 Fall 2002 Lecture 19 T Menhaj Demorgan s Law AUBZ A BZUE CS 3653 Fall 2002 Lecture 110 T Menhaj Lecture 14 Mathematical Logic Logic 7 its subject is reasoning it measures the value of reasoning whether something is correct it is a set of rules to draw inferences Note The form of logic is nothing to do with the content of the subject to which it is applied Example 1 1A11 CS graduate students know Discrete Math Everyone who knows discrete math knows the fundamentals of mathematical logic Therefore all CS graduate students know the fundamentals of mathematical logic 2 No even natural number has a square root 4 is an even number Therefore 4 does not have a square root OSU CS 3653 Fall 2002 Lecture 141 T Menhaj OSU CS 3653 Fall 2002 Note The conclusion is false but the reasoning is valid logically correct ie Whenever the premises are true the conclusion must be true 3 No even natural number has a square root 8 is an even number Therefore 8 does not have a square root Note Here the conclusion is true and the reasoning is valid but is not sound because the rst premise is not true A valid reasoning called sound if the premises are true Question Does logic help us to nd out the truth of these statements NO Then Why do we need to know mathematical logic To check if the computer programs are correct39 logical analysis Mathematical Induction is one of the general methods in logical analysis to prove that an argument is correct Lecture 142 T Menhaj L 39Propositional Logic og1c Predicate Logic Note In any system established by some certain axioms a class of statements is true it is possible to make some other statements Whose truth values are unknown Propositional Sentential Calculus De nitions Proposition The basic building block oflogic A declarative sentence which is either true or false is called a proposition eg John is tall eg p John is tall Propositional Variable nnl pm 2 Combined compound propositions They are obtained from single propositions using connectives and conjunction and or disjunction OSU CS 3653 Fall 2002 Lecture 143 T Menhaj OSU CS 3653 Fall 2002 p John is tall q John is a CS Graduate Student r p andq 2 John is tall and he is a CS graduate student Truth Table It describes de nes precisely and concisely the truth values meaning of compound propositions Note Two propositions are logically equivalent if they have the same truth value Compound proposition P consists of elementary propositions p1 pn T T T F F F F T F cc 3 3 cc inclusive or a not and ccV exor exclusive or Lecture 144 T Menhaj Example 2 171 John is tall 172 John is a CS student 173 John wrote a computer program and implemented the lucky key problem Either John is tall and it is not the case that he is a CS student or he wrote a computer program to implement the lucky key problem P p1 p2 v p3 If all three are true the value ofP is T F v T T Different forms of and l p and q X is even and y is odd 2 p q X is even y is odd 3 Whereas p q X is even Whereas y is odd 4 p but q X is even but y is odd 5 Although p q although X is even y is odd OSU CS 3653 Fall 2002 Lecture 145 T Menhaj OSU CS 3653 Fall 2002 Mathematically they all are expressed uniquely as pAq Question why different forms Consistency oflanguage in writing like a poem not recommended whereas in mathematics strongly recommended Question How many binary connectives do eXist Answer Use of Product Rule There are 4 entries in the truth table that each can have values ofT true or F False each entry has two choices from the product rule we can conclude that there will be totally 222224 16 possible binary truth tables or logical functions De nition Conditional Propositions A compound proposition pr then q or p q p John has enough background in CS3653 discrete math Lecture 146 T Menhaj OSU CS 3653 Fall 2002 q He will solve the lucky key problem p is called the antecedent hypothesis if part cc 3 q is called the consequent conclusion thenpart Example 3 1 John may take CS4883 only if he has sophomore junior or senior standing 2 if John takes CS4883 then he has sophomore junior or senior standing 2 When you talk I will enjoy 2 I will enjoy when you talk 3 A suf cient condition for John to pass CS3653 is that he should make at least a C in this course 2 If John makes at least a C in CS3653 then he will pass it The hypothesis eXpresses the suf cient condition 4 A necessary condition for John to take CS 3653 is that he should have taken the prerequisite courses 2 if Lecture 147 T Menhaj OSU CS 3653 Fall 2002 John is taking CS 3653 then John has already taken the prerequisite courses The conclusion expresses a necessary condition Implication Connectives peg T Not making a claim about q ifp is false so p a q is nothing but to say q is true ifp is true p iffq E p if and only if q biconditional proposition 2 equivalence connective E p is a necessary and suf cient condition for q 2 p exor q let p3lt9 q 10ltl7 The statement if3 lt 9 then 10 lt 17 or the statement p q is true because both p and q are true Lecture 148 T Menhaj The statement if p 2 lt 15 then q 10 lt17 or the statement p q is true because p is false and q is true The statement p 3 lt 9 iff 10 lt17 3 p lt gt q is true Logical Expression le A logical eXpression le can be obtained de ned recursively by some syntactic rules as 1 An individual atomic proposition is an 1e 2 pr is an le so is p 3 pr and q are les so are pq pvq p e q and p 9 q 4 Any le formed by 13 or by this rule may have parentheses placed around it 5 Whenever there are two or more binary connectives not separated by parenthesis the le evaluated by using the precedence rule for connectives from high to low 1 2 A 3 v 4 a 5 lt gt and iffurther two or more instances of the same binary connectives are OSU CS 3653 Fall 2002 Lecture 149 T Menhaj OSU CS 3653 Fall 2002 not separated by parentheses they are evaluated from left to right Example 4 pqsa Sq 39P pAq amp SAq PND AS pAq AS e SAq De nition Compound propositions P and Q are made up of the propositions p1 pn It is said that P and Q are logically equivalent P E Q if given any truth values pi s either P and Q are both true or P and Q are both false Example 5 F F q v p E p q these are logically equivalent Show that Lecture 1410 T Menhaj p q E p q Contrapositive or Transposition of p gt q Proof P q P v 1 q Hp T T T T T F F F F T T T F F T T Example 6 Show that the following propositions are equivalent 1 If it is Sunday and I am not on call I will drive to a short trip 2 If it is Sunday then ifI am not on call I will drive to a short trip Sol n De ne p it is Sunday q I am not on call s I ll drive to a short trip OSU CS 3653 Fall 2002 Lecture 1411 T Menhaj u t O p q s P Q pm as w q as T T wmwwaaaa WWHHmmHH wawawama HHHHHHw HHHHHHw HHHHHHHH Tautology A logical expression le possessing the property that it is true for all possible values of its atomic propositions is called a tautology it is true no matter What the inputs are no matter What the facts are see last column of the above table Note Given logical expressions P and Q we said that P logically implies Q if P a Q is a tautology OSU CS 3653 Fall 2002 Lecture 1412 T Menhaj Lecture 18 Graph Theory cont d Multigraph Need to use some notation like the ones used before for graphs Let G N A A 7 a multiset of ordered pairs from N X N What is a multiset De nition multiset 7 A collection of objects not necessarily distinct Examples E l22l333 F 1111 G 123H L 8 In E 1 has multiplicity 2 element 2 has multiplicity 2 element 3 has multiplicity 3 Ifa g E we say that the multiplicity ofa in E is 0 Note A set is a special case ofa multiset OSU CS 3653 Fall 2002 Lecture 181 T Menhaj E UF llll22333E F 11 Let E and F be two multisets The union intersection of E and F E U F E n F is a multiset such that the multiplicity of an element in E U F E n F is equal to the maximum minimum of the multiplicities of the element in E and in F The difference ofE and F E 7 F is a multiset such that the multiplicity of an element in E 7 F equals the multiplicity of the element in E minus the multiplicity of the same element in F provided that the difference is positive and it becomes zero if the difference is zero or negative E 7 F 22333 OSU CS 3653 Fall 2002 Lecture 182 T Menhaj Back to multigraphs An undirected multigraph is similarly de ned as G N A A 7 a multiset of unordered pairs from N X N l G G a 3 ZS b Directed Multigraph Undirected Multi graph G 1234 12 13 13 14 41 41 23 34 43 34 24 24 G aab aab ebb 210 210 bac bc bc Now we are ready to express the K6nigberg Problem which is a multigraph in a more proper pair as follows OSU CS 3653 Fall 2002 Lecture 183 T Menhaj G abcdab130acacadadbd N A Weighted Graphs Sometimes it is necessary to attach some additional information to nodes andor the arcs of a graph Consider the soccer tournament problem we might want to assign a number to each arc to indicate the score from the two teams connected by the arc In addition we might wish to label each team with its correct rank in the soccer society This is the motivation for weighted graphs A weighted graphs is either an ordered quadruple N A f g or N A t or an ordered triple N A g OSU CS 3653 Fall 2002 Lecture 184 T Menhaj Where N 7 set of nodes A 7 set of arcs f a function to assign some information to the node in N g a function with domain A to assign some information weight to each arc in A fand g are called weight functions ie fg is an assignment of weights to the nodes arcs Weights can be number symbols or any other desired quantities Example 1 Model the behavior of a citybus vending ticket machine that sells tickets for 50 cents and 1 Assume that the machine accepts only quarters and 1 bills and it will not return any change when more than the correct amount needed is deposited The weighted graph given below represents a description of the behavior of the machine39 the nodes correspond to the OSU CS 3653 Fall 2002 Lecture 185 T Menhaj amounts that have already been deposited for the current sale 0 25 cents etc l 0 cents deposited 2 25 cents deposited 3 50 cents deposited 4 75 cents deposited 5 1 or more deposited OSU CS 3653 Fall 2002 Lecture 186 T Menhaj Note A customer at any moment can do one of the three things deposit a quarter deposit a 1 bill or press a button for a ticket of her choice Definition A path from no to nm oflength m is de ned as an alternating sequence of ml nodes and m arcs starting with no and ending with node nm The path is represented by n09a 19n19a2939H nmbammm the arc a1 is incident on nodes ni1 and n1 il m Example 2 OSU CS 3653 Fall 2002 Lecture 187 T Menhaj In the above graph la12a86a73a4la96 is a path oflength 5 from node 1 to 6 Also the path 3 is a path oflength 0 from node 3 to node 3 Note If there is no parallel arcs we may omit the arcs and simply use the sequence of nodes to represent the path39 eg the above path may also be represented as l263l6 Example 3 Look at the following multigraph and de ne a path A sequence of arcs a11a12ajk such that the terminal node of aqj coincides with the initial node of aiGH forj 12 k 7 that is all an an is a path39 it is a simple path because it does not include the same arc twice A path is OSU CS 3653 Fall 2002 Lecture 188 T Menhaj called elementary if it does not cross the same node more than once ie no two arcs in the sequence have the same terminal node a11a13 is an elementary path all an a14 an an an is not a elementary path and all an a31 an an all is not a simple path Definition Connected graph A connected graph is a graph in which you can reach any node from any other node on a path ie for any node ni and nj there eXists a path from n1 to nj Connected Not Connected Note A connected graph consists of one piece Whereas a nonconnected graph has two or more pieces called subgraphs components of the original graph OSU CS 3653 Fall 2002 Lecture 189 T Menhaj Definition Subgraph Let GNA be a graph The pair N A is called a subgraph if 1 N QN amp A g A 2 Varc a EA if a is incident on nodes i andj then i andj must be in N A subgraph ofG is said to be a spanning subgraph if it has all the nodes of G The complement of a subgraph G N A with respect to the graph G N A is another subgraph G N A such that A A 7 A and N contains only the nodes with which the arcs in A are incident G N A N 1234 1 OSU CS 3653 Fall 2002 Lecture 1810 T Menhaj A 12 13 232a4 14 G N A 7 subgraph ofG N 123 A 12 13 23 G1 N A 7 spanning subgraph G N A Find A AiA 24 14 SON 124 Graphs OSU CS 3653 Fall 2002 Lecture 1811 T Menhaj Example 4 Find all subgraphs of the following graph n2 a1 n1 Gnlan2aal subgraphsG1G2G3G4 G1n1 111 G3 111112 OSU CS 3653 Fall 2002 G2n2 G4n1n2a1 2 a1 1 Lecture 1812 T Menhaj Definition Component The subgraph G ofG containing all arcs and nodes in G that are contained in some path starting at n a node in G is called the component ofG that contains n Example 9 1 13 1391 5 1 17 Let Gn1n2n3n4 9a1gta29a3gta4 G has one component namely itself Exercise Show that a graph is connected iff it has exactly one component OSU CS 3653 Fall 2002 Lecture 1813 T Menhaj Let G n1n2H3n4n5n6n7n8 313233a435936 The component of G containing n2 is the subgraph G1n1n2n3n4 a19a29a39a4 The component ofG containing n8 is G2 n8 Definition Let GNA be a graph A simple path from i toj is a path from i toj with no repeated nodes A cycle or circuit is a path of nonzero length from i to i with no repeated arcs A simple cycle is a cycle from i to i in which there are no repeated nodes except for the beginning and ending nodes both equal i For the graph given in example 3 OSU CS 3653 Fall 2002 Lecture 1814 T Menhaj a cycle is a path ai1a12 aik Where the terminal node of aik coincides with the initial node of ail The cycle is said to be simple ifit does not include the same edge twice and it is said to be elementary if it does not meet the same node twice In the above graph all an a31 a41 is a simple and elementary cycle39 all a21 an all is a simple cycle but not an elementary one Example 10 Path 7 is a simple path it is not a cycle and it is not a simple cycle Path 2642 is not a simple path is a cycle and it is a simple cycle OSU CS 3653 Fall 2002 Lecture 1815 T Menhaj How do we know if there is a path from one node to another Proposition In a graph with n nodes there is a path of no more than n 7 l arcs from node n1 to node nj provided that there exists a path from node n1 to node nj i ij Proof Consider the graph given below 531 n 3 From n1 to n2 there is a path an there are paths all an and an a31 from n1 to n2 Now suppose there is a path from n1 to nj Let ni nk nu nj be the sequence of nodes that the path crosses when it is traced from n1 to nj If there are m arcs in the path then there exist m 1 nodes in the OSU CS 3653 Fall 2002 Lecture 1816 T Menhaj sequence So if m gt n 7 1 there must be a node nt that appears at least twice in the sequence ie nintnknrntnj By deleting the arcs in the path that connect nt back to nt we get a path from ni to n containing fewer arcs than the original one We repeat this reasoning until we obtain a path with n 7 l or fewer arcs De nition An undirected graph is called connected if there is a path between every two nodes otherwise it is called disconnected A directed graph is connected if its corresponding undirected graph is connected A disconnected graph consists of more than two components Each of which is a connected graph A directed graph is called strongly connected if for every two nodes a and b in the graph there is a path from a to b as well as a path from b to a OSU CS 3653 Fall 2002 Lecture 1817 T Menhaj 2 5 3 4 3 Connected Disconnected E Definition Euler path and cycle Euler graph Back to the KOnigberg Problem Bridges represent arcs and the islands and the two banks of the river are nodes Clearly the problem of crossing each of the bridges once and only once is equivalent to nding a path in the graph that passes each of the arcs once and only once Euler developed a very simple rule to determine ifthere is a path OSU CS 3653 Fall 2002 Lecture 1818 T Menhaj in a graph that traverses each of the arcs once and only OHCC An Eulerian path is a path that traverses each arc once and only once An Eulerian cycle is a cycle that traverses each arc once and only once Proposition An undirected multigraph has an Eulerian path iff it is connected and has either zero or two nodes of odd degree OSU CS 3653 Fall 2002 Lecture 1819 T Menhaj Lecture 7 Probability cont d Joint Probability For two events A amp B that intersects in the sample space the probability pAnB is called the Joint Probability A B Venn Diagram Shown that pAuB pA pB pAnB SO pA B pA 1703 pAUB J0int Probability Note Probability amp Union ofA amp B never exceeds sum of pA amp pB The equality holds for mutually exclusive disjoint events OSU CS 3653 Fall 2002 Lecture 71 T Menhaj Conditional Probability Event B given such that pB 039 Form the ratio pAnB pB for any event A39 This ratio called Conditional Probability of the event A assuming the event B given B is denoted by pAlB m pAB p3 no meaning ifpB 0 Motivation In a manufacturing process 15 of the parts contain special labels and 30 of them are functionally defective Only 10 of parts Without such labels are defective The probability of a functionally defective part depends on our knowledge of the presence or absence of a label If a part has a label the probability ofit being functionally defective is 030 Let A a part is functionally defective and B a part has the special label then we denote the probability ofA given a part has a label B pAB03 OSU cs 3653 Fall 2002 Lecture 7 2 T Menhaj Interpretation 1 The conditional probability makes intuitively sense in terms of relative Frequencies n Trials of some experiment nA no oftimes eventA occurs nB no oftimes event B occurs nAB no oftimes both events Aamp B occur Given that event B has occurred the relative frequency of A is n AB nB In other words this means that An experiment is repeated n times and on each case the occurrence of the events A and B is observed Now because our interest is in those outcomes for which B occurs we disregard the nonoccurrence experiments This leads to a smaller collection oftrials In that collection the proportion of times that A occurs is nA nBnB39 since B occurs at each of nA Bnz pAmB them This ratio equals n n MB B OSU CS 3653 Fall 2002 Lecture 73 T Menhaj So pAlB 7 relative frequency of event A among the trials that produce an outcome in event B Example 1 Find the probability of drawing two aces in succession from a deck of 52 cards A1 iEvent that the rst card is an Ace A2 iEvent that the second card is an Ace Find PA1 A2 POM A2 PAZ l A1 PA1 PA1 4 52 PA1 lAz 3 51 51 cards left amp 3 A s PA1 A2 1221 Now consider drawing three cards from a 52 deck Ai iEvent that the ith card is an ace i123 Case 1 With replacement Intuitively we know that Ai s are independent so pal mAZ nA3j 45510quot OSU CS 3653 Fall 2002 Lecture 74 T Menhaj Case 2 Without replacement keep each card after drawn We expect Ai s are not independent PA1 A2 mA3 PA1PA2 mA3 l A1 PA1PA2 l A1PA3 l A1 mAZ iil18110 4 52 51 50 Thus we have approximately 455l8125 times better chance of drawing three aces when cards replaced than when put aside This is an intuitively satisfying result because replacing the aces drawn raises chances for an ace on the succeeding draw Interpretation 2 We may understand this de nition in a special case in which a random eXperiment are equally likely if there are n total outcomes then No of outcomes in B 113 PB n n pA B No ofoutcomes 1n A B nAnB n n pAmB 11AM PB quotB OSU CS 3653 Fall 2002 Lecture 75 T Menhaj Consequently Given B occurs A occurs ifA n B occurs Thus the conditional probability of A given B should be proportional to pA n B which is to say that39 pAlB 0c pAnB for some constant or we need to nd or use normalizing factor pSlB 1 ocps n13 ocpBl xlpB Thus 39 PA l B pA BpB Note pApAS Why Probability of A given B is nothing but the probability of A assuming that the entire sample space is B39 is that reasonable Yes because the event B has already occurred and we know that the occurrence of any outcome outside B is impossible OSU CS 3653 Fall 2002 Lecture 76 T Menhaj Proof of Conditional Probability formula Now as a probability we need to check the fundamental property of conditional probability pAB for a xed B as A ranges over all the events of S To do so we must show that these numbers pAB s are indeed probabilities that is they satisfy the three postulates 1 pABZO 2 pSB1 3 lfAnCCD then pAUCBpABpCB Knowing that AnB is an event and SnBB the rst two axioms are easily veri ed To prove the third one we know that if A amp C are disjoint their subsets AnB and CnB are also disjoint And since AUCnB A BUC BWC may write pAUC B pA B pCnB Mm 123 2 123 123 pABpCB OSU CS 3653 Fall 2002 Lecture 77 T Menhaj Example 2 Two Boxes B1 and B2 are given B1 contains 6 red cards and 12 White B contains 10 red and 8 white Select at random one of the following boxes and pick up at random one of its cards Find the probability p that the card selected is white Sol n The outcomes of this experiment are 36 cards B1 event consists of 18 cards B2 event consists of 18 cards 1 pB1pB2l 2 a box selected at random the event WWhite consists of20 outcomes The problem is to nd its probability We cannot directly do so because the 36 outcomes are not equally likely They are however conditionally equally likely subject to the condition that a box is selected As a model concept this means that 2 pWB1 12 18pW1B28 18 1 amp 2 are not derived they are assumptions about the model based on the hypothesis that the box and cards are selected at random OSU CS 3653 Fall 2002 Lecture 78 T Menhaj Now we shall derive pW deductively using the above assumptions PWl BlPW Bl PO31 PWl 132 pWo B2 B2 pW 0B112181213 PWn B2491229 The events Wm B1 amp Wm B2 are mutually exclusive and their union equals the event W Hence pWl32959 Note In about 55 ofthe trials the selected card will be White Graphical Representation Decision Tree for ball and box problem given above Root BOXl BOX2 OSU White Red White Red CS 3653 ecture 79 T Menhaj Outcomes and sample space S B0X1WhiteB0X1RedB0X2White Boxvred lt gt Mcomes Sequence of decisions Taken randomly We rather deal with pBoxi and pRedlBOXi Probabilities pBox 05 139 12 predlbox1 pwhitelbox1 predlbox2 p Whitelbox2 and 12 l 8 2 pbox1 whlte pboxz whlte Generalization OSU CS 3653 Fall 2002 Lecture 710 T Menhaj Repeated application of pAnBpAlBpB yields pAanCpAanCpBnC PAlB CpBlCPC pAnBrCnDpAlBnCnDpBlCnDpClDpD and so on Statistical Independence Example 3 Suppose a box contains 10 parts 3 ofthem are not good and suppose two parts taken at random from the box with replacement it means that the rst part is replaced before the second one is selected What is the Probability that the second part is defective given that the rst one is defective Sol n Denote A the second part is defective Bthe rst part is defective pAB Because the rst part is replaced prior to selecting the second one this makes the box contains still 10 parts of which 3 are defective Therefore the probability of A does OSU CS 3653 Fall 2002 Lecture 711 T Menhaj not depend on whether or not the rst part was defective That is pABpA310 Note Knowledge that the outcome of the experiment is in event B does not affect the probability that the outcome is in event A Definition Two event A amp B are independent iff one of the following statement is true 1 pABpApB 2 pAiBPA pB 0 3 pBiAPB pA i0 Consider example 3 Find the probability that the outcome defective defective 3 2 occurs th1s 1s equal to E 009 OSU CS 3653 Fall 2002 Lecture 712 T Menhaj Total unconditional or average Probability May show that S B AA BUA E AnB l Disjoint From axiom 3 pA pA m B pltA m pA BpB pltA 136 Generalization May express the probability of an event in terms of the known conditional probabilities Suppose A1 Am is a partition ofS consisting ofm events as shown below OSU CS 3653 Fall 2002 Lecture 713 T Menhaj S Consider B as an arbitrary event of S the probability PB can be written as sum mmimm4wwgt Why Obviously BBms SUA1 11 BBolJ1AlUBmAI 11 E UEI Ei 39s disjoint 11 mmipmt pE1pBoAzPBlA7PA7 This is called Total Probability theorem Summary Find PB of an event B ifits conditional probabilities are given OSU CS 3653 Fall 2002 Lecture 714 T Menhaj Ai s conditioning events possible causes B 7 an effect event Interpretation This provides us a way to evaluate an effect from its causes this determines the probability of an effect from all its possible causes probabilities and the relationship between these possible causes Ai s and effects and pBlAi s Now we may show that how pAilB is related to pAi pAilB Posterior probability pAi 7 Prior probability Known A703 mm ZT PBo4 MW pm BM Ax Plt4 Bgt W pltBMgtPltAgt CS 3653 Fall 2002 11 pa 147715 T Menhaj This is an important result known as Bayes theorem Special case For any two events A amp B we may write 128 pBnA 170302 pB l ApA pB l ApA M l ApA M l ZmZ pAlB B pAlB B Illustrative Example 5 of the Fort Worth Matadors football team uses steroids an illegal drug A certain test for steroids is 98 accurate if the player is using steroids 1 of the time the same test will indicate that a player is using steroids when they are not false positive The team quarter back Ju Painman OSU CS 3653 Fall 2002 Lecture 716 T Menhaj was selected at random for testing If the test was positive saying that he was taking steroids what is the probability that he was actually taking steroids Solution S Use of Steroids T Test for Steroids pcnoi pawgosa p w oor pST PT PT l SPS z pTlSpSpTlSpS 098005 098005001095 pSlT 03403 0 Example 4 Back to the lucky key problem demonstrated in the class 0 There are three boxes One of them does have the key You select one of them and you will have a chance to switch to the remaining box after one of the two boxes not containing the key was opened OSU CS 3653 Fall 2002 Lecture 717 T Menhaj Denote the event that box i may have the key by Bi il23 and assume that you select box 1 and box 2 opened Fact the event E that you will get the key by switching is equivalent to 33 mEZ mgr E means that there is no key in box i S0 7B3KWEzWE1I7B3 E2 E1pEz E1 lxpE1 Chance of getting the key by switching gets doubled Another way to look at it 0 Modeling 0 K A key is selected ErAn empty box revealed 0 Need To nd PKlEr Facts pKl3 pthe empty box selected lpK23 OSU CS 3653 Fall 2002 Lecture 718 T Menhaj 0 Use ofBayes theorem PKEr pEJIrK pEr pErKpK ngr pf By Total theorem The above conditiona probabi ities depend upon a random selection is made between the unchosen box or a prior knowledge is used so that always to open a box that does not contain the key 1 pErlK1 41 From 2 boxes one Is selected 1 Intentionally the empty box is opened pErll3l22323 for random selection pErl 13l 231 use of prior knowledge 1 1 1 T3 5 for random selection case p K IEr g 11 1 T3 g Use of prior knowledge OSU CS 3653 Fall 2002 Lecture 719 T Menhaj 0 So the probability of having selected a key given the empty box is observed is 12 with random selection and 13 if we use the prior knowledge that the empty box is always observed it means that here we are not using the additional information that the box being opened is empty The conclusion is We should switch Experimental Results We run some computer simulations The results are given in the following plots As one may easily see the results show a trend in the average consistent with the theoretical results obtained logically from the theory of probability axiomatic approach OSU CS 3653 Fall 2002 Lecture 720 T Menhaj Figure 1The probability ofchoosing the key in case of keeping i i i i i i i i l 0 o probability of nding the key ifthe chosen box was kept ii ii W iquot m Iii m M i iili ill iii nmilmii iil Crquot 4 quotW I H 39H iquot quot 1 Wu Ii n iiu39mili OSU CS 3653 Fall 2002 50 100 200 250 300 350 400 Different number oftrials 150 Lecture 721 450 500 T Menhaj ngure 2 The probabmty ofchoosmg the key H V case ofswwtchmg o oo o 1 JV 0 7 m l lhh quotHUN 1x luhxlanm J MHMl IhH LAWN 65 M Wm hr quotWI th h w w o 0 JV ow Probabmty of ndmg the key fthe chosen box Was Sthched o y 50 100 150 350 400 450 500 o 200 250 D fferent number ofma S O e g ngure 2 The probabmty ofchoosmg the key H V case ofrandom Se ectwon 7 2 g 065 e E E m 067 e Z 6 Q 0557 J H E 3 g 05 Whh IM IH I Ix HWMIHH WhiJllll h Mn 2 I WW quotqu w 1 ym q wwr w i 045 a x a E m 04 E e E f 0357 o i I 0 g 0 50 100 150 300 350 400 450 500 ci Dwfferent number OHr a S O OSU CS 3653 Fall 2002 Lecture 722 T Menhaj 39 Generalization for n boxes the chance of getting the key by switching becomes pE 17Bj mgquot j im e1np i 1 1 n l 1 gtlt 1 gt n 2 n nn 2 n note Bi chosen first Bm next opened Chance of finding the key becomes higher by switching OSU CS 3653 Fall 2002 Lecture 723 T Menhaj Lecture 6 Probability cont d The rating of tails or heads to tosses approaches 12 the ratio stays the same if one consider say every third toss This means for every 8gt0 may experimentally nd the number of times that 05 8 lt E lt 8 05 m 2 no oftime Tails occurs n becomes very large as 11 increases We have to note that the likelihood of getting exactly half of no of tosses tails is very small as the number of tosses increases but our intuition says that prob tail05 Example 6 In an election we poll hundred voters selected at random and 48 respond party X then we say that probability that a voter is of party X is 048 Now we can have the following physical interpretation With this estimated number PE we may say predict that in the next election 48 of the people vote party X CS 3653 Fall 2002 Lecture 61 T Menhaj Note This represents an objective interpretation of probability because it can be tested empirically Noting that the subjective interpretation of probability may be used as a measure of our belief that something is TrueFalse This is indeed subjective interpretation because it is based on some evidence ie one Juror may conclude with probability of 070 a defendant is not guilty and at the same time another juror may say that with probability of 095 the defendant is guilty Note Need to seek for a proper interpretation de nition of probability that the skepticism about the truth of probabilistic results shall be overcome Axiomatic Kolmogoroff 1933 Given S as a set of elements called Outcomes The set S and its subsets are called Events Assign to each event defined in a sample space a nonnegative number called CS 3653 Fall 2002 Lecture 62 T Menhaj Probability As a function of the events the probability assigned is chosen such that it satis es the following three axioms Selfevident Postulates 1 pE 2 0 2 p S 1 S0 S is called certain sure event Alternatively the empty set Q an event with no elements has a probability of zero p 0 hence Q it is known as the impossible better to say null event 3 If two disjoint events A1 and A2 de ned in a sample space S ie they have no elements in common Ala12 Q then the probability of the event A1 uA containing the outcomes that are in A1 or A2 is equal to the sum of the their probabilities pA1UA2pA1pA2 Note This applies to N events Ai i 1 N N 00 having the property A n A d for all i i j CS 3653 Fall 2002 Lecture 63 T Menhaj It is p UAI39 2 p Ai Z In nite Additivity Property as It goes to in nity i1 i1 probability of the union of any number of mutually exclusive disjoint events is equal to the sum of the probability of the individual events Note From all of the many observable actual outcomes characteristics of a real experiment which are large in number select those that are of the area of interest in their investigation Summary Given some real physical experiment having a set of particular outcomes possible Perform 1 De ne a sample space to mathematically represent the physical outcomes 2 De ne events to represent mathematically certain characteristics of the outcomes which are of interest 3 Assign probabilities to the events these mathematically account for the random nature of the experiments and they satisfy the three axioms CS 3653 Fall 2002 Lecture 64 T Menhaj Probability Space In probability theory the interest is the set of all possible outcomes of random experiments This set makes up the sample space S Each outcome is called a sample point An event contains one or more sample points The collection of events associated with a random experiment B should contain all S complement of each of its elements and union of any countable number of its elements The probability p is a function from this big set B to O 1 this function assigns a nonnegative number not bigger that l to the likelihood of each event The triple S B p is called a probability space Notes 1 An event ei consisting of the single outcome ei is called an elementary event 2 If S has N outcomes the number of its subsets equals 2N CS 3653 Fall 2002 Lecture 65 T Menhaj Hence an experiment with N outcomes has 2N events including the certain impossible elements Example Roll a single die S f1f6 it has 26 64 events all of them are members of B C60 1 events without any element namely null event Q 7 C6l events with one elements each namely the elementary events f1f6 C62 15 events two elements f1 f2f5f6 Finally C66l events with siX elements namely the certain event S Examples 1 Tossing a coin 2 Rolling a die CS 3653 Fall 2002 Lecture 66 T Menhaj 3 CS 3653 Fall 2002 Consider the experiment of tossing a coin repeatedly till the rst head turns up Model the universal set set of all possible outcomes If we de ne s E the outcome when the rst jl ips are tails and the ith ip is a head So S sls2 2 sp 139 123 Now wish to calculate a probability to the event E that the rst head occurs after an odd numbers of ips E U St i2k1kEN i6135 Example Remember the key problem demonstrated in the rst lecture in the class We have three boxes One box contains the key The host knows this The host always opens the box does not have the key Modeling Y Box Picked by you H Box picked by Host U Box left nonchosen KBox Contains the key Lecture 67 T Menhaj Let YK The event that Box picked by you indeed contains the key HK The event that Box picked by Host has the key UK The event that Box not selected contains the key Then pHKUUKl 12 3339 Fact HK UK 3 2 pHKUUKpHKPUK From Axiom3 Fact H m K 2 becasue the host always chooses the wrong box 3 p U m K Conclusion You must switch this will double your chance of getting the key Lemmas For a probability space S B p show that l p 0 Proof Since S and Q are disjoint pS pSU pSp from Axiom 3 llP fromAXiom2gtP 0 CS 3653 Fall 2002 Lecture 68 T Menhaj 2ifA c B thenpAS pBAandB are in B Proof SinceACBthenCB ACB A amp C are disjoint AuCzB PBPAPC fromAxiom3gtPB2PA Alternatively BBmSBMAUZBKAUBMZ AUBMZgtpBpApBmZgtpASpB disjoint so ifA g B then pBmZ pB pA 3 pZ1 pA A is in B Proof Events A amp Z are disjoint and their union equals S hence pS pApZ1 gt PA1 PA CS 3653 Fall 2002 Lecture 69 T Menhaj 4 0 g pASl Proof Since 19 2 0 axiom 1 it follows from l pA thatpA 1 gt 0 pA 1 5 Given two arbitrary events A and B in B pAUB pApB pA B Proof BAnBUXnBgt AUBAUAMBUKMBAUBMZgt pAUBpApZnB We know pZnBpAnBpB Therefore pAUB PAPB PAMB CS 3653 Fall 2002 Lecture 610 T Menhaj if Apt 2 l 2n are events then pEiiLJTAiZpAipLnAJikpMAJ Ak quot1p 4 where for example 2 sums over all unordered pairs iltj U 13 Forn3 pA1UA2U143pA1pA2pA3pA10A2 pAmA3 pAznA3pAmAmA3 CS 3653 Fall 2002 Lecture 611 T Menhaj Equally Likely Events Suppose Ai s are equally likely events of a partition it means their probabilities are the same PA1PA2 PAm Since S U A from Axiom 3 il Example Place m balls into n 2 711 boxes Find the probability p that the balls are placed in m preselected boxes one in each box 8 Place m balls into 11 boxes E Balls are placed into m preselected boxes one in each box Note Sol n to this problem depends on what we consider as outcomes different models may be obtained CS 3653 Fall 2002 Lecture 612 T Menhaj 1 Assume that m particles are distinct and consider as outcomes all possible ways of placing them into 11 boxes So the number of outcomes S equals nm since there are n choices for each particle we saw that in lecture 4 There are m ways of placing the m particles into the pre selected boxes permutations of 111 objects see lecture 4 Thus the number of favorable outcomes equals E m from the assumptions of equally likely outcomes 2 Assume that m particle are identical unlabled There is of course one way of placing the m particles identical in the m preselected boxes El and Cnmlm possible ways of placing m identical objects into n distinct boxes S Cnmlm see lecture 4 Thus 1 mn l p Cnm lm nm l CS 3653 Fall 2002 Lecture 613 T Menhaj 3 Assume again the particles are identical that we place only one particle in each box El In this case the no of possibilities S equals Cnm combinations of 11 objects taken m at a time CS 3653 Fall 2002 Lecture 614 T Menhaj Lecture 12 Mathematical Induction Induction A standard proof technique most powerful and easy to learn for most theories and problems in discrete mathematics ie to verify the algorithms discussed in Lectures 8 10 are indeed correct Example 1 56 7 nZi i5 0 Closedform solution determination First we need to nd a closedform solution or analytical solution for the above problem 135 6 7 n Pn nl n2 5 2Pn5 n5 n5 n5 OSU CS 3653 Fall 2002 Lecture 121 T Menhaj 2Pn51 n5 n4n5 Solve for P m m P closed form solution Now we may restate the problem as prove pnZi W i5 2 Let pn denotes the proposition that PnZi equals i5 W is true Steps 1 Basis step 7 show pn is true for an initial value ofn 2 Assumption 7 assume that pn is true for n 3 Inductive step 7 using the assumption show pnl is true 1 Basis step 5 5 4x55n00 HQ 15 j 2 5 So Pn is true for initial value n5 p5 is true OSU CS 3653 Fall 2002 Lecture 122 T Menhaj 2 Assumption assume that pn is true ie Pn W is true for n 3 Inductive step using the assumption prove that pnl is also true show 1301 nl 42nl5 n1 Pnl 2139 i5 21 n1 i5 P01 n1 n1 use assumption m m 2 n 4n 5 2n 1 2 n2 n 202n 2 2 OSU CS 3653 Fall 2002 Lecture 123 T Menhaj n23n 18 n 3n6 2 2 nl 4nl5 2 Now we may summarize a theorem as stated below Theorem For all positive integers n 21 n no ln 110 6 N 7 2 0 Summary Suppose that for each positive integer n we have a proposition pn statement that is either true or false Steps of induction to prove pn is true for all n 2 n0 are 0 Formulate pn in a closedfomi like Pn 1 Basis step pn0 is true 2 Assumption assume pi s are true for all no 139 lt quot1 3 Inductive step show that pnl is true nn0lnn02 OSU CS 3653 Fall 2002 Lecture 124 T Menhaj Notes 1 Sigma 2 notation is de ned inductively or recursively as 0 ifrzltrz0 1 c if nn0 nil ch 0 1f ngtn0 znu This is also called an inductive de nition Another inductive recursive definitions you may remember are 1 if n30 n n n l if ngt0 and Natural Numbers the set of nonnegative integers factorial N 0L2 that you may define it as the smallest set with OSU CS 3653 Fall 2002 Lecture 125 T Menhaj 1 OEN 2 if neN then nleN Example 2 De ne multiplication recursively for natural numbers 1 Oa 0 2 nla naa Note 2 Question How do you know What to prove by induction How do you guess the closed solution There is no general rule but you have to stick With trial and error techniques and your experience Back to Example 1 Find a closed solution for OSU CS 3653 Fall 2002 Lecture 126 T Menhaj Pn 2121 You can guess from example 1 that Pquot is a polynomial of degree two Pquot A172 317 C The objective will be to nd the coefficients A B and C These can be detemiined as follows Pquot goes to An2 as n gets larger and larger so P Fact A for large n n 55 grj5 A 0 100 210 P20 210 A 7 0525 400 5050 gmwwA 0w5 10000 20100 gm20w0 A 05m5 40000 gmu wA 90w1 250000 A a 05 as 11 gets larger and larger Now need to nd B and C39 may do the same procedure given above to nd B as P 71112 a B as 11 gets larger and larger B 71252507 050250000 7 500 05 OSU CS 3653 Fall 2002 Lecture 127 T Menhaj and C is obtained as C P An2 Bn as n gets larger and larger ie C 132 054 0523 2 l 0 Hence Another example Example 3 Consider the sequence 101072879192431924 P 2139 05n2 05n 11 n1 2 Surprise Find the formula for the sequence n 1 2 3 4 5 6 7 8 9 10 an 1 0 1 0 7 28 79 192 431 924 aanJ 0 inf inf 4 282 243 224 214 2quot 2 4 8 16 32 64 128 256 512 1024 a quot 1 1 1 1 79 quot2 5 0 0 mz HE Hm gtl 2quota 1 4 9 16 25 36 49 64 l 81 l 100 Rule 2391 an1223an2quot n2 OSU CS 3653 Fall 2002 Lecture 128 T Menhaj Back To more examples of induction Analysis Example 4 Find a closed solution for and prove it quot l l l l 1 1 1 1 g ml 4X 9 n2 quot 2 1 quot 1 1 11 2 FEW m2 m2 m m m lmlligii n l n1 m 2 2 3 3 4 4 m quot12 m n n l nlnl 2 n 2n Note In the above we found the closed solution which is n1 2n Now we can prove ifPn i equals m2 1 2 2n Let denote the proposition pn as quot 1 n1 pnPn 2 EH W equals 3 OSU CS 3653 Fall 2002 Lecture 129 T Menhaj 1 Basis step p2 is correct to show this we need to evaluate P2 and check whether it equals 21 22 2 1 721 1 1 ml 22 1 721 1 22 22 173 l 4 4 LE 4 4 n l n1 2 Assume 1strueP 1 PW n H m2 2 m2 quot1 1 nll 3Prove n1 1strueP n1 l P g ml 201 n1 1 n 1 1 E1WE1W391 WHY nl nl2 lnlz lnz2nl l 2n n12 2nnl 2n22n n22n nn2 n2 nll 2n2 2n n2n2 2nl 2nl OSU CS 3653 Fall 2002 Lecture 1210 T Menhaj OSU CS 3653 Fall 2002 Lecture 1211 T Menhaj Lecture 11 Algorithms cont d Algorithm Analysis From the last example we learned that we have to be able to analyze the properties of an algorithm Main questions 1 How to measure its performance how fast does it perform Number ofiterations in each interation number of instructions required to execute the algorithm aka Time complexity 2 How much storage space does the algorithm require Space complexity Analysis of an algorithm is a mechanism to derive estimates for the computer time and storage needed to run the algorithm The actual amount of time and storage is OSU CS 3653 Fall 2002 Lecture 111 T Menhaj referred to the complexity of an algorithm Back to the previous example Algorithm Poly Assume that Tatime for execution of an addition Tmtime for execution of a multiplication Total time required to execute the polynomial evaluation for an input of size n becomes Tpolyn1 Ta nnI2Tm Tpolyl n TanTm nTa Tm Now let n100 TM101TG50101T 1010a50m OSU CS 3653 Fall 2002 Lecture 112 T Menhaj TM100T0 Tm Obviously Tpoly gt Tpolyl As n increases Tpoly gtgt Tpolyl Notes 1 The time required to execute an algorithm is a function of the input size This time may vary depending on the actual input Thus we can evaluate different scenarios including bestcase worstcase and averagecase Best case is the minimum time required to perform the algorithm for a wellformed input of size n Worstcase is the maXimum time required to perform the algorithm for a malformed input of size n Averagecase is the average time required to perform the algorithm for a random set if n inputs 2 Execution time of an algorithm is mostly proportional to the number of iterations of its loops OSU CS 3653 Fall 2002 Lecture 113 T Menhaj Tpolym n15nquot25n Tpob101150566 Tpoly 00 10150005051 61 Tpoly500N5500A2 Tpolym N5nA2 as n increases It is said that Tpolym is of order nAZ Clari cation 05m2 l5nlS 05m2 15n2 n2 S3n2 V7121 Tpoly n quot2 Tp01yns 372 3 3 const You can easily show that Tpolylm is of order n OSU CS 3653 Fall 2002 Lecture 114 T Menhaj De nition Let g and h functions on N We call gn is of order at most hn or gn3hn if ther are a positive constant C and M e N so that S Chnl Vn 2M ie the above inequlity does not hold for nitely many positive integers n It is further said that gn is of order at least hn or gn Qhn ifthere are a positive constant D and NE NV so that 2Dhnl Vn ZN Note gn is of order hn or gn hn if gn3hn and at the same time gn 90101 Each to polynomial problem Based on the above de nitions and knowing that T poly n S 3112 Vn e N ltgt TF0y 19112 Obviously T poly n 2 05112 Vn e N ltgt TF0y Qn2 OSU CS 3653 Fall 2002 Lecture 115 T Menhaj Therefore Tpoly n is of order n2 2 Tpoly n We may do the same things to nd the time required to execute the polyl algorithm as T 2n n polyl Tpolyl n is of order n De nition If an algorithm need Tn units of time to complete the bestcase worst case or averagecase for an input of size n and Tn gn it is asid that the best case worstcase or averagecase time needed the agorithm to do its task is of order of at most gn OSU CS 3653 Fall 2002 Lecture 116 T Menhaj Example Consider the following algorithm Input n Function m 7tn m 0 s true while s pn3 ifp 00rp then m mI quot17 else s false endif endwhile endfunction What is this algorithm doing We can easily see that for n3 9 27 and 54 the output m OSU CS 3653 Fall 2002 Lecture 117 T Menhaj become 1 2 3 and 3 So we may conclude that the algorithm nds the the maximum power of 3 that divides the input n Example Assume that n is randomly picked up from the interval 0 19683 and the only time consuming step is division we may nd The best case is l if3 does not divides n The worst case is 10 since nl9683309 The average case is 19683L J 2L19283J g 17 139 19683 9 19683ZL193LF3J 1 5 1 19683 OSU CS 3653 Fall 2002 Lecture 118 T Menhaj Example Consider the following algorithm Inputs n wk kl2 n v Outputs k or Failure Function k ssearehv n wI to n F while klt n if v wk then display k return vlt wk then display Failure return vgt wk then kkl endif endwhile display failure endfunetion Note 1 The list of words are alphabetized the words are alphabetically ordered 2 Number of comparisions makes the time complexity of the algorithm OSU CS 3653 Fall 2002 Lecture 119 T Menhaj BestCase l comparision if vltw1 WorstCase n comparisions vgtw1 Averagecase First assume that v is on the list Because the chance of v equals any of wi s is the same the number of computations linnl n1 n H n 2 2 I In general you may assume that the probability see lecture 5 that v equals w PmblV Wt 17 and PVObV i W q from lecture 5 we know that 2111 q 1 Obviously vltw1 w1 Svltw2 w2 Svltw3wni1 Svltwn w Sv Using the total ignorance interpretation of probabity L n139 they each should have the same probability OSU CS 3653 Fall 2002 Lecture 1110 T Menhaj The number of computations quotquotL i J quotMl EPIHEMF quotJ EWW 2nl With the assumption of each vw is equally likely then Zpiq13pi 1 q i1 n and the average becomes 1 n H nn3n1 11 q 2 q2ltnl 2 q2nl Check ifv is on the list q0 and the above average becomes nI2 as we obtained before OSU CS 3653 Fall 2002 Lecture 1111 T Menhaj
Are you sure you want to buy this material for
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'