이산수학: 논리 ②

목차

​

1. 논리와 명제

2. 단순명제와 합성명제

3. 논리연산자와 진리표

4. 역, 이, 대우

5. 항진명제와 모순명제

6. 동치

7. 추론

8. 술어논리

9. 변수의 명세와 한정화

6. 동치

두 명제 p, q의 쌍방조건이 항진명제이면 논리적 동치(logical equivalence)라하고, p↔q, p⇔q, p≡q라고 표시한다.

예로, 5와 2+3은 동치다.

6-1. 동치 관계식

작성은 하나 논리 연산자를 알고 있으면 굳이 볼 필요는 없다. 연산 흐름 따라가면 되기 때문이다.

분류	법칙 이름		동치 관계식	설명
기본	1. 멱등 법칙 Idempotent Laws		p ∨ p ≡ p p ∧ p ≡ p	동일 명제 반복 연산은 자기 자신
​	2. 교환 법칙 Commutative Laws		p ∨ q ≡ q ∨ p p ∧ q ≡ q ∧ p	순서 변경 가능
​	3. 결합 법칙 Associative Laws		(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)	결합 순서 변경 가능
​	4. 분배 법칙 Distributive Laws		p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)	괄호 전개 및 묶기
항등/부정	5. 부정 Negation Law		~T≡F ~F=T p∨(~p)≡T p∧(~p)≡F	부정
​	6. 이중 부정 Double Negation Law		~(~p) ≡ p	강한 긍정
​	7. 드 모르간 De Morgan's Laws		~(p ∨ q) ≡ ~p ∧ ~q ~(p ∧ q) ≡ ~p ∨ ~q	부정의 분배
​	8. 흡수 법칙 Absorption Laws		p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p	큰 범위가 작은 범위를 흡수
상수 관련	9. 항등 법칙 Identity Laws		p ∨ F ≡ p p ∧ T ≡ p	F와 OR, T와 AND는 자기 자신
​	10. 지배 법칙 Domination Laws		p ∨ T ≡ T p ∧ F ≡ F	T와 OR는 T, F와 AND는 F
​	11. 보완 법칙 Complement Laws		p ∨ ~p ≡ T p ∧ ~p ≡ F	자신과 부정을 연산한 결과
변형	12. 조건 변형 Conditional Disjunction		p → q ≡ ~p ∨ q	조건문을 OR식으로 변환
​	13. 대우 법칙 Contrapositive Law		p → q ≡ ~q → ~p	위치와 부정 변경
​	14. 쌍방조건 Biconditional Equivalence		p ↔ q ≡ (p → q) ∧ (q → p)	양방향 조건 분해

7. 추론

참인 명제로부터 새로운 명제가 참임을 이끌어내는 논리적인 과정을 추론(Argument)이라고 한다.

7-1. 유효추론과 허위추론

유효추론(valid argument)	주어진 전제가 참이고 결론도 참인 추론
허위추론(fallacious argument)	주어진 전제는 참이나 결론은 거짓인 추론

7-2. 추론 법칙

작성은 하나 충분히 생각할 수 있는 부분이라서 가볍게 읽고 넘어가도 된다.

(이름을 외울 필요까진 없다. 시험 안 보잖아요~)

법칙 이름	논리 기호 표현	설명
긍정 논법 (Modus Ponens)	p→q p ∴q	p이면 q이고 p가 참이면 q도 참이다.
부정 논법 (Modus Tollens)	p→q ~q ∴~p	p이면 q일 때 q가 거짓이면 p도 거짓이다.
조건삼단논법 (Hypothetical Syllogism)	p→q q→r ∴p→r	p면 q고 q면 r일 때 p면 r이다.
선언 삼단논법 (Disjunctive Syllogism)	p∨q ~p ∴q	p또는 q가 참인데 p가 거짓이면 q는 참이다.
단순화 법칙 (Simplification)	p∧q ∴p	p와 q가 모두 참이면 그중 하나인 p도 참이다.
결합 법칙 (Conjunction)	p q ∴p∧q	p가 참이고 q가 참이면 p와 q의 논리곱도 참이다.
부가 법칙 (Addition)	p ∴p∨q	p가 참이면 p또는 q는 무조건 참이다.
구성적 양도논법 (Constructive Dilemma)	(p→q)∧(r→s) p∨r ∴q∨s	p면 q고 r이면 s일 때, 두 조건문이 모두 참이고 p나 r이 참이면 q나 s도 참이다.

