카르노맵 위의 4변수 부울 함수 공간의 군론적 분류

초록 / Abstract

본 논문은 4변수 카르노맵 위의 부울 함수 공간 F₄를 변수 순열군 S₄, 입력 반전군 Z₂⁴, 이 둘이 이루는 부호 순열군 B₄ = Z₂⁴ ⋊ S₄와 그 부분군인 카르노맵의 격자 대칭군 W의 작용으로 분류한다. 필요한 정의와 증명을 본문에 싣는 것을 목표로 하는 논문이며, 일부 수치(궤도 크기 분포, 그림 종류별 함수 개수)는 컴퓨터로 수행한 유한 계산이다. 주요 결과: 변수 배치 동치류 $24 \to 3$, 대칭 부울 함수 $2^5 = 32$개, 아핀 함수 10궤도 · 단조 함수 30궤도 · 자기쌍대 함수 32궤도 · 전체 F₄ 3,984궤도 (S₄ 작용). S₄와 격자 평면 대칭 D₄^grid(회전·반사 8개)가 생성하는 합성군 B₄(크기 384) 하에서는 전체 F₄ 402궤도 · 아핀 6궤도 · 자기쌍대 7궤도. 본문의 수치는 Burnside 보조정리의 계산과 저자가 작성한 Python 전수 열거의 출력을 서로 대조했다.

핵심 개념: 변수 배치 동치류 Hamming Layer S₄ 궤도 (Burnside) B₄ 합성군

🔑 핵심 정리 / Key Theorems

정리 1 — 변수 배치 동치류 (격자 대칭 W, 위수 128)

$|\mathcal{E}| = \dfrac{\binom{4}{2}}{2} = 3$

24개 배치 → 격자 대칭 W(위수 128)가 배치에 일으키는 변환(위수 8의 이면체군, 자유 작용) → 3개 동치류 (AB/CD, AC/BD, AD/BC). 토러스 이동 없이 격자 평면 대칭 D₄^grid 8개만 쓰면 12개로 갈라진다. 그림의 행·열 구조를 보존하는 W 대신 B₄ 전체를 허용하면 모든 배치가 한 동치류가 되어 구분이 사라진다.

§4 — 완전 대칭 함수

$|\text{Sym}_4| = 2^5 = 32$

Hamming weight 5개 레이어 × 독립적 0/1 선택

§5 — S₄ 궤도 분류 (Burnside)

전체 F₄: 3,984궤도 · 아핀: 10 · 단조: 30 · 자기쌍대: 32

Fix 표 전부 수록, 단조 30궤도 완전 목록 포함, Python 전수 열거와 대조

§5.5 — 자기쌍대 ∩ 완전 대칭 = ∅

$D \cap \mathcal{S}_4 = \emptyset$

완전 대칭이면서 자기쌍대이려면 $v_{4-k} = \neg v_k$인데 $k = 2$에서 $v_2 = \neg v_2$가 되어 모순

정리 2·3 — 합성군 ⟨S₄, D₄^grid⟩ = B₄

$G = \langle S_4, D_4^{\mathrm{grid}} \rangle = B_4 = \mathbb{Z}_2^4 \rtimes S_4$, $|G| = 384$ · F₄: 402궤도 · 아핀 6 · 자기쌍대 7

직접곱이 아님 (두 군은 가환하지 않고 |D₄^grid ∩ S₄| = 2). 20개 켤레류 Burnside로 증명 + 전수 열거 검증

명제 2 — 패리티와 체커보드

Gray 축 순서에서 4변수 XOR의 그림은 체커보드, 이진 축 순서에서는 이중대각

Gray 인접 셀은 한 비트만 달라 해밍 무게의 홀짝이 반전됨. 대칭 함수의 그림은 24개 변수 배치에서 모두 같음(명제 1)

정리 4 — 카르노맵 그림의 대칭과 종류

시각 대칭 = $W$ 안정화군의 원소 · 그림 종류 수 = $B_4$-궤도 안의 $W$-궤도 수 (1, 2, 3)

함수 3,220 / 36,204 / 26,112개가 각각 1 / 2 / 3종의 그림을 가짐 (전수 열거와 일치)

