[이산수학]2강 논리
[출처] 방송통신대학교 이산수학 강의 정리
학습 목표
- 명제와 명제가 아닌 것을 구분할 수 있다.
- 다양한 논리연산자의 역할을 이해하고 합성명제의 진리값을 판별할 수 있다.
- 조건명제와 쌍조건명제를 구분하고 진리값을 찾아낼 수 있다.
- 서로 다른 두 명제의 논리적 동치 여부를 판별할 수 있다.
- 추론규칙 또는 벤 다이어그램을 이용하여 타당한 추론을 판별할 수 있다.
2.1 명제(Proposition)
- 참과 거짓을 구별할 수 있는 문장이나 수학적 식
- 명제의 진리값
- 참 true, 거짓 false
- 명제의 종류
- 합성명제 (and, or) : 하나 이상의 명제와 논리연산자 그리고 괄호로 이루어진 명제
- 조건명제, 쌍조건명제
- 항진명제, 모순명제
- 예제) 다음 문장이 명제인지 아닌지 구분하시오.
1) 철수는 영희보다 키가 작다. (명제)
2) 철수는 공부를 잘 한다. (x)
3) 73+2 = 76 (명제)
4) x + 1 = 0 (x의 값에 따라 침일 수도 있고 , 거짓 일 수도 있다. 그런데 명제는 아니다 (명제함수라고함)
2.2 논리 연산
- 실수집합(상수, 변수등)
- 실수연산(+,-,*,/)
- 수식 : 실수집합과 실수연산을 사용하여 표현한 식
- 논리 상수 : T, F
- 논리 변수 : p, q, r
- 논리 연산의 종류
- 논리곱 (AND; ∧) 둘다 참일때만 참 나머진 거짓
- 논리합 (OR; ∨) 둘다 참, 둘중에 하나 참 일떄 참
- 부정 논리곱 (NAND; ↑)
- 부정 논리합 (NOR; ↓)
- 배타적 논리합 (XOR; ⊕) p ⊕ q : p와 q가 참일떄 거짓 , p와 q가 거짓일때 거짓 나머진 참
- 동치 (EQV; =)
- 조건 명제(conditional proposition)
- 명제 p와 q가 있을 때, 명제 p가 조건의 역할을 수행하고 명제 q가 결론의 역할을 수행하는 경우
- p -> q ( p => q)
- 조건절이 참이고 결론이 거짓이면 거짓 나머지는 참
- 쌍조건 명제(conditional proposition)
- 명제 p와 q가 있을때, 명제 p와 q가 조건의 역할과 결론의 역할을 동시에 수행하는 경우
- p <-> q
- 논리적 동치 (logical equivalence, ≡)
- p ↔ q ( p <=>q, p = q, p ≡ q)
- 두 명제 p와 q가 논리적으로 동등하면 논리적 동치라고 하고, p ≡ q로 표시한다.
- 논리적으로 동등하다는 말은 두 명제가 항상 동일한 진리값을 가진다는 의미
- 조건 명제 p -> q
- 역 (converse) : q -> p
- 이 (inverse) : ~p -> ~q
- 대우 (contrapositive) : ~q -> ~p
논리적 동치법칙
1) 교환법칙 (commutation law)
- p ∨ q ≡ q ∨ p
- p ∧ q ≡ q ∧ p
- p ↔ q ≡ q ↔ p
2) 결합법칙 (associative law)
- (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
- (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
3) 분배법칙 (distributive law)
- p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
- p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
4) 항등법칙 (identity law)
- p ∨ F ≡ p
- p ∧ T ≡ p
5) 지배법칙 (domination law)
- p ∨ T ≡ T
- p ∧ F ≡ F
6) 부정법칙 (negation law)
- ~T ≡ F
- ~F ≡ T
- p ∨ ( ~p ) ≡ T
- p ∧ ( ~p ) ≡ F
7) 이중 부정 법칙(double negation law)
- ~(~ p) ≡ p
8) 멱등법칙 (idempotent law)
- p ∨ p ≡ p
- p ∧ p ≡ p
9) 드 모르간 법칙(de Morgan`s law)
- ~(p ∨ q) ≡ (~p) ∧ (~q)
- ~(p ∧ q) ≡ (~p) ∨ (~q)
10) 흡수법칙 (absorption law)
- p ∨ (p ∧ q) ≡ p
- p ∧ (p ∨ q) ≡ p
11) 함축법칙 (implication law)
- p → q ≡ ~p ∨ q
12) 대우법칙
- p → q ≡ ~q → ~p
항진명제(tautology)와 모순명제(contradiction)
- 합성명제를 구성하는 명제의 진리값과 상관없이
1) 항상 참(T)인 명제를 항진명제라고 함.
2) 항상 거짓(F)인 명제를 모순명제라고 함.
- 논리 (logic)
- 명제논리 (proposition logic)
- 명제
- 술어논리 (predicate logic)
- 명제 함수 : 변수의 값에 의해 함수의 진리값이 결정되는 문장이나 식
- 한정화 (quantification)
- 전체한정자 (universal quantifier, ∀)
- 전체한정자는 "모든"을 의미하며, 명제함수 ∀xP(x) 와 같이 사용되었을 경우에는 정의역의 모든 x에 대해서 P(x)가 참(T)임을 의미
- 존재한정자 (existential quantifier, ∃)
- "존재한다"를 의미하며, 명제함수 ∃xP(x)와 같이 사용되었을 떄는 정의역의 어떤 x에 대해서 P(x)가 참(T)임을 의미
- 명제함수의 타당성
- 벤 다이어 그램(Venn diagram) : 한정자가 사용된 명제함수의 타당성을 직관적으로 검사함.
예) 삼단논법 "영희는 서울에 있다" , "서울은 한국에 있따" , "영희는 한국에 있다"
2.4 추론 (inference)
- 참으로 알려진 명제를 기초로 하여 다른 명제를 유도해 내는 과정
1) 결론의 근거를 제공하는 알려진 명제를 전제(premise)라고 한다.
2) 새로 유도된 명제는 결론(conclusion)
- 유효추론 : 전제를 참(T)이라고 가정하였을 때 결론이 항상 참(T)이 되는 추론
예) ((p → q) ∧ (q → r)) → (p → r)
- 추론규칙 : 기본적인 추론 규칙은 논리적 동치를 이용하는 것
