Tài liệu Toán Học

Definition: R is symmetric iff (b,a) ∊ R whenever (a,b) ∊ R for all a,b ∊ A. Written symbolically, R is symmetric if and only if ∀x∀y [(x,y) ∊R ⟶ (y,x) ∊ R] Example: The following relations on the integers are symmetric: R3 = {(a,b) | a = b or a = −b}, R4 = {(a,b) | a = b}, R6 = {(a,b) | a + b ≤ 3}. The following are not symmetric: R1 = {...

52 trang | Chia sẻ: huyhoang44 | Ngày: 19/03/2020 | Lượt xem: 862 | Lượt tải: 0

Example: A young pair of rabbits (one of each gender) is placed on an island. A pair of rabbits does not breed until they are 2 months old. After they are 2 months old, each pair of rabbits produces another pair each month. Find a recurrence relation for the number of pairs of rabbits on the island after n months, assuming that rabbits never die. ...

69 trang | Chia sẻ: huyhoang44 | Ngày: 19/03/2020 | Lượt xem: 968 | Lượt tải: 0

Example: In a lottery, a player wins a large prize when they pick four digits that match, in correct order, four digits selected by a random mechanical process. What is the probability that a player wins the prize? Solution: By the product rule there are 104 = 10,000 ways to pick four digits. Since there is only 1 way to pick the correct digit...

74 trang | Chia sẻ: huyhoang44 | Ngày: 19/03/2020 | Lượt xem: 844 | Lượt tải: 0

Example: How many different license plates can be made if each plate contains a sequence of three uppercase English letters followed by three digits? Solution: By the product rule, there are 26 ∙ 26 ∙ 26 ∙ 10 ∙ 10 ∙ 10 = 17,576,000 different possible license plates.

64 trang | Chia sẻ: huyhoang44 | Ngày: 19/03/2020 | Lượt xem: 764 | Lượt tải: 0

Example: Use mathematical induction to prove that n < 2n for all positive integers n. Solution: Let P(n) be the proposition that n < 2n. BASIS STEP: P(1) is true since 1 < 21 = 2. INDUCTIVE STEP: Assume P(k) holds, i.e., k < 2k, for an arbitrary positive integer k. Must show that P(k + 1) holds. Since by the inductive hypothesis, k < 2k, it f...

74 trang | Chia sẻ: huyhoang44 | Ngày: 19/03/2020 | Lượt xem: 721 | Lượt tải: 0

To construct the base b expansion of an integer n: Divide n by b to obtain a quotient and remainder. n = bq0 + a0 0 ≤ a0 ≤ b The remainder, a0 , is the rightmost digit in the base b expansion of n. Next, divide q0 by b. q0 = bq1 + a1 0 ≤ a1 ≤ b The remainder, a1, is the second digit from the right in the base b expansion of n. Continue by suc...

103 trang | Chia sẻ: huyhoang44 | Ngày: 19/03/2020 | Lượt xem: 1563 | Lượt tải: 0

Definition: The general searching problem is to locate an element x in the list of distinct elements a1,a2,.,an, or determine that it is not in the list. The solution to a searching problem is the location of the term in the list that equals x (that is, i is the solution if x = ai) or 0 if x is not in the list. For example, a library might want t...

81 trang | Chia sẻ: huyhoang44 | Ngày: 19/03/2020 | Lượt xem: 668 | Lượt tải: 0

S = {a,b,c,d} Order not important S = {a,b,c,d} = {b,c,a,d} Each distinct object is either a member or not; listing more than once does not change the set. S = {a,b,c,d} = {a,b,c,b,c,d} Elipses ( ) may be used to describe a set without listing all of the members when the pattern is clear. S = {a,b,c,d, ,z }

137 trang | Chia sẻ: huyhoang44 | Ngày: 19/03/2020 | Lượt xem: 734 | Lượt tải: 0

A argument in propositional logic is a sequence of propositions. All but the final proposition are called premises. The last statement is the conclusion. The argument is valid if the premises imply the conclusion. An argument form is an argument that is valid no matter what propositions are substituted into its propositional variables. If the p...

71 trang | Chia sẻ: huyhoang44 | Ngày: 19/03/2020 | Lượt xem: 802 | Lượt tải: 0

Propositional functions become propositions (and have truth values) when their variables are each replaced by a value from the domain (or bound by a quantifier, as we will see later). The statement P(x) is said to be the value of the propositional function P at x. For example, let P(x) denote “x > 0” and the domain be the integers. Then: P(-3) ...

57 trang | Chia sẻ: huyhoang44 | Ngày: 19/03/2020 | Lượt xem: 802 | Lượt tải: 0