수리논리학 특강(1)

[mathmania]

 

제 1 강 명제와 논리

(1) 명제: 참, 거짓을 분명하게 판별할 수 있는 문장이나 식

명제들은 여러 가지 방법으로 결합해서 새로운 명제를 형성할 수 있다.

기호 논리학에서는 명제들의 기본적인 결합을 적절한 기호를 사용해서 표현한다. 이를 위해 다음의 다섯 가지 기호를 사용한다.

① p∧q('p이고 q이다'라고 읽는다)는 p와 q가 모두 참일 때 그리고 이 때에만 참인 명제를 나타낸다. 이런 꼴의 명제를 합접(conjunction) 명제라고한다.

② p∨q('p이거나 q이다'라고 읽는다)는 두 명제 p와 q 중 적어도 하나가 참일 때 그리고 이 때에만 참인 명제를 나타낸다. 이런 꼴의 명제를 이접(disjunction) 명제라고 한다.

③ p→q('p이면 q이다'라고 읽는다)는 p가 참이고 q가 거짓일 때 그리고 이때에만 거짓인 명제를 나타낸다. 이런 꼴의 명제를 조건 또는 함의(implication) 명제라고 한다.

④ p↔q('p이기 위한 필요충분조건은 q이다'라고 읽는다)는 p와 q가 모두 참이거나 모두 거짓일 때 그리고 이 때에만 참인 명제를 나타낸다.

따라서 명제 p↔q는 p와 q가 똑같은 진리값을 갖는다는 사실을 의미한다. 이런 꼴의 명제를 동치(equivalence) 명제라고 한다.

⑤ ~p('p가 아니다'라고 읽는다)는 p의 부정 또는 모순을 나타낸다.

즉, ~p는 p가 거짓일 때 참이고 p가 참일 때 거짓인 명제를 나타낸다. 이런 꼴의 명제를 부정(negation) 명제라고 한다.

(2) 정의

합접
p	q	p∧q
T	T	T
T	F	F
F	T	F
F	F	F

  

이접
p	q	p∨q
T	T	T
T	F	T
F	T	T
F	F	F

  

함의
p	q	p→q
T	T	T
T	F	F
F	T	T
F	F	T

동치
p	q	p↔q
T	T	T
T	F	F
F	T	F
F	F	T

  

부정
p	~p
T	F
F	T

전칭명제: “모든~”으로 시작하는 명제, ∀

존재명제: “어떤~”으로 시작하는 명제, ∃

항진명제: 항상 진리값이 참인 명제, t

모순명제: 항상 진리값이 거짓인 명제. c

(3) 정리

(쌍대의 원리:①~⑧, Bool대수:①~⑫)

① 반사율(동일률): p≡p

② 이중부정의 법칙: ~(~p)≡p

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

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

⑤ 결합법칙: (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∧(p∨q)≡p, p∨(p∧q)≡p

⑧ 드 모르간의 법칙: ~(p∧q)≡~p∨~q, ~(p∨q)≡~p∧~q

⑨ p∧~p≡c, p∨~p≡t

⑩ p∧t≡p, p∨c≡p

⑪ p∧c≡c, p∨t≡t

⑫ ~t≡c, ~c≡t