Action Learninghttp://matrix.skku.ac.kr/2018-DM-Sol/2018-DM-Sol.htm

 

Discrete Mathematics

 

Prof : Sang-Gu LEE (http://matrix.skku.ac.kr/sglee/ )

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-PBL/

 

주경용 (조장) 생명과학과, 남영욱 시스템경영공학과, 박종호 시스템경영공학과, 김동준 융합생명공학과

 

 

Chapter 1

 

1.    1]Q&A                                                                   

Question & Answer

Chapter

Ch1, Sets and Logics

Date

2018.03.09

 

Type

Writer

Title

Contents

Question

조규상

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Problems in solving Quiz 1,2

In Quiz1.Problem 3

 

(6)T/F The proposition "If all cats are white, then all dog is brown" is true

 

Solution says it is True.

 

I wonder if it is true because hypothesis is false.

 

Or are there any other reason exists?

 

2. In Quiz2. Problem 1

 

Solution writes a truth table to determine the validity.

 

Is it okay to solve in this way?

 

p: Socrates is a cat.

q : Socrates is a mortal.

r: Socrates is a man.

 

p q

r (¬q)

 

r (¬q) (¬q) r q r

 

p q

q r

p

 

Answer

1

이상구

교수님

Final: Dear Mr. 조규상, Use truth table to determine^^

Final: Dear Mr. 조규상,  Use truth table to determine^^

Dear Mr. 조규상,  Here is my Comment^^ 1. In Quiz1. Problem 3

 

(6) T/F The proposition "If all cats are white, then all dog is brown" is true

Because if it is true because the hypothesis (all cats are white) is false. [Yes you are right]

2. In Quiz2. Problem 1

 

Solution writes a truth table to determine the validity.

 

p: Socrates is a cat.

q : Socrates is a mortal.

r: Socrates is a man.

 

p q

r (¬q)

 

r (¬q) (¬q) r q r

 

p q

q r

________

p

 

Is it okay to solve in this way?  틀리지는 않았지만truth table 을 이용하여 validity determine 하라고 요구하였으니이 답을 부분 점수를 받을 수 있습니다

 

Use truth table to determine the validity. 로 다시 한번 해 보시는 것이 맞습니다.

 

2

박종호

final 박종호 : quiz2 problem1

In Quiz2.Problem 1

Solution writes a truth table to determine the validity.

 

p: Socrates is a cat.

q : Socrates is a mortal.

r: Socrates is a man.

 

p q

r (¬q)

r (¬q) (¬q) r q r

p q

q r

________

p

 

->위 문제에 대한 진리표는 솔루션에 있으니 생략하고

r (¬q) (¬q) r q r라고 작성하신 부분에서 동치가 나와 참고하시라고 작성합니다.

 

예제 1.2.13을 참고하시면 p->q의 부정과 p 또는 ㄱq와의 논리적 동치(logically equivalent)를 다뤘습니다. 같은 방식으로 동치 관계를 구한 것들을 올립니다.

 

1. (p v q) p and q

2. (p and q)  p v q

3. p->q  p and q

4. p<->q  (p->q) and (q->p)

 

p q

q r

________

p

 

작성자는 동치를 이용해 q->r을 이끌어내고 가설적 삼단논법(hypothetical syllogism)의 규칙으로 p->r이 타당함을 증명해냈습니다. 근데 문제에는 진리표를 작성하라는 말이 없음에도 불구하고 부분 점수를 받는군요~ 삼단논법은 그림 1.4.1과 예제 1.4.4를 참고하시면 이해가 편할 것 같습니다.  

 

 

 

 

 

 

 

 

 

 

 

 

 

2.     2]Q&A                                                                    Final Ok

Question & Answer

Chapter

Ch1, Sets and Logics

Date

2018.03.10

 

Type

Writer

Title

Contents

Question

이세영

'Example 1.3.2' & 'Definition 1.3.3'

I'm little bit confusing with 'Example 1.3.2'&'Definition 1.3.3' in the textbook.

 

​​pq

p: The Mathematics Department gets an additional $60,000.

q: The Mathematics Department will hire one new faculty member.

 

the book says... we should define pto be true when p is false.

 

But I think... 

 

If p is false, whatever q is, We cannot know whether pq true or not.

 

We should conclude 'it is true!' when we don't know exactly the result that pq is true or not?

 

Answer

1

이상구

교수님

