[이산수학] 집합과 논리

📌 들어가며

이번 글에서는 인공지능을 위한 기초수학 중 이산수학(Discrete Math)의 집합·명제·논리를 정리한다.

이산(discrete): 별개의, 개별적인, 분리된. 이런 이산적 수학 구조를 연구하는 학문이 이산수학이며, 인공지능의 기초가 된다.

---

1. 집합 (Set)

집합: 여러 원소(element)의 모임. 중복된 원소를 갖지 않는다.

구분	정의
원소 개수	\|A\|로 표기
유한집합	원소가 유한개
무한집합	원소가 무한개

---

2. 명제 (Proposition)

명제: 객관적으로 참·거짓을 판단할 수 있는 문장이나 수식. 참은 T, 거짓은 F로 표시하며, 이 값을 진릿값(Truth value)이라 한다.

다음 중 명제는?

문장	명제 여부
신동희는 잘생겼다	❌ (주관적)
신동희는 머리가 좋다	❌ (주관적)
신동희는 만 21살이다	✅ 명제 (거짓일 수 있음)
1 + 1 = 2	✅ 참인 명제

💡 핵심은 “객관적으로 참·거짓을 판단할 수 있는가”다. 주관적 문장은 명제가 아니다. 명제는 거짓이어도 명제다.

---

3. 논리 연산자

연산	표기	참이 되는 조건
부정(not)	~p	p의 진릿값을 반대로
논리곱(and)	p ∧ q	p, q 모두 참일 때만 참
논리합(or)	p ∨ q	p, q 모두 거짓일 때만 거짓

---

4. 조건 명제와 역·이·대우

조건 명제 p → q: p가 가정, q가 결론. “p이면 q이다(if p, then q)”.

이름	형태	설명
원명제	p → q	기준
역	q → p	가정·결론 교환
이	~p → ~q	각각 부정
대우	~q → ~p	교환 + 부정

      p → q  (원명제)
     /       \
    역        이
  q → p     ~p → ~q
     \       /
      대우 (~q → ~p)

💡 원명제와 대우는 진릿값이 항상 같다. (역과 이도 서로 진릿값이 같다.) 증명에서 대우를 활용하는 이유다.

---

📝 정리

집합 & 논리
├─ 집합    중복 없는 원소의 모임 (|A|, 유한/무한)
├─ 명제    객관적 참·거짓 판단 가능 (T/F)
├─ 연산    ~(부정) · ∧(and) · ∨(or)
└─ 조건명제  p→q, 역/이/대우 (원명제=대우)

개념	한 줄 정의
명제	참·거짓을 객관적으로 판단하는 문장
논리곱/합	모두 참 / 하나라도 참
대우	~q → ~p, 원명제와 진릿값 동일

집합과 명제 논리는 이산수학의 출발점이자, 프로그래밍의 조건 판단과도 직결된다. 특히 원명제와 대우의 진릿값이 같다는 성질은 논리적 증명의 핵심 도구다.