[DiscreteMath]논리
📚명제
📄명제
명제란 참과 거짓을 구별할 수 있는 문장이나 수학적 식을 말합니다. 참인 사실 뿐만 아니라 거짓인 사실도 명제가 될 수 있습니다. 참과 거짓을 구별할 수 없는 문장은 명제가 아닙니다.
- 5는 3의 배수입니다. -> 거짓인 명제입니다.
- 1 + 2 = 3 -> 참인 명제입니다.
- x + 1 = 3 -> 명제가 아닙니다.
- 게임은 재밌다. -> 명제가 아닙니다.
📄진리값
참과 거짓을 명제의 진리값이라고 합니다.
- 2 + 3 = 5 -> 참
- 대한민국의 수도는 서울이다. -> 참
- 하루는 25시간이다. -> 거짓
📚논리연산
논리연산은 명제를 대상으로 하는 연산입니다. 논리연산은 기호로 나타냅니다.
- 논리합: or 연산이라고 하며 ∨를 사용
- 논리곱: and 연산이라고 하며 ∧를 사용
- 부정: not 연산이고 ~를 사용
- 배타적 논리합: xor 연산이며 ⊕를 사용
📄합성명제
합성명제란 하나 이상의 명제와 논리연산자들이 결합되어 만들어진 명제를 말합니다. 합성명제의 진리값은 합성 명제를 구성하는 단순명제들의 참과 거짓 여부에 따라 결정됩니다.
📄기본 논리연산
- 논리합(or)
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
- 논리곱(and)
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
- 부정(not)
| p | ~p |
|---|---|
| T | F |
| F | T |
- 배타적 논리합(xor)
서로 다른 진리값을 가지면 참이되고, 동일한 진리값을 가지면 거짓이 됩니다. 논리식은 p ⊕ q = (p ∧ ~q) ∨ (~p ∧ q)가 됩니다.
| p | q | p ∧ ~q | ~p ∧ q | p ⊕ q |
|---|---|---|---|---|
| T | T | F | F | F |
| T | F | T | F | T |
| F | T | F | T | T |
| F | F | F | F | F |
📄조건명제
명제 p와 q가 있을 때, p가 조건의 역할을 수행하고 q가 결론의 역할을 수행하는 경우, 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를 q의 충분 조건이라고 합니다.
- if not p, then not q 형식으로 표현할 수 있으면 q가 일어나는데 p가 필요하다는 의미에서 p를 q를 필요조건이라고합니다.
p → q에서 p를 q의 충분조건, q를 p의 필요조건이라고 합니다.
📄쌍조건명제
명제 p와 q가 있을 때, p가 조건일 때 q가 결론이 되고 q가 조건일 때 p가 결론이 되는 경우, p와 q의 합성명제를 쌍조건명제라고 하고 p ↔ q로 표시합니다.
p ↔ q는 (p → q) ∧ (q → p)와 같습니다. p는 q이기 위한 필요충분조건이라고도 합니다. p와 q가 동시에 동일한 진리값을 가질 때 참이 됩니다.
| p | q | p ↔ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
📄논리적 동치
명제 p와 q가 논리적으로 동등하면 논리적 동치라고 합니다. p ≡ q로 표시합니다.
p와 q가 항상 동일한 진리값을 가지므로 두 명제가 서로 바뀌어도 무방합니다.
- 역, 이, 대우
p → q에 대해- 역: q → p
- 이: ~p → ~q
- 대우: ~q → ~p
명제 p → q와 대우는 서로 진리값이 같습니다. 따라서 두 명제는 논리적 동치 관계에 있습니다.
| p | q | ~p | ~q | p → q | q → p | ~p → ~q | ~q → ~p |
|---|---|---|---|---|---|---|---|
| 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 |
📄항진명제와 모순명제
- 항진명제: 항상 참인 명제
- p → p
- p ∨ ~p
- p ∧ q → p ∧ q
- p ∨ ~(p ∧ q)
- 모순명제: 항상 거짓인 명제
- p ∧ ~p
- (p ∧ q) ∧ ~p
- (p ↔ q) ∧ (p ⊕ q)
- (p ∧ q) ∧ ~(p ∨ q)
📚술어논리
논리는 명제논리와 술어논리로 구분합니다.
- 명제논리: 주어와 술어를 구분하지 않고 문장 전체를 하나의 명제로 간주합니다.
- 술어논리: 주어와 술어를 구분하여 참과 거짓을 판별하는 법칙을 다룹니다.
📄명제함수
명제함수란 변수의 값에 의해 참과 거짓을 구별할 수 있는 문장이나 수학적 식을 말합니다. 변수를 포함하고 변수의 영역이 제한된 문장이나 식을 명제함수이고, 여기서 사용된 변수의 영역을 정의역이라고 합니다. 명제함수를 명제로 만들기 위해 두가지 방법이 있습니다.
- 각 변수에 특정한 값을 부여합니다.
- 한정자를 이용해 변수의 값을 제한합니다.
📄전체한정자
전체한정자는 ‘모든’을 말하며, 명제함수 ∀xP(x)와 같이 사용되었을 때 정의역의 모든 x에 대해서 P(x)가 참임을 의미합니다.
전체한정자를 갖는 명제함수가 참이 되기 위해 정의역의 모든 x에 대해 명제함수가 참이어야 합니다.
📄존재한정자
존재한정자는 ‘존재한다’를 의미하고, 명제함수 ∃xP(x)와 같이 사용되었을 때 P(x)가 참이 되는 어떤 x가 정의역에 존재한다는 것을 의미합니다.
존재한정자를 갖는 명제함수가 참이 되기 위해 정의역의 어떤 원소x에 대해 명제함수가 참이 되어야 합니다.
📄타당성 검사
한정자가 사용된 명제함수의 타당성을 분석하기 위해 벤 다이어그램을 사용합니다.
📚추론
📄추론
참이라고 알려진 명제로부터 논리적인 과정을 거쳐 또 다른 명제를 유도하는 과정을 추론이라고 합니다. 추론은 하나 이상의 전제와 하나의 결론으로 구성됩니다.
- 전제: 결론의 근거를 제공하는 이미 알려진 명제
- 결론: 새로 유도된 명제
유효추론은 전제를 참이라고 가정했을 때, 결론이 항상 참이 되는 추론을 말합니다.
📄추론법칙
기본적인 추론법칙은 논리적 동치를 이용한 대치법입니다.
| 법칙 이름 | 추론 법칙 | 항진명제 |
|---|---|---|
| 선언적 부가 | p ∴ p ∨ q |
p → (p ∨ q) |
| 단순화 | p ∧ q ∴ p |
(p ∧ q) → p |
| 긍정논법 | p p → q ∴ q |
(p ∧ (p → q)) → q |
| 부정논법 | ~q p → q ∴ ~p |
(~q ∧ (p → q)) → ~p |
| 선언적 삼단논법 또는 소거 | p ∨ q ~p ∴ q |
((p ∨ q) ∧ ~p) → q |
| 가설적 삼단논법 또는 추이 | p → q q → r ∴ p → r |
((p → q) ∧ (q → r)) → (p → r) |
💡추가
식이란 상수와 변수를 연산자로 묶어낸 것입니다. 따라서
-
실수식은 실수 집합의 실상수와 실변수를 실수 연산자로 묶어낸 것입니다.
-
논리식은 논리 집합의 논리상수와 논리변수를 논리 연산자로 묶어낸 것입니다.
-
부울식도 부울상수(0, 1)와 부울변수(X, Y)를 부울 연산자로 묶어낸 것입니다.
논리식과 합성명제는 같다고 보면 됩니다.
논리연산과 부울대수의 연산은 같습니다.
식 앞에 등호(=)가 있으면 함수입니다.
Leave a comment