Final: Answer: Dear 이세영, 'Example 1.3.2' & 'Definition 1.3.3'

Dear 이세영,

 

 설명을 읽어보고 이해가 되면 제목에 Final 을 주어 자신이 이해한 요약을 답으로 정리하여 달아주세요^^

 

pq

p: The Mathematics Department gets an additional $60,000.

q: The Mathematics Department will hire one new faculty member.

 

We did agree [p→q to be true when p is false] from the observation of the Truth table.

 

1. If p is false (The Mathematics Department 가 추가 예산을 확보 못하면),  

  whatever q is (The Mathematics Department  가 새 교수요원을 고용하거나, 안 하거나), 

 

 The Mathematics Department​​  false인 행동을 한 것이 전혀 없다 

[예를 들어, "학장이 학과장들에게 만일 단과대학이 추가예산 5천만원을 확보하면 (p), 수학과에 교수요원을 한 두 명 고용하도록 도와 주겠다 (q)." 하고 얘기를 한 상황에서 생각해 보시오. 이 때 학장이 만을 재단으로부터 추가 예산을 확보 못하면, 학장이 추가 교수요원을 뽑아 주어도 OK 이고, 못 뽑아주어도 OK 입니다)]

  

따라서 

 

2.  (The Mathematics Department  가 새 교수요원을 고용한 것도  false 인 행동을 한 것이 전혀 없으니까   False True 중에서 하나만 고른다면 True 로 정의하는 것이 더 합리적이고, 따라서 True 이고

 

3. (The Mathematics Department  가 새 교수요원을 고용하지 않아도, false 인 행동을 한 것이 전혀 없으니까   False True 중에서 하나만 고른다면 True 로 정의하는 것이 더 합리적이고, 따라서 True 입니다.) 

 

결론 

      We know whether pq is not False. 

 

So we agreed to conclude 'it is not False = It is true' when we know exactly the result that pq is not false. 

 

Final

 

이세영

Final : summery (Tautology), Final OK by SGLee

Final : summery (Tautology),  Final OK by SGLee

 

pq

p : The Mathematics Department gets an additional $60,000.

q : The Mathematics Department will hire one new faculty member.

 

If p is false => whatever q is....

 

The Mathematics did not do "false" action.

 

It is more reasonable to choose 'True' than 'False' in this 'Not false' action.

 

헷갈렸었는데 답을 듣고 확실히 알 수 있었습니다!

감사합니다: D

 ******

Final을 붙여 답을 다는 것이 이렇게 하는게 맞나요

 

 

 

 

 

 

 

 

 

 

 

2.     3]Q&A                                                                    

Question & Answer

Chapter

Ch1, Sets and Logics

Date

2018.03.10

 

Type

Writer

Title

Contents

Question

이진용

Quiz 1 (4), (5)

Tautology contradiction 이 두 단어가 의미하는 것이 무엇인지 잘 모르겠습니다.

Answer

1

이상구

교수님

Final: Dear 이진용, contradiction (모순), tautology(항진(恒眞)명제) (4), (5)

이진용, contradiction (모순),    tautology(항진(恒眞)명제

https://en.wikipedia.org/wiki/Proof_by_contradiction 

Proof by contradiction

From Wikipedia, the free encyclopedia

In logicproof by contradiction is a form of proof, and more specifically a form of indirect proof, that establishes the truth or validity of a proposition. It starts by assuming that the opposite proposition is true, and then shows that such an assumption leads to a contradiction. Proof by contradiction is also known as indirect proofapagogical argumentproof by assuming the opposite, and reductio ad impossibilem. It is a particular kind of the more general form of argument known as reductio ad absurdum.[1][2]

G. H. Hardy described proof by contradiction as "one of a mathematician's finest weapons", saying "It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."[1] 

 

Principle[edit]

Proof by contradiction is based on the law of noncontradiction as first formalized as a metaphysical principle by Aristotle. Noncontradiction is also a theorem in propositional logic. This states that an assertion or mathematical statement cannot be both true and false. That is, a proposition Q and its negation {\displaystyle \lnot } Q ("not-Q") cannot both be true. In a proof by contradiction, it is shown that the denial of the statement being proved results in such a contradiction. It has the form of a reductio ad absurdum argument. If P is the proposition to be proved:

2.       P is assumed to be false, that is {\displaystyle \lnot } P is true.

3.       It is shown that {\displaystyle \lnot } P implies two mutually contradictory assertions, Q and {\displaystyle \lnot } Q.

4.       Since Q and {\displaystyle \lnot } Q cannot both be true, the assumption that P is false must be wrong, and P must be true.

An alternate form derives a contradiction with the statement to be proved itself:

1.     P is assumed to be false.

2.     It is shown that {\displaystyle \lnot } P implies P.

3.     Since P and {\displaystyle \lnot } P cannot both be true, the assumption must be wrong and P must be true.

An existence proof by contradiction assumes that some object doesn't exist, and then proves that this would lead to a contradiction; thus, such an object must exist. Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts this kind of nonconstructive proof as universally valid. 

 

http://www.aistudy.co.kr/logic/tautology.htm 

 

Tautology- 항진(恒眞)명제(tautology) 

 

논리식 혹은 합성명제에 있어 각 명제의 참·거짓의 모든 조합에 대하여 항상 참인 것을 항진(恒眞)명제(tautology) 라고 한다

 

Tautology  : 진리표 에서 알 수 있는 바와 같이......

 

i) 가능한 모든 조건 아래에서 모든 진리치가 진이 되는 명제

