[논리학] 기초개념 정리

알고리즘 공부를 하던 중 생소하게도 논리학 개념을 접하게 되었습니다.

충분한 논리력이 뒷받침이 되지 않는다면 알고리즘 설명을 아무리 봐도 이해를 못하거나, 

코드를 정확하게 고치지 못하고 원하는 실행 결과가 나올 때까지 막연한 수정만 반복하는 함정에 빠질 수 있으므로

논리적으로 정확하게 확인하는 과정을 연습한다는 것이 학습의 취지입니다.

학습한 내용 및 구글링을 통해 배운 개념을 정리합니다.

 

 

---

 

논리 기호와 개념

F(Function) : '함수' / '개념'

 

∃(turned E) : '적어도 한 개가 존재한다'

- ∃x : "x가 존재한다" / "적어도 하나의 x가 존재한다"

- ∃xFx : "어떤 x가 F를 만족한다"

 

 

∀(turned A) : '모든 ~에 대하여'

- ∀x : "모든 x에 대하여"

- ∀xFx : "모든 x가 F를 만족한다"

 

 

￢ (not) : 부정

명제 앞에 붙이면 본래 명제와 반대의 진릿값(참/거짓)을 갖게 된다.

 

 

⊥ : 모순

- F→⊥ : 'F를 가정할 경우 모순이 생긴다'

 

 

p∧q : 'p and q', p와 q를 모두 충족한다.

- ∀x(Fx∧Gx) : 모든 x는 F와 G를 만족한다.

 

p∨q : 'p or q', p 또는 q를 충족한다.

 

p≡q : p와 q는 동치equivalent이다. (p와 q의 진릿값이 서로 같다)

 

역, 이, 대우 :

p → q 라는 조건문에 대해

- 역(connverse) : q → p

- 이(inverse) : ￢p → ￢q

- 대우 (contrapositive) : ￢q → ￢p

 

---

 

 

 

명제식 p → q의 참 / 거짓

1. 전건 p가 항상 거짓이면, 명제식 p → q는 무조건 참이다.

예컨대 어머니가 아들에게 '전교 1등을 하면 → 용돈 백만 원을 주겠다'는 말을 했다고 생각해 봅시다.

상식선에서 보면 아무리 봐도 진짜로 백만 원을 줄 것 같진 않기 때문에 어머니가 참말을 했다고 생각되진 않습니다.

 

이 때 아들이 한 번도 전교 1등을 하지 못했다면, 

어머니가 한 말이 참말인지 거짓말인지는 검증할 방법이 없으니까 '알 수 없다'고 생각하는 게 보통일 텐데,

논리학에서는 의외로 어머니가 '참말'을 했다고 간주하는 모양입니다.
'거짓말은 하지 않았다'는 걸까요.

 

'논리학'인 만큼 이것이 단순한 약속이라기보단 뭔가 명확한 증명이 있을 것 같은데,

그런 증명이 있는지는 따로 찾아봐야겠습니다.

 

 

2. 후건 q가 항상 참이면, 명제식 p → q는 무조건 참이다.

1) 1 + 1 = 3이라면, 2는 짝수이다.

2) 1000 < 10일 때, 3 * 3  = 9다. 

 

위와 같이 전건이 명백히 거짓이더라도, 후건이 명백히 참이라면 명제식은 항상 참이라고 합니다.

 

 

---

 

명제식 변형

2중 부정법:     $∼(∼p)≡p$

교환법칙:       $p∧q≡q∧p$,   $p∨q≡q∨p$

멱등법칙:       $p∧p≡p$,     $p∨p≡p$

대우법칙:       $(p→q) ≡ (∼q→∼p)$

 

드 모르간의 법칙(De Morgan's laws)

$∼(p∧q)≡∼p∨∼q$,

$∼(p∨q)≡∼p∧∼q$

 

 

결합법칙:

$(p∨q)∨r≡p∨(q∨r),$

$(p∧q)∧r≡p∧(q∧r)$

 

분배법칙:

$p∧(q∨r)≡(p∧q)∨(p∧r)$

$p∨(q∧r)≡ (p∨q)∧(p∨r)$

 

 

---

 

진리표

명제식에 대해 각 명제의 진릿값을 나타낸 표를 말합니다.

 

[예시] $p∧q$의 진리표 :

 

p	q	p∧q
T	T	T
T	F	F
F	T	F
F	F	F

 

 

---

 

 

수학적 귀납법

P(1)이 참이고, 명제식 P(n) → P(n+1)이 참임을 보임으로써 명제 P(n)은 모든 자연수 n에 대해 참임을 증명하는 것

 

귀류법

참/거짓밖에 존재하지 않는 명제에 대해, 명제를 부정했을 경우 모순이 발생한다는 것을 찾아내어, 명제가 참임을 증명하는 것

 

        

 

수학적 귀납법과 귀류법은 예제를 충분히 풀고 나면 별도 포스팅으로 다뤄보도록 하겠습니다.

 

 

 

[참고자료]

http://sjoh.hannam.ac.kr/Science/proof/index.html

명제의 증명

'명제식 변형'과 관련하여 참고한 자료지만 명제의 역에 대한 설명이 틀리게 나와있는 것 같습니다.