Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 141Classification of Combinatorial problems i) Order matters / does not matter• Choose a committee of 3 out of 10 members (members are distinguishable): the order of the members in committee does not matter• Choose president, vice-president and secretary out of 10 members: three different assignments mean the order is important C (10, 3) 3!89107!3!10! 10982ii) identical objects• Count different arrangements of 4 objects: AABCModify the problem: AaBCThen we have 4!=24 distinguishable arrangementsFor any positions of B and C we have 2 choices, that shouldnot be distinguished. So only 24/2=12 arrangements are distinct• Count arrangements of AABB 12/2=63iii) with/without repetitions • How many distinct 3-letter passwords exist? (order is important abc bac) only once(without repetition) many times(with repetition) Any letter can be used262524 263•You draw 3 balls from a box with 10 red, 10 blue and 10green (order is not important: rbg=brg=gbr=… )*|*|* **||*||***4A committee of 3 is to be chosen from 5 Democrats,3 Republicans and 4 Independents. a) In how many ways it can be done?• all representatives are not distinguished• all members of a committee are equivalent• selections with repetition • the same problem: 5 red, 3 blue and 4 green balls arepicked at random. How many different outcomes are possible?**|*| 10!2!3!5DDD IDDDDR IDRDRR IRRRRR IIRI I I IID5Consider the situation, when all representatives are distinguished. What will be the number of possible committees? C (12, 3)b) In how many ways it can be done if the committee must contain at least one independent? We must put one star in the “independent box” and count different ways to distribute two remaining stars in three boxes. | |* DRI6!2!2)!22(**||**|*|**||**|**|*|*|**||***DDIDRIDIIRRIRIIIII6For what situations the following answers apply ? 121110 3 distinguished positions in the committeeand all representatives are distinguished3!4!5!12!12 distinguished positions in the committee,representatives of a party are not distinguished7In how many ways can we select three books each from different subject from a set of 6 distinct history books,9 distinct classic books, 7 distinct law books, and 4 distinct education books?C (6,3) C (9,3) C (7,3) C (4,3) An exam has 12 problems. How many ways can integer pointsbe assigned to the problems if the total of the points is 100 andeach problem is worth at least five points? x1+ x2 +…+ x12=100 ( xi 5 )11!40!11)!(408Find the formula involving the connectives , , and that has the following truth table: q r q # r 1 1 1 1 0 10 1 00 0 1You can observe that q # r (rq) rq9Let ? be an unknown boolean logical operator. The logical statement [(p q) r] (q ? r) is equivalent to [(p q) r]. Given this information, there are 2 possible truth tables for the boolean logical operator ?. List both of these truth tables. p q r pq (p q)r 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 (p q) r [(p q) r] (q ? r)10111111q ? r 1 0 1 1/0 11/0 1 1/010Answer: q r q ? r 1 1 1 1 0 00 1 10 0 0/111Use laws of logic to show that the following expression is a tautology:p [( pq ) (q r )] ( q r )( pq ) (q r ) (q p) (q r ) q (p r )[( pq ) (q r )] ( q r ) [q (p r )] ( q r ) (q q) (p r ) r T (p r ) r T p T T12In each case determine whether or not two propositions are logically equivalent:x [ p(x) q (x) ] [x p(x)] [x q (x) ] x [ p(x) q (x) ] [x p(x)][x q (x) ] x [ p(x) q (x) ] [x p(x)] [x q (x) ] x [ p(x) q (x) ] [ x p(x)][ x q (x) ] 13Suppose A B and C is any set. Prove or disprove that C B C A. C B AB AC AC Proof.Given A BGoal C B C A14Given A BGoal C B C A x C B x C A Contrapositive: x C A x C B x C B (x C xA) (x C x A) (x C x B) (x C x B) x C B A Bx C
View Full Document
Unlocking...