집합론 - 명제와 논리

💡 유튜브 이상엽Math 를 보며 정리한 글입니다.

 

명제와 증명

---

1️⃣ 명제와 연결사

---

명제

참, 거짓이 분명히 판단되는 문장

 

단순 명제

p,q,r 등의 기호로 나타내며, 단일 명제를 의미

ex. 사과는 과일이다.

 

합성 명제

몇 개의 단순 명제들이 연결사에 의해 결합된 명제

ex. 사과는 과일이고 바나나도 과일이다.

 

연결사

단순 명제를 연결하는 연결사로 다음과 같은 기호로 나타냅니다.

연결사

 

 

2️⃣ 진리표

---

명제의 진리값을 표로 나타낸 것으로 5가지 연결사들에 대한 진리표는 다음과 같습니다.

 

진리표 , T = True , F = False

 

💡 부가 설명

 

진리집합이란 해당 명제가 참이되도록 하는 모든 원소들의 집합입니다.

 

명제 p의 진리집합은  p → P 로 나타냅니다.

ex. p : ~는 과일이다.   P = { 사과, 포도, 바나나 } 

 

이 때, p 가 F라는 의미는 진리집합 P에 해당하는 원소가 없다는 것을 의미하며,  U(전체집합) - P 가 아닌 ∅ (공집합)을 의미합니다.

 

더불어, p -> q는 Q에 P가 포함되는지를 묻는 것을 의미합니다. 이를 기반으로 위 표의 4가지 경우를 보자면 다음과 같습니다.

• p = T  , q = T  : P가 Q 에 포함되므로 참이 된다.
• p = T , q = F : Q가 공집합이므로, 공집합에 포함될 수 없으니 거짓이 된다.
• p = F , q = T  / p = F , q = F : P는 공집합이며 공집합은 다른 집합에 항상 포함되기 때문에 참이 된다.

 

p ↔ q는 두 진리집합이 같은 지를 묻는 것으로 둘 다 T 거나 , F(공집합)이면 같으므로 참이고, 하나라도 다르면 거짓입니다.

 

연결사의 연산 순서는 ~ , ∧ , ∨ , → , ↔ 이고 괄호가 있다면 괄호를 먼저 처리합니다. (프로그래밍 언어에서의 논리연산자와 동일합니다.)

 

다음은 알아두면 좋을만한 항상 참인 식 입니다.

• p → q ≡ ~p ∨ q
• ~(p ∧ q) ≡ ~p ∨ ~q  : 드모르간 법칙
• p → q  ≡ ~q → ~p  : 대우 법칙
• (p ∨ q) V r  ≡ p ∨ (q ∨ r)  : 결합 법칙
• p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)  : 분배 법칙

 

이와 관련된 법칙들은 다음과 같습니다.

 

 

3️⃣ 연역적 추론

---

진리표의 경우, 간단할 때 사용하지만 길어질 경우 검증할게 많아집니다. 그래서 수학적인 추론 방법을 사용하는데 그중 하나가 연역적 추론입니다.

 

연역적 추론

이미 알고 있는 판단을 근거로 새로운 판단을 유도하는 것

 

 굳이 T,F를 하나하나 비교해서 하는 것이 아니라 위의 항상 참인 식들에서 알아본 법칙들을 이용해서 연역적 추론으로 구해내면 빠르게 구해낼 수 있습니다. 

 

 

명제 함수

---

1️⃣ 명제함수와 한정기호

---

명제함수

변수 x가 결정되어야만 참, 거짓이 판단되는 문장을 의미하며, p(x)와 같은 형태로 나타냅니다.

 

여기서 x의 범위를 대상영역 혹은 모집단(U) 이라고 합니다.

 

한정기호

전칭기호 ∀ : for every , 모집단 모두를 대상으로 함

ex. ∀x, p(x) : 모집단 모두가 x에 해당

 

존재기호 ∃ : for some , 모집단 일부를 대상으로 함

ex.∃x, p(x) : 모집단 일부가 x에 해당(적어도 1개 이상 존재, 어떤으로 생각하면 됩니다)

 

 

2️⃣ 명제의 부정

---

두 명제 p와 q에 대해, x의 모집단은 건드리지 않으며 다음과 같은 4가지 원리를 모두 적용합니다.

아래는 서로 반대되는 것을 의미합니다.

• ∀ ↔ ∃
• ∧ ↔ ∨
• p ↔ ~p
• < ↔ ≥

 

다음은 예시 입니다. 

• ∀x , p(x) → 성공 ∧ 행복 ≡ ∀x , ~p(x) ∨ (성공 ∧ 행복) 
• 위를 부정 : ∃x , ~( ~p(x) ∨ (성공 ∧ 행복) ≡ ∃x , p(x) ∧ ~(성공 ∧ 행복) ≡ ∃x , p(x) ∧ (~성공 ∨ ~행복)

 

 

함의와 동치

---

1️⃣ 항진명제와 모순명제

---

항진명제

모든 논리적 가능성의 진리값들이 참인 명제로 t로 나타냅니다.

여기서 t는 모집합을 의미하며 참으로 볼 수 있습니다.

 

모순명제

모든 논리적 가능성의 진리값들이 거짓인 명제로 c로 나타냅니다.

여기서 c는 공집합을 의미하며 거짓으로 볼 수 있습니다..

 

 

2️⃣ 함의와 동치

---

함의

항진인 조건문 p → q를 논리적 함의라 하고 p => q로 나타내며 p는 q의 충분조건, q는 p의 필요조건이라 합니다.

 

동치

항진인 쌍조건문 p ↔ q를 동치라 하고 p <=> q로 나타내며 p와 q는 서로의 필요충분조건이라 합니다.