Wabu대표(김형모) [403909] · MS 2012 (수정됨) · 쪽지

2020-05-23 13:41:10
조회수 1,411

컴공이 보는 논리학 2

게시글 주소: https://orbi.kr/00030259028

1편: https://orbi.kr/00030233091


컴퓨터공학 관점에서 본 기호논리학 정리

공학에 엄밀한 정의/증명은 필요없기 때문에 그냥 대충 썼음

동의하지 않는다면 수리과학부 대학원에 가서 학위를 따와라


1. 명제논리


1.2. 증명 (continued)


이전 편에서 정리 "p->p"를 증명하였다. 즉, 전제로부터 전제 자신을 증명할 수 있다.

이번에는 정리 "~p->p->q"를 증명해보자. 즉, 모순으로부터 모든 것을 증명할 수 있다.

까먹었을 테니 공리꼴과 추론 기법을 복붙하였다.


<명제논리의 공리꼴>

(1) 모든 명제 p, q에 대하여 "p->q->p"

(2) 모든 명제 p, q, r에 대하여 "(p->q->r)->(p->q)->(p->r)"

(3) 모든 명제 p, q에 대하여 "(~p->~q)->(q->p)"


<추론 규칙>

(1) [ T ⊢ p ] 이고 [ S ⊢ p->q ] 이면 [ T ∪ S ⊢ q ]이다.

(2) [ T ⊢ p->q ] 이면 [ T ∪ { p } ⊢ q ] 이고,  [ T ∪ { p } ⊢ q ] 이면 [ T ⊢ p->q ]이다.


공리꼴 (1)의 p, q에 각각 ~p, ~q를 대입하면

⊢ ~p->~q->~p

deduction principle에 의하여

~p ⊢ ~q->~p ... (a)

공리꼴 (3)의 p, q에 각각 q, p를 대입하면

⊢ (~q->~p)->(p->q) ... (b)

modus ponens에 의하여 (a+b)

~p ⊢ p->q

deduction principle에 의하여

⊢ ~p->p->q

Q.E.D.


지금까지 배운 내용을 모두 활용하여 정리 "((p->q)->p)->p"를 유도해보자.


증명은 전제 T = { p, ~p, (p->q)->p } 에서 출발한다. 여기서 p, q는 임의의 명제이다.

p, ~p, (p->q)->p ⊢

정리 "~p->p->q"에 의하여

p, ~p, (p->q)->p ⊢ ~p->p->q

deduction principle에 의하여

p, ~p, (p->q)->p ⊢ p->q

deduction principle에 의하여

p, ~p, (p->q)->p ⊢ q

deduction principle에 의하여

~p, (p->q)->p ⊢ p->q ... (a)

전제로부터 자기 자신을 증명할 수 있으므로

~p, (p->q)->p ⊢ (p->q)->p ... (b)

modus ponens에 의하여 (a+b)

~p, (p->q)->p ⊢ p

deduction principle에 의하여

(p->q)->p ⊢ ~p->p ... (c)

정리 "~p->p->q"의 q에 ~(~p->p)를 대입하면

(p->q)->p ⊢ ~p->p->~(~p->p) ... (d)

공리꼴 (2)의 p, q, r에 각각 ~p, p, ~(~p->p)를 대입하면

(p->q)->p ⊢ (~p->p->~(~p->p))->(~p->p)->(~p->~(~p->p)) ... (e)

modus ponens에 의하여 (d+e)

(p->q)->p ⊢ (~p->p)->(~p->~(~p->p))

deduction principle에 의하여

~p->p, (p->q)->p ⊢ ~p->~(~p->p) ... (f)

공리꼴 (3)의 q에 ~(~p->p)를 대입하면

~p->p, (p->q)->p ⊢ (~p->~(~p->p))->((~p->p)->p) ... (g)

modus ponens에 의하여 (f+g)

~p->p, (p->q)->p ⊢ (~p->p)->p

deduction principle에 의하여

~p->p, (p->q)->p ⊢ p

deduction principle에 의하여

(p->q)->p ⊢ (~p->p)->p ... (h)

modus ponens에 의하여 (c+h)

(p->q)->p ⊢ p

deduction principle에 의하여

⊢ ((p->q)->p)->p

Q.E.D.


이 정리의 이름은 peirce's law로, 공리꼴 (3) 대신 peirce's law를 공리꼴로 채택하면 공리계에 부정(~) 기호가 없는 동등한 논리 체계를 구성할 수 있다.


지금까지 확인한 정리 또는 공리

"p->p"

"p->q->p"

"(p->q->r)->(p->q)->(p->r)"

"((p->q)->p)->p"

는 각각 프로그래밍에 자주 이용되는 개념인 항등함수, 상수함수, 함수호출, 예외처리의 타입에 해당한다.

여기서 p, q, r이 임의의 명제라는 것은 임의의 타입이라는 것과 같아, 다형함수의 개념으로 이어진다.


숙제 1: 이중 부정 "p->~~p"와 "~~p->p"를 증명해보자.

숙제 2: 삼단 논법 "(p->q)->(q->r)->(p->r)"을 증명해보자.

숙제 3: 귀류법 "(~p->q)->(~p->~q)->p"를 증명해보자.

0 XDK (+2,500)

  1. 1,000

  2. 500

  3. 1,000