[이산구조 개념-17] 영-일 행렬과 부울린 연산

1. 영-일 행렬 (Zero-One Matrix)이란

정의

모든 원소가 오직 0 또는 1로만 구성된 행렬.

0과 1의 의미

원소의미

0	거짓(False), 관계 없음, 연결 안 됨
1	참(True), 관계 있음, 연결됨

친구 관계 예시

4명의 친구 그룹: A, B, C, D A는 B, C와 친구. B는 A, D와 친구. C는 A와만 친구. D는 B와만 친구.

       A  B  C  D
   A [ 0  1  1  0 ]
   B [ 1  0  0  1 ]
   C [ 1  0  0  0 ]
   D [ 0  1  0  0 ]

→ aᵢ,ⱼ = 1 means "i와 j는 친구"

활용 분야 핵심

분야활용

관계(Relations) 표현	두 집합 원소 사이의 관계
방향 그래프	노드 간 방향성 연결
인접 행렬	그래프의 연결 정보
소셜 네트워크	팔로우/친구 관계
웹 그래프	페이지 간 링크
데이터베이스	다대다 관계 표현

💡 다음 단원 예고: 영-일 행렬은 곧 다룰 관계(Relation) 와 그래프(Graph) 단원의 핵심 표현 도구다. 17강이 그 가교 역할을 한다.

2. 왜 영-일 행렬에는 새로운 연산이 필요한가

문제점

영-일 행렬에 일반 산술 덧셈을 적용하면?

1 + 1 = 2 ❌

하지만 영-일 행렬에서는 0과 1만 허용된다. 결과가 2면 영-일 행렬이 아니다.

해결책

산술 연산(+, ×) 대신 논리 연산(∨, ∧) 을 사용한다.

산술 연산영-일 행렬 대응 논리 연산

+ (덧셈)	∨ (OR, 결합)
× (곱셈)	∧ (AND, 만남)

이렇게 하면 결과도 항상 0 또는 1로 유지된다 → 영-일 행렬 보존.

💡 본질적 통찰: 영-일 행렬은 단순한 행렬이 아니라 "논리의 행렬화" 다. 1~3강에서 배운 명제 논리가 행렬 차원으로 확장된 것.

3. 만남 연산 (Meet, ∧) ⭐

정의

두 영-일 행렬의 대응하는 위치 원소끼리 AND 연산을 적용.

표기

A ∧ B = [aᵢ,ⱼ ∧ bᵢ,ⱼ]

핵심 조건

반드시 같은 m × n 크기여야 연산 가능 (덧셈처럼)

AND 연산 규칙 (복습)

aba ∧ b

0	0	0
0	1	0
1	0	0
1	1	1

→ 둘 다 1일 때만 1

만남 계산 예제

A = [1 0 0; 1 1 0], B = [1 1 0; 1 1 1]

위치ABA ∧ B

(1,1)	1	1	1
(1,2)	0	1	0
(1,3)	0	0	0
(2,1)	1	1	1
(2,2)	1	1	1
(2,3)	0	1	0

A ∧ B = [ 1  0  0 ]
        [ 1  1  0 ]

만남의 의미

"두 관계가 동시에 성립하는 경우"만 살아남음.

실생활 예시

A = "수강 등록한 학생들", B = "수강료 납부한 학생들" → A ∧ B = "수강 등록 + 수강료 납부 모두 완료한 학생들"

4. 결합 연산 (Join, ∨) ⭐

정의

두 영-일 행렬의 대응하는 위치 원소끼리 OR 연산을 적용.

표기

A ∨ B = [aᵢ,ⱼ ∨ bᵢ,ⱼ]

OR 연산 규칙 (복습)

aba ∨ b

0	0	0
0	1	1
1	0	1
1	1	1

→ 하나라도 1이면 1

결합 계산 예제

A = [1 0 0; 1 1 0], B = [1 1 0; 1 1 1]

위치ABA ∨ B

(1,1)	1	1	1
(1,2)	0	1	1
(1,3)	0	0	0
(2,1)	1	1	1
(2,2)	1	1	1
(2,3)	0	1	1

A ∨ B = [ 1  1  0 ]
        [ 1  1  1 ]

결합의 의미