이것은 원자명제 진리치에 상관없이 항상 진인 이런 명제를 항진명제 (tautology)라 한다

 

일반적으로어떤 진리함수적 명제의 가능한 진리치가 모두 진일 때, 오직 그 때에만, 그 명제를 tautology 라 부른다

 

항진명제는 그 논리적 형식상 결코 위가 될 수 없고 항상 진이어야만 한다. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.     4]Q&A                                                                    Final Ok

Question & Answer

Chapter

Ch1, Sets and Logics

Date

2018.03.10

 

Type

Writer

Title

Contents

Question

함형빈

Quiz #1 Problem 1 number 3

Cardinality of P(T)를 물어봤는데 이중 P가 정확히 무엇을 의미하는지는 모르겠지만 solution에 답이 8로 나와있는데...... 그건 아닌 것 같다고 생각됩니다.

 

P가 전체를 의미한다면 10이 나올 것이고, 중복되지 않는 것이나 T set에 있는 것과 같은 것의 총합이라 한다면 6이 답일텐데...... 8이 나왔는지 모르겠습니다.

Final

 

이상구

교수님

Final OK by SGLee: Answer : Quiz #1 Problem 1 number 3, Cardinality of P(T) = 8

Answer : Quiz #1 Problem 1 number 3,  Cardinality of P(T) = 8 

Answer

Given set T=(2,4,8) , 

Cardinality of P(T), the power sot of T.

empty set,(2), (4), (8), (2,4), (2,8), (4,8), (2,4,8)  

 

Total   8 

 Cardinality of P(T) = 8

 

그러므로 #Promblem1-(3)의 답이 8 입니다. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.     5]Q&A                                                                    Final Ok

Question & Answer

Chapter

Ch1, Sets and Logics

Date

2018.03.10

 

Type

Writer

Title

Contents

Question

장호

Power set P( ) 질문

Quiz1 problem1이나 problem2에서 P(T) P(S)가 나왔는데, 그 의미를 모르갰습니다.

Answer

1

조규상

Final: Final OK by SGLee Quiz 1 Problem 1-3, Power set, 8

Final: Final OK by SGLee Quiz 1 Problem 1-3, Power set, 8

Power set으로 생각하시면 8으로 나옵니다

 

Q set T=  {2, 4, 8} Power set 안의 부분집합의 개수는?

 

Answer 

Final: Answer Re: Quiz #1 Problem 1 number 3, Power set, 8  

 

공집합, {2},  {4}, {8}, {2, 4},  {2, 8}, {4, 8}, {2, 4, 8}

8 개입니다.

*******************

그러므로 #Promblem1-(3)의 답이 8입니다.

Final: Answer Re: Quiz #1 Problem 1 number 3, Power set, 8  

 

위에도 답을 주셨습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.     6]Q&A                                                                    

Question & Answer

Chapter

Ch1, Sets and Logics

Date

2018.03.10

 

Type

Writer

Title

Contents

Question

홍석호

Quiz1 2번문제 질문드립니다.

{0, {1, 2}, {3, 4, 5}} Z.    

 

For any set S, S P(S).

이 둘이 False인 이유를 모르겠습니다

 

그리고 더불어   p (p q) is a tautology.

