📚 지식 노트

명제와 논리: 진리표, 함의, 드모르간

명제는 참이나 거짓 중 하나로 정해지는 문장이다. "7은 소수다"는 참인 명제, "x는 소수다"는 x가 정해지기 전엔 명제가 아니다. 명제를 ¬(아니다), ∧(그리고), ∨(또는)로 묶어 복합 명제를 만들고, 가능한 모든 참·거짓 조합에서 값을 따져 보는 표가 진리표다. 명제가 n개면 줄이 2ⁿ개다.

가장 헷갈리는 연결사가 함의 p → q("p이면 q")다. p가 참인데 q가 거짓일 때만 거짓이고, 나머지 셋은 모두 참이다. "비가 오면 우산을 쓴다"는 약속은 비가 안 온 날 무엇을 하든 깨지지 않는다. 그래서 p → q는 ¬p ∨ q와 같다. 주의할 짝도 있다.

• 대우 ¬q → ¬p는 원래 명제와 항상 진리값이 같다. "비가 오면 땅이 젖는다" ≡ "땅이 안 젖었으면 비가 안 왔다".
• 역 q → p와 이 ¬p → ¬q는 원래 명제와 다를 수 있다. 땅이 젖었다고 비가 온 건 아니다(물을 뿌렸을 수도 있다).
• 드모르간의 법칙: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q. 부정을 안으로 넣으면 그리고·또는이 서로 바뀐다. 코드의 !(a && b)를 !a || !b로 바꿔 쓰는 근거다.

술어와 양화사

"x는 짝수다"처럼 변수가 들어 있어 값을 넣어야 참·거짓이 정해지는 문장을 술어 P(x)라 한다. 술어를 명제로 만드는 방법이 양화사다. ∀x P(x)는 "모든 x에 대해 P(x)", ∃x P(x)는 "P(x)인 x가 적어도 하나 있다"이다. 정의역이 무엇인지가 중요하다. ∀x ∃y (x < y)는 정수에서는 참이지만 {1, 2, 3, 4}에서는 4보다 큰 y가 없어 거짓이다.

양화사가 둘 이상이면 순서가 뜻을 바꾼다. ∀x ∃y P(x, y)는 "누구에게나 (사람마다 다를 수 있는) 연락처를 아는 상대가 있다", ∃y ∀x P(x, y)는 "모두가 연락처를 아는 한 사람이 있다"로, 뒤의 것이 훨씬 강하다. 부정은 양화사를 뒤집고 술어를 부정한다. "모든 학생이 합격했다"의 부정은 "모든 학생이 불합격했다"가 아니라 "불합격한 학생이 한 명은 있다"(¬∀x P(x) ≡ ∃x ¬P(x))이다. 그래서 전칭 명제는 반례 하나로 무너뜨릴 수 있다.

증명 방법: 직접, 대우, 귀류, 수학적 귀납법

• 직접 증명: 가정에서 정의와 이미 아는 사실로 결론까지 곧장 간다. "두 짝수의 합은 짝수다": 2a + 2b = 2(a + b)이므로 짝수다.
• 대우 증명: p → q 대신 동치인 ¬q → ¬p를 보인다. "n²이 짝수면 n도 짝수다"는 직접 하기 어렵지만, 대우 "n이 홀수면 n²도 홀수"는 (2k + 1)² = 2(2k² + 2k) + 1로 바로 나온다.
• 귀류법: 결론이 거짓이라 가정하고 모순을 끌어낸다. √2 = a/b(기약분수)라 하면 a² = 2b²이라 a가 짝수, a = 2c를 넣으면 b² = 2c²이라 b도 짝수가 되어 "기약분수"와 모순이다. "소수는 무한히 많다"도 같다. 소수가 p₁, …, pₖ뿐이라면 p₁⋯pₖ + 1은 어느 pᵢ로 나눠도 1이 남으므로, 목록에 없는 소인수를 가진다.
• 수학적 귀납법: 자연수 n에 대한 명제 P(n)을 두 단계로 증명한다. 기초 단계 P(1)이 참이고, 귀납 단계 "P(k)가 참이면 P(k + 1)도 참"을 보이면, 도미노처럼 모든 n에서 참이다. 1 + 2 + … + n = n(n + 1)/2(n = 100이면 5,050)도, 아래 홀수의 합도 이렇게 증명한다. 재귀 함수가 올바르다는 증명, 반복문의 불변식도 같은 구조다.

집합: 벤 다이어그램과 포함–배제

