[ 이산 수학 ] 4. premises ( 전제 )

전제를 2가지 설정해보자

 

1. '모든 남자는 호전적이다.'
2. '소크라테스는 남자이다'

이 두 가지 전제가 참이라고 했을 때 

" 소크라테스는 호전적이다 " 라고 할 수 있을까?

 

여러 전제가 참일 때 우리는 새로운 결과를 어떻게 도출해낼 수 있을까 ? 가 이번 챕터의 시작이다.

 

위 예시를 식으로 바꾸면 아래와 같다.

 

 

ㅡㅡㅡㅡ막대선을 기준으로 위가 전제, 아래가 결론으로 나뉜다.

 

 

---

논증                                   = 명제의 연속

그 결과로 나오는 것           = 결론

 

 

Tautology = 항상 참이 되는 명제 (라는 뜻)

 

---

(예시1)

결론을 제외한 나머지들을 뜯어서 하나하나 보아야 한다.

 

재료로는 1) P ,  2) P → Q가 있다.

이 두 가지가 참이면 Q도 참이 된다는 것을 정리해보면

이런 형태가 나온다.

 

참고로 → 이거는 P → Q일 땐, if P, then Q라고 해석하면 된다.

---

이거도 풀어보기

 

 

---

그 밑에 글들이랑 같이 엮어서 예시들은 다 숙지할 수 있도록 하기

---

지금까지 우리가 했던 것은 " 추론 " 이다.

추론은 참인 명제들을 바탕으로 새로운 명제가 참인 것을 나타내는 것임.

 

•    부당한 논증
    : 전제 조건이 참인데, 결론은 참이 아닐 때

대표적인 예

 

---

기본적인 추론 법칙

 

☑️ 긍정 법칙(modus ponens) : p가 참, p→ q 도 참   = > q도 참

  이유) p->q 일 때, p가 참이면, 그 명제에 참 거짓은 q에 달려있는데, p도 참이고, q도 참이라 해 

 

☑️ 부정 법칙(modus tollens) : ~q (참)  / p→ q (참)    => ~p 도 참

   이유) 우선 뒤에 명제부터 대우로 돌려보자. ~q → ~p 도 참

     여기에서 ~q가 참이라는 재료가 있기 때문에, 해당 결과는 ~p에 따라가는데 이것도 참이어야 한다~!

 

 

☑️ 조건 삼단 법칙(hypothetical) : p → q (참)  /  q→r (참) 이면,  p→r도 참이다.

 

☑️선언 삼단 법칙(disjunctive) : p or q (참) / ~p도 참 이면, q는 참

   이유) ~p가 참이라 했으니, p or q = F or q이다. 근데 이게 참이면 q는 참

 

 

☑️양도 법칙(constructive)

p와 r이 참인 경우를 나누어서 생각해보자.

i) p가 참일 때 : q가 참이어야함

ii) r이 참일 때 : s가 참이어야함

iii) p와 r 모두 참일 때 : q,s 모두  참이어야함

 

 

☑️파괴적 법칙(deconstructive)

두 번째 참인 명제에 드모르간 법칙을 이용한다.

~(q and s) = T   // q and s = F  즉, q와s 둘 다 참인 경우는 없다.

경우의 수를 따져보자

 

i) q가 거짓일 때 : p → q 가 참이어야 하므로, q가 거짓일 땐 p가 F가 되어야 한다.

ii) s가 거짓일 때 : r → s 가 참이어야 하므로, s가 거짓일 땐, r이 F이어야 한다.

ii) q s 모두 거짓일 때 : p와 r 모두 F여야 한다.

 

 

☑️선접 법칙 (disjunctive addtion) : 한 명제가 참이면, 다른 명제와 or 한 명제도 참이다.

 

☑️분리 법칙(simplication)         : 두 명제를 and한 것이 참  → 각각의 명제도 참 

☑️연접 법칙(conjuntion = and ) : 각각의 명제가 참  → 두 명제를 and한 것도 참 

 

 

 

 

 

---

 

UI

:모든 x에 대해 P(x)가 참이면

임의의 c에 대한 P(c)도 참이다.

 

UG

: 그 반대도 가능함. 임의의 c에 대해 P(c)가 참이면, 모든 x에 대한 P(x)도 참

 

 

EI

: P(x)를 만족하는 x가 있으면

P(c)를 만족하는 C도 있다. 

 

EG

: P(c)를 만족하는 C가 있으면

 P(x)를 만족하는 x가 있다.

 

 

위 조건을 이용하여 풀이해봐라

 

---

Theorems

p → q

 

