cyphen156
Chapter2 논리와 명제 본문
논리
주어진 문제를 객관적으로 명백하게, 사고의 법칙을 체계적으로 분석하는것, 1. 명제와 2. 술어로 나뉜다.
1. 명제 - 주어와 술어를 구분하지 않고 참/거짓을 판별하는 법칙(is truth)
일반적으로 𝒑, 𝒒, 𝒓, …등으로 표기한다.
명제가 참 또는 거짓의 값을 갖을 때 이를 진리값이라 하며, T(true≒1)/F(false≒0)로 표시한다.
이진 논리라고도 한다.
참/거짓이 애매하지 않고 명확해야 한다. → 애매하면 명제가 아니다!
논리연산
단순 명제 : 하나의 문장이나 식으로 구성되어 있는 명제
합성 명제 : 여러 개의 단순 명제들이 논리 연산자들로 연결되어 만들어진 명제, 1진리표(Truth Table)를 사용하여 단계적으로 연산
변수 : 논리 기호를 이용해 합성 명제를 구성할 경우 생기는 부분 명제
| 연산자의 이름 | 기호 | 의미 | 표현방법 |
| 부정 | ~ | NOT | ~𝒑, 𝒑', ￢𝒑 등 |
| 논리곱 | ∧ | AND | 𝒑 ∧ 𝒒, 𝒑·𝒒, 𝒑&𝒒, 𝒑𝒒 등 |
| 논리합 | ∨ | OR | 𝒑 ∨ 𝒒, 𝒑+𝒒 |
| 배타적 논리합 | ⊕ | Exclusive OR | 𝒑⊕𝒒 |
| 조건 | → | if … then | 𝒑→𝒒 |
| 쌍방 조건 | ↔ | if and only if (iff) | 𝒑↔𝒒 |
1) 부정(negation)
명제의 반대되는 진리값을 갖는다.
~𝒑라고 쓰며, 'not 𝒑' 또는 '𝒑가 아니다'라고 읽는다.
| 𝒑 | ~𝒑 | |
| 진리값 | T | F |
| F | T |
2) 논리곱(conjunction)
임의의 두 명제가 그리고(AND)로 연결되어 있을 때 두 명제 모두 참인 경우에만 참이고 나머지는 거짓이다,
𝒑 ∧ 𝒒로 표기하고 '𝒑 and 𝒒' 또는 '𝒑 그리고 𝒒'라고 읽는다.
| 𝒑 | 𝒒 | 𝒑 ∧ 𝒒 |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
3) 논리합
임의의 두 명제가 또는(OR)으로 연결되어 있을 때 두 명제 모두 거짓인 경우에만 거짓이고 나머지는 참이다,
𝒑 ∨ 𝒒로 표기하고 '𝒑 or 𝒒' 또는 '𝒑 또는 𝒒'라고 읽는다.
| 𝒑 | 𝒒 | 𝒑 ∨ 𝒒 |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
4) 배타적 논리합(Exclusive OR)
임의의 두 명제의 진리값이 서로 반대일 경우에만 참이 된다,
𝒑⊕𝒒로 표기하고 Exclusive OR 또는 XOR이라 읽는다.
| 𝒑 | 𝒒 | 𝒑 ∨ 𝒒 |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
5) 조건(Implication)
임의의 두 명제의 진리값 중 𝒑가 참, 𝒒가 거짓인 경우에만 거짓이고 나머지는 참이 된다.
𝒑 → 𝒒로 표기하고 읽는 법은 다음과 같다.
- '𝒑 이면 𝒒'이다.
- 𝒑는 𝒒의 충분조건이다(𝒑 is sufficient for 𝒒)
- 𝒒는 𝒑의 충분조건이다(𝒒 is necessary for 𝒑)
- 𝒑는 𝒒를 함축한다.(𝒑 implies 𝒒)
| 𝒑 | 𝒒 | 𝒑 → 𝒒 |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
6) 쌍방 조건
임의의 두 명제의 진리값 중 𝒑와 𝒒가 모두 참 또는 거짓인 경우에만 참이고 나머지는 서로 다르면 거짓이 된다.
𝒑 ↔ 𝒒로 표기하고 읽는 법은 다음과 같다.
- 𝒑 이면 𝒒이고, 𝒒이면 𝒑 이다(𝒑 if and only if 𝒒)
- 𝒑는 𝒒의 필요충분조건이다(𝒑 is necessary and sufficient for 𝒒)
| 𝒑 | 𝒒 | 𝒑 ↔ 𝒒 |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
논리연산자의 우선순위
괄호가 있다면 괄호를 우선 연산한다.
괄호가 없는 경우 [ ~ > ∧ > ∨ > → > ↔ ]의 순서대로 연산한다.
명제의 역(Converse), 이(Inverse), 대우(Contrapositive)
| 명제 | 역 | 이 | 대우 | ||||
| 𝒑 | 𝒒 | ~𝒑 | ~𝒒 | 𝒑 → 𝒒 | 𝒒 → 𝒑 | ~𝒑 → ~𝒒 | ~𝒒 → ~𝒑 |
| T | T | F | F | T | T | T | T |
| T | F | F | T | F | T | T | F |
| F | T | T | F | T | F | F | T |
| F | F | T | T | T | T | T | T |
명제와 대우는 서로 같은 값을 갖는 2논리적인 동치 관계이다.
역과 이는 서로 대우 관계이다.
- 항진명제 : 단순 명제들의 진리값에 관계없이 합성 명제의 진리값이 항상 참이 되는 명제
- 모순명제 : 단순 명제들의 진리값에 관계없이 합성 명제의 진리값이 항상 거짓이 되는 명제
𝒑 ↔ 𝒒가 항진 명제이면 논리적 동치 관계(Logical equivalence)라 하며 𝒑 ≡ 𝒒 또는 𝒑 ⟺ 𝒒로 표시한다.
논리적 동치 관계의 여러가지 법칙
| 법칙 이름 | 논리적 동치 관계 |
| 멱등(idempotent) | 𝒑 ∨ 𝒒 ⟺ 𝒑 𝒑 ∧ 𝒒 ⟺ 𝒑 |
| 항등(identity) | 𝒑 ∨ T ⟺ T 𝒑 ∨ F ⟺ 𝒑 𝒑 ∧ T ⟺ 𝒑 𝒑 ∧ F ⟺ F |
| 부정(negation) | ~T ⟺ F ~F ⟺ T 𝒑 ∨ (~𝒑) ⟺ T 𝒑 ∧ (~𝒑) ⟺ F |
| 이중 부정(double negation) | ~(~𝒑) ⟺ 𝒑 |
| 교환(commutative) | 𝒑 ∨ 𝒒 ⟺ 𝒒 ∨ 𝒑 𝒑 ∧ 𝒒 ⟺ 𝒒 ∧ 𝒑 𝒑 ↔ 𝒒 ⟺ 𝒒 ↔ 𝒑 |
| 결합(associative) | (𝒑 ∨ 𝒒) ∨ r ⟺ 𝒑 ∨ (𝒒 ∨ r) (𝒑 ∧ 𝒒) ∧ r ⟺ 𝒑 ∧ (𝒒 ∧ r) |
| 분배(distributive) | 𝒑 ∨ (𝒒 ∧ r) ⟺ (𝒑 ∨ 𝒒) ∧ (𝒑 ∨ r) 𝒑 ∧ (𝒒 ∨ r) ⟺ (𝒑 ∧ 𝒒) ∨ (𝒑 ∧ r) |
| 흡수(absorption) | 𝒑 ∨ (𝒑 ∧ 𝒒) ⟺ 𝒑 𝒑 ∧ (𝒑 ∨ 𝒒) ⟺ 𝒑 |
| 드 모르간 법칙(De Morgan's law) | ~(𝒑 ∨ 𝒒) ⟺ (~𝒑) ∧ (~𝒒) ~(𝒑 ∧ 𝒒) ⟺ (~𝒑) ∨ (~𝒒) |
| ※ 조건 | 𝒑 → 𝒒 ⟺ ~𝒑 ∨ 𝒒 |
| 대우 | 𝒑 → 𝒒 ⟺ ~𝒒 → ~𝒑 |
추론(Argument)
주어진 명제가 참인 것을 바탕으로 새로운 명제가 참이 되도록 유도하는 방법
A, B ├ C로 표시한다.
유효 추론 : 전제가 참이고 결론도 참인 추론
허위 추론 : 전제는 참이지만 결론은 거짓이 되는 추론
여러 가지 추론 법칙
| 법칙 이름 | 추론 법칙 |
| 긍정 법칙 (modus ponens) |
𝒑 𝒑 → 𝒒 ∴ 𝒒 |
| 부정 법칙 (modus tollens) |
~𝒒 𝒑 → 𝒒 ∴ ~𝒒 |
| 조건 삼단 법칙 (hypothetical syllogism) |
𝒑 → 𝒒 𝒒 → r ∴ 𝒑 → r |
| 선언 삼단 법칙 (disjunctive dilemma) |
𝒑 ∨ 𝒒 ~𝒒 ∴ 𝒒 |
| 양도 법칙 (constructive dillemma) |
(𝒑 → 𝒒) ∧ (r → s) 𝒑 ∨ r ∴ 𝒒 ∨ s |
| 파괴적 법칙 (destructive dillemma) |
(𝒑 → 𝒒) ∧ (r → s) ~𝒒 ∨ ~s ∴ ~𝒑 ∨ ~r |
| 선접 법칙 (disjunctive addition) |
𝒑 ∴ 𝒑 ∨ 𝒒 |
| 분리 법칙 (simplication) |
𝒑 ∧ 𝒒 ∴ 𝒑 |
| 연접 법칙 (conjunction) |
𝒑 𝒒 ∴ 𝒑 ∧ 𝒒 |
2. 술어 - 주어와 술어를 구분하며, 참/거짓에 관한 법칙(about)
명제 중 진리값이 명확하게 결정되지 않은 변수가 있어서 그 값에 따라 명제의 진리값이 결정되는 것
술어한정자
- 전체한정자(∀, for all) : 모든 것에 대하여 진리값이 항상 참이 되는 술어 명제, ∀x p(x)로 나타낸다. 필요충분조건은 p(x)가 전체 집합 U에 대하여 성립해야 한다.
- 존재 한정자(∃, there exist) : 명제 p(x)를 만족시키는 x가 존재하는 술어 명제, ∃x p(x)로 나타낸다. p(x)가 참이기 위한 필요충분조건으로 전체 집합 U안에 p(x)를 만족시키는 x가 적어도 하나 존재한다.
※ 전체한정자의 부정과 존재한정자의 부정
p(x)가 성립하지 않는 x가 존재한다 ~(∀x p(x)) ⟺ ∃x (~p(x))
모든 x는 p(x)가 성립하지 않는다 ~(∃x p(x)) ⟺ ∀x (~p(x))
Prolog(논리용 용어)
논리와 명제를 컴퓨터 프로그램을 통해 빠르고 쉽게 구현하기 위해 만들어진 언어
특징
- 사실, 규칙, 질문들로 프로그램이 구성되어 있다.
- 사용자가 사실과 규칙들을 입력하고 이를 데이터베이스로 구성하였다.
- 프로그램 실행은 명령 방식의 자료에 대한 대화식의 질문과 응답 형식이다.
- 사용자의 질문에 대답하기 위해 추론 엔진을 사용한다
논리의 응용과 4차 산업혁명
응용분야
- 디지털 논리
- 관계형 데이터베이스
- 논리 기반의 인공지능과 전문가 시스템 등
4차 산업혁명 시대의 이산수학을 베이스로 공부한 내용을 정리한 글입니다.
'수학 > 이산수학' 카테고리의 다른 글
| Chapter2 연습 문제 (0) | 2022.08.27 |
|---|---|
| Chapter2 예제 (0) | 2022.08.15 |
| Chapter1 연습문제 (0) | 2022.07.31 |
| Chapter1 이산수학이란? (0) | 2022.07.30 |