정리 5 — 그림 종류 수의 판정

그림 종류 수 = 안정화군 $H_f$의 $S_3$ 상이 세 변수쌍 분할에 작용할 때의 궤도 수 (자명 → 3종, 위수 2 → 2종, 위수 6 → 1종)

$W \backslash B_4 / H_f$의 개수 = $H_f$의 $B_4/W$ 위 궤도 수. 402개 궤도 전부에서 열거와 일치

따름정리 6 — 위수 3인 상은 없다

안정화군의 $S_3$ 상은 위수 1, 2, 6 중 하나. 3-순환을 포함하면 상 = $S_3$ (그림 1종)

위수 3 원소는 부호 벡터 공액으로 순수 3-순환과 켤레이고, 세 좌표 위에서 $C_3$-궤도 = $S_3$-궤도(해밍 무게별)이므로 3-순환 불변이면 호환 불변

개수의 유도 — 포함·배제와 뫼비우스

그림 1/2/3종 함수: 3,220 / 36,204 / 26,112 · 단조 궤도 크기 1, 3, 4, 6, 12: 6, 2, 9, 6, 7개 · $\mathrm{Fix}_M((12)(34)) = 28$

군 폐포 위 포함·배제로 $N_6 = 3{,}220$, $N_{\ge 2} = 39{,}424$ ($S_4$ 부분군 30개 위 뫼비우스로 단조 안정화군 위수별 개수). 계산은 컴퓨터로 수행한 유한 계산(닫힌 식 아님)

참고 — 알려진 값과의 관계

3,984(A003180) · 402(Slepian 1953) · 단조 30, 210(A003182)은 문헌에 있는 값의 독립 재계산

새로움은 카르노맵 격자 대칭군 $W$의 식별과 그림 종류 수(정리 1, 4, 5)에 한정됨. 선행 연구 조사는 제한적임

🖼️ 그림 / Figures

Gray 순서와 표준 카르노맵 (2.2절)

2비트 Gray code 00, 01, 11, 10의 순환 순서 — 그림 1. 2비트 Gray code $00 \to 01 \to 11 \to 10 \to 00$. 이웃한 라벨은 한 비트만 다르고, 마지막과 처음도 한 비트만 다르다.

표준 배치 AB/CD의 카르노맵, 좌상단 칸만 1 — 그림 2. 배치 $AB/CD$의 카르노맵. 좌상단 칸이 입력 $0000$. 민텀 $m_0$만 1인 함수 $E_0$의 그림.

변수 쌍의 맞교환 = 위치 1과 3의 줄 교환 (3.2절, 보조정리 1)

XY와 YX 라벨 대응표 — 그림 3 (표). $XY$와 $YX$의 라벨 대응. $01$과 $10$이 서로 바뀐다.

행 변수를 맞바꾸면 위치 1과 3의 행이 바뀐다 — 그림 3 (그림). 행 변수 $X, Y$ 맞교환. 같은 색은 원래 같은 행. $YX$ 배치에서 위치 $1$과 $3$의 행이 바뀐다.

ZW와 WZ 라벨 대응표 — 그림 4 (표). $ZW$와 $WZ$의 라벨 대응.

열 변수를 맞바꾸면 위치 1과 3의 열이 바뀐다 — 그림 4 (그림). 열 변수 $Z, W$ 맞교환. 행 대신 열이 바뀐다.

패리티 함수: Gray 축은 체커보드, 이진 축은 이중대각 (3.5절, 명제 2)

XOR, Gray 축 순서, 체커보드 — 그림 5. XOR, Gray 축 순서 (체커보드).

XOR, 이진 축 순서, 이중대각 — 그림 5. XOR, 이진 축 순서 (이중대각).

레이어와 기저 함수 $E_k$ (4.2~4.3절, 명제 1: 24개 배치에서 모두 같은 그림)

칸별 레이어 L1부터 L5 — 그림 6. 칸별 레이어. 그림의 $L1 \dots L5$는 본문의 $L_0 \dots L_4$ (해밍 무게 $0 \dots 4$).