"두 관계 중 하나라도 성립하는 경우"가 모두 포함됨.

실생활 예시

A = "수학 동아리 회원", B = "코딩 동아리 회원" → A ∨ B = "수학 또는 코딩 동아리 회원" (둘 다 가능)

5. 만남 vs 결합 한눈에 비교

항목만남 (Meet, ∧)결합 (Join, ∨)

논리 연산	AND	OR
1이 되는 조건	둘 다 1	하나라도 1
의미	공통(교집합 역할)	합침(합집합 역할)
결과 행렬 크기	m × n (같음)	m × n (같음)
집합 연산 대응	∩ (교집합)	∪ (합집합)

💡 명제 논리 ↔ 집합 ↔ 영-일 행렬 3중 대응: AND ↔ ∩ ↔ ∧ (만남) OR ↔ ∪ ↔ ∨ (결합)

13강에서 배운 "명제 논리 = 집합론" 대응이 이제 영-일 행렬까지 확장된다.

6. 부울린 곱 (Boolean Product, A ⊙ B) ⭐⭐⭐ 시험 핵심

정의

일반 행렬 곱셈과 형태는 비슷하지만, 덧셈과 곱셈 자리에 논리 기호(∧와 ∨)를 이식한 돌연변이 연산.

일반 곱셈 vs 부울린 곱

항목일반 곱셈 (AB)부울린 곱 (A ⊙ B)

곱셈 자리	×	∧ (AND)
덧셈 자리	+	∨ (OR)
크기 조건	A의 열 = B의 행	동일
결과 크기	m × n	동일

부울린 곱 공식

cᵢ,ⱼ = (aᵢ,₁ ∧ b₁,ⱼ) ∨ (aᵢ,₂ ∧ b₂,ⱼ) ∨ ... ∨ (aᵢ,ₖ ∧ bₖ,ⱼ)

쉽게 말해: A의 i번째 행과 B의 j번째 열을 AND로 만난 결과들을 OR로 결합.

부울린 곱 계산 예제 ⭐

A = [1 0 1; 0 1 0] (2×3), B = [1 1 0; 0 1 1; 1 0 1] (3×3) 결과 크기: 2 × 3

c₁,₁ 계산 (1행 1열)

A의 1행: [1, 0, 1] B의 1열: [1, 0, 1]

단계식

1	(1 ∧ 1) ∨ (0 ∧ 0) ∨ (1 ∧ 1)
2	1 ∨ 0 ∨ 1
3	1

c₁,₂ 계산 (1행 2열)

A의 1행: [1, 0, 1] B의 2열: [1, 1, 0]

단계식

1	(1 ∧ 1) ∨ (0 ∧ 1) ∨ (1 ∧ 0)
2	1 ∨ 0 ∨ 0
3	1

c₁,₃ 계산 (1행 3열)

A의 1행: [1, 0, 1] B의 3열: [0, 1, 1]

단계식

1	(1 ∧ 0) ∨ (0 ∧ 1) ∨ (1 ∧ 1)
2	0 ∨ 0 ∨ 1
3	1

c₂,₁ 계산 (2행 1열)

A의 2행: [0, 1, 0] B의 1열: [1, 0, 1]

단계식

1	(0 ∧ 1) ∨ (1 ∧ 0) ∨ (0 ∧ 1)
2	0 ∨ 0 ∨ 0
3	0

c₂,₂, c₂,₃ 계산 (생략 — 같은 방식)

c₂,₂ = (0∧1) ∨ (1∧1) ∨ (0∧0) = 1 c₂,₃ = (0∧0) ∨ (1∧1) ∨ (0∧1) = 1

최종 결과

A ⊙ B = [ 1  1  1 ]
        [ 0  1  1 ]

💡 풀이 패턴: 일반 곱셈과 똑같이 진행하되, 곱은 ∧로, 합은 ∨로 바꾸기만 하면 된다. 16강의 일반 곱셈에 익숙하면 어렵지 않다.

7. 부울린 곱 알고리즘과 시간 복잡도

알고리즘 구조 (3중 루프)

for i := 1 to m       (각 행)
  for j := 1 to n     (각 열)
    cᵢⱼ := 0
    for q := 1 to k   (내적 계산)
      cᵢⱼ := cᵢⱼ ∨ (aᵢ,q ∧ bq,j)

