그나저나 이번 여름 방학에는 뭐하지?

선대 공부할까? Coq 공부할까?

아니면 오토마타 같은 거 배울까?

람다-프롤로그 구현은 너무 어렵고 ...

사실은 영어 공부부터 해야 됨 ㅋㅋㅋ


수학 이야기: Hinman의 수리논리학 책에 있는 연습문제 1.3.20임.


Definition. A set of C of connectives is called adequate iff

every L-sentence is tautologically equivalent to a sentence

using only the connectives in C.

Proposition. The set {'∨', '∧', '→', '↔'} is not adequate.

Proof.

성질 P를, 문장 α에 대하여,

α의 모든 명제 변수에 진릿값을 1로 주면 α의 진릿값은 1로 평가된다는 걸

P(α)의 필요충분조건으로 둠으로써 정의하자.

이때 φ를, 주어진 4가지의 연결사로 만들어진 어떤 문장과 의미론적으로 동등한, 임의의 문장이라고 하자.

그러면 P(φ)이다.

하지만 P("￢p")이지 않다.

그러므로 주어진 4가지의 연결사로 만들어진 모든 문장은 "￢p"와 의미론적으로 동등한 문장이 아니다.

따라서 {'∨', '∧', '→', '↔'}은 adequate하지 않다.

■