E0, Exactly-0의 그림 — 그림 7. $E_0$ (Exactly-0).

E1, Exactly-1의 그림 — 그림 7. $E_1$ (Exactly-1).

E2, Exactly-2의 그림 — 그림 7. $E_2$ (Exactly-2).

E3, Exactly-3의 그림 — 그림 7. $E_3$ (Exactly-3).

E4, Exactly-4의 그림 — 그림 7. $E_4$ (Exactly-4).

배치에 따라 그림이 달라지는 예 (6.5절, 정리 4·5)

m(5,6,9,10)의 AB/CD 배치 그림 — 그림 8. $f = m(5,6,9,10)$, 배치 $AB/CD$.

m(5,6,9,10)의 AC/BD 배치 그림 — 그림 8. 같은 $f$, 배치 $AC/BD$.

m(5,6,9,10)의 AD/BC 배치 그림 — 그림 8. 같은 $f$, 배치 $AD/BC$ ($AC/BD$와 같은 그림). 그림 종류 2, $|\mathrm{Stab}_W| = 32$.

m(0,6,9,15)의 AB/CD 배치 그림 — 그림 9. $f = m(0,6,9,15)$, 배치 $AB/CD$.

m(0,6,9,15)의 AC/BD 배치 그림 — 그림 9. 같은 $f$, 배치 $AC/BD$ ($AB/CD$와 같은 그림).

m(0,6,9,15)의 AD/BC 배치 그림 — 그림 9. 같은 $f$, 배치 $AD/BC$. 그림 종류 2, $|\mathrm{Stab}_W| = 16$.

📊 Hamming Weight 레이어 구조

L₀

weight = 0

1개 입력

L₁

weight = 1

4개 입력

L₂

weight = 2

6개 입력

L₃

weight = 3

4개 입력

L₄

weight = 4

1개 입력

완전 대칭 함수 = 각 레이어에 0/1을 독립 할당 → $2^5 = 32$개

🔵 S₄ 궤도 분류 요약

공간	생성 게이트	원소 수	S₄ 궤도 수	수학적 구조	검증 방법
아핀 L	XOR, 상수 1	32	10	아핀 함수 공간 (F₂ 위 벡터 공간)	Burnside + Python
단조 M	AND, OR, 상수 0·1	168	30	단조 부울 함수	Burnside + Python
자기쌍대 D	NOT, 3입력 다수결 MAJ₃	256	32	자기쌍대 함수 ($f(\neg\mathbf{x}) = \neg f(\mathbf{x})$)	Burnside + Python
전체 F₄	ALL	65,536	3,984	4변수 부울 함수 전공간 (합성군 G 하에서는 402궤도)	Burnside + Python

🗂️ 변수 배치 동치류 (격자 대칭 W)

동치류 ε₁

AB/CD

AB/CD, BA/CD, AB/DC, BA/DC, CD/AB … (8개 배치)

동치류 ε₂

AC/BD

AC/BD, CA/BD, AC/DB, CA/DB, BD/AC … (8개 배치)

동치류 ε₃

AD/BC

AD/BC, DA/BC, AD/CB, DA/CB, BC/AD … (8개 배치)

🔗 대칭군 관계도

격자 대칭 W (위수 128)
변수 배치 24→3 동치류

⊂

B₄ = ⟨S₄, W⟩ (위수 384)
전체 F₄ 402궤도

⊃

S₄ 변수 순열 (위수 24)
B₄의 부분군 · 전체 F₄ 3,984궤도

↕

Hamming Weight
S₄-고정 함수 = 대칭 함수 32개

아핀 L
S₄ 10궤도

·

단조 M
S₄ 30궤도

·

자기쌍대 D
S₄ 32궤도

📋 인용 / Citation

@misc{choi2026karnaughgroupclassification,
  author       = {Choi, Jonghun},
  title        = {Group-Theoretic Classification of 4-Variable Boolean Function Spaces on Karnaugh Maps},
  howpublished = {Independent Mathematics Research Program Preprint},
  year      = {2026},
  url       = {https://github.com/inha20/7KarnaughGroupClassification}
}