Tài liệu Khoa Học Tự Nhiên

Syntax (form of a sentence) vs. semantics (meaning of a sentence) The sentence the frog writes neatly is a valid sentence according to the rules of English grammar. That is, it is syntactically correct, even though it’s nonsensical (unless we are talking about a fantasy world). The sequence of words swims quickly mathematics is not a valid senten...

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

Definition: Let B = {0, 1}. Then Bn = {(x1, x2, , xn) | xi ∈ B for 1 ≤ i ≤ n } is the set of all possible n-tuples of 0s and 1s. The variable x is called a Boolean variable if it assumes values only from B, that is, if its only possible values are 0 and 1. A function from Bn to B is called a Boolean function of degree n. Example: The function F(x...

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

Theorem: An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices. Proof: Assume that T is a tree. Then T is connected with no simple circuits. Hence, if x and y are distinct vertices of T, there is a simple path between them (by Theorem 1 of Section 10.4). This path must be unique - for if there ...

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

When we build a graph model, we use the appropriate type of graph to capture the important features of the application. We illustrate this process using graph models of different types of computer networks. In all these graph models, the vertices represent data centers and the edges represent communication links. To model a computer network whe...

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

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: 853 | 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: 948 | 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: 831 | 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: 751 | 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: 709 | 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: 1536 | Lượt tải: 0