시간 복잡도

Θ(mnk) — 일반 행렬 곱셈과 동일

특히 정방 영-일 행렬(n × n)의 부울린 곱은 Θ(n³).

💡 함의: 부울린 곱도 일반 곱셈만큼 비싼 연산이다. 그래프에서 노드 수가 1000개라면 한 번의 부울린 곱에 약 10억 번의 논리 연산이 필요하다.

8. 부울린 곱의 진짜 의미 — 그래프 경로 찾기 ⭐

부울린 곱이 왜 중요한가? 그래프에서 경로 존재 여부를 판단하기 때문이다.

핵심 통찰

영-일 행렬 A가 그래프의 인접 행렬이라면: (A ⊙ A)의 (i, j) 원소가 1이면, i에서 j로 가는 길이 2의 경로가 존재

구체적 예시

A = "직접 친구 관계" (1단계) A ⊙ A = "친구의 친구" (2단계 경로)

단계의미

A	1단계로 도달 가능 (직접 연결)
A ⊙ A	2단계로 도달 가능 (친구의 친구)
A ⊙ A ⊙ A	3단계로 도달 가능

케빈 베이컨의 6단계 비유

"세상의 모든 사람은 6단계 안에 연결되어 있다"는 가설. 이것을 수학적으로 검증하려면? A^[6] 의 모든 원소가 1인지 확인하면 된다!

💡 응용: 페이스북의 "내가 아는 사람"(People You May Know) 추천, LinkedIn의 "1차/2차/3차 연결" 기능, Google PageRank 알고리즘 — 모두 부울린 곱의 응용이다.

9. 부울린 거듭제곱 (Boolean Power, A^[k]) ⭐⭐⭐

정의

정사각 영-일 행렬 A를 자신과 k번 부울린 곱(⊙) 한 결과.

표기 ⚠️ 중요

A^[k] ← 대괄호 사용 (일반 거듭제곱 Aᵏ과 구분)

대괄호로 표기하는 이유: 일반 행렬 거듭제곱과 헷갈리지 않기 위함.

0승 규칙

A^[0] = Iₙ (항등 행렬)

부울린 거듭제곱의 의미

A^[k]의 (i, j) 원소가 1 ⟺ i에서 j로 가는 길이가 k인 경로가 존재

거듭제곱별 의미

부울린 거듭제곱의미

A^[1] = A	직접 연결 (길이 1)
A^[2]	길이 2 경로 (친구의 친구)
A^[3]	길이 3 경로
A^[k]	길이 k 경로

포화 상태 (Saturation)

어느 순간부터 A^[k]가 더 이상 변하지 않는 포화 상태에 도달한다.

왜 그런가?

노드 수가 n인 그래프에서, 두 노드 간 최단 경로는 최대 n−1. 따라서 k가 충분히 커지면 더 이상 새로운 경로가 발견되지 않는다.

부울린 거듭제곱 활용 예시

A^[1], A^[2], A^[3], ...을 차례로 계산하면 어느 순간부터 결과가 동일해진다 → 모든 도달 가능 관계 발견 완료

💡 컴퓨터 과학 응용: A ∨ A^[2] ∨ A^[3] ∨ ... ∨ A^[n−1] 을 계산하면 "임의 길이의 경로로 도달 가능한지"를 판단할 수 있다. 이를 연결성 행렬(Connectivity Matrix) 또는 추이 폐포(Transitive Closure) 라고 한다 (다음 관계 단원의 핵심 개념).

10. 일반 행렬 vs 영-일 행렬 종합 비교 ⭐

항목일반 행렬영-일 행렬

원소	모든 숫자	0 또는 1만
덧셈	+	∨ (결합)
곱셈	×	∧ (만남)
행렬 곱셈	AB	A ⊙ B (부울린 곱)
거듭제곱	Aᵖ	A^[k] (부울린 거듭제곱)
응용	컴퓨터 그래픽, 머신러닝	관계, 그래프, 네트워크
의미	수치 변환	관계의 존재/연결

두 세계의 통일된 패턴

일반영-일