• 공허한=무의미한 증명(vacous proof)
  : p가 거짓이면 p->q가 참임으로 
     p가 거짓임을 보여 p->q를 증명.
  
  
  
• 자명한 증명 (Trivial proof)
  :  만약 우리가 q가 참인 것을 알고 있다면, p에 관계없이  p → q 도 참이다
  
  
  
• 직접 증명 (Direct proof)
  p가 참이라고 가정하고 진행
  p가 참일 때, q도 참인 것을 증명
  
  
• 대우를 통한 증명 (Proof by Contraposition)
  ~q → ~p 를 이용한다.
  ~q가 참일 때 ~p가 참임을 보여 p->q 참임을 증명
  
  (직접 증명과 대우를 통한 증명은 주로 n이 짝수/홀수 일 때, @@n +a 은 짝수/홀수 이다. 문제 풀 때 쓰임)
  
  
• 모순에 의한 증명 (Proof by Contradiction) = 귀류법
  p → q에서 조건 명제를 바꾸어﹁p → q 가 참이 아닌 것을 증명하여 명제 p가 참임을 보이는 증명.
   
  주어진 가정(p)을 부정(false)했을 때 항상 false가 되는 명제 q가 있음을 보이면, p의 가정이 잘못되었으므로 p는 true가 된다.
  
  간단히 말하면 조건명제만 부정하여 이게 참이 안 된다는 걸 보여주면 된다.
  
  예) 달력에서 22일을 선택했을 떄, 적어도 4일은 같은 요일에 해당한다
  풀이) 우선 위 명제를 p라고 했을 때, ~p가 참이 된다. 왜냐하면 일주일은 7개의 요일이 있는데, 22개를 뽑았을 때
  하루를 제외하고 나머지는 3일이 있기 때문이다.
  
  예) 귀류법을 사용하여 루트2가 무리수임을 증명하라.
  풀이) 루트 2가 유리수라고 가정하고 유리수로 만들어서 식을 전개해본다.
   주어진 가정(p)을 부정(false)했을 때 항상 false가 되는 명제 q가 있음을 보이면, p의 가정이 잘못되었으므로 p는 true가 된다.
  

---

필요 충분 조건

p→ q 도 되고 q→ p도 되는 상태

 

---

일반성을 잃지 않고(without loss of generality)
: 일반성 있는 한 경우에 대해 증명함으로써, 다른 경우들을 추가적으로 증명할 필요가 없음을 의미한다.

 

존재 증명

: 생산적 증명 = 한 명제 P(c)에 대해, 참인 c가 하나만 있어도 Ex P(x)가 존재한다.고 할 수 있

 위에 개 빡센 조건을 충족하는 게 하나라도 있으면 참 ㅇㅇ

 

 

비생산적 증명

: 생산적 증명 + 귀류법

 

예) x^y가 유리수가 되게 하는 두 무리수 x와 y를 구하여라

증명 ) 루트2는 무리수,

위와 같은 수를 생각해보자, 이게 유리수라고 가정함.

저렇게 x와 y 둘 다 루트 2.

근데 결과가 유리수가 안 됨.. 도저히 안 됨

(교수님한테 질문, 처음부터 루트2의 루트2제곱 하면 안되나?)

 

그래서 위에 사진 저거 하나를 x, 루트 2를 y로 놓고 계산해봤을 때는 결과가 2, 유리수가 나옴

 

유일성 증명(uniqueness proof)

: 유일하게 하나의 값 ( 요소 ) 만이 주어진 특성을 만족하는 경우

 

존재성: x가 주어진 특성을 갖고 있음을 보인다.

유일성: y≠x면 y는 주어진 특성을 갖지 않음을 보인다. 
∃x(P(x)∧∀y(y≠x->﹁P(y)))임을 증명
= 어느 x는 되고, 모든 y는 P()가 안 된다는 걸 증명 

 

존재성을 띈 후에야 유일성 판단 가능 (당연함) 있어야 유일한지 알 수 있음.

 

 

 

 

전향추론과 후향추론(forward and backward reasoning): 
가정에서 결론으로 도달하거나 결론이 나게하는 전단계를 찾아가느냐

 

(출처)

https://laurent.tistory.com/entry/%EC%9D%B4%EC%82%B0%EC%88%98%ED%95%99-%EC%B6%94%EB%A1%A0-argument

여기도 짱
https://www.youtube.com/watch?v=u8LBVQ-h9cY&list=PLTnkH9H3NaqWdYFAki1VDaze2dlbCPllu&index=4

증명 파트 간단 요약
http://gentleandkindness.blogspot.com/2015/05/1_28.html

증명

https://slidesplayer.org/slide/16168702/