집합은 서로 다른 원소의 모임이다. 합집합 A ∪ B, 교집합 A ∩ B, 차집합 A − B, 여집합 Aᶜ을 만들 수 있고, 원소가 n개인 집합의 부분집합은 2ⁿ개다(각 원소를 넣거나 빼거나). 집합의 연산은 논리 연산과 짝을 이뤄서, 드모르간의 법칙 (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ도 그대로 성립한다. SQL의 UNION·INTERSECT·EXCEPT가 이 연산이다.

합집합의 크기를 셀 때 겹친 부분을 두 번 세지 않게 빼는 것이 포함–배제 원리다. 둘이면 |A ∪ B| = |A| + |B| − |A ∩ B|, 셋이면 셋을 더하고, 둘씩 겹친 것을 빼고, 셋 다 겹친 것을 다시 더한다. 1부터 100까지 2·3·5 가운데 하나라도 나누어떨어지는 수는

50 + 33 + 20 − 16 − 10 − 6 + 3 = 74

개다. 6의 배수 16개는 2의 배수로도 3의 배수로도 세였으니 한 번 빼고, 30의 배수 3개는 세 번 더하고 세 번 빠졌으니 다시 더한다. 하나씩 세어 봐도 74개다. 나머지 26개는 2·3·5와 서로소인 수다.

관계와 함수

집합 A의 원소와 B의 원소 사이의 관계는 순서쌍 (a, b)의 모음이다. A의 모든 원소가 B의 원소 정확히 하나와 짝지어지면 함수 f: A → B다. 함수는 세 가지로 나눈다.

• 단사(일대일): 서로 다른 입력은 서로 다른 출력으로 간다. 해시 함수가 단사가 아니라서 충돌이 생긴다.
• 전사(위로의 함수): 공역의 모든 원소가 누군가의 출력이다.
• 전단사: 단사이면서 전사. 하나씩 빠짐없이 짝지어지므로 역함수가 있고, 두 집합의 크기가 같다. 암호화와 복호화가 역함수 관계인 것도 이 성질 덕이다.

세어 보면 원소 3개짜리 집합에서 3개짜리 집합으로 가는 함수는 3³ = 27개, 그 가운데 단사는 3 × 2 × 1 = 6개다.

한 집합 안의 관계가 반사(a ~ a), 대칭(a ~ b면 b ~ a), 추이(a ~ b, b ~ c면 a ~ c)를 모두 만족하면 동치 관계다. 동치 관계는 집합을 겹치지 않는 묶음(동치류)으로 나눈다. "3으로 나눈 나머지가 같다"는 0~11을 {0, 3, 6, 9}, {1, 4, 7, 10}, {2, 5, 8, 11} 세 묶음으로 나누고, 이것이 아래 정수론의 합동식이다.

비둘기집 원리

비둘기 n + 1마리가 집 n개에 들어가면, 어떤 집에는 두 마리 이상 있다. 너무 당연하지만 "존재한다"를 증명하는 데 강력하다. 일반형은 n개를 k칸에 넣으면 어느 칸에는 ⌈n/k⌉개 이상이 들어간다는 것이다.

• 13명이 있으면 생일이 같은 달인 사람이 반드시 있다(⌈13/12⌉ = 2). 100명이면 같은 달이 적어도 9명이다.
• 1~10에서 아무 수나 6개를 고르면 합이 11인 두 수가 반드시 있다. (1, 10), (2, 9), (3, 8), (4, 7), (5, 6)의 다섯 쌍을 상자로 보면, 수 6개가 상자 5개에 들어가기 때문이다.
• 길이를 줄이는 무손실 압축은 모든 파일을 줄일 수 없다. n비트 파일은 2ⁿ개인데 n비트보다 짧은 문자열은 2ⁿ − 1개뿐이라, 두 파일이 같은 압축 결과로 가야 한다. 해시 충돌이 반드시 존재하는 이유도 같다.

점화식: 피보나치와 하노이 탑

점화식은 수열의 항을 앞의 항으로 정의한다. 처음 몇 항(초기 조건)과 규칙만 있으면 모든 항이 정해지며, 재귀 함수와 동적 계획법이 바로 이 구조다.

피보나치 수열 Fₙ = Fₙ₋₁ + Fₙ₋₂(F₁ = F₂ = 1)는 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, …로 자란다. 이웃한 두 항의 비 F₁₅/F₁₄ = 1.618037는 황금비 (1 + √5)/2 = 1.618034에 다가간다. 정의대로 재귀 호출하면 같은 값을 수없이 다시 계산해 호출 수가 지수적으로 늘고, 앞의 값을 저장해 두면 n번에 끝난다. 이 차이는 알고리즘 노트의 동적 계획법에서 다룬다.

하노이 탑은 기둥 셋과 크기가 다른 원판 n개로, 한 번에 하나씩, 작은 원판 위에 큰 원판을 올리지 않고 모두 다른 기둥으로 옮기는 퍼즐이다. 가장 큰 원판을 옮기려면 그 위의 n − 1개를 먼저 비켜 둬야 하므로 최소 이동 수는 T(n) = 2T(n − 1) + 1, T(1) = 1이다. 몇 항을 써 보면 1, 3, 7, 15, …라 T(n) = 2ⁿ − 1로 짐작되고, 귀납법으로 증명된다(2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1). 원판 64개면 18,446,744,073,709,551,615번, 1초에 한 번 옮겨도 약 5,845억 년이 걸린다.

정수론: 나눗셈, 합동식, 모듈러 산술

나눗셈 정리: 정수 a와 양의 정수 b에 대해 a = bq + r, 0 ≤ r < b인 몫 q와 나머지 r이 하나씩 있다. 17 = 5 × 3 + 2다. 음수도 나머지를 0 이상으로 맞추면 −7 = 3 × (-3) + 2다. 프로그래밍 언어마다 음수의 % 결과 부호가 달라(C·Java·JavaScript는 −1, Python은 2) 버그가 잦다.

두 수의 최대공약수는 유클리드 호제법으로 구한다. gcd(a, b) = gcd(b, a mod b)를 나머지가 0이 될 때까지 되풀이한다. 252와 105는 252 mod 105 = 42, 105 mod 42 = 21, 42 mod 21 = 0이라 gcd = 21다.

n으로 나눈 나머지가 같으면 합동이라 하고 a ≡ b (mod n)으로 쓴다. 합동은 동치 관계이고, 덧셈·뺄셈·곱셈을 해도 유지된다. 그래서 큰 수를 끝까지 계산하지 않고 나머지만 들고 다닐 수 있다. 이것이 모듈러 산술이고, 가장 익숙한 예가 시계다. 9시에서 5시간 뒤는 14시가 아니라 2시, 곧 9 + 5 ≡ 2 (mod 12)다. 요일 계산(mod 7), 해시 테이블의 칸 번호, 주민등록번호·ISBN의 검증 숫자가 모두 모듈러 산술이다.

거듭제곱도 나머지만 들고 다니면 작게 유지된다. 2¹⁰⁰을 7로 나눈 나머지는, 2³ = 8 ≡ 1 (mod 7)이므로 2¹⁰⁰ = (2³)³³ × 2 ≡ 2이다. 페르마 소정리는 이런 주기를 보장한다. p가 소수이고 a가 p의 배수가 아니면 a^p−1 ≡ 1 (mod p)이다. 3을 계속 곱해 7로 나눈 나머지는 3, 2, 6, 4, 5, 1로 1~6을 한 번씩 거쳐 3⁶ ≡ 1로 돌아온다. RSA 암호가 이 정리를 확장한 오일러 정리 위에 서 있으며, 그 이야기는 암호학 노트에서 깊게 다룬다.

나눗셈만은 그대로 옮겨지지 않는다. a/b (mod n)은 b의 모듈러 역원 b⁻¹, 곧 b·b⁻¹ ≡ 1 (mod n)인 수를 곱하는 것으로 정하는데, 역원은 gcd(b, n) = 1일 때만 있다. 3 × 7 = 21 ≡ 1 (mod 10)이라 3의 역원은 7이지만, 2는 10과 서로소가 아니어서 역원이 없다. 역원은 확장 유클리드 알고리즘으로 O(log n)에 구하고, n이 소수 p면 페르마 소정리로 b^p−2 mod p이기도 하다.

프로그래밍 언어의 % 연산자는 음수에서 이 노트의 나머지와 다를 수 있다. 파이썬은 몫을 아래로 내림하므로 −7 % 3이 2(나누는 수의 부호)지만, JavaScript는 나뉘는 수의 부호를 따라 −7 % 3이 −1이다. JavaScript에서 0 이상의 나머지가 필요하면 ((n % d) + d) % d로 고친다(MDN의 Remainder). 음수 좌표를 격자 칸 번호로 바꾸거나 배열을 원형으로 돌 때 자주 터지는 버그다.

그래프 이론: 오일러 경로, 트리, 색칠

그래프는 꼭짓점과 그것을 잇는 변으로 이루어진다. 꼭짓점에 닿은 변의 수를 차수라 하고, 변 하나가 양 끝 두 꼭짓점의 차수를 하나씩 올리므로 차수의 합은 항상 변 수의 두 배다(악수 정리). 그래서 홀수 차수 꼭짓점은 늘 짝수 개다.

그래프 이론은 1736년 오일러의 쾨니히스베르크 다리 문제에서 시작했다. 강으로 나뉜 땅 네 곳을 다리 일곱 개가 잇는데, 모든 다리를 한 번씩만 건너는 산책길이 있을까? 오일러는 땅을 점으로, 다리를 선으로 줄였다. 길 중간에 지나가는 땅은 들어가고 나가는 다리가 짝을 이뤄야 하므로 차수가 짝수여야 한다. 출발점과 도착점만 예외다. 따라서 연결된 그래프에서 모든 변을 한 번씩 지나는 오일러 경로가 있으려면 홀수 차수 꼭짓점이 0개나 2개여야 한다. 쾨니히스베르크는 차수가 3, 3, 5, 3로 4곳 모두 홀수라 불가능하다. 다리 하나를 없애면 홀수 차수가 2곳으로 줄어 가능해진다. 한붓그리기 문제가 바로 이것이다.

• 트리: 사이클 없이 연결된 그래프. 꼭짓점이 n개면 변은 정확히 n − 1개이고, 두 꼭짓점 사이 경로가 딱 하나다. 꼭짓점 4개에 이름을 붙여 만들 수 있는 트리는 4² = 16가지다(케일리 공식 nⁿ⁻²). 파일 시스템, DOM, 조직도가 트리다.
• 색칠: 이웃한 꼭짓점끼리 다른 색이 되도록 칠할 때 필요한 최소 색 수를 채색수라 한다. 지도의 이웃 나라를 칠하는 데는 4색이면 충분하다는 4색 정리가 유명하다(1976년 컴퓨터로 경우를 나눠 증명). 시험 시간표(같은 학생이 듣는 과목은 다른 시간), 컴파일러의 레지스터 배정이 그래프 색칠 문제다.

최단 경로, 최소 신장 트리, 위상 정렬처럼 그래프 위에서 도는 알고리즘은 알고리즘 노트의 그래프 절에 있다.

불 대수와 논리 회로

참을 1, 거짓을 0으로 두고 ∧를 곱(AND), ∨를 합(OR), ¬을 보수(NOT)로 쓰는 대수가 불 대수다. 분배 법칙, 드모르간의 법칙, 흡수 법칙 a + ab = a 같은 규칙으로 식을 줄일 수 있다. 1938년 섀넌이 스위치 회로를 불 대수로 설계할 수 있음을 보이면서, 앞에서 본 논리가 곧 하드웨어가 되었다.

두 비트를 더하는 반가산기를 보자. 1 + 1 = 10₂이므로 결과는 두 비트, 자리의 합 S와 다음 자리로 넘기는 올림 C다. 진리표를 보면 S는 두 입력이 다를 때만 1(XOR), C는 둘 다 1일 때만 1(AND)이다. 아랫자리 올림까지 세 비트를 더하는 전가산기를 비트 수만큼 이어 붙이면 여러 자리 덧셈기가 된다. 4비트 덧셈기로 1011₂ + 0110₂(11 + 6)를 계산하면 17이 나온다. CPU의 산술 장치는 이런 게이트 수십억 개를 쌓은 것이다. 실제 칩의 게이트와 트랜지스터는 임베디드 노트에 있다.

무한의 크기: 대각선 논법

유한 집합의 크기는 세면 되지만 무한 집합은 어떻게 비교할까? 칸토어는 앞의 전단사로 정의했다. 두 집합의 원소를 하나씩 빠짐없이 짝지을 수 있으면 크기가 같다. 그러면 이상한 일이 생긴다. 자연수 0, 1, 2, 3, 4, …를 정수 0, 1, −1, 2, −2, …에 짝지을 수 있으므로 정수는 자연수와 개수가 같다. 짝수도, 유리수도 자연수와 짝지을 수 있다. 자연수와 짝지을 수 있는 집합을 가산 집합이라 한다.

그런데 0과 1로 된 무한 수열 전체(또는 0과 1 사이의 실수)는 가산이 아니다. 대각선 논법(귀류법)이다. 모든 수열을 1번, 2번, 3번, …으로 빠짐없이 나열한 목록이 있다고 하자. 1번 수열의 첫째 칸, 2번 수열의 둘째 칸, … 곧 대각선을 따라 읽으며 0과 1을 뒤집어 새 수열을 만든다. 이 수열은 i번 수열과 i번째 칸에서 반드시 다르므로 목록 어디에도 없다. "빠짐없이 나열했다"는 가정과 모순이다.

그래서 무한에도 크기가 다른 것들이 있다. 이 논증은 컴퓨터 과학에서 다시 나온다. 프로그램은 유한한 문자열이라 가산 개뿐인데, 자연수에서 0·1로 가는 함수(문제)는 셀 수 없이 많다. 따라서 어떤 프로그램으로도 풀 수 없는 문제가 반드시 있고, 튜링이 정지 문제가 결정 불가능함을 보인 증명도 같은 대각선 구조를 쓴다.

핵심 자료