AB의 (i,j) = A의 i행과 B의 j열의 수치적 내적	A⊙B의 (i,j) = A의 i행과 B의 j열의 논리적 내적
Aᵖ = p번 곱셈 → 변환 누적	A^[k] = k번 부울린 곱 → 길이 k 경로

💡 두 세계는 완전히 같은 구조이지만, 사용하는 연산만 다르다. 16강을 잘 익혔다면 17강은 자동으로 따라온다.

11. 영-일 행렬과 1~13강의 거대한 연결고리

지금까지 배운 모든 개념이 영-일 행렬에서 만난다.

3중 대응 정리

명제 논리 (1~3강)집합론 (12~13강)영-일 행렬 (17강)

∧ (AND)	∩ (교집합)	∧ (만남)
∨ (OR)	∪ (합집합)	∨ (결합)
¬ (NOT)	¯ (여집합)	(행렬에서 0↔1 뒤집기)
T (참)	U (전체)	(모든 원소 1)
F (거짓)	∅ (공집합)	(모든 원소 0)

💡 이산구조의 통합 비전: 명제 논리, 집합론, 행렬, 영-일 행렬, 그리고 곧 다룰 관계와 그래프까지 — 모두 같은 수학적 본질을 다른 옷을 입고 표현한 것이다. 이것이 이산구조를 "수학적 구조의 통일 이론"이라 부르는 이유다.

📌 한눈에 보는 핵심정리

개념핵심

영-일 행렬	원소가 0 또는 1만, 관계·그래프 표현
0과 1의 의미	0 = 관계 없음, 1 = 관계 있음
만남 (Meet, ∧)	원소별 AND, 둘 다 1일 때만 1
결합 (Join, ∨)	원소별 OR, 하나라도 1이면 1
만남·결합 조건	같은 m × n 크기 필수
부울린 곱 (A ⊙ B)	일반 곱셈에서 ×→∧, +→∨로 치환
부울린 곱 크기 조건	일반 곱셈과 동일 (안쪽 차원 일치)
시간 복잡도	Θ(mnk), 정방행렬 Θ(n³)
부울린 곱의 의미	A⊙A = 길이 2 경로 존재 여부
부울린 거듭제곱	A^[k], 길이 k 경로
표기 주의	대괄호 [k] 사용 (일반 거듭제곱과 구분)
A^[0]	항등 행렬 Iₙ
포화 상태	어느 순간부터 결과 동일 (도달 완료)

🧠 예상문제 2제

문제 1. 만남과 결합 연산

영-일 행렬 A = [1 0; 1 1], B = [0 1; 1 0]일 때, A ∧ B와 A ∨ B를 모두 올바르게 구한 것은?

① A ∧ B = [0 0; 1 0], A ∨ B = [1 1; 1 1] ② A ∧ B = [0 1; 1 0], A ∨ B = [1 0; 1 1] ③ A ∧ B = [1 1; 1 1], A ∨ B = [0 0; 1 0] ④ A ∧ B = [1 0; 1 1], A ∨ B = [0 1; 1 0]

👉 정답: ①

A ∧ B 계산 (AND)

위치ABA ∧ B

(1,1)	1	0	0 (둘 다 1 아님)
(1,2)	0	1	0 (둘 다 1 아님)
(2,1)	1	1	1 (둘 다 1)
(2,2)	1	0	0 (둘 다 1 아님)

→ A ∧ B = [0 0; 1 0] ✅

A ∨ B 계산 (OR)

위치ABA ∨ B

(1,1)	1	0	1
(1,2)	0	1	1
(2,1)	1	1	1
(2,2)	1	0	1

→ A ∨ B = [1 1; 1 1] ✅

💡 시험 풀이 팁: 영-일 행렬 연산은 위치별로 천천히 한 칸씩 풀자. AND는 둘 다 1, OR는 하나라도 1만 기억하면 된다. 4×4 행렬도 같은 방식으로 16칸을 채우면 끝.

문제 2. 부울린 곱 적용

영-일 행렬 A = [1 0; 1 1]을 자기 자신과 부울린 곱한 A ⊙ A의 값은?

① [1 0; 1 1] ② [1 0; 0 1] ③ [1 1; 1 1] ④ [0 1; 1 0]