0️⃣ 학습 목표
- 주요 논리 연산에 대한 이해
- 항진 명제와 모순 명제의 이해
- 논리적 동치 관계와 술어 한정자에 대한 이해
- 유효 추론과 허위 추론의 이해
1️⃣ 논리와 명제
논리(Logic)란 무엇인가?
수학적 표현의 의미를 정확하게 기술하는 도구
추론(Reasoning)을 통해 사고 법칙의 타당성을 검증
명제 논리 (Propositional logic)과 술어 논리(Predicate logic)
– 명제 논리 : 주어와 술어를 구분하지 않고 전체를 하나의 식으로 처리하여 참 또는 거짓을 판별하는 법칙을 다룸
– 술어 논리 : 주어와 술어를 구분하여 참 또는 거짓에 관한 법칙을 다룸
명제 (Proposition)
어떤 사고를 나타내는 문장 중 참(true: T) 또는 거짓(false: F)을 객관적이고 명확하게 구분할 수 있는 문장이나 수식을 의미
일반적으로 영문 소문자 p,q,r... 등으로 표기
명제가 갖는 참 또는 거짓 값을 명제의 진리값(Truth value)이라 한다.
명제는 T와 F의 2가지 진리값만 가지므로 이진논리
e.g.
- 축구는 재미있다.
- 27은 3의 배수이다.
- 2x + 7y = 85
- 수업 언제 끝나?
1,2,4 는 참이나 거짓을 판별할 수 없다. 따라서 명제가 될 수 없다. 3은 참이기 때문에 명제이고 진리값은 T.
2️⃣ 논리 연산
단순 명제
하나의 문장이나 식으로 구성되어 있는 명제
합성명제
여러 개의 단순 명제들이 논리 연산자들로 연결되어 만들어진 명제
합성 명제의 진리값은 그 명제를 구성하는 단순 명제의 진리값과 논리 연산자의 특성에 따라 결정
논리 연산자
| 기 호 | 이 름 | 의 미 |
| ⁓ | 부정 | NOT |
| ⋀ | 논리곱 | AND |
| ⋁ | 논리합 | OR |
| ⊕ | 배타적 논리합 | Exclusive OR |
| → | 조건 | if ... then |
| ↔ | 쌍방 조건 | if and only if (iff) |
부정 NOT
임의의 명제 p가 주어졌을 때 그 명제에 대한 부정(negation)은 명제 p의 반대되는 진리값을 가짐
기호로 ⁓p, 'not p 또는 p가 아니다'라 읽음
p의 진리값이 참이면 ⁓p의 진리값은 거짓
p의 진리값이 거짓이면 ⁓p의 진리값은 참
| p | ⁓p |
| T | F |
| F | T |
논리곱 AND
임의의 두 명제 p와 q가 AND로 연결되어 있을 때 논리곱(conjunction)은 p ⋀ q 으로 표시
두 명제가 모두 참인 경우에만 진리값으로 참을 도출
| p | q | p ⋀ q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
논리합 OR
임의의 두 명제 p와 q가 OR로 연결되어 있을 때 논리합(disjunction)은 p ⋁ q 으로 표시
두 명제가 모두 거짓인 경우에만 진리값으로 거짓을 도출
| p | q | p ⋁ q |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
배타적 논리합 Exclusive OR
임의의 두 명제 p와 q의 Exclusive OR (배타적 논리합)은 p ⨁ q 으로 표시
두 명제의 진리값이 다를 때에만 진리값으로 참을 도출
| p | q | p ⨁ q |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
조건 if ... then
함축(implication)이라고도 함임의의 두 명제 p와 q의 조건 연산자는 p → q (p 이면 q이다)로 표시p 가 참이고 q 가 거짓인 경우만 진리값으로 거짓을 도출
| p | q | p → q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
조건 연산자의 다양한 표현
- p 이면 q 이다. (if p, then q)
- p 는 q 의 충분조건이다. (p is sufficient for q)
- q 는 p 의 필요조건이다. (q is necessary for p)
- p 는 q 를 함축한다. (p implies q)
쌍방 조건 if ... and only if
상호조건명제(biconditional)이라고도 함.임의의 두 명제 p와 q의 쌍방 조건은 p ↔ q (p 이면 q이고, q 이면 p 이다.)로 표시p 와 q 가 같은 진리값을 갖는 경우만 진리값으로 참을 도출
| p | q | p ↔ q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
논리 연산자의 우선순위
| 우선순위 | 논리 연산자 |
| 1 | ⁓ |
| 2 | ⋀ |
| 3 | ⋁ |
| 4 | → |
| 5 | ↔ |
예시
| p | q | ⁓q | p ⋀ ⁓q | ⁓( p ⋀ ⁓q ) |
| T | T | F | F | T |
| T | F | T | T | F |
| F | T | F | F | T |
| F | F | T | F | T |
명제의 상호 관계
명제 p → q 에 대하여
역(converse): q → p
이(inverse): ~p → ~q
대우(contrapositive): ~q → ~p
3️⃣ 항진 명제와 모순 명제
항진 명제
합성 명제에서 그 명제를 구성하는 단순 명제들의 진리값에 관계없이 그 합성 명제의 진리 값이 항상 참의 값을 갖는 명제
모순 명제
합성 명제에서 그 명제를 구성하는 단순 명제들의 진리값에 관계없이 그 합성 명제의 진리 값이 항상 거짓의 값을 갖는 명제
4️⃣ 논리적 동치 관계
논리적 동치
두 개의 명제 p, q의 쌍방 조건 p ↔ q가 항진 명제이면 두 명제 p, q는 논리적 동치
p ≡ q 또는 (p ⟺ q)로 표시
즉, 두 명제 p, q가 같은 논리값을 갖는다는 의미
두 명제의 논리적 동치 관계에 대한 입증 방법
- 두 명제에 대한 진리표를 구하고 진리값이 같음을 증명
- 논리적 동치관계의 기본법칙을 이용하는 방법
논리적 동치의 기본 법칙
| 법칙 | 논리적 동치 관계 |
| 멱등 법칙 | p ⋁ p ⟺ p p ⋀ p ⟺ p |
| 항등 법칙 | p ⋁ T ⟺ T p ⋁ F ⟺ p p ⋀ T ⟺ p p ⋀ F ⟺ F |
| 부정 법칙 | ~T ⟺ F ~F ⟺ T p ⋁ (~p) ⟺ T p ⋀ (~p) ⟺ F |
| 이중 부정 법칙 | ~ (~p) ⟺ p |
| 교환 법칙 | p ⋁ q ⟺ q ⋁ 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 → q ⟺ ~p ⋁ q |
| 대우 법칙 | p → q ⟺ ~q → ~p |
5️⃣ 추론
주어진 명제가 참인 것을 바탕으로 새로운 명제가 참이 되는 것을 유도하는 방법을 추론(Argument)이라 함
여기서 주어진 명제들인 p1,p2,...,pn을 전제(premise)라 하고 새로 유도된 명제 q를 결론(conclusion)이라고 함
유효 추론
주어진 전제가 참이고 결론도 참인 추론
허위 추론
주어진 전제가 참이지만 결론은 거짓인 추론
전제가 p1,p2,...,pn이고 결론을 q라 할 때 이에 대한 추론의 수학적 식은
p1,p2,...,pn ⊢ q
예시
p → q,q ⊢ p
| p | q | p → q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
전제가 참인 경우 중 결론이 거짓인 경우가 존재 ∴ 허위추론
6️⃣ 술어 논리
명제 내에 변수가 존재하여 변수의 값에 따라서 명제의 진리값이 변경되는 명제를 p(x) 로 표현
p(x)를 변수 x에 대한 명제 술어(propositional predicate)라 함
명제 논리와 구분하여 명제 술어에 대한 논리를 술어 논리(predicate logic)라고 함
술어 한정자
술어를 나타낼 때 변수의 범위를 한정시키는 방법
- ∀ : for all (모든 것에 대하여)
- ∃ : there exist (존재한다)