8. 술어논리

앞서 배운 논리에는 명제논리와 술어논리가 있다고 했다. 명제논리에서 만난 명제들은 참과 거짓이 명확했는데,

이번엔 참과 거짓이 명확하게 구분이 안되는 수식을 만나게 되었다.

x+2 = 9

라는 명제가 있을 때, 이 명제는 참인가 거짓인가?

우리는 이런 형태의 명제를 p(x)로 표시하고, p(x)를 변수 x에 대한 명제함수(Propositional Function)라 하고 명제논리(propositional logic)와 구분하여 술어논리(predicate logic)라고 부른다.

명제함수 p(x)는 무엇일까요? 명제술어는 한마디로 '빈칸이 있는 문장'이에요. - 일반 명제: "사과는 빨갛다." (누가 봐도 맞거나 틀린 확실한 문장) - 명제술어 (p(x)): "x는 빨갛다." 여기서 x는 비어 있는 빈칸과 같아요. 이 빈칸에 무엇을 넣느냐에 따라 이 문장이 참(맞는 말)이 될 수도 있고, 거짓(틀린 말)이 될 수도 있죠. - x에 '사과'를 넣으면: "사과는 빨갛다" → 정답(참)! - x에 '바나나'를 넣으면: "바나나는 빨갛다" → 땡(거짓)! 이렇게 안에 들어가는 재료(x)에 따라 맛이 결정되는 붕어빵 틀 같은 문장을 p(x)라고 부르는 거예요. - 명제 술어(propositional predicate)는 명제함수를 문법적인 관점에서 부르는 말이다.

9. 변수의 명세와 한정화

그래서 p(x)가 참인지 거짓인지 어떻게 구분할 것이냐.

​

9-1. 변수의 값을 적시

먼저 변수의 값을 적시하는 방법이 있다.

명제함수 p(x)가 x+2 = 4일 때, p(1)의 진리값은?

이런경우 변수의 값을 적시했고, False군요~할 수 있다.

​

9-2. 한정화

그리고 두번째는 한정화(quentification)를 통해 범위를 지정해서 구분할 수 있다.

9-2-1. 전체 한정자 ∀

전체 한정자(universal quantification)는 "모든"이란 의미를 가지며 ∀xp(x)와 같이 사용되고 "모든 x에 대하여 p(x)이다."라고 읽는다.

정의역의 모든 x에 대해서 p(x)가 참(T)임을 의미한다.

정의역(Domain)이란, 쉽게 말해서 '함수라는 기계에 넣을 수 있는 재료들의 꾸러미'를 말해요. 아까 설명한 붕어빵 틀(p(x)) 비유로 다시 이해해 볼까요? 붕어빵 틀 (p(x)): "x는 맛있다"라는 문장 넣을 수 있는 재료 (정의역): {팥, 슈크림, 피자, 초코} 여기서 재료 꾸러미인 {팥, 슈크림, 피자, 초코}가 바로 정의역이에요.

9-2-2. 존재 한정자 ∃

존재 한정자(Existential Quantification)는 값이 하나라도 만족하면 참이란 의미를 가지며 ∃xp(x)와 같이 사용되고 "어떤 x가 존재하여 p(x)이다."라고 읽는다.

정의역의 어떤 x에 대해서 p(x)가 참(T)임을 의미한다.

예제1. p(x)가 x=자연수이고 x의 정의역이 양수일 경우 ∀xp(x)의 진리값을 구하시오. ​ 예제2. p(x)가 x=자연수이고 x의 정의역이 실수일 경우 ∃xp(x)의 진리값을 구하시오. ​ 답. ① 참(T) ② 참(T)