진리표를 만들어보면 항진명제라는 것은 자명합니다. 그러나 진리표 없이 문맥상으로 항진, 모순 명제를 유추할수는 없는지요? 문맥상으로 보면 P Q의 합집합입니다. 명제는 집합으로는 접근하면 안되는지도 궁금합니다

 

Answer

1

이상구

교수님

Final: Dear 홍석호, 용도에 따라 다양한 증명이 있습니다. 이것을 2장에서 배웁니다.

홍석호,

 

Dear 홍석호, quiz 1 problem 2 - (10) False 인 이유를 알려드립니다.

For any set S, element S is in P(S)    [True,  # 9], 

 

            but  [element SP(S) is False,  # 10] 

 

멱집합(冪集合영어power set) 정의를 자세히 보시면

 

S power set of S element 이기는 하지만 [True,  # 9 ] ,​,   

S power set of S  subset 아닙니다 [ False,  # 10] 

 

     

https://ko.wikipedia.org/wiki/%EB%A9%B1%EC%A7%91%ED%95%A9 

 

 p (p q) is a tautology.

진리표를 만들어보면 항진명제라는 것은 자명합니다...... 

 

진리표 없이 문맥상으로 항진, 모순 명제를 유추할수 있습니다.

문맥상으로 P Q의 합집합 임을 유추할 수 있습니다.

 

명제를 집합으로 접근하는 것이 벤 다이어그램을 이용하는 설명법입니다.

용도에 따라 다양한 증명이 있습니다. 이것을 2장에서 배웁니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.     7]Q&A                                                                    Final Ok

Question & Answer

Chapter

Ch1, Sets and Logics

Date

2018.03.10

 

Type

Writer

Title

Contents

Question

강민석

quiz1 단어뜻질문드립니다

tautology가 무슨뜻인지 몰라서 인터넷에 검색해보니

동의어반복이라는데 정확히 무슨의미인지 궁급합니다 

 

Answer

1

이동욱

항진명제입니다.

항진명제: 언제나 참인 명제라는 뜻입니다.

 

Final

 

이상구

교수님

Final OK by SGLee to 이동욱, 강민석군, 항진(恒眞)명제(tautology) ......

강민석군, 항진(恒眞)명제(tautology) quiz1 단어 뜻

 

http://www.aistudy.co.kr/logic/tautology.htm 

 

Tautology- 항진(恒眞)명제(tautology) 

 

논리식 혹은 합성명제에 있어 

 

각 명제의 참·거짓의 모든 조합에 대하여 항상 참인 것을 항진(恒眞)명제(tautology) 라고 한다

 

Tautology :  진리표 에서 알 수 있는 바와 같이,...

 

i) 가능한 모든 조건 아래에서 모든 진리치가 진이 되는 명제

 

이것은 원자명제 진리치에 상관없이 항상 진인 이런 명제를 항진명제 (tautology) 라 한다 일반적으로어떤 진리함수적 명제의 가능한 진리치가 모두 진일 때, 오직 그 때에만, 그 명제를 tautology 라 부른다

항진명제는 그 논리적 형식상 결코 위가 될 수 없고 항상 진이어야만 한다.

 

 

 

 

 

 

 

 

 

 

 

 

2.   8]Q&A                                                                    

Question & Answer

Chapter

Ch1, Sets and Logics

Date

2018.03.10

 

Type

Writer

Title

Contents

Question

이동욱

quiz 1 problem 2 질문 드립니다.

quiz 1 problem 2 - (10) 번 문제 질문드립니다.

 

For any set S, SP(S)

 

I don't have any idea why this is False...

 

Final

 

이상구

Final: Dear 이동욱 군, quiz 1 problem 2 - (10) False 인 이유를 알려드립니다.

 

Dear 이동욱 군, quiz 1 problem  2 - (10)   False 인 이유를 알려드립니다

For any set S, element S is in P(S)    [True,  # 9], 

 

            but  [element SP(S) is False,  # 10] 

 

멱집합(冪集合영어power set) 정의를 자세히 보시면

 

S power set of S element 이기는 하지만 [True,  # 9 ] ,​,   

S power set of S  subset 아닙니다 [ False,  # 10] 

 

     

https://ko.wikipedia.org/wiki/%EB%A9%B1%EC%A7%91%ED%95%A9 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.   9]Q&A                                                                   

Question & Answer

Chapter

Ch1, Sets and Logics

Date

2018.03.11

 

Type

Writer

Title

Contents

Question

강민구

example 1.4.6 질문입니다

p r and p Using modus ponens to conclude r.

modus ponen을 쓰면

p->r

p

-----

r

인데 r conclude 할 때는 p true라는 건 모르지 않나요?

 

Final

 

이상구

Final: Answer: example 1.4.6 답입니다. (이 조교님, 학생들 질문에 답을 주어 보세요-TA 채점이랍니다)

 

:   

 

p->r

p

-----

r

 

라는 의미는

 

p->r  true 이고   (1)

p     true  이면   (2) 

 

-------------------------------------------------

r   이다 라는 의미인데,

 

이는  (2) p True 이므로, (1) 에 의하여 p->r  true 됩니다.

 

따라서 r Ture 임이 (2) (1) 에의하여 유도 되는 것입니다^^

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.     10]Q&A                                                                   Final Ok

Question & Answer

Chapter

Ch1, Sets and Logics

Date

2018.03.11

 

Type

Writer

Title

Contents

Question

김지만

Quiz1 - Problem 2 - (5) 질문드립니다.

There are two partitions of a set with two element

 

두 개의 원소를 가진 집합을 partition(분할) 할 경우에는 오직 한가지의 경우, 2개의 원소가 두 개의 집합에 하나씩 나뉘어서 들어가는 경우 밖에 없기에 two partitions이 아니지 않나요? 답에는 True라고 되어 있었습니다.

two Partitions이라는 단어가 분할이 된 두개의 집합이라는 뜻인가요?

Answer

&

Final

 

이상구

교수님

Final OK by SGLee to 김지만

Ans. 1-Problem2-(5) : There are two partitions ... (T)

김지만

 

Ans. 1-Problem2-(5) : There are two partitions of a set with two element. (True)  

 

There are two partitions of a set with two element. 의미는  

 

두 개의 원소를 가진 집합을 partition(분할) 할 경우에는 

오직 한가지의 경우가 아니라 2가지 경우가 존재합니다.

 

1. 두 개의 집합에 각각 0개와 2개 씩 들어가게 나누는 방법과

 

2. 2개의 원소가 두 개의 집합에 하나씩 나뉘어서 들어가는 경우가 있습니다.

 

그래서 two partitions 가 존재하고 그래서 답에 True 라고 되어 있었습니다

 

Re-Final

 

박종호

final : dear 김지만

There are two partitions of a set with two elements.

->두개의 원소를 가진 집합은 2개의 분할을 갖느냐는 문제입니다.

 

교수님께서 설명해주셨지만 이해를 돕고자 예를 들어 표현해봤습니다.

집합 X={a, b} 라고 하면 집합 X 분할은 {{a, b}}, {{a}, {b}}, 공집합 이렇게 3개가 나옵니다

 

다음은 원소 3개를 가진 집합의 분할입니다. (참고)

-> 공집합의 원소 포함 여부에 대한 부분에 대해서도 참고하시면 좋을 것 같습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.   11]Q&A                                                                   Final Ok

Question & Answer

Chapter

Ch1, Sets and Logics

Date

2018.03.11

 

Type

Writer

Title

Contents

Question

이상철

Quiz 1. Problem 2-(6)

Quiz 1. Problem 2-(6) 문제가 True인데

정확히 어떻게 True 인지 알고 싶습니다.

 

Answer

1

박종호

final : dear 이상철

quiz1 problem2-6 

 

(6) If A and B are finite sets, then A X B is also finite

질문에서 집합 A,B가 유한집합이라면 그 데카르트 곱(Cartesian product)은 유한한가라고 물었습니다.

당연히 true입니다. 일반적으로 lA X Bl = AXBㅣ입니다.

예제 1.1.24 를 참고하시면 될 것 같습니다.

 

Final

 

이상철

final OK by SGLee Dear 이상철

말씀하신 예제를 다시 보고 확인해보니ㅣA X B = A X Bㅣ 가 true일 수 밖에 없군요.

답변 감사합니다. 이해되었습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

2.     12]Q&A                                                                   Final Ok

Question & Answer

Chapter

Ch1, Sets and Logics

Date

2018.03.11

 

Type

Writer

Title

Contents

Question

황병재

English Q. 프린트내용질문

이해안되는 부분이있는데

 

1. We define the union of an arbitrary family S of be those element x belonging to at least one X in S 이거랑 

 

2. We define the intersection of an abitrary family S of sets to be those elements x belonging to every set X in S 

 

이부분이 해석이잘안되는데 정확히 무슨뜻인지 알려주시면 감사하겠습니다

 

Answer

1

이상구

교수님

Answer : 여러분이 그동안 배운 union 집합과 intersection 집합 의 집합을 유한개의 부분집합들 X_1, X_2, ...... , X_n 을 가진 S 또는 무수히 많은 부분집합들 X_1, X_2, X_3, ...... 에 대한 개념으로 확장한 (일반화한) 개념입니다.

1. We define the union of an arbitrary family S of be those element x belonging to at least one X in S 

 

 의 의미는 예를 들어 X_1, X_2, ...... ,  X_n  S 의 부분집합이라고 할 때    X_1, X_2, ...... ,  X_n  union 집합이란 S  = {X_1, X_2, ......, X_n} 들 중 적어도 하나의 X_i 에 속하는 element x 들을 모은 집합 이라는 의미입니다

 

2. We define the intersection of an abitrary family S of sets to be those elements x belonging to every set X in S 

  

  의 의미는 예를 들어 X_1, X_2, ...... ,  X_n  S 의 부분집합이라고 할 때    X_1, X_2, ...... ,  X_n   intersection 집합이란 모든 X_1, X_2, ...... ,  X_n  들에 속하는 element x 들을 모은 집합 이라는 의미입니다

 

즉 여러분이 그동안 배운 union 집합 과  intersection 집합 의 집합을 유한개의 부분집합들 X_1, X_2, ...... ,  X_n 을 가진 또는 무수히 많은 부분집합들

X_1, X_2, X_3,  ......  에 대한 개념으로 확장한 (일반화한개념입니다.

 

Final

 

박종호

final : dear 황병재

. We define the union of an arbitrary family S of be those element x belonging to at least one X in S 이거랑 

 

2. We define the intersection of an abitrary family S of sets to be those elements x belonging to every set X in S 

이부분이 해석이잘안되는데 정확히 무슨뜻인지 알려주시면 감사하겠습니다 

 

교수님께서 예를 들어 자세히 설명해주셨지만 질문자가 정확한 뜻을 물었기에 번역해드립니다.

 

1.We define the union of an arbitrary family S of be those element x belonging to at least one X in S 

-> 임의의 집합족 S의 합집합은 S내의 적어도 하나의 집합 X에 속하는 원소 x들로 구성된 집합으로 정의한다.

 

2.We define the intersection of an abitrary family S of sets to be those elements x belonging to every set X in S 

-> 임의의 집합족 S의 교집합은 S 내의 모든 집합 X에 속하는 원소 x들로 구성된 집합으로 정의한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

Chapter 2 PBL Report

Team6

1.     1] Summary                                                            Final OK

        Summary

             Chapter

2 Proofs

Date

2018.03.16

 

             Type  

Writer

Title

Contents

        Summary

이세영

Final OK by SGLee summary : 2018.03.16 the Class-Lecture chapter 2 . Proof

2.1 Mathematical Systems, Direct Proofs, and

    Counterexamples

 

2.2 More Methods of Proof Problem-Solving Corner:

    Proving Some Properties of Real Numbers

 

2.3 Resolution Proofs (Skipped)

 

2.4 Mathematical Induction Problem-Solving Corner:

    Mathematical Induction

 

2.5 Strong Form of Induction and

    the Well-Ordering Property

 

#수학적 체계, 직접 증명 및 반례(Mathematical Systems, Direct proofs and Countereexamples)

 *What is "axioms,definition,theorem,lemma,corollary" is?

  =>axioms(공리) : 참이라고 간주

   definition(정의)

   theorem(정리) : 참이라고 증명된 명제

   lemma(보조정리) : 다른정리를 증명하는데 유용하게 사용

   corollary(따름증명) : 다른 정리로 부터 쉽게 얻어지는 정리

   proof(증명) : 정리가 참임을 확립하는 논법

 

*Direct Proofs

   : A direct proof assumes that the hypotheses are true and then, using the hypotheses as well as other axioms, definitions, and previously derived theormes, show directly that the conclusion is true

 


2.2 More Methods of Proof

 

Discuss several more methods of proof:

Proof by contradiction, Proof by contrapositive, Proof by cases, Proofs of equivalence, existence Proofs

 

#기타증명방법 : 실수 성질의 증명

 *proof by contradiction(모순에 의한 증명)

  : A proof by contradiction assumes that the hypotheses are true and that the conclusion is false and then, using the hypotheses and the nagated couclusion as well as other axioms, definitions, and previously derived theorems, derives a contradiction.

 *indirect proof(간접증명)

  : is another name for proof by contradiction

 *proof by contrapositive(대우에 의한 증명)

  :To proof p->q, proof not p -> not q

 *proof by cases(경우에 의한 증명)

 *proof of Equivalence(동치 증명)

  : Proof of equivalence shows that two or more statements are all true or all false.

 *existence proof(존재 증명)

 *constructive existence proof(건설적 존재 증명)

 

 

#분해 증명(Resolution proofs)

 

 

1 30 ~

 

#수학적 귀납법(mathmatical induction)

 

*What is mathmatical induction?

 =>S(1)is true

   for all n >= 1 , if S(n) is true, then S(n+1)is true

 

#강한 형식의 귀납법 및 정렬 순서 속성(Strong Form of Induction and the Well-Ordering Property)

  *Strong form of mathematical induction 

   : allows us to assume the truth of all of the preceding statements.

 

* Well-Ordering Property

 

The Well-Ordering Property for nonnegative integers states that every nonempty set of nonnegative integers has a least element.

         This property is equivalent to the two forms of induction.

 

  We use the Well-Ordering Property to prove something familiar from long division:

       divided by 

 is dividend,   is divisor,   is quotient,   is remainder,

Comment

이상구

summary : chapter 2 다른 학생이 조금 더 보충하고 이쁘게 하여 Final 선언 하세요^^

다른 학생이 조금 더 보충하고 이쁘게 하여 Final 선언 하세요^^

Final

강민석

summary : chapter 2 .Mr Kang 강민석 and 홍석호, added some on it

1. 수학적 체계는

 

공리(항상 참이라고 간주함), 정의, 미정의 용어로 구성된다.

 수학에서 중요한 것은 정리이다.

 

정리를 증명하기 위해서는 증명(proof)이라는 과정이 필요하다.

정리에서도 특이한 정리가 있는데, 그것은 보조정리(lemma), 따름정리(corollary)가 있다.

보조정리는 다른 정리를 증명하기 위해 필요한 도구이고

따름정리는 다른 정리로부터 쉽게 얻어지는 정리이다.

 

2. 증명의 종류

①직접 증명(direct proof)

 직접 증명은 명제p가 참이라 가정했을 때 공리, 정의 등을 이용하여 명제q가 참임을 직접적으로 증명하는 것이다.

②반증(disprove) 

 어떤 명제가 "모든 x에대해 P(x)가 참이다"라고 하자. 그 명제가 거짓인 것같으면

반례(counterexample) x하나만 찾으면 그 명제가 거짓임을 밝힐 수 있다.

③모순에 의한 증명(proof by contradiction) 

 pq를 증명하려 했는데 힘들다. 그러면 명제 r을 이용하여 모순임을 밝히면 된다.

논리적으로 따지자면 pq (p∧¬q)(r∧¬r), 이 둘이 동치이기 때문에 가능한 증명법이다.

모순에 의한 증명은 직접 증명보다 쉽다. 왜냐하면 도구가 하나 더 있기 때문이다.

직접증명은 도구 하나로 결론을 도출해야하는 반면 모순에 의한 증명은 두개로 결론을 도출할 수 있기때문이다.

이 증명에 대한 예시는 고등학교 때 배운 "2가 무리수이다"에 대한 증명이다.

④대우에 의한 증명(proof by contrapositive) 

 pq와 ¬q→¬p가 동치이므로 가능한 증명법이다.

예를 들어, "모든 실수x에 대해 x^2가 무리수이면 x는 무리수이다"를 증명할 때

직접증명은 까다롭다. 대신 무리수의 반대인 유리수의 정의를 알고 있기 때문에

대우인 "모든 실수x에 대해 x가 유리수이면 x^2은 유리수이다"로 증명하면 매우 쉬워진다.

⑤경우에 의한 증명(proof by case) 

 고등학교 때 배운 확률과 통계의 경우의 수와 비슷하다.

경우의 수를 나눌 때 케이스분류를 하듯이, 증명에 필요한 변수를 범위에 따라 나누어 각각 증명하면 된다.

가끔 변수의 크기가 작으면 모두 검사하여 증명할 수 있는데 이를 전수 증명(exhaustive proof)라고 한다.