[how to prove it] 0.intro ~ 1장 일부
- 구조화된 프로그래밍이란? 차례로 나열하는 것이 아니라, if-else, do-while 같은 기본 구조를 결합하여 프로그래밍하는 것
- 들여쓰기의 사용도 그 예시가 될 수 있다.
- 수학적인 증명또한 이러한 기본 증명 구조를 결합하여 구성한다. 기본 구조들을 중첩한다.(수학자들은 들여쓰기를 하지는 않는다.)
- 어떤 증명 구조를 사용할 것인지는 필요한 논리 형식에 따라 결정된다.
- 따라서 이 책은 수학 문장에 취하는 다양한 형태를 친숙하게 만들기 위한 목표를 가진다.
- 1,2 장: 집합론
- 3장: 수학적 진술이 취할 수 있는 다양한 형태와 각 형태에 적합한 증명구조
- 4장, 5장: 3장 내용을 연습
- 6장: 수학적 귀납법
- 7장: 지금까지 배운 것들의 종합
- 수학자들은 항상 연역을 사용함
- 연역을 이용하여 추론하고, 정리하는 과정을 보여줌
- 수학과 관련된 흥미로운 내용을 제시함
-
- 완전수
- 예를 들어, 6을 나누는 6보다 작은 양의 정수는 1, 2, 3이고, 1 + 2 + 3 = 6이다. 그러므로 6은 완벽한 숫자이다. 그 다음으로 작은 완전수는 28이다.
-
- 솎아지는 소수
- 무한히 많은 소수가 있지만, 소수는 우리가 점점 더 큰 수를 볼 때 솎아진다. 예를 들어, 1과 100 사이의 소수는 25개이고, 1000과 1100 사이의 소수는 16개이며, 1,000,000과 1,000,100 사이의 소수는 6개뿐이다.
증명과 연역적 추론은 수학에서 중요한 역할을 한다.(기초)
-
연역적 추론의 예시를 들어 설명해줌
-
전제라고 불리는 다른 추론들이 진실이라고 가정할 때 결론을 도출할 수 있음
-
하나의 전제가 false로 밝혀지면 결론은 거짓이 됨
-
앞으로 몇 장에 걸쳐서 추론의 키워드가 되는 몇가지 단어들에 대해서 학습할 것임
-
이 장에서는 복잡한 statements를 만들기 위해서 statements를 합치는데 사용하는 words들을 살펴볼 것
- 모호하지 않은 true이거나 false인 statements들에 한해서 살펴볼 것 이다.
- 연결기호
논리합 or (disjunction) ∨ 논리곱 and (conjunction) ∧ 부정 not ￢
- 존이 슈퍼에 가지 않으면 계란이 없어 존이 슈퍼에 간다 => P 계란이 없어 => Q 둘 중에 하나가 참 => or
P ∨ Q
- 조는 집을 떠나서 돌아오지 않을거야 조가 집을 떠남 => P 돌아오지 않음 => Q
P ∧ Q
그런데 Q가 부정을 포함하고 있으므로 돌아옴(부정형을 뺀 statement) => R
P ∧ ￢R 이렇게 쓰는 것이 더 나은 표현임
- 빌이 사무실에 있고 제인이 없거나, 반대로 제인이 사무실에 있고 빌이 없어 빌이 사무실에 있음 => B 제인이 사무실에 있음 => J
(B ∧ ￢J) ∨ (J ∧ ￢B)
- 여기서 괄호를 사용하는 것은 대수학의 관습을 따르는 것이다.
- (존은 멍청하지 않다 and 존은 게으르다) or 존은 멍청하다. 존은 게으르지만 멍청하지 않거나, 혹은 멍청하다.
- 존은 멍청하지 않다 and (존은 게으르다 or 존은 멍청하다) 존은 멍청하지 않고, 존은 게으르거나 멍청하다
- not(존은 멍청하다 그리고 게으르다) or 존은 멍청하다. 존은 멍청하지 않고 게으르지 않다. 혹은 존은 멍청하다.
// For example 부터 시작
-
위의 1.1.2와 1.1.3에서 쓰인 표현은 문법적으로 맞는 표현이다.
- well-formed formulas, formulas라고 부름
- 제대로 쓰일때만 의미가 있는 표현이다.(순서와 위치를 지킬때)
-
가끔 논리적인 단어들은 수학적인 표기법안에 숨어있다.
-
≤===(3 < π) ∨ (3 = π)
-
a.
읽기 과제가 생길 것이다 => P
문제푸는 숙제가 새길 것이다. => Q
둘 중에 하나가 생긴다 => P or Q => P ∨ Q
문제푸는 숙제와 테스트가 둘다 생기지는 않는다.
문제 푸는 숙제 => Q
테스트 => R
Q or R => Q ∨ R
(P ∨ Q) ∧ (Q ∨ R)
b.
스키타러 간다 => P
눈이 있다 => Q
스키타러 가면 눈이 하나도 없다 => P ∧ ￢Q
￢P ∨ (P ∧ ￢Q)
c.
!(√7은 2보다 작거나 같다)
√7은 2보다 작지 않고 2와 같지 않다.
￢(√7 < 2) ∧ ￢(√7 = 2)
a.
존은 진실을 말한다 => J
빌은 진실을 말한다 => B
(J ∨ B) ∨ ￢(J ∧ B)
b.
생선을 먹겠다 => F
치킨을 먹겠다 => C
메쉬드 포테이토를 먹겠다 => P
(F ∨ C) ∧ ￢(C ∧ P)
c.
3이 6의 공약수이다. => P
3이 9의 공약수이다. => Q
3이 15의 공약수이다. => R
P ∧ Q ∧ R
Alice가 방에 있다. => A
Bob이 방에 있다. => B
a. (A ∧ ￢B) ∨ (￢A ∧ B) b. ￢(A ∧ B) c. ￢A ∨ ￢B d. ￢(A ∧ B)
a, c
바지를 살거야 => P
셔츠를 살거야 => S
a. 바지를 사지 않고 셔츠를 사겠어 b. 셔츠도 사지 않고 바지도 사지 않겠어 c. 셔츠를 사지 않거나 바지를 사지 않겠어
스티브는 행복해 => S
죠지는 행복해 => G
a. 둘 중에 한명이 행복하고, 둘 중에 한명이 행복하지 않아 b. 스티브가 행복하거나 스티브가 불행하고 죠지가 행복해. 혹은 죠지가 행복하지 않아 c. 스티브가 행복하거나, 죠지가 행복하고 둘 중에 한명이 불행해
a. pete가 둘 중에 한 대회에서 상을 타는데, math prize에서 jane과 함께 상을 탈 수 없으므로 맞는 추론이다. b. 틀린 추론이다. fish랑 corn을 같이 안먹겠다고 한것과 관계없는 추론 c. 존과 빌 둘 중에 한명이 진실을 말한다. 샘과 빌 둘 중에 한명이 거짓을 말한다.
경우의 수
1. 빌 거짓, 존 진실 => 빌 거짓, 샘 진실
2. 빌 진실, 존 거짓 => 빌 진실, 샘 거짓
존이 진실(1)이거나 샘이 거짓(2)이다 => 맞는 추론
d. 판매가 증가하면 상사가 행복하다. 비용이 증가하면 상사는 행복하지 않다. 그래서 판매와 비용이 둘다 증가할 수는 없다는 맞는 추론이다. 왜냐면 둘중에 하나만 성립할 수 있기 때문에
and, or, not이 어떻게 주장의 유효성에 영향을 미치는가? truth value => true, false
∧ => AND 게이트, 논리곱 : 둘다 1일때만 1 ￢ => NOT 게이트: 입력의 반대가 출력 ∨ => OR 게이트, 논리합 : 둘 중에 하나만 1이어도 1
- XOR 게이트: 1의 개수가 홀수 일때만 1(그 반대는 XNOR)
1.2.2 연습
P | Q | R | P ∧ Q | ¬(P ∧ Q) | ¬R | ¬(P ∧ Q) ∨ ¬R
--+---+---+-------+----------+----+---------------
0 | 0 | 0 | 0 | 1 | 1 | 1
0 | 0 | 1 | 0 | 1 | 0 | 1
0 | 1 | 0 | 0 | 1 | 1 | 1
(...)
-
테이블의 길이는 경우의 수 만큼 길어진다.
- P, Q, R => 2 * 2 * 2
- 2의 n제곱?
-
더 컴팩트하게 만들수도 있다.
셋다 참일때의 예시
step
¬(P ∧ Q) ∨ ¬R
1. 1 1 1
2. 1 0
3. 0 0
4. 0
합치면 0111001 이런 형태의 테이블 row 한 줄 나온다.
-
이제 테이블을 만들 줄 아니까 주장의 유효성을 분석해보자
- 결론이 참이 아닌 이상 모든 부분(premises)가 true일 수는 없다.
- 모든 부분이 True라면 그 주장은 유효하다고 볼 수 있다.
-
만약에 결론이 참이 아닌데 모든 premises가 참인 row가 있다면 그 주장은 유효하지 않다.
-
premises가 모두 참인 row에서 conclusion가 true라면, 그 주장은 유효하다.
1.2.3
버틀러는 무죄다 => B
쿡은 무죄다 => C
버틀러가 거짓말을 한다 => L
￢(B ∧ C)
L ∨ C
--------------
∴ L ∨ ￢B
1.2.4 같은 포뮬라 찾기
P=1 Q=1 P=0 Q=1 P=1 Q=0 P=0 Q=0
¬(P ∧ Q) 0 1 1 1 => 동시에 true일 수 없음
¬P ∧ ¬Q 0 0 0 1
¬P ∨ ¬Q 0 1 1 1 => 둘 중에 하나는 무조건 false임
===> DeMorgan’s laws
¬(P ∧ Q) is equivalent to ¬P ∨ ¬Q.
¬(P ∨ Q) is equivalent to ¬P ∧ ¬Q.
=> NOT이 붙은 괄호를 전개할 때는 OR/AND를 뒤집으면 같다.
P ∧ Q is equivalent to Q ∧ P.
P ∨ Q is equivalent to Q ∨ P
=> 순서를 바꿔도 같다
P ∧ (Q ∧ R) is equivalent to (P ∧ Q) ∧ R.
P ∨ (Q ∨ R) is equivalent to (P ∨ Q) ∨ R.
=> OR만 연달아 있거나 AND만 연달아 있을때는 괄호가 의미 없다.
P ∧ P is equivalent to P.
P ∨ P is equivalent to P.
=> 같은 걸 OR/AND 연산하면 원본과 같다.
P ∧ (Q ∨ R) is equivalent to (P ∧ Q) ∨ (P ∧ R).
P ∨ (Q ∧ R) is equivalent to (P ∨ Q) ∧ (P ∨ R).
=> OR/AND 연산자의 전개시 각 요소를 바깥에 있는 연산자와 연산한 것을 괄호 안의 연산자로 연산한다.
P ∨ (P ∧ Q) is equivalent to P.
P ∧ (P ∨ Q) is equivalent to P.
=> 같은 요소로 AND 연산, OR 연산을 각 한번씩 거치면 원본과 같다
¬¬P is equivalent to P.
1.2.5 포뮬라 다듬기
- ￢P ∧ Q
- ￢Q ∨ P
- tautologies: P ∨ ￢P
- contradictions: P ∧ ￢P
1.2.6 tautologies, contradictions 찾기
P ∨ (Q ∨ ¬P) => (P ∨ Q) ∨ (P ∨ ￢P) => (P ∨ ￢P)가 무조건 true => 결론은 무조건 true => tautology
P ∧ ¬(Q ∨ ¬Q) => ¬(Q ∨ ¬Q) 이 부분이 무조건 false => P에 관계없이 결론은 무조건 false => contradiction
P ∨ ¬(Q ∨ ¬Q) => 그냥 P와 같다.
1.2.7 포뮬라 단순화
- P ∨ (Q ∧ ¬P) => (P ∨ Q)
- ¬(P ∨ (Q ∧ ¬R)) ∧ Q => ¬P ∧ (￢Q ∨ R) ∧ Q => ¬P ∧ ((￢Q ∨ R) ∧ Q) => ¬P ∧ ((￢Q ∧ Q) ∨ (R ∧ Q))) => ¬P ∧ R ∧ Q
Exercises
1, 2 truth tables 만들기
1.
(a) ¬P ∨ Q.
P Q ¬P ¬P ∨ Q
--------------------
0 0 1 1
0 1 1 1
1 0 0 0
1 1 0 1
(b) S G (S ∨ G) ∧ (¬S ∨ ¬G)
----------------------------
0 0 0 0 0 0 1 1 1
0 1 0 1 1 1 1 1 0
1 0 1 1 0 1 0 1 1
1 1 1 1 1 0 0 0 0
2.
(a) P Q ¬[P ∧ (Q ∨ ¬P)]
-------------------------
0 0 1 0 0 (0 1 10) => 1
0 1 1 0 0 (1 1 10) => 1
1 0 1 1 0 (0 0 01) => 1
1 1 0 1 1 (1 1 01) => 0
(b) P Q R (P ∨ Q) ∧ (¬P ∨ R)
------------------------------------
0 0 0 (0 0 0) 0 (10 1 0) => 0
1 0 0 (1 0 0) 0 (01 0 0) => 0
0 1 0 (0 1 1) 1 (10 1 0) => 1
0 0 1 (0 0 0) 0 (10 1 1) => 0
1 1 0 (1 1 1) 0 (01 0 0) => 0
0 1 1 (0 1 1) 1 (10 1 1) => 1
1 0 1 (1 1 0) 1 (01 1 1) => 1
1 1 1 (1 1 1) 1 (01 1 1) => 1
- XOR 테이블 => 1이 홀수 일때만 true
P Q =
-------
0 0 0
1 0 1
0 1 1
1 1 0
* ∧/∨/¬로 나타내기
(P ∧ ￢Q) ∨ (￢P ∧ Q)
* 같은지 table그려서 증명하기
P Q (P ∧ ￢Q) (￢P ∧ Q) (P ∧ ￢Q) ∨ (￢P ∧ Q)
----------------------------------------------
0 0 0 0 0
1 0 1 0 1
0 1 0 1 1
1 1 0 0 0