SKKU Discrete Mathematics
Prof : Sang-Gu Lee at SKKU
http://matrix.skku.ac.kr/2018-DM/DM-Labs.htm Discrete Math Labs (실습실)
http://matrix.skku.ac.kr/2018-album/2018-Lectures-sglee.htm (강의실)
http://matrix.skku.ac.kr/2018-DM-QnA/ (질문과 답변)
http://matrix.skku.ac.kr/2018-DM-Sol/2018-DM-Sol.htm (문제풀이)
http://matrix.skku.ac.kr/2018-DM-PBL/ (PBL report 보고서)
http://matrix.skku.ac.kr/2018-DM-PBL-Eng/ (PBL report Eng, 영문 보고서)
DM Ch. 1, Sets and Logic
Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-1/
DM-Ch-1-Lab http://matrix.skku.ac.kr/2018-DM/DM-Ch-1-Lab.html
DM Ch. 1, 동영상강의
Ch 0 Introduction https://youtu.be/9ahFnOFTWNQ
1.1, 1.2 Propositions https://youtu.be/QgdKqmCFW2Y
1.3, 1.4 Rules of Inference https://youtu.be/92siPfThf0M
1.5, 1.6 Nested Quantifiers https://youtu.be/7M7w9eX5D0Q
DM Ch. 2, Proofs
Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-2/
DM-Ch-2-Lab http://matrix.skku.ac.kr/2018-DM/DM-Ch-2-Lab.html
DM Ch. 2, 동영상강의
2.1, 2.2 More Methods of Proof Problem https://youtu.be/xEMkHb2AkYk
2.4, 2.5 Math Ind &Well-Ordering Prop https://youtu.be/areatkjOjcg
Midterm Exam Solutions : https://youtu.be/iAfQCycd6ac
Chapter 1 Page 63 Problem 1
Solved By Muhammed/모하메드, Date: 2018.09.17.
Finalized By 전종문, Date: 2018.09.20.
Final OK by SGLee
Problem
If A = {1, 3, 4, 5, 6, 7}, B = {x | x is an even integer}, C = {2, 3, 4, 5, 6}, find (A ∩ B) − C.
Solution
1. A = {1, 3, 4, 5, 6, 7}
2. B = {x | x is an even integer}={2, 4, 6, 8, 10, ....}
3. C = {2, 3, 4, 5, 6}
4. A ∩ B= {4,6}
5.
6. Since, (A ∩ B) ⊆ C
Comment:
We can solve the problem by only using formula, but we learned that we can visualize and solve the problem more easily if we use Venn-diagram through this problem.
■
Chapter 1 Page 63 Problem 2
Solved by 권재현 Date: 2018.09.21.
Finalized by 서명원 Date: 2018.09.25.
Final OK by SGLee
Problem
If A U B = B, What relation must hold between A and B?
Solution
1. Lets show it as pictures.
1) 2)
2. A is subset of B. (A ⊆ B).
3. It means that all the elements of A are elements of B.
Comment
This problem made us rethink about the basic concept of sets. ■
Chapter 1 Page 63 Problem 3
Solved By : 강병훈 Date : 2018.09.18.
Finalized By : 전종문 Date : 2019.09.20.
Final OK by SGLee
Problem
Are the sets {3, 2, 2}, { x ∣ x is an integer and 1 < x ≤ 3 } equal? Explain.
Solution
1. We know that elements of {3, 2, 2} = {2, 3}.
Ex)
Sources : http://matrix.skku.ac.kr/2018-DM/DM-Ch-1-Lab.html
2. Then, { x ∣ x is an integer and 1 < x ≤ 3} = {2, 3}
3. So, { x ∣ x is an integer and 1 < x ≤ 3} = {2, 3} = {3, 2, 2}.
4. Therefore, {3, 2, 2} = { x∣ x is an integer, and 1 < x ≤ 3}.
Comment
If the elements of the two sets are the same, even if there are several elements in the group, it can be seen that they are the same set regardless of the number of elements. ■
Chapter 1 Page 63 Problem 4
Solved by 김정주, Date: 2018.09.19.
Finalized by 전종문, Date: 2018.09.20.
Final OK by SGLee
Problem
If A={a, b, c}, how many elements are in ?
Solution
1. The power set of a set with elements has elements.
2. Set has 3 elements.
3. So, the number of elements of .
4. {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}
5. The Cartesian product is the set of all ordered pair , where
6. Then, {}.
7. In this time, we already know the number of elements of P(A) and A
8. Therefore,
Comment
From this problem we can think about the concept of sign ㅣㅣand X. ■
Chapter 1 Page 63 Problem 5
Solved by정호진 Date : 2018.09.17.
Revised By : Muhammad/모하메드Date : 2018.09.17.
Finalized By : Muhammad/모하메드Date : 2018.09.26.
Re-Finalized By : Muhammad/모하메드Date : 2018.10.05.
[Offline] In person meeting-Final Ok By Professor, Date : 2018.10.05.
Problem
If p, q and r are true, find the truth value of the proposition (p∨q)∧((p∧r)∨q))
Solution
1. p∨q is true.
2. p∧r is false.
3. (p∧r)∨q) is true.
4. ((p∧r)∨q)) is false.
5. (p∨q)∧((p∧r)∨q)) is false.
6. Truth Table
p |
q |
r |
-p |
p∨q |
¬p∧r |
(¬p∧r)∨q |
¬((¬p∧r)∨q) |
(p∨q)∧¬((¬p∧r)∨q) |
T |
T |
T |
F |
T |
F |
T |
F |
F |
■
Chapter 1 Page 63 Problem 6
Solved by 권재현 Date: 2018.09.21
Finalized by 서명원 Date: 2018.09.25
Final OK by SGLee
Problem
Write truth table of the proposition ¬(p∧q)∨(p∨¬r).
Solution
Truth Table |
Truth Table |
Truth Table |
||||||
p |
q |
¬(p∧q) |
p |
r |
(p∨¬r) |
¬(p∧q) |
(p∨¬r) |
¬(p∧q)∨(p∨¬r) |
T |
T |
F |
T |
T |
T |
F |
T |
T |
T |
F |
T |
T |
F |
T |
T |
T |
T |
F |
T |
T |
F |
T |
F |
T |
F |
T |
F |
F |
T |
F |
F |
T |
T |
T |
T |
Comment
This conceptual problem can make you understand the basic symbol and the way to show true/false of discrete math. ■
Chapter 1 Page 63 Problem 7
Solved by 만우흠 Date:2018.09.21.
Finilized by 칭기즈 Date:2018.09.30.
Problem
Formulate the proposition p ∧ (¬q v r )
p : I take hotel management.
q : I take recreation supervision.
r : I take popular culture.
Solution
1. ¬q : I don't take recreation supervision.
2. p ∧ (¬q v r ) :
I take hotel management and either I don't take recreation supervision or I take popular culture. ■
Chapter 1 Page 64 Problem 8
Solved by 정호진 2018.09.17.
Revised by SGLee 2018.09.17.
Finalized by Muhammad /모하메드 2018.9.26.
Re-Finalized By : Muhammed /모하메드 2018.10.05.
[Offline] In person meeting-Final Ok By Professor, 2018.10.05.
Problem
Assume that a, b , and c are real numbers. Represent the statement
a < b or ( b < c and a ≥ c )
symbolically, letting
p : a < b, q : b < c, r : a < c.
Solution
1. r : a c
2. “or” is same to “”.
3. “and” is same to “”.
4. Therefore, p ∨ (q ∧ r)
Comment
We could practice the way to show a proposition by using symbols. ■
Chapter 1 Page 64 Problem 9
Solved by 금상인 Date 2018.09.20.
Revised by TA Date 2018.10.04.
Final OK by TA Date 2018.10.04..
Problem
Restate the proposition "A necessary condition for Leah to get an A in discrete mathematics is to study hard" in the form of a conditional proposition.
Solution
1. Let p : Leah gets an A in discrete mathematics.
2. Let q : Leah studies hard.
3. Since q is necessary condition for p.
4. it follows that p q
5. Hence, the statement is followed :
If Leah get an A in discrete mathematics , Leah studied hard ■
Chapter 1 Page 64 Problem 10
Solved by 금상인 Date 2018.09.20
Finalized by 오동찬 Date 2018.09.20
Final OK by TA Date 2018.10.04
Problem
Write the converse and contrapositive of the proposition of problem 9.
Solution
1. Converse(q p) : If Leah studies hard, she will get an A in discrete mathematics.
2. Contrapositive(q p) : If Leah doesn't study hard, she will not get an A in discrete mathematics.
Comment
This problem made me revise what a proposition is and its role, hypothesis, treatment etc. is, which I learned during upper school. ■
Chapter 1 Page 64 Problem 11
Solved by 전솔람 Date : 2018.09.19.
Revised and Finalized by 강병훈 Date : 2018.09.20.
Problem
If p is true and q and r are false, find the truth value of the proposition.
(p∨q)→ r
Solution
Operator precedence |
|
The operator , , and using in the absence of parentheses. The order of operation is , , and . In algebra, operator precedence tells us to evaluate and / before and . |
Definition 2.6 |
|
||||||||||||||||||
The truth value of the proposition is defined by truth table
|
3. True ∨ False True
4. r is false so r is true.
Definition 1,3.3 |
Truth table |
||||||||||||||||||
The truth value of the conditional proposition is defined by truth table:
|
6. As a result, (p∨q)→r is true ■
Chapter 1 Page 64 Problem 12
Solved by 전솔람 Date 2018.09.19.
Revised and Finalized by Muhammad/모하메드 Date 2018.09.26.
Final OK by TA Date 2018.10.04.
Problem
Represent the statement.
If ( a ≥ c or b < c ), then ( b ≥ c ) symbolically using the definitions of Exercise 8
( p : a < b, q : b < c, r : a < c )
Solution
1. a ≥ c is equivalent to the reverse of r ( a < c ), so a ≥ c represents ¬ r
2. And, b < c is equivalent to q ( b < c )
3. And, b ≥ c is same to the reverse of q ( b < c ), so b ≥ c represents ¬ q
4. As a result, ( a ≥ c or b < c ), then ( b ≥ c ) can be ( ¬r ∨ q ) → ¬q ■
Chapter 1 Page 64 Problem 13
solved by 백선민 DATE 2018.09.20
revised by 김주형 DATE 2018.09.20
Final OK by TA DATE 2018.10.04
Problem
If p and q are proposition, the proposition “if p then q” is symbolized as p → q, p(left proposition) is hypothesis and q(right proposition) is conclusion.
Solution
1. If we let,
p : the Skyscrapers win.
q : Proposition I'll eat my hat.
r : Proposition I'll be quite full.
2. we can write the argument
p → q
q → r
∴ p → r
3. So, we can find the used rule of inference is hypothetical syllogism. ■
Chapter 1 Page 64, Problem 14 (Chapter 1 Self-Test)
Solved by 김희성Date : 2018.09.16.
Revised by 조영은 Date : 2018.09.21.
Finalized by 모하메드 Date : 2018.09.26.
Re-Finalized by 모하메드 Date : 2018.10.05.
[Offline] In person meeting-Final Ok By Professor : 2018.10.05.
Problem
Write the following argument symbolically and determine whether it is valid. If the Skyscrapers win, I'll eat my hat. If I eat my hat, I'll be quite full. Therefore, if I'm quite full, the Skyscrapers won.
Solution
1. First, let’s give each statement(proposition) a symbol as following:
The Skyscrapers win proposition p
Eat my hat proposition q
Quite full proposition r
2. Secondly, changing the given argument into symbols we get:
If the Skyscrapers win, I'll eat my hat) : p q
If I eat my hat, I'll be quite full : q r
Therefore, if I'm quite full, the Skyscrapers won : r p
3. Finally, we check the validity. For the argument to be valid, the conclusion and the premises should be true (no matter what the inputs are) but assuming that p is false, q is false and r is true we can get
p q (Is true)
q r (Is true)
r p (but the conclusion is false)
4. Since the conclusion is False while the premises are true (counter example), we can say that the argument is invalid.
Comment
This Invalidity is called the fallacy of affirming the conclusion. ■
Chapter 1 Page 64, Problem 15 (Chapter1 Self-Test)
Solved by 전종문, 2018.09.14.
Revised by Muhammad/모하메드, 2018.09.17.
Finalized by 전종문, 2018.09.20.
Refinalized by Muhammad/모하메드. 2018.10.05.
[Offline] In person meeting-Final Ok By Professor, 2018.10.05.
Problem
Determine whether the following argument is valid.
p →q ∨ r
p ∨¬q
r ∨ q
∴ q
Solution
1. By using Truth Table.
Case |
p |
q |
r |
-q |
q ∨ r |
p →q ∨ r |
p ∨¬q |
r ∨ q |
q |
1 |
T |
T |
T |
F |
T |
T |
T |
T |
T |
2 |
T |
T |
F |
F |
T |
T |
T |
T |
T |
3 |
T |
F |
T |
T |
T |
T |
T |
T |
F |
4 |
T |
F |
F |
T |
F |
F |
T |
F |
F |
5 |
F |
T |
T |
F |
T |
T |
F |
T |
T |
6 |
F |
T |
F |
F |
T |
T |
F |
T |
T |
7 |
F |
F |
T |
T |
T |
T |
T |
T |
F |
8 |
F |
F |
F |
T |
F |
T |
T |
F |
F |
2. For the conclusion to be true we have to consider the cases when all premises are true (cases marked in yellow), these cases are: 1 , 2 , 3 , 7.
3. Then we try to find a counter example -if any- in the conclusion for these cases.
4. We can see that counter examples can be found in case 3 and case 7 where q is false.
5. Therefore, this argument is invalid.
Comment
we can determine True/False easily and see all of case when we use truth table. ■
Chapter 1 Page 64 Problem 16
Solved By 김승연, Date: 2018.09.15.
Finalized By 유가이 올렉산드르, Date: 2018.09.21.
Problem
Give an argument using rules of inference to show that the conclusion fallows from the hypotheses.
Hypotheses : If the Council approve the founds, then New Atlantic will get the Olympic Games. If New Atlantic gets the Olympic Games, then New Atlantic will build a new stadium. New Atlantic does not build a new stadium.
Conclusion: The Council does not approve the funds or the Olympic Games are canceled.
Solution
1. Suppose that :
p : The Council approve the funds.
q : New Atlantic gets the Olympic Games.
r : New Atlantic builds a new stadium.
s : The Olympic Games are canceled.
p q
q r
r
ps
2. To begin with using a hypothetical syllogism, we can prove that, to build a stadium it’s important the Council approve the funds (p => r).
3. Then using the rule of Modus tollens, we can prove that, in order to the New Atlantic to builds a new stadium we need to the Council approve the funds (p => r), but the result implies that, the New Atlantic hasn’t built a new stadium (ㄱr), which means that, the Council was not approve the funds (ㄱr). And it also follows that, since the New Atlantic didn’t build a new stadium, either the Council wasn’t approve the funds or the Olympic Games was cancel. (ㄱp∨s). ■
Chapter 1 Page 64 Problem 17
Solved by 전솔람19th Sep.
Revised and Finalized by Muhammad/모하메드 26th Sep.
Final OK by SGLee
Problem
Is the statement
"The team won the 2006 National Basketball Association championship“
a proposition? Explain.
Solution
1. Answer is No!
2. It is not proposition.
3. Because the statement cannot be determined to True or False.
4. Why? Because we don't know what "team" the statement is referring to. ■
Chapter 1 Page 64 Problem 18
Solved By : 오동찬, Date: 2018.09.20
Finalized By: 유가이 올렉산드르, Date: 2018.09.21
Re-Finalized By : 오동찬, Date 2018.09.30
Problem
Is the statement of Exercise 17 a propositional function? Explain.
Statement of Exercise 17 is that
"The team won the 2006 National Basketball Association championship".
Solution
1. Yes, the statement is a propositional function.
2. Let P(x) be a statement involving the variable x , with respect to D(where D is the team that won the 2006 National Basketball championship).
3. And now when we substitute a particular team for the variable x (P(x); x ∈D)), the statement becomes a proposition. ■
Chapter 1 Page 64 Problem 19
Finalized by 오동찬 Date : 2018.09.30.
Final OK by TA Date : 2018.10.04.
Problem
Let P(n) be the statement. n and n+2 are prime. In Exercises 19 and 20, write the statement in words and tell whether it is true or false. Is ∀n P(n) True or False?
Solution
1. The given statement means that "For all positive integers n, n and n+2 are prime.".
2. In this statement there is an counterexample such as n = 13.
3. Thus, the proposition is false.
Comment
This problem helped me understand Mathematical Notation and make it into a sentence. ■
Chapter 1 Page 64 Problem 19
Solved by 장형준, Date 2018.09.18
Finalized by 전종문, Date 2018.09.20
Problem
Let P(n) be the statement and n and n+2 are prime. Write ∀nP(n) in words and tell whether it is true or false.
Solution
Definition 1.5.4 |
|
is a propositional function with domain of discourse . The statement for every , is a universally quantified statement of . The symbol means “for every.” The symbol is a universal quantifier (범용 정량자, ∀). |
2. ∀nP(n) in words is that for all n, P(n) is true.
3. However, according to P(n) in this question, this statement is False.
4. Because if n = 23, where 23 is a prime number, but n+2 = 25 is not prime.
5. Hence through a counterexample, ∀nP(n) is False. ■
Chapter 1 Page 64 Problem 20
Solved by 장형준, Date 2018.09.18.
Finalized by 전종문, Date 2018.09.20.
Problem
Let P(n) be the statement and n and n+2 are prime. Write ∃nP(n) in words and tell whether it is true or false.
Solution
Definition 1.5.9 |
|
Let be a propositional function with domain of discourse . The statement there exists , is an existentially quantified statement. The symbol means “there exists.” The symbol is an existential quantifier of . |
2. ∃nP(n) in words is: There exists n where P(n) is true.
3. This statement is True.
4. Let n = 3. n+2 = 5. 3 and 5 are both prime numbers.
5. Hence there exists n where P(n) holds true. Hence ∃nP(n) is True. ■
Chapter 1 Page 64 Problem 21
Solved by 칭기즈, Date : 2018. 09. 19.
Finalized by 유가이 올렉산드르, Date : 2018. 09. 21.
Final OK by TA , Date : 2018. 10. 04.
Problem
Let K(x, y) be the propositional function “x knows y”. The domain of discourse is the Cartesian product of the set of students taking discrete math with itself (i.e. both x and y take on values in the set of students taking discrete math). Represent the assertion “someone does not know anyone” symbolically.
Solution
1. Denote the statement “x does not know y” as ㄱK (x, y).
2. Since both x and y are the Cartesian product of the set of students who have taking discrete mathematics.
3. Then, we can assume that someone of the student x (∃x) doesn’t know anyone of the student y (∀y).
4. Full symbolic expression (someone does not know anyone) : ∃x ∀y ㄱK (x, y).
Comment
Through this problem, we studied how to change the standardized proposition, to the symbolized. In fact, it is easier to change a symbolized proposition than a standardized one, which helps to change the written one. ■
Chapter 1 Page 64 Problem 22
Solved by : 오동찬, Date : 2018. 09. 20.
Finalized by : 유가이 올렉산드르, Date : 2018. 09. 21.
Re-Finalized by : 오동찬, Date : 2018. 09. 30.
Problem
Write the negation of the assertion of Exercise 21 symbolically and in the words.
Solution
1. The negation of expression “someone does not know anyone” is “∃x ∀y K(x, y)“.
2. We should find ㄱK(x, y).
3. As a result, ∀x ∃y ㄱK (x, y) is “anyone know someone”.
Comment
The above problem is the reference in problem 21 and the negation of the written proposition through symbols. Therefore, it is more accurate and easier to find an answer than to deny it with a sentence. ■
Chapter 1 Page 64 Problem 23
Solved By : 백선민, Date: 2018.09.20
Finalized By: 유가이 올렉산드르, Date: 2018.09.21
Final OK by TA Date: 2018.10.04
Problem
Determine whether the statement ∀x ∃y () is true or false. The domain is R x R. Explain your answer. Explain in words the meaning of the statement.
Solution
1. The domain of discourse of the two variable propositional function P is R x R.
2. It means that each variable x and y must belong to the set of real numbers.
3. It can be assumed that x and y are real numbers R.
4. This expression we can expressed in terms of the cube root function().
5. Through this function, we see that, for every x, there exist a certain y
6. In other words, every real number has a cube root.
7. It follows that, this statement ∀x ∃y is true. ■
Chapter 1 Page 64 Problem 24
Solved by 김승연
finalized by 오동찬
Problem
Use the generalized De Morgan's laws for logic to write the negation of ,
Solution
1.
2. ■
Chapter 2 Page 124 Problem 1
Solved by 유가이 올렉산드르 Date : 2018. 09. 23.
Finalized by Muhammad/모하메드 Date : 2018. 09. 26.
Final OK by SGLee
Problem
Distinguish between the terms axiom and definition.
Solution
1. By definition axioms(postulate) is a statement that is taken to be true to serve as a premise or starting point for further reasoning and arguments in simple words that are assumed to be true.
2. In my opinion, the distinctive feature of the axioms is that, it is the mainstay of mathematics, which don't require proof
3. Because they are obvious and cannot be proved.
4. Definition is used to create new concepts in terms of existing ones.
5. Some terms are not explicitly defined, but rather are implicitly defined by the axioms.
Reference
<수학에서의 정의, 공리, 정리의 차이>
Chapter 2 Page124 Problem 2
Solved by 서명원 Date : 2018. 09. 25.
Finalized by 김은율 Date : 2018. 09. 26.
Final OK by SGLee
Problem
Prove that for all integers m and n, if m and m - n are odd, then n is even.
Solution
1. Since m and m - n are odd.
2. Let m = 2k1 + 1 and m - n = 2k2 + 1 for some integers k1 and k2.
3. Then, n = m - (m - n) = (2k1 + 1) - (2k2 + 1) = 2(k1 – k2) where are integers.
4. As a result, n is even because it is 2 times an integer k1 – k2 ■
Chapter 2 Page 124 Problem 3
Solved by 전종문 Date : 2018. 09. 23.
Finalized 서명원 Date : 2018. 09. 25.
Final OK by SGLee
Re-Finalized by 전종문 Date : 2018. 09. 23.
Final OK by SGLee
Problem
Prove that for all rational numbers and , () is rational.
Solution
1. The definition of rational number is that any number that can be expressed as a ratio of two integers.(The denominator is not zero.)
2. Since and are rational numbers(), they can be expressed by and for some integers .
4. So, we can write that where
5. Therefore, is rational number because is the quotient of integers and ■
Chapter 2 Page 124 Problem 4
Solved by 서명원, Date: 2018.09.25
Finalized by 김은율, Date: 2018.09.26
Final OK by SGLee
Problem
Prove that for all sets X, Y, and Z, if X ⊆ Y and Y ⊂ Z, then X ⊂ Y.
Solution
1. Let x ∈ X, x ∈ Y (because X ⊆ Y )
2. So, we have to show that X is a proper subset of Z.
3. Since Y ⊂ Z, ∃z ∈ Z , ∃z ∉ Y.
4. z ∉ X (because X ⊆Y ) and Y ⊂ Z.
5. Therefore, X ⊂ Z.
Comment
The above problem can be proved more easily with the use of Ven diagram. ■
Chapter 2 Page 124 Problem 5
Solved by 정호진 Date : 2018. 09. 26.
Finalized by 칭기즈 Date : 2018. 09. 26.
Final OK by SGLee, Refinalized by SGLee Date : 2018. 09. 27.
Problem
What is the difference between a direct proof and a proof by contradiction?
Solution
1. When we want to prove the conclusion using the proof by contradiction, the negated conclusion is assumed in addition to the given condition. And we only need to find one contradiction among many.
2. Whereas in a direct proof , we have to use the given condition only to prove the one given conclusion. (the negated conclusion is not assumed!!)
3. So, there are more conditions and more conclusions for us in a proof by contradiction.
Comment
It was a matter for us to think about why we use evidence that used contradiction. Simply using contradictions in this case, you can think of it as comfortable, but you can think specifically about why it is more convenient, which makes it possible to think even more logically. ■
Chapter 2 Page 124 Problem 6
Solved by 강병훈 2018. 09. 27.
Finalized by 정호진 2018. 09. 27.
Re-Finalized by 강병훈 2018. 09. 27.
Final OK by SGLee 2018. 09. 27.
Problem
Show, by giving a proof by contradiction, that if four teams play seven games, some pair of teams plays at least two times.
Solution
1. p : four teams play seven games.
2. q : some pair of teams plays at least two times.
3. Suppose p and ¬q
(if four teams play seven games and all pair of teams plays only one game)
4. Let each team be named as {a, b, c, d}.
5. Then play game like {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}.
6. So the next 7th game should be a rematch of the pair of team who had a match each others already.
7. It occurs a contradiction.
8. Therefore, if four teams play seven games, some pair of teams should play at least two times. ■
Chapter 2 Page 124 Problem 7
Solved by 칭기즈 Date : 2018. 09. 26.
Finalized by 서명원 Date : 2018. 09. 27.
Final Ok by TA Date : 2018. 09. 27.
Problem
Use proof by cases to prove that min{min{a, b}, c}= min{a, min{b, c}} for all real numbers a, b and c
Solution
Discussion: In order to proof by cases we have to identify all possible cases and try each of them to identify whether the given statement is true of false. There are 6 possible cases, which are:
1. a >= b >= c
2. a >= c >= b
3. b >= a >= c
4. b >= c >= a
5. c >= a >= b
6. c >= b >= a
[Case 1:a >=b >=c]
min{min{a,b},c}= min{a,min{b,c}}
min{b,c}= min{a,c}
c=c
[Case 2: a>=c>=b]
min{min{a,b},c}= min{a,min{b,c}}
min{b,c}= min{a,b}
b=b
[Case 3:.b>=a>=c]
min{min{a,b},c}= min{a,min{b,c}}
min{a,c}= min{a,c}
c=c
[Case 4:b >= c >= a]
min{min{a,b},c}= min{a,min{b,c}}
min{a,c}= min{a,c}
a=a
[Case 5:c>=a>=b]
min{min{a,b},c}= min{a,min{b,c}}
min{b,c}= min{a,b}
b=b
[Case 6:c>=b>=a]
min{min{a,b},c}= min{a,min{b,c}}
min{a,c}= min{a,b}
a=a
Let me rearrange these cases, we arrange these cases to two case: a≤b and a>b.
In each of these two cases, we should consider the two cases: b≤c and b>c.
First suppose that a≤b.
If b≤c, then
min{min{a,b},c}=min{a,c}=a=min{a,b}
=min{a,min{b,c}}.
if b>c, then
min{min{a,b},c}=min{a,c}=min{a,min{b,c}}.
In either case,
min{min[a,b},c}=min{a,min{b,c}}.
And, Suppose that a>b.
if b≤c, then
min{min{a,b},c}=min{b,c}=b=min{a,b}
=min{a,min{b,c}}.
if b>c, then
min{min{a,b},c}=min{b,c}=c=min{a,c}
=min{a,min{b,c}}.
In either case,
min{a,min{b,c}}=min{a,min{b,c}}.
Therefore, The statement is true because all cases are true. ■
Chapter 2 Page 124 Problem 8
Solved By 강병훈 Date : 2018. 09. 27.
Finalized By 엄자균 Date : 2018. 09. 08.
Problem
prove that the following are equivalent for sets A and B
(a) A ⊆ B (b) A ∩ B =? (c) A ∪ B = B (a) A ⊆ B
Solution
1. Suppose prove that { x∈z : 24|x| } ⊆ { x∈z : 6|x| }.
2. Suppose a ∈ { x∈z : 24|x| }
3. This means a∈z and 24|x|
4. By the definition of divisibility, there is an integer c for which a=24c consequently a=6(4c), and from this we deduct 6|a|.
5. Therefore a is one integers that divides, so a ∈ {x∈z : 6|x| }.
6. We have shown a ∈ { x∈z : 24|x| } implies a ∈ { x∈z : 6|x| }.
7. So it follows { x∈z : 24|x| } ⊆ { x∈z : 6|x| } (c) A ∪ B = B.
8. Proof A ∪ B = B mean A is a sub set of B for example A=(2,4) and B=(1,2,3,4,5).
9. So A ∪ B = (1,2,3,4,5) which set B actually.
10. Thus proved that A ∪ B = B.
■
Chapter 2 Page 124 Problem 9
Solved by 칭기스 Date : 2018. 09. 24.
Finalized by 강병훈 Date : 2018. 09. 27.
Final OK by SGLee
Problem
Write an expression, which is the and of clauses, equivalent to (p v q) → r.
Solution
Definition 1.3.1 |
Conditional Proposition |
If and are proposition, the proposition if then is a conditional proposition. () : if then . Proposition is hypothesis (or antecedent, 가설). Proposition is conclusion (or consequent, 결론). |
1. (p v q) → r = ¬(p v q) v r
2. De Morgan's Law : ¬(p v q) = ¬p ∧ ¬q
(¬p ∧¬q) v r
3. Distributive Law: (r v ¬p) ∧ ( r v ¬q)
(r v ¬p) ∧ (r v ¬q)
Truth tables
(r v ¬p) ∧ ( r v ¬q) = (p v q)-> r
Comment
<Python Code>
expression=input("enter a logical expression")
print("p |","q |","r |",expression)
count=0
value=[0]*8
for q in range(2):
for p in range(2):
for r in range(2):
value[count]=eval(expression)
print(bool(p),"|",bool(q),"|",bool(r),"|", bool(value[count]))
count=count+1
■
Chapter 2 Page 124 Problem 10
Solved By Muhammad/모하메드 Date : 2018. 09. 24.
Finalized by 유가이 올렉산드르 Date : 2018. 09. 26.
Re-Finalized By Muhammad/모하메드 Date : 2018. 10. 05.
[Offline] In person meeting-Final Ok By Professor Date : 2018. 10. 05.
Problem
Find an expression, which is the "and of clauses", equivalent to ( p ∨¬q) → ¬r s.
Solution
1. Our Goal is to change the expression so that it becomes "and-clause".
2. “and-clause” is a clause/statement of the form as following:
e.g. a^b^c^d^e
e.g.2. (!a∨b)^(c)^(d∨!e)
3. Remember that in DM or Logic Design we can omit the “and” Symbol.
e.g. a^b is equivalent to ab
4. Preparation Before Solving
Refer to the resolution proof (Chapter 2 Section 3) and equivalent statements mentioned throughout the section.
5. Extra Info:
this question is essential in Digital Logic Design where we have to minimize a Boolean expression to (and-clause)(also named max term). ■
Chapter 2 Page124 Problem 11
Solved by 칭기즈, Date: 2018.09.24
Finalized by 김은율, Date: 2018.09.26
Final OK by SGLee
Problem
Use resolution to prove
1. ¬p v q
2. ¬q v ¬r
3. p v ¬r
-------
¬r
Solution:
[ Resolution rule: if pvq and ¬p v r are both true, then q v r is true.]
If
1. ¬p∨q
2. ¬q∨¬r
3. p∨¬r
=>
4. ¬p∨¬r ( From 1 and 2, we have this )
=>
5. ¬r ( From 3 and 4, we have this )
Given the hypotheses 1,2 and 3 , we have proved the conclusion. ■
Chapter 2 Page 124, Problem 12
Solved by 김은율, Date : 2018. 09. 26
Finalized by 전종문, Date : 2018. 09. 26
Re-Finalized by 전종문, Date : 2018. 09. 27
Final OK by SGLee
Problem
Reprove Exercise 11 using resolution and proof by contradiction.
Solution
Show
1. ¬p∨q
2.¬q∨¬r
3.p∨¬r
------------
∴¬r
Proof by contradiction
4. r (negation of conclusion ¬r)
⟶ From 3 and 4, we have 5. p
⟶ From 1 and 5, we have 6. q
⟶ From 2 and 6, we have 7.¬r
At this point, we have derived a contradiction : 4. r and 7. ¬r
Thus, ¬r must be True.
Reference(Truth table)
p |
¬p |
q |
¬q |
¬r |
¬p∨q |
¬q∨¬r |
p∨¬r |
r |
T |
F |
T |
F |
T |
T |
T |
T |
F |
T |
F |
T |
F |
F |
T |
F |
T |
T |
T |
F |
F |
T |
T |
F |
T |
T |
F |
T |
F |
F |
T |
F |
F |
T |
T |
T |
F |
T |
T |
F |
T |
T |
T |
T |
F |
F |
T |
T |
F |
F |
T |
F |
F |
T |
F |
T |
F |
T |
T |
T |
T |
T |
F |
F |
T |
F |
T |
F |
T |
T |
F |
T |
■
Chapter 2 Page 124, Problem 13
Solved by 전종문, Date : 2018. 09. 21.
Revised by 유가이 올렉산드르, Date : 2018. 09. 23.
Finalized by Muhammad/모하메드, Date : 2018. 09. 26.
ReFinalized and Final OK by SGLee, Date : 2018. 09. 27.
Problem
Use mathematical induction to prove that the statements in Exercises 13-16 are true for every positive integer n.
2 + 4 + … + 2n = n(n+1) (*)
Solution
1. Basis Step
(*) is true for n=1
2=1(1+1)=2 is true.
2. Inductive Step
Assume (*) is true for n=k :
That is n=k, then 2 + 4 + … + 2k = k(k+1) --- (*) is true.
* We want to [show that it's true for n=k+1]
Add 2(k+1) at the left hand side of (*)
2 + 4 + … + 2k + 2(k+1)
= k(k+1) + 2(k+1) (because of (*) 2 + 4 + … + 2k = k(k+1) )
= (k+1)(k+2) (because k(k+1) +2(k+1) is equal to (k+1)(k+2) )
So, 2 + 4 + … + 2k + 2(k+1) = (k+1)(k+2) is true.
By Principle of Mathematical Induction.
2 + 4 + … + 2n = n(n+1) is true for every positive integer n.
Comment
Mathematical imputation methods can be used when formulas with certain rules always exist in natural water areas. This indicates that mathematical inductive method is useful when it shows that a proposition always exists in an infinite area, such as a natural water region. ■
Chapter 2 Page 124, Problem 14
Solved by 유가이 올렉산드르, Date : 2018. 09. 23.
Finalized by 강병훈, Date : 2018. 09. 23.
Final OK by SGLee, Date : 2018. 09. 23.
Problem
Use mathematical induction to prove that the statements in Exercise 13-16 are true for every positive integer n.
22+42+…+(2n)2 =
Solution
1. basic step
If k= 1;
4 =
4=4. (True)
2. Inductive step
Assume true it is true when ;
22+42+…+(2n)2=
LHS = 22+42+…+(2n)2+(2(n+1))2= = RHS
LHS = 22+42+…+(2n)2+(2(n+1))2= + (2(n+1))2
==
= = =RHS
Comment
Thanks to this task, I consolidated my knowledge of mathematical induction. ■
Chapter 2 Page 124, Problem 15
Solved by 정호진 Date: 2018.09.26.
Finalized by 서명원 Date: 2018.09.27.
Refinalized and Final OK by SGLee Date: 2018.09.27.
Problem
Use mathematical induction to prove that the statements in Exercises 13-16 are true for every positive integer n.
1/2! + 2/3! + ... +n/(n+1)!=1-1/(n+1)!
Solution
1. Basic step
If n=1
1/2!=1-1/2!
1/2=1/2
2. Inductive step
Assume true that it is true for k=n .
1/2! + 2/3! + ... +n/(n+1)!=1-1/(n+1)! ---- (*)
Show it is true for k =n+1
Add (n+1)/(n+2)! on the left hand side of (*)
1/2!+2/3!+...+n/(n+1)!+ (n+1)/(n+2)! =1-1/(n+1)!+(n+1)/(n+2)!
=1-(n+2)/(n+2)!+(n+1)/(n+2)!
=1-1/(n+2)!
We have shown that it (*) is true for k =n+1 .
Therefore, by Math Induction, we can tell that
'1/2! + 2/3! + ... +n/(n+1)!=1-1/(n+1)!' --- (*) is true for all interger n.
Comment
It is a matter of proving a formula using the inductive method. I could see that the proof should be as brief as possible, but not missing. I also felt that I should not miss the 'Assume true it true for k=n' that I would often miss. ■
Chapter 2 Page 124, Problem 16
Solved by 오동찬, Date : 2018. 09. 27.
Revised and Finalized by 정호진, Date : 2018. 09. 27.
Final OK by SGLee, Date : 2018. 09. 27.
Problem
Use mathematical induction to prove that the statements in Exercises 13-16 are true for every positive integer n.
2^(n+1) <1+(n+1)2^n
Solution
1. Basic step:
If n =1
2^2 < 1+2*2^1
=> 4<5
So the statement is true for n=1.
2. Inductive step:
Assume that it is true for k=n
Show it is true for k=n+1 that is 2^(n+1) <1+(n+1)2^n (*)
LHS= 2^(n+2) = 2 · 2^(n+1) < 2 [1+(n+1)2^n] (by (*) )
=> 2^(n+2) < 2+(n+1)2^(n+1) = 1 + [1+(n+1)2^(n+1)]
=> 2^(n+2) < 1 + [2^(n+1)+(n+1)2^(n+1)] (by ???)
=> 2^(n+2) < 1+ (n+2)2^(n+1) .
Therefore we have shown that 2^(n+2) < 1+(n+2)2^(n+1).
By mathematical induction, 2^(n+1)<1+(n+1)2^n is true rational for every positive integer n. ■
Chapter 2 Page 124, Problem 17
Solved by 엄자균, Date : 2018. 09. 17
Finalized by 강병훈, Date : 2018. 09. 17
Final OK by SGLee, Date : 2018. 09. 17
Problem
Find the quotient q and remainder r as in theorem 5.6 when n=101 is divided by d=11.
Solution
DM Ch. 3, Functions, Sequences, and Relations
DM-Ch-3-Lab http://matrix.skku.ac.kr/2018-DM/DM-Ch-3-Lab.html
Theorem 5.6 |
Quotient-Remainder Theorem |
If and , , there exist integers (quotient) and (remainder) satisfying . and are unique; that is, if and then and . |
Let
.
Show that is nonempty.
n = 101, n ≧ 0 , then
so .
Suppose that .
Since is a positive integer, .
Thus
.
In this case, .
Therefore is nonempty.
Since is nonempty set of nonnegative integers,
by Well-Ordering Property,
has a smallest element, which we denote .
We let denote the specific of for which . Then
.
Since , . [Show that .] (BWOC) Suppose that . Then
.
Thus . Also .
But is the smallest integer in .
This contradiction shows that .
Shown that if and , , there exist integers and satisfying
We turn now to the uniqueness of and . Suppose that
and .
We must show that and .
Subtracting the previous equations, we obtain
,
which can be rewritten
The preceding equation shows that divides .
However, because and ,
.
But the only integer strictly between and divisible by is .
Therefore,
.
Thus,
:
hence
.
The proof is complete.
So, when d=11, 101= n = dq + r has only one solution and
101= n = dq + r= 9×11+2 where q = 9 and r = 2
Comment
It was a simple calculation to get the share of the division and the remainder. And with other colleagues and professor’s additional solutions, I could learn the Quotient-Remainder Theorem and learn more about the fine-grained methods. ■
Chapter 2 Page 128, Problem 18
Solved by 김희성 Date: 2018.09.21
Finalized by 전종문 Date: 2018.09.23
Final OK by SGLee
Problem
Exercise 18 and 19 refer to the sequence c1,c2,... defined by the equations
c1=0 , cn = 2c⌊n/2⌋ + n for all n > 1.
Compute c2,c3,c4, and c5 when it was
c1=0 , cn = 2c⌊n/2⌋ + n for all n >1.
Solution
ⅰ) n =2
c2 = 2c⌊1⌋ + 2 = 2c1 + 2 = 0 + 2 = 2
ⅱ) n =3
c3 = 2c⌊3/2⌋+ 3 = 2c1 + 3 = 0 + 3 = 3
ⅲ) n =4
c4 = 2c⌊2⌋ + 4 = 2c2 + 3 = 4 + 4 = 8
ⅳ) n =5
c5 = 2c⌊5/2⌋ + 5 = 2c2 + 5 = 4 + 5 = 9
∴ (c1=0 ,) c2=2, c3=3, c4=8, and c5=9 ■
Chapter 2 Page 124 Problem 19
Solved by 김정주 Date:2018.09.30
Finalized by 칭기즈 Date:2018.09.30
Problem
c1=0, cn= 2c[n/2] +n for all n>1
prove that cn <= nlgn for all n >= 1
Solution
1. Basis step (n=1)
C1 ≤ 1lg1 ⟶ C1=0 ≤ 0 = 1lg1
The Basis Step is verified.
2. Inductive step:
Assume it is true for all k, 1 ≤ k < n,
Ck ≤ k lgk (*)
Show it is true for k = n, Cn ≤ nlgn
Pf) Since
C[n/2] = Ck ≤ klgk = [n/2] lg[n/2]
⟶ Cn=2*C[n/2]+n≤ 2*[n/2] lg[n/2] +n
≤ 2*(n/2) lg(n/2) + n
≤ n(lgn-1) + n
≤nlgn
Thus
Cn ≤ nlgn
Comment
Problem 19 is that kind of problem in which Strong form of Induction is effective. ■
Chapter 2 Page 124, Problem 20
Solved by 모하메드, Date : 2018. 09. 25
Finalized by 강병훈, Date : 2018. 09. 27
Final OK by SGLee
Problem
Use the Well-Ordering Property to show that any nonempty set X of nonnegative integers that has an upper bound contains a largest element.
(Hint: Consider the set of integer upper bounds for X)
Solution
From the given question; we want to show that if there exists a nonempty set X of nonnegative integers that has an upper bound, then it contains a largest element.
Using the hint given, let’s assume there exists a set Y which is the set of integers upper bound for the set X. Bythisassumption,wecandeducethat Y is a non-empty set of nonnegative integers following the properties of the Set X. Using the Well Ordering Property, the set Y has a least element (let’s call it y). By the previous deductions, we can say that y≧x for every x in the set X.
Now to ensure that the element y is in the set X , we can assume that y is not in X then there should be an element (y-1) ∈ Y which is greater or equal to each element in X , but there isn’t since y is the lowest element in the set Y that makes an upper bound for X (contradiction).
Hence, y≧x for every x ∈ X and y is the largest element in X.
An example would further clarify: X= {3} , Y={3, 4, 5}. ■
Purpose
We started to study mathematicians for three reasons.
1. If you know history, we can see the future.
Studying history such as mathematicians and how the history of mathematics been developed light the way to future of mathematics. If you get stucked on certain problems, you can receive help from the mathematician’s history.
2. It is an opportunity for fellow student to know mathematicians.
It is easy for fellow student to pass or to ignore who the mathematicians is, while studying mathematician’s achievement. It would be good opportunity to study mathematicians for ease.
3. It is helpful to teach young students.
The writer of this part dreams to be a teacher. The story of mathematicians is helpful for young student to remember who the mathematician is and what achievement of mathematician is. It leads to the interest of mathematics.
About Mathematicians
John Venn ( 1834 ~1926 )
Reference
Daejun-ilbo, The founder of 'Venn Diagram' and mathematician John Venn's 180th birthday, 2014.08.05.
His life
John Venn entered Cambridge University and showed outstanding talent. After graduating from college, he spent a year as a priest, but went back to Cambridge to teach ethics to students. He developed the semantic philosophy that was created by then-British mathematician George Fire. It deals with groups, attestation, inductive theory, etc. Venn studied a part of the collective theory and created a Venn diagram that could logically represent the relationship between the groups. Until Venn used the diagram, it was very rare to use the shape or diagram in formal logic, which is a logic that ignores the thought and examines the validity of reasoning in its form.
In the 1880 paper, a form of Venn diagrams that we know well and frequently use in a set emerged. He was also said to be interested in not only mathematics but also other studies, but also in writing history books, and was good at making machines.
Comment
Mathematics and logic were closely related, and there were often attempts to solve logical problems mathematically. Venn’s achievements in building up a foothold of such attempts are great. Personally, I took a seminar on symbolics last semester and listened to discrete mathematics this semester, which helped me to study the 1st and 2nd sections. Then, as I learned about John Venn, I realized again the relationship between logic and mathematics.
More about Venn diagram
Reference
Jang, Gyeonga, Marvrey Rick. “[Information] Is there a van diagram that looks like ice cream.?!”, Mathdonga 02 (2016). Seoul
Euler Diagram
Before Ben diagram, there was Euler diagram. Euler diagrams are similar to Ben diagrams, although they do not overlap sets without common elements.
Venn diagram for more than four sets
First, Venn drew the set in 'C' shape when there were more than four sets.
He then added that when there are n sets, the number of areas needed is . If the value of n is finite, then (number of zones) is also finite. Therefore the Venn diagram can be drawn regardless of the number of groups. There have been many studies since then.
A.W.F. Edwards has found a way to draw a Venn diagram regardless of the number of set. As you can see in the figure above, draw three circles perpendicular to each other on a sphere, and when you shine the light, a three-column Ben diagram appears on the floor. Taking this approach, we found that we could draw three circles, each of the largest and most perpendicular to the sphere, and then we could draw a Ben diagram by drawing a series of wave-shaped curves on a plane.
Frank Rusk, a professor of computer science at the University of Victoria in Canada, was studying with interest whether a symmetrical venn diagram could be drawn even when the number of set increased. The results showed that a symmetrical venn diagram could be drawn whem the number of sets were a prime number. The first thing he found after proving it was a rotating, symmetric Venn diagram with seven sets.
이미지 확대하기 이미지 확대하
Professor Rick Marvrey created a funny-looking Ben diagram (left) with five ice cream cones. Recently, Marvrey found a Venn diagram (right) in the form of a seven-column ring with her student. This is the second way of drawing set of seven rotating symmetric Venn diagrams.
이미지 확대하기
After proving that there are symmetric Venn diagrams when the number of sets is a prime number, mathematics professor Peter Hamburg at Central State University in the U.S. worked with his wife Eddie Heff, who was an artist. As a result, a symmetrical Venn diagram was found with 11 sets in 2002. Art works with 2048 different colors have produced complex and perfectly symmetrical works. The right picture represents 11 sets. The pair also presented the symmetrical Venn diagram at the Bridge Academy, which combines math and art in 2005.
How to draw Venn diagram
Reference
Understanding Hamiltonian path finding in graph theory is easy to draw.
How to draw Venn diagram with n sets
1. Draw Venn diagram with (n-1) sets.
2. Write down number at the set so that the number is continuous between the sets which are sharing the boundary.
3. Connect the number with the line.
Drawing Venn diagram for 4 sets.
Drawing Venn diagram for 5 sets
Georg Ferdinand Ludwig Philipp Cantor (1845~1918)
The essence of mathematics is its freedom.
"Das Wesen der Mathematik liegt in ihrer Freiheit"
Reference
Kim, Byeonghan. “Contor and Set Theory”, Jipyeong
His life
He earned his Ph.D. in 1967 with a number theory. He proved the uniqueness of trigonometry series in 1870. Since 1885, Cantor has left his mathematical studies for theology and literature. But he did not stop studying math completely. He also published a diagonal argument and contributed greatly to the first World Congress of Mathematicians in Zurich, Switzerland, in 1897. But his youngest son suddenly changed his fate, and his nervous breakdown was weakened. Because of these factors, the life of a nursing home was repeated until his death in 1918.
Cantor and the set
During the 19th century, there was a rejection against infinity for religious and academic reasons. In addition, with the tremendous development of calculus and modern analysis in the 17th century, math became increasingly abstract. Therefore it was necessary to lay the foundations of mathematics. He dealt with the size of an infinite set. The whole set of natural number described whether a one-on-one response with a whole set of rational number was possible, and whether the total number of real number could be counted. Cantor's discussion of the size of an infinite set goes beyond this, as the number of points in the finite dimension (i.e. n) is one-on-one with the number of job losses. The problem that Cantor put his heart and soul into is continuous theory. He expected there to be no larger or smaller set than the total number of natural numbers, but he failed to prove it.
Comment
Cantor is a mathematician who was handle infinity, which was taboo at the time. He himself was a religious man, and people around him criticized Cantor for his quest for infinity. But without his quest, today's mathematics may have been quite different. His desire for learning is a warning to me today, sitting comfortably in college and taking classes.
Additional Data
Reference
Wikipedia, Countable Set. https://en.wikipedia.org/wiki/Countable_set
Wikipedia, Aleph number. https://en.wikipedia.org/wiki/Aleph_number
1. The natural number set is a set of numerous elements (infinite elements).
2. The set of real number has more elements than set
It shows that there is also a difference in size between infinite sets.
The word ‘countable’ is from ‘countable set’, which means that there is one-to-one response to the set of natural number.
Countable Set
In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set. Whether finite or infinite, the elements of a countable set can always be counted one at a time and, although the counting may never finish, every element of the set is associated with a unique natural number.
Aleph Number
In particular set theory, the aleph numbers are a sequence of numbers used to represent the cardinality (or size) of infinite sets that can be well-ordered.
Democracy Prep (데모크라시 프렙 고등학교) 를 아시나요??
First-Commented by 강병훈 Date : 2018.11.21.
Commented by 신혜수 Date : 2018.11.21
http://democracyprep.kr/
First-Commented by 강병훈
Democracyprep High School is a high school attended by students in Harlem, U.S., who did not expect anyone to go to college. However, it is a Korean style high school that introduces new teaching methods such as teaching Korean or leading participation, presentation and performance classes. More than 80 percent of the students entered universities in the U.S. and more than 40 percent of students entered Ivy League schools, and recently, it was headline that there was a student who went on to Harvard University.
But now, I also think this way of teaching in Korea is not compatible with modern society. If knowing a lot of knowledge at one time was a proper study, I think knowing how to combine that information in a flood of information is the right way to study. If we break down the old ways of doing things and adopt a new way that is relevant to modern times, I think education will become even more advanced.
Commented by 신혜수
This time, I was introduced to the new Democra Prere School. Even though it was built in Harlem, I think it was a great achievement.
I also agree that today's teaching style should be converted to a way that enhances the ability to combine information given to you, rather than simply memorizing content.
In modern times, information is so plentiful as to be called a flood of information. In those days when IT did not evolve, it was important to study a lot.
I think it becomes important that in addition to the ability to search for information, the ability to understand the reliability and value of information, to extract valuable information, to produce new valuable information from it, to use and deliver it.
Chronology of Discrete Mathematics
- Green circle means the history of world
- Black circle indicates the mathematian who didn’t commented in this PBL Report.
- Blue circle indicates the mathematician who commented in this PBL Report.
- Arrow indicates a teacher and his/her student. ( Teacher → Student )
|
|
|
|
|
|
|
|
|
|
|
|
|
|
About Mathematicians
John Venn ( 1834 ~1926 )
Commented by 신혜수 Date : 2018.10.30
Reference
Daejun-ilbo, The founder of 'Venn Diagram' and mathematician John Venn's 180th birthday, 2014.08.05.
His life
John Venn entered Cambridge University and showed outstanding talent. After graduating from college, he spent a year as a priest, but went back to Cambridge to teach ethics to students. He developed the semantic philosophy that was created by then-British mathematician George Fire. It deals with groups, attestation, inductive theory, etc. Venn studied a part of the collective theory and created a Venn diagram that could logically represent the relationship between the groups. Until Venn used the diagram, it was very rare to use the shape or diagram in formal logic, which is a logic that ignores the thought and examines the validity of reasoning in its form.
In the 1880 paper, a form of Venn diagrams that we know well and frequently use in a set emerged. He was also said to be interested in not only mathematics but also other studies, but also in writing history books, and was good at making machines.
Commented by 신혜수
Mathematics and logic were closely related, and there were often attempts to solve logical problems mathematically. Venn’s achievements in building up a foothold of such attempts are great. Personally, I took a seminar on symbolics last semester and listened to discrete mathematics this semester, which helped me to study the 1st and 2nd sections. Then, as I learned about John Venn, I realized again the relationship between logic and mathematics.
More about Venn diagram
Reference
Jang, Gyeonga, Marvrey Rick. “[Information] Is there a van diagram that looks like ice cream.?!”, Mathdonga 02 (2016). Seoul
Euler Diagram
Before Ben diagram, there was Euler diagram. Euler diagrams are similar to Ben diagrams, although they do not overlap sets without common elements.
Venn diagram for more than four sets
First, Venn drew the set in 'C' shape when there were more than four sets.
He then added that when there are n sets, the number of areas needed is . If the value of n is finite, then (number of zones) is also finite. Therefore the Venn diagram can be drawn regardless of the number of groups. There have been many studies since then.
A.W.F. Edwards has found a way to draw a Venn diagram regardless of the number of set. As you can see in the figure above, draw three circles perpendicular to each other on a sphere, and when you shine the light, a three-column Ben diagram appears on the floor. Taking this approach, we found that we could draw three circles, each of the largest and most perpendicular to the sphere, and then we could draw a Ben diagram by drawing a series of wave-shaped curves on a plane.
Frank Rusk, a professor of computer science at the University of Victoria in Canada, was studying with interest whether a symmetrical venn diagram could be drawn even when the number of set increased. The results showed that a symmetrical venn diagram could be drawn whem the number of sets were a prime number. The first thing he found after proving it was a rotating, symmetric Venn diagram with seven sets.
Professor Rick Marvrey created a funny-looking Ben diagram (left) with five ice cream cones. Recently, Marvrey found a Venn diagram (right) in the form of a seven-column ring with her student. This is the second way of drawing set of seven rotating symmetric Venn diagrams.
After proving that there are symmetric Venn diagrams when the number of sets is a prime number, mathematics professor Peter Hamburg at Central State University in the U.S. worked with his wife Eddie Heff, who was an artist. As a result, a symmetrical Venn diagram was found with 11 sets in 2002. Art works with 2048 different colors have produced complex and perfectly symmetrical works. The right picture represents 11 sets. The pair also presented the symmetrical Venn diagram at the Bridge Academy, which combines math and art in 2005.
How to draw Venn diagram
Reference
Understanding Hamiltonian path finding in graph theory is easy to draw.
How to draw Venn diagram with n sets
1. Draw Venn diagram with (n-1) sets.
2. Write down number at the set so that the number is continuous between the sets which are sharing the boundary.
3. Connect the number with the line.
Drawing Venn diagram for 4 sets.
Drawing Venn diagram for 5 sets
Georg Ferdinand Ludwig Philipp Cantor (1845~1918)
Commented by 신혜수 Date : 2018.11.21
The essence of mathematics is its freedom.
"Das Wesen der Mathematik liegt in ihrer Freiheit"
Reference
Kim, Byeonghan. “Contor and Set Theory”, Jipyeong
His life
He earned his Ph.D. in 1967 with a number theory. He proved the uniqueness of trigonometry series in 1870. Since 1885, Cantor has left his mathematical studies for theology and literature. But he did not stop studying math completely. He also published a diagonal argument and contributed greatly to the first World Congress of Mathematicians in Zurich, Switzerland, in 1897. But his youngest son suddenly changed his fate, and his nervous breakdown was weakened. Because of these factors, the life of a nursing home was repeated until his death in 1918.
Cantor and set
During the 19th century, there was a rejection against infinity for religious and academic reasons. In addition, with the tremendous development of calculus and modern analysis in the 17th century, math became increasingly abstract. Therefore it was necessary to lay the foundations of mathematics. He dealt with the size of an infinite set. The whole set of natural number described whether a one-on-one response with a whole set of rational number was possible, and whether the total number of real number could be counted. Cantor's discussion of the size of an infinite set goes beyond this, as the number of points in the finite dimension (i.e. n) is one-on-one with the number of job losses. The problem that Cantor put his heart and soul into is continuous theory. He expected there to be no larger or smaller set than the total number of natural numbers, but he failed to prove it.
Commented by 신혜수
Cantor is a mathematician who was handle infinity, which was taboo at the time. He himself was a religious man, and people around him criticized Cantor for his quest for infinity. But without his quest, today's mathematics may have been quite different. His desire for learning is a warning to me today, sitting comfortably in college and taking classes.
Additional Data
Reference
Wikipedia, Countable Set. https://en.wikipedia.org/wiki/Countable_set
Wikipedia, Aleph number. https://en.wikipedia.org/wiki/Aleph_number
1. The natural number set is a set of numerous elements (infinite elements).
2. The set of real number has more elements than set
It shows that there is also a difference in size between infinite sets.
The word ‘countable’ is from ‘countable set’, which means that there is one-to-one response to the set of natural number.
Countable Set
In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set. Whether finite or infinite, the elements of a countable set can always be counted one at a time and, although the counting may never finish, every element of the set is associated with a unique natural number.
Aleph Number
In particular set theory, the aleph numbers are a sequence of numbers used to represent the cardinality (or size) of infinite sets that can be well-ordered.
Augustus De Morgan (1806 ∼ 1871)
Commented by 신혜수 Date : 2018.11.07.
Reference
Wikipedia, De Morgan’s laws, https://en.wikipedia.org/wiki/De_Morgan%27s_laws
Daum blog, De Morgan. http://m.blog.daum.net/sshyorim/5888127?tp_nil_a=2
His life
He entered Trinity College at Cambridge in 1823, when he was sixteen. In 1828 he became a professor of mathematics at the University of London without a single thesis on mathematics and served as dean. He is also famous for being a mathematician who expresses groups or propositions with abstract symbols.
It was the first to define the "Mathematical induction" and also to create "the law of de Morgan." Semiotics are also a great achievement he left behind. His definition of 'limit' was his first attempt to express limit ideas as symbols, which contributed to the completion of limit concepts in the 19th century. In addition, he invented the decimal coin system and published "Arithmetic Books," which recorded the life and history of as many as 1,500 mathematicians in 1847.
De Morgan's Law
¬(P ∨ Q) = ¬ P ∧ ¬ Q
¬(P ∧ Q) = ¬ P ∨ ¬Q
This is a rule that anyone who has studied groups has ever faced.
For example,
The negation of "I like dogs and cats" is, "I hate dogs or cats."
The negation of "I like red or blue" says, "I hate both red and blue."
This is often used not only in set theory but also in logics.
Commented by 신혜수
De Morgan's Law is introduced in middle school math, so I think it's a familiar rule for all students. Also, it is not difficult for students who are new to Logics/Set theory because it is not difficult to understand it. That is, it is difficult to explain unless de Morgan's law is used. We often take de Morgan's law lightly, but we will always have to bear in mind its practicality and convenience.
More about De Morgan’s law
Writed by 칭기즈 Date : 2018.11.07.
Actually De Morgan's laws are widely used in programming in order to reduce the time needed to execute the code, hence the efficiency is increased.
Let me show you a good example of it. Consider the following code:
Python code:
a=0
def my_function1():
return 1
def my_function():
global a
a=1
return 0
if (not(my_function1() and my_function())):
print("hello world!")
print(a)
Discussion:
In this example both my_function1() and my_function() are functions, a named section of a program that performs a specific task.
Meanwhile "a" is a global variable which is used in this example in order to see how computer uses De Morgan's law.
Now consider this statement:
if (not(my_function1() and my_function())):
So, just imagine that A is
A=my_function1()
and B is
B=my_function()
Hence, the statement theoretically becomes
if ¬(AB)
Now we need do find numerical values of A and B
A=my_function1() is result of what my_function1() returns, which is 1.
B=my_function() is result of what my_function() returns, which is 0.
Moreover, global variable changes in value from 0 to 1,
global a
a=1
which shows that the function was executed.
Now
A=1 B=0
AB=0
¬(AB)=1
Question:
So you may think now that computer in the condition
if (not(my_function1() and my_function())):
executes my_function1() to get the value as we did and then the same with my_function().
But in practice computer does not do so, that is why I said theoretically.
Proof:
Consider the following Python code:
a=0
def my_function1():
return 0
def my_function():
global a
a=1
return 0
if (not(my_function1() and my_function())):
print("hello world!")
print(a)
Now
A=my_function1() becomes 0
B=0
But as you may notice the value of the variable "a" did not change! Why??
Simply, because when the code is compiled, computer "translates" the statement
if (not(my_function1() and my_function())):
into something like
if (not(my_function1()) or not(my_function())):
using De Morgan's law ¬(P ∧ Q) = ¬ P ∨ ¬Q.
or symbolically
¬(AB)=¬A ∨¬B
Hence it computes initially only the value obtained from A=my_function1()
and if it satisfies the condition (if (¬A ∨¬B) =1)
computer just ignores the second one because the value of B does not affect on the result in this case if A=1.
That is why computer did not execute B= my_function() and the value of variable "a" did not change. Why?
Because it helps to save time of execution and increase ifficiency.■
Isn't it amazing?^^
Euclid
Commented by 신혜수 Date : 2018.11.04
Reference
Wikipedia, Euclid’s Elements, https://en.wikipedia.org/wiki/Euclid%27s_Elements
His life
It is assumed to have been active around the 3rd century B.C. and no exact date of birth or death is reported.
According to some people, Ptolemaeus asked Euclid, "Is there no shortcut to learning about geometry?" Euclid says, "Lord, there is no royal road for you only."
Euclid’s Element
Euclid writes a book called 'Euclid's Element' which covers mathematics at that time in the 3rd century B.C. It is made up of 13 books, and contains the mathematics of Pythagorean Theorem, geometry, construction, and sequence.
Euclid began with 23 definitions, 5 axioms, and 5 postulates. This was the basis for his development of mathematics. He selected them according to his needs and proved his first proposition. The results of the thesis were mixed to prove the next thesis. The original theory is that the construction of a axiom system was constructed in this way.
Euclidean Algorithm
Theorem 3.2 |
|
If , , and (), then . |
In addition, in Chapter 9, the fundamental theorem of arithmetic was shown and that the prime number is infinite is proved.
The "Euclid’s Element" which contains all of this, is still established as an introduction to mathematics.
Commented by 신혜수
Although many non-Euclidean geometry studies are being done in modern times, it will never be possible to ignore the significance of Euclid's element. His influence in early mathematics is enormous. Starting with a little definitions and axioms in his early days, he established a system of mathematics.
Commented by 전솔람 Date : 2018.11.06
Thank you for your always good information.
It would be great to use our team report as an interesting subject!
Commented by 김은률 Date : 2018.11.05
I am looking at the mathematician and the writing that keep raising.^^
Thank you, classmate!
Johann Carl Friedrich Gauss( 1777 ~ 1855 )
Commented by 신혜수 Date : 2018.11.08
Reference
Wikipedia, Carl Friedrich Gauss,
https://en.wikipedia.org/wiki/Carl_Friedrich_Gauss
Tistory Blog, the remainder and modulus, http://j1w2k3.tistory.com/391
Materials for class, http://matrix.skku.ac.kr/2018-DM/Ch-5/
His life
His father was a brick builder, so he wanted Gaus to run his family business rather than study. With the help of his mother and other relatives, he was able to enter University of Göttingen. He showed that at the age of 19, a Fermat prime, regular polygon can be composed only by the ungraded ruler and the compass. Especially, he was so happy that he found it possible to draw a regular heptadecagon that he asked his tombstone to be drawn with a regular heptadecagon. At the age of 21, he completed a book called Disquisations Arithmeticae. In this book, he describes modulus, secondary mutual law, etc. In addition, he has a variety of accomplishments, including fundamental theorem of arithmetic, prediction of dwarf planet Ceres' trajectory, and the invention of the electromagnetic telegraph. He died at the age of 77, and there are 17 stars on his tombstone.
Modulus
When the remainder of integers a and b divided by the positive integer m is the same, they are expressed as:
There is a useful theorem as regards modulus.
Theorem 2.17 |
|
If , and are positive integers, . |
If the above theorem are used, the remainder of the larger numbers can be easily obtained by any means.
Fundamental Theorem of Arithmetic
Theorem 1.11 |
Fundamental Theorem of Arithmetic |
|
That is, all positive integers have the only one prime factorization.
Commented by 신혜수
Modulus is one of the things you learn when you first encounter Number theory and can be very useful in the field of dealing with remain of a large number. Also, the fundamental theorem of arithmetic has been used since elementary school, and although it has not been directly certified, it has recognized and used. Prime factorization is not a difficult concept in itself, and it is easy to ignore the value of the verification process because it has been accepted for a long time. However, RSA's cryptographic theory, which has a wide range of uses in modern times, is also based on this theorem. The stability of RSA's code is focused on the difficulty of prime factorization of large numbers, and if there were multiple methods of prime factorization of large number, this would not have been adopted as a password. Even the most easily neglected theorem has come to realize that it is becoming the foundation for modern mathematics.
Blaise Pascal (1623~1662)
Commented by 신혜수 Date : 2018.11.06
Reference
Wikipedia, Blaise Pascal
https://ko.wikipedia.org/wiki/%EB%B8%94%EB%A0%88%EC%A6%88_%ED%8C%8C%EC%8A%A4%EC%B9%BC
Naver blog, The properties of Pascal's triangle and binomial coefficient;
https://m.blog.naver.com/PostView.nhn?blogId=vollollov&logNo=220947452823&proxyReferer=https%3A%2F%2Fwww.google.com%2F
His life
Pascal's father did not teach Pascal math, but instead Pascal was interested in math and asked the professor constantly about it. When he was 12 years old, he discovered on his own that the triangle's anglesum is 180 degrees. As a result, my father gave Pascal Euclid's Element to study. He discovered Pascal's triangle at the age of 13, and at the age of 14, he participated in a weekly gathering of French mathematicians. He also proved Pascal's theorem at the age of 16, and proved 400 prepositions at the following years. At 19 years old, he invented the world's first calculator to help his father work, and at the age of 21, he established Pascal's law concerning pressure. But at age 27, he stopped studying math and science and concentrated on studying theology. In his mid-30s, he developed a headache and studied cycloid to forget his headache. But soon he dies.
Pascals’ Triangle
First, write the number 1 in the first line. To create the next line, add the upper left and the right numbers. For example, a fourth row of numbers 1 and 3 are added to form a fifth row of four.
You can make Pascal's triangle in the above method. It has many properties, most representative of which is the coefficient of an expansion.
Commented by 신혜수
It was impressive writing the life of Pascal. His achievements are being renewed every year. I felt that a real child was that kind of person. What's noteworthy here is that Pascal also learned mathematics from Euclid's Element. The importance of textbooks is illustrated in this section. As a dreamer of writing a textbook, I learned it once again by describing the meaning and importance of Pascal.
Commented by 강병훈 Date : 2018.11.06
사이클로이드는 원을 굴렸을 때 원에 찍은 점이 그리는 곡선이다.
사이클로이드 곡선은 적당한 반지름을 갖는 원 위에 한 점을 찍고, 그 원을 한 직선 위에서 굴렸을 때 점이 그리며 나아가는 곡선이다. 이 곡선은 수학과 물리학에 있어서 매우 중요하며 초기 미분적분학의 개발에 크게 도움을 준 곡선이다. 특히, 갈릴레오는 맨 처음 이 곡선의 중요성을 이야기하면서 다리의 아치를 이 곡선을 이용하여 만들 것을 추천하기도 했다.
사이클로이드에 대하여는 많은 성질이 있지만 그 중에서도 흥미로운 것은 사이클로이드를 거꾸로 한 형태의 그릇을 만들고 그 벽에 유리구슬을 놓으면 위치와는 상관없이 바닥에 닿기까지 걸리는 시간은 같다는 것이다. 그 이유는 다음 그림을 보면 알 수 있다.
위 그림에서 각 원은 반지름이 a인 원이 ¼회전한 상태이며 P1은 출발전, P2는 P1에서 ¼회전한 후에 사이클로이드와 만나는 점, P3는 P2에서 ¼회전한 후에 사이클로이드와 만나는 점, P4는 P3에서 ¼회전한 후에 사이클로이드와 만나는 점, P5는 P4에서 ¼회전한 후에 사이클로이드와 만나는 점으로 원이 완전히 한 바퀴 돌고 난 후의 점이다. 그림에서 알 수 있듯이 P1에서 P2까지의 거리는 P2에서 P3까지의 거리보다 짧다. 즉, 원의 이동속도는 같은 시간에 더 멀리 가야하므로 P1에서 P2까지 이동하는 속도보다 P2에서 P3까지 이동하는 속도가 더 빠르다. 증명을 하려면위치에너지와 운동에너지를 이용하면되는데, 상세한 내용에 관심이 있으면 자료(원문,번역)를 참고하라.
우리나라 전통 기와에 나타난 사이클로이드
전통 기와의 곡선은 사이클로이드이다.
우리 민족은 이미 오래 전부터 사이클로이드를 여기저기에 이용해 왔는데, 그 중에서 가장 쉽게 볼 수 있는 것이 기와이다. 우리나라의 기와를 보면 우묵한 곡선 모양으로 되어 있다. 기와가 이런 모양으로 만들어진 이유는 빗물이 기와에 스며들어 목조 건물이 썩는 것을 막기 위해서이다. 즉, 빗물이 가능한 기와에 머무는 시간을 줄여서 빨리 흘러가게 하기 위해서 기와의 모양을 사이클로이드로 만든 것이다.
사이클로이드는 경사면에서 가장 빠른 속도를 내는 특별한 성질을 가지고 있기 때문에 ‘최단강하선’이라고도 한다. 그리고 동물들도 이와 같은 성질을 이용하는 것으로 알려져 있다. 하늘 높이 나는 독수리나 매가 땅위에 있는 들쥐나 토끼를 잡을 때 직선으로 내려오는 것이 아니라 사이클로이드에 가깝게 목표물을 향해 곡선비행을 한다. 한갓 동물들도 수학적 사실을 활용하고 있으니 수학은 역시 대단한 학문이다.
[네이버 지식백과] 사이클로이드 - 불화의 사과 (수학산책)
Pierre de Fermat (1607~1665)
Commented by 신혜수 Date : 2018.11.21
Reference
Wikipedia, Pierre de Fermat
https://ko.wikipedia.org/wiki/%ED%94%BC%EC%97%90%EB%A5%B4_%EB%93%9C_%ED%8E%98%EB%A5%B4%EB%A7%88
Tistory, Fermat's Little Theorem. http://freshrimpsushi.tistory.com/121
His life
His childhood is known to be normal. In 1626, he showed interest in law by earning his bachelor's degree in law, but after reading Apollonios article, he was fascinated with mathematics and began studying mathematics.
He didn't announce it because he was annoyed by the media spotlight even after he did the proof, and that's how Fermat's final theorem was born. He has made a lot of contributions in the field of Number Theory and analytical studies. In particular, he studied orthogonal coordinate systems but did not publish them. Descartes' study of coordinate systems at similar times became more widely known, so it is now called orthogonal coordinate systems or Cartesian coordinate systems.
Fermat's last theorem, named after him, was a mathematical challenge until the 20th century. Although less known than the last theorem, still important, Fermat's little theorem is known to have been first proven by Leibnitz.
Fermat’s little theorem
Prime p and coprime integer a.
Fermat's little theorem is a simple but widely used arrangement.
Although there is a generalized theorem by Euler, Fermat's little theorem is often enough.
In particular, it is essential for cryptography, which deals with the power of finite field.
For example, suppose you need to divide the number 3298^12 by 13. By Fermat's theorem, you can see that the answer is 1. Using this, the remainder of 3298^24 divided by 13 is also 1. Using Fermat's theorem would make it easier to deal with a large number of others.
Commented by 신혜수
Although it is obvious that Fermat's name is widely known and a great mathematician, I think it is undesirable not to give an announcement. While taking discrete math classes, we were able to solve problems with our classmates and develop by talking about each other's good and bad points through the Revised/Finalized step. Although Fermat exchanged letters with friends or colleagues, it would have been desirable to talk and discuss with more people. I also think it is consideration for latecomers to let the world know about their research. If all the mathematicians had hidden their studies, we would not have learned equations even in universities today. That's why his mathematical talents are great, but it's as bad as he didn't want to publish his research.
Commented by 김영철 Date : 2018.11.21.
I remember reading an article about Andrew Wiles, who won the Abel Award for proving Fermat's last theorem.
Thank you!
Commented by 정호진 Date : 2018.11.21.
Thank you for explaining the life of mathematician Fermat and the theory he organized. In a book I read about Fermat when I was young, I knew that he had a solution to a theory (the last theorem of Fermat), but he left the world and went to prove his theory, not to others. I didn't really know how great a person was because I didn't really know the importance of proving the subject of mathematics and one theory, or whether he died without leaving a solution to Fermat's final theorem. After entering college, I learned about the importance of this process by proving the definition and theory of terminology in the mathematics subject, so I started to feel empathy. I think that modern learning has been created by applying the theories discovered and organized by our ancestors in all disciplines and correcting the errors in their theories a little by little. Modern scholars also think that learning develops little by little as they leave their research to posterity. So, I think that if we left a few of the things that Fermat did when she was alive, modern mathematics could have improved a lot. In his words, since there were advances in physics and chemistry due to advances in mathematics, I think that if Fermat's final theorem had been introduced in the 17th century, our lives today would have changed greatly.
Commented by 조영은 Date : 2018.11.21.
Thank you for your briefing on Fermat.
I agree with what you wrote in the comment.
If he was more active in explaining and presenting his theory to others,
Maybe the theory of mathematics has expanded and evolved, and the history has changed.
Commented by 오동찬 Date : 2018.11.21.
I solved several problems using Fermat's theorem this semester's major, but I remember then!
Thank you!
Leonardo Fibonacci (1175~1250)
Commented by 신혜수 Date : 2018.11.14
Reference
Wikipedia, Fibonacci. https://en.wikipedia.org/wiki/Fibonacci
Discrete Mathematics the materials for the class. http://matrix.skku.ac.kr/2018-DM/Ch-6/
His life
He was a mathematician who lived in Pisa, Italy. He is also known as Pisa of Leonardo. He traveled around the Mediterranean coast and met many merchants and learned math from them. He was invited by Frederick II and also played a role in advising citizens about math problems. In Liber Abaci (1202), Fibonacci introduced things that are now well known for Arabic numerals. The book talks about numbers and number system from 0 to 9 and shows several examples such as currency calculation and unit conversion. He is well known for Fibonacci sequence, too.
Fibonacci Number
Fibonacci's introduction to Europe begins with counting rabbits.
In the first month, only one newly born pair exists.
Rabbits that are more than two months old can reproduce.
A pair of reproducible rabbits give birth to a pair of babies every month.
Rabbits do not die.
At n th, how many rabbits are there in the nth month?
It is Fibonacci's number to explain this. In mathematics, the Fn of Fibonacci sequence is defined as follows.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...
Characteristics of Fibonacci numbers:
1) Start with 1.
2) The same two numbers are repeated at first.
3) The following are the two consecutive totals.
4) Numbers are composed of odd, odd, and even numbers.
Commented by 신혜수
Fibonacci is well known for his Fibonacci sequence, but it is not well known that he has introduced Arabic numerals in Europe. Our country accepted Arabic numerals through the United States and Japan, and the United States adopted the Arabic numerals from Europe again. So the Arabic numerals we use today are due to Fibonacci.
Commented by 양진욱 Date : 2018.11.30.
I didn't know about the history of Fibonacci, and thought it was just a kind of sequence, but it helped me a lot. Thank you.
Johann Peter Gustav Lejeune Dirichlet (1805~1859)
Commented by 신혜수 Date : 2018.11.15
Reference
Wikipedia, Johann Peter Gustav Lejeune Dirichlet
https://ko.wikipedia.org/wiki/%ED%8E%98%ED%84%B0_%EA%B5%AC%EC%8A%A4%ED%83%80%ED%94%84_%EB%A5%B4%EC%A3%88_%EB%94%94%EB%A6%AC%ED%81%B4%EB%A0%88
DM Materials for Class. http://matrix.skku.ac.kr/2018-DM/DM-Ch-6-Lab.html
Dong-a science. http://mdl.dongascience.com/magazine/view/M200910N004
His life
Dirichlet studied under the brilliant mathematicians such as Fourier, Laplace and Poisson. Soon he proved Fermat's last theorem with Lecandre in 1825 and n=5.Then, we proved the case with n=14. He was a professor at the university until the end of his life. He was very interested in Number Theory and studied it, and is known as the founder of analytical Number Theory. In addition, there are still many mathematical theorem named after him, such as the Dirichlet series and the Dirichlet arithmatic progression, and there are also pigeon hole principles that are often used to prove their existence.
Pigeonhole Principle
Pigeonhole Principle (1st Form) |
|
If pigeons fly into pigeonholes and , some pigeonhole contains at least two pigeons. |
If n pigeons enter k's pigeon house and k is smaller than n, there are at least two pigeons in some pigeon houses.
Other names include Dirichlet's division of room and drawers' principle.
The content itself seems self-evident and useless at first glance, but is often used to prove its existence. For example, it is difficult to prove in other ways that there is more than one person whose birthday is the same as me in a school with 366 students, but the principle of pigeon housing can be easily solved. (If you ignore your birthday on February 29th)
Commented by 신혜수
The pigeon house principle is so natural that it is easy to get over it. However, the pigeon housing principle was used to prove Fermat's final theorem, which was the most difficult subject in mathematics at the time. I learned that the most obvious thing should be suspected.
Commented by 오동찬 Date : 2018.11.16.
Since there are 365 days in a year, if there are more than 366 people, there will be two people whose birthdays are the same according to the Pigeon Hole Principle.
In fact, if you have only 23 people together, you're more than 50 percent likely to have two people on the same birthday, and if 57 people get together, it's 99 percent.
Dennis Ritchie (1941~2011)
Commented by 신혜수 Date : 2018.12.05.
Reference
Jung, Jihoon. "Almost all of the history of the Internet (8) - the founder of the C language, Dennis Ritchie" Venture Sqaure. 4 March. 2013.
Wikipedia, "C(Programming language)“
https://ko.wikipedia.org/wiki/C_(%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D_%EC%96%B8%EC%96%B4)
His life and achievements
Dennis Ritchie was born September 9, 1941 in Bronxville, a small town near New York. His father, Alistair E. Ritchie, is a well-known computer scientist who has long worked at Bell Labs and established the theory of switching circuits. Dennis Ritchie graduated from Harvard University with a degree in physics and applied mathematics and joined the Bell Labs where his father worked in 1967.
At Bell Labs, Kenneth Thompson creates a B language named after the Bell Labs by adapting the BCPL language to its needs. Dennis Ritchie then invented a new language to port his colleagues Brian Kernighan and Unix to various computers. He refined a B language, so his new language became C language.
Dennis Ritchie and Ken Thompson were especially strong in community orientation, so they would kindly give a lot of explanation to their programs without asking for anything. Ken Thompson and Dennis Ritchi read the Unix code line by line in the 1970s through the Unix User Group on the West Coast, It is said to have spread the spirit of Unix to people.
Dennis Ricci and Ken Thompson wanted their Unix to be used by many people, and by taking over their will, Berkeley University's programmers created many improvements to BSD Unix. These thoughts lead to the open source movement.
Commented by 신혜수
C is a widely used programming language that I have heard from anyone who is unfamiliar with programming. Especially, it helped me to draw graphs and answer and understand using codes made in discrete mathematics class.
In addition even though we have created this general language, the attitude of sharing and explaining the program is a great example. I think sharing information with people is very similar to discrete math QnA activities. Just as the people who created the C language were developers and users, I think that those who make discrete mathematics classes are professors and students. I do not have much time left until the end of the term, but I want to finish discrete mathematics through QnA activities.
Commented by 김은률 Date : 2018.12.05.
Thanks to you. I’ve learned Dennis Ritchie who specializes in the area ^ ^
It is the person who made the C language with Linus Torvalds who made Linux.
There are many talent in UC Berkeley. Through discrete mathematics it's really fun to exchange and share information.
If the field of information exchange and productive teaching methods develop further, just as we or our juniors did someday important things in their time, I think that it is possible to do more creative discussion and research beyond education.
Professor!
Less than a few days ago, I would appreciate your continued patronage of innovative teaching methods.Such efforts will be remembered by us or our younger students, Sungkyunkwan University.
Thank you!
Commented by 김영철 Date : 2018.12.05.
Dennis Rich, who created the C language with Linus Torvalds who created Linux, was also an open-source spirit. I think computer engineering has evolved so fast thanks to them.
UC Berkeley, located around the free Silicon Valley in western California, also visited last year, and it is said that it has a strong ranking in computer engineering as a rival to Stanford.
The link below shows MIT, Stanford, Carnegie-Mellon, followed by the 2018 QS survey and ranked fourth in the world of computer science.
(https://www.topuniversities.com/university-rankings/university-subject-rankings/2018/computer-science-information-systems)
Steve Wozniak, who founded Apple with Steve Jobs, is also a Berkeley person. DARPA was in charge of UNIX development at Berkeley, and Berkeley's genius developer Bill Jaw, who implemented the TCP / IP protocol in the C language.
Those who studied and studied in the area in those days seemed very happy.
Alan Mathison Turing (1912~1954)
Commented by 신혜수 Date : 2018.12.07.
Reference
ITWorld, "The start of every computer in the world" "Turing Machine" Inventor Mathematician Alan Turing's achievements. (http://www.itworld.co.kr/print/76494)
Kim, Hyungja, "ENIAC was not the first computer?" Premiumchosun.
(http://premium.chosun.com/site/data/html_dir/2015/03/05/2015030503165.html)
Wikipedia, Alan Turing. (https://en.wikipedia.org/wiki/Alan_Turing)
His life
In 1931, he entered King's College at Cambridge University and earned a bachelor's degree in mathematics. In 1937, while studying at a university, he invented a Turing machine. The Turing machine was a rudimentary type of computer capable of handling complex calculations and logic problems. He then changed the situation of the war by releasing the complex code "Enigma" of the German army during World War II. At this time, the machine created for decryption became the technical foundation of the world's first computing computer, Colossus. He also made a Turing test. With these achievement he is praised as the father of computer science. But he was accused of homosexuality, which was illegal at the time, and he was persecuted by society. In the end, he succumbs to eating poisonous apples. Recently, Stephen Hawking and many other mathematicians and scientists alleged his innocence, and in 2013 the British Queen officially pardoned his sins. The ACM awarded the Turing Award, named after Turing, to those who have had a profound influence on computer science every year.
Turing test
The Turing test was an experiment proposed by Alan Turing in 1950, and is a criterion for determining whether a machine has human-level intelligence. The interrogator speaks with two respondents (computer and person) on the computer screen, and the interrogator does not know which one is the computer. After a certain number of questions are answered, the respondent computer passes the test if the questioner can not tell which of the two is the person. If deceiving people with text is the first step in the Turing test, then the next is the technique of identifying images, and the last is the level of communicating with the natural voice.
Commented by 신혜수
Turing is the father of modern computers and one of the first to ask about 'thinking artificial intelligence', which is a hot topic these days.
His accomplishments are numerous, but he has made a great contribution to ending the war. As a child, I thought the number of soldiers was important to win the war. But when I heard that the Second World War ended with the victory of the Allied forces through machine decryption(a rudimentary type of computer), I came to think that moving the world beyond war is a computer. Although there is no war now, I’ve found that the use of computers is inevitable to lead the world.
Commented by 조영은 Date : 2018.12.07.
Movie 'Imitation Game' is based on Alan Mathison Turing's story, it is also related to cryptology and second world war.
I recommend you to watch this movie after final exam, if you did not watch it.
◆ Final comment
PBL보고서를 마치고
9월 : 참여가 부족했다. 아무래도 이런 수업이 처음이었기 때문일 것이다. 처음에는 이런 방법이 싫기도 했다. 왜냐하면 다른 수업같은 경우에는 시험 주간 1주일 전에만 바짝 공부하면 그럭저럭 성적을 얻을 수 있는데, 이 이산수학은 항시 내용을 이해하고 참여해야 하기 때문이다. 그러나 다시 생각해보면, 그것은 제 실력이 아니었다. 종강 후 아무것도 남지 않기 때문이다. 이 방법이 좀 귀찮기는 하겠지만, 나의 진정한 실력 향상에 도움이 될 것이라 믿어 의심치 않는다.
10월 : 9월보다 참여가 늘긴 했지만, 그러나 여러 훌륭한 학우들에 비하면 그에 못 미친다 생각한다. 조금 더 열심히 해서, 그동안 못한 양을 따라잡고 싶다. 또한 이제는 팀원들과 함께 공부를 하게 되었다. 팀원들 중 내가 가장 어린 만큼, 더 많이 공부해야겠다. 그리고 평소에 수학사에 대해 관심이 많았는데, 교수님께서 올리는 기삿거리에 대해 토론하는 시간을 더 많이 갖고 싶다.
11월 : 많은 수학자들에 대해 학우들과 토론하는 시간을 가졌다. 저 역시 수학자들을 조사하면서 배운 것이 많습니다. 12월달에는 컴퓨터와 관련된 학자들을 탐구해보는 시간을 많이 갖고 싶습니다.
더불어, 11월달은 본격적으로 팀원들과 이야기하고 토론하는 시간을 자주 나눴습니다. 팀원들에게 묻고 답하면서 확실히 알고 있는지 검증하는 시간이 되기도 하였습니다. 또한 팀별로 활동하다 보니 책임감도 많이 자랐던 11월이었습니다.
12월 : 어느덧 날도 추워지고 종강 날짜가 머지않은 지금, 다시 한 학기를 되돌아보았습니다. 처음에는 Flipped Learning 방식이 익숙치 않아 헤메기도 하였습니다. QnA 활동도 처음에는 내키지 않았습니다. 그러나 하면 할수록 지식을 주고 받는 과정이 재미있었고, 문제를 푸는 것 뿐만 아니라 새로운 자료나 기사글을 보며 많은 것을 배울 수 있었던 시간이었습니다. 특히 그동안 QnA에 올렸던 수학자들의 연표를 만들어보니, 이제는 정말로 모든 것을 마무리한다는 느낌이 들어 아쉽기도 하였습니다. 아쉬움을 발판으로, 다음 학기에 더 거듭나야겠다는 다짐을 하였습니다.
■
Final PBL보고서를 마치고
9월 : 첫 수업에 들어가며, 열정적인 교수님의 모습에 귀감을 받았다. 때문에 초기에는 열심히 수업을 따라가 보자라는 결심을 했던 것 같다. 하지만, icampus 공지사항을 보았을 때 조금은 겁을 먹었다. 많은 공지내용과 숙지해야하는 학습내용이 있었고, 이를 내가 전부 감당할 수 있을까 걱정이 됐었다.
10월 : 생각보다 수업시간 외에 해야 할 것이 많았다. 때문에 어쩌면 포기하고 싶었는지도 몰랐을 것 같다. 하지만, 막상 포기 후 내게 지어질 책임을 생각한다면, 절대 포기하면 안 되겠다고 생각했다. 반 학기 동안의 나의 학습 내용을 정리하는 시간을 가져보니, 참 부족한 점만 많이 떠올랐다. 참여 횟수도 다른 이들보다 확연히 적었고, 실제 개인 학습 시간도 너무 부족했다. 비록 이번 첫 보고서는 많은 부족함을 품고 있지만, 앞으로의 모든 보고서는 절대 이렇게 하지 않아야겠다고 다짐하는 계기가 되었다. 이번 수업은 다른 수업에 비해 능동적으로 공부하고 소통해야한다는 것을 잊지 말고, 앞으로 더욱 최선을 다하길 다짐한다.
11월 : 이번 달에는 기존 풀이와 더불어 1, 2단원의 문제들을 다시 한 번 볼 수 있는 기회가 있었습니다. 덕분에 이전에 수업 참여를 성실히 하지 못해 보지 못했었던 문제들을 다시 볼 수 있는 기회를 얻었고, 이를 정리할 수 있는 시간을 가졌습니다. 게다가 팀원들과 만나 소통하며 공부할 수 있는 시간이 주어져 더욱 도움이 되었습니다. 이전에는 모르는 사항을 QnA에 물어보았다면, 이번 달에는 팀원들 간의 소통을 통해 더욱 신속한 질의응답이 가능하여졌다. 또한 이번 달에는 이전 보다 더욱 적극적으로 학습에 참여하였습니다. 학습을 통해 내가 모르는 것을 다른 학우에게 물어볼 수 있어서 흥미로웠으며, 문제를 풀고 이를 수정 받아, 틀리는 부분이 없도록 더욱 견고한 학습을 할 수 있었습니다.
12월 : 마지막 학기를 보내고 있는 저에게 이번 학기의 모든 과목은 특별한 의미를 갖습니다. 특히나 이산수학 과목은 제게 꽤나 오래 기억에 남을 것 같습니다. 처음 보는 교수님의 열정에 놀랐고, 이를 열심히 따라가려는 학우들의 모습을 볼 수 있는 기회였습니다. 단순히 열심히 하는 학생이 좋은 성적을 받아가겠지 라고만 생각했지만, 이번에는 그런 학우들을 직접 보고 경험할 수 있는 좋은 시간이었습니다. 앞으로 대학을 졸업하고 사회에 진출하면, 다시금 이번 수업을 되새기며 열심히 노력하는 사람이 되고 싶습니다. 힘들었지만, 감사함으로 마무리할 수 있게 해주신 교수님께도 감사드립니다. ■
Copyright @ 2018 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
*This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2017R1D1A1B03035865).