명제와 논리연산
명제 proposition: 참과 거짓을 구별할 수 있는 문장이나 수학적 식
합성명제 compound proposition: 하나 이상의 명제와 논리연산자들이 결합되어 만들어진 명제
논리연산: 참, 거짓을 구별할 수 있는 명제를 대상으로 하는 연산
- 논리합(or, ∨) disjunction
- 하나라도 T가 있으면 T
- 논리곱(and, ∧) conjunction
- 하나라도 F가 있으면 F
- 부정(not, ~) negation
- T → F, F → T
- 배타적 논리합(xor, ⊕) exclusive disjunction
- 2개 중 1개만 T인 경우 T (T, T 거나 F, F면 F)
- p ⊕ q = (p ∧ ~q) ∨ (~p ∧ q)
- or인데 and를 포함하지 않은 경우 (두개가 동일한 경우를 배제)
- 두개가 서로 다를 때만 True
배타적 논리합 진리표
| p | q | p ⊕ q |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
연산은 크게 보면 두 종류
- 1항 연산
- 피연산자가 1개인 경우 (ex. 여집합, 절대값, 부정)
- 2항 연산
- 피연산자가 2개인 경우
조건명제 conditional proposition: p가 조건의 역할, q가 결론의 역할인 경우 p와 q의 합성명제 (p → q)
- 조건이 T이고 결과가 F인 경우만 F
- 조건이 F이면 무조건 T
- 조건명제이려면 조건도 명제, 결론도 명제여야 함
- p는 q의 충분조건, q는 p의 필요조건
- p가 참일때는 q가 참이어야만 조건명제가 참
- p가 거짓이면 결론이 무엇이든 거짓이라고 약속함
조건명제의 진리표
| p | q | p → q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
쌍조건명제 biconditional proposition: p가 조건일 때 q가 결론이 되고 동시에 q가 조건일 때 p가 결론이 됨 (p ↔ q)
- p와 q의 진리값이 동일할 때 T
- p ↔ q = (p → q) ∧ (q → p)
- p if and only if q
- p ↔ q ≡ ~ (p ⊕ q)
쌍조건명제의 진리표
| p | q | p ↔ q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
논리적 동치 logical equivalence
- 명제와 대우는 서로 진리값이 동일한 동치관계
- 역과 이도 서로 대우관계이면서 진리값이 동일한 동치관계
- 진리표가 완전히 같다는 뜻
항진명제 tautology: 항상 T인 명제
모순명제 contradiction: 항상 F인 명제
논리연산자 우선순위
1. ~
2. ∨, ∧
3. →, ↔
4. ≡
조건명제가 참이라고 해서 역이 언제나 참인 것은 아님
P ^ (q v r) -> 실수집합에서와 같음
p * (q + r) = (p * q) + (p * r)
드 모르간 법칙
- 합집합의 여집합은 여집합의 교집합
- 교집합의 여집합은 여집합의 합집합
술어논리
명제논리 propositional logic: 주어와 술어 구분 없이 문장 전체를 하나의 명제로 간주
술어논리 predicate logic: 주어와 술어 구분하여 참과 거짓 판별
명제함수: 변수를 포함하고 변수의 영역이 제한된 문장이나 식, 변수의 값에 의해 참과 거짓을 구별할 수 있는 문장이나 수학적 식
전체한정자 universal quantifier: ∀xP(x), 정의역의 모든 x에 대해서 P(x)가 참
존재한정자 existential quantifier : ∃xP(x), 어떤 x가 정의역에 존재
추론
추론 inference: 참으로 알려진 명제를 기초로 다른 명제를 유도해 내는 과정
유효추론: 전제를 T라고 가정하였을 때 결론이 항상 T인 추론
출처: 이산수학(손진곤, 2021)