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

**Group-Theoretic Classification of 4-Variable Boolean Function Spaces on Karnaugh Maps**

**저자:** 최종훈 (Jonghun Choi)  
인하공업전문대학 2학년 재학 · 독립 연구자  
**연락처:** cjh3cjh@naver.com  
**GitHub:** [github.com/inha20/7KarnaughGroupClassification](https://github.com/inha20/7KarnaughGroupClassification)  

---

## 초록 / Abstract

4변수 부울 함수 공간 $\mathcal{F}_4$ ($|\mathcal{F}_4| = 2^{16} = 65{,}536$)에는 서로 다른 세 종류의 대칭이 작용한다. (i) 변수의 이름을 바꾸는 순열군 $S_4$, (ii) 입력 비트를 뒤집는 반전군 $\mathbb{Z}_2^4$, (iii) 카르노맵 평면의 격자 대칭이다. 본 논문은 이 대칭들의 관계를 정리하고 각각이 만드는 궤도(동치류)의 개수를 모두 계산하며, 아핀 함수(10개 궤도)와 단조 함수(30개 궤도)는 궤도의 목록까지 제시한다. 이 논문은 필요한 정의와 증명을 본문에 싣는 것을 목표로 한다. 요구하는 배경은 군론의 기초(군의 작용, 부분군의 지표, 반직접곱, 켤레류)와 Burnside 보조정리이다. 일부 수치(5.5절의 궤도 크기 분포, 6.5절의 그림 종류별 함수 개수)는 컴퓨터로 수행한 유한 계산이며, 본문에 계산 방법을 적고 값은 스크립트로 재현한다.

주요 결과는 다음과 같다.
1. **변수 배치.** 4변수 카르노맵에 변수를 배치하는 방법 $4! = 24$가지는 카르노맵의 격자 대칭군 $W$ (위수 128; 행과 열 각각의 이동·반사와 행·열 맞바꿈이 만드는 군, 3.2절)에 의해 정확히 3개의 동치류 $\lbrace AB|CD\rbrace$, $\lbrace AC|BD\rbrace$, $\lbrace AD|BC\rbrace$로 나뉜다. $W$는 입력 반전과 변수 순열이 이루는 군 $B_4 = \mathbb{Z}_2^4 \rtimes S_4$ (위수 384)에서 변수 쌍 분할 하나의 안정화군이며 지표가 3이다.
2. **그림의 불변성.** 완전 대칭 함수(XOR, 다수결 등 32개)의 카르노맵 그림은 24개 배치 모두에서 동일하다. 배치에 따라 그림이 달라지는 것은 비대칭 함수이며, 전체 중 26,112개는 세 동치류에서 서로 다른 그림이 된다.
3. **$S_4$ 궤도 분류.** 전체 공간은 3,984개, 아핀 함수 32개는 10개, 단조 함수 168개는 30개, 자기쌍대 함수 256개는 32개의 궤도로 분할된다. 각 Burnside 계산의 Fix 값을 모두 제시한다.
4. **합성군.** $S_4$와 격자 대칭이 생성하는 군은 직접곱이 아니라 $B_4$이며, 이 군 아래에서 $\mathcal{F}_4$는 402개, 아핀 공간은 6개, 자기쌍대 공간은 7개의 궤도로 분할된다. 3,984, 30, 402는 문헌(OEIS, 곧 정수열 온라인 백과사전의 수열 A003180, A003182, A000616)에 알려진 값과 일치하는 독립 재계산이다.

본문의 수치는 저자가 작성한 전수 열거 스크립트(1.4절)의 출력과 대조했다. 이론 계산과 스크립트는 같은 저자의 작업이므로 외부 검증은 아니다.

**주제어:** 카르노맵, 부울 함수 공간, 변수 배치 동치류, $S_4$ 대칭군, 부호 순열군, 번사이드 보조정리, Hamming Weight 레이어, 궤도 분류, Post의 격자

---

## 1. 서론 (Introduction)

### 1.1 연구 배경과 문제
카르노맵(Karnaugh, 1953)은 논리식의 곱의 합(SOP) 표현을 최소화하는 도구로 널리 쓰인다. 인접한 셀의 입력이 정확히 한 비트만 다르도록 Gray code (Gray, 1953) 순서로 입력을 $4 \times 4$ 격자에 배열하면, 인접한 셀 묶음으로 공통 변수를 소거할 수 있다. 이 도표는 Veitch (1952)의 차트를 개량한 것으로, Veitch의 차트가 입력을 이진수 순서로 배열한 데 비해 Karnaugh는 Gray code 순서를 쓴다 (이 순서의 차이는 3.5절의 명제 2에서 다시 나온다). 스위칭 회로에 부울 대수를 적용한 것은 Shannon (1938)이고, 논리식 최소화의 알고리즘적 방법은 Quine (1952)과 McCluskey (1956)에 있다. 그러나 카르노맵은 단순한 표가 아니라 수학적 구조를 가진다.

1. 격자의 양끝(첫 행과 마지막 행, 첫 열과 마지막 열)도 한 비트 차이이므로 인접하다. 4변수 카르노맵의 인접 그래프는 $4 \times 4$ 이산 토러스, 곧 4-순환 그래프 $C_4$ 둘의 데카르트 곱 $C_4 \thinspace\square\thinspace C_4$이고, 이는 4차원 초입방체 $Q_4 = \mathbb{Z}_2^4$의 인접 그래프와 동형이다.
2. 변수 $A, B, C, D$를 행과 열에 배치하는 방법은 $4! = 24$가지인데, 교재가 제시하는 $AB/CD$는 하나의 선택일 뿐이다. 배치를 바꾸면 같은 함수의 그림이 달라질 수 있다. 어떤 배치들이 본질적으로 같은가?
3. 65,536개의 함수 중 어떤 것들이 변수 이름을 바꾸거나 입력을 반전해도 같은 구조인가? 이를 세는 것이 궤도 분류 문제이다. 배치를 바꾸는 것은 함수에 변수 순열을 적용하는 것과 같으므로(6.5절), 위 2의 배치 문제는 이 궤도 분류 문제의 한 조각이다.

### 1.2 관련 연구와 본 논문의 위치
- **고전적 계수 결과.** 부울 함수를 입력 변수의 순열(P), 입력의 반전(N), 출력의 반전(N)으로 분류하는 문제는 스위칭 이론의 고전적 주제이다. 입력의 순열과 반전을 허용한 동치류를 NP류, 여기에 출력의 반전까지 허용한 동치류를 NPN류라 한다. NP류의 개수는 Slepian (1953)이 구했고, Pólya (1937)의 계수 이론과 Harrison (1963, 1971)이 이를 일반화했다. Golomb (1959)도 이 분류 문제를 다룬다. 4변수에서 NP 동치류는 402개(OEIS A000616), NPN 동치류는 222개(A000370)로 알려져 있다. 본 논문의 $B_4$-궤도가 NP류이다(6.3절). 변수 순열군 $S_n$만의 작용 아래 4변수 함수의 궤도 수 3,984는 A003180에 있다. 따라서 **본 논문의 3,984와 402는 새 결과가 아니라 독립 재계산이며**, 우리의 Fix 표가 이 값들을 재현한다는 점이 검증이다.
- **단조 함수.** 변수 순열 아래 비동치 단조 함수의 개수 30($n=4$)과 210($n=5$)은 A003182에 있다(2, 3, 5, 10, 30, 210, 16353, …). 이는 Dedekind 수의 동치류 버전이다. 단조 함수의 총수(Dedekind 수)는 Dedekind (1897)가 처음 다루었고, 5변수 자유 분배 격자의 크기는 Church (1940)가 계산했다(상수 두 개를 더하면 7,581). $n=7$까지의 동치류 계산이 Stephen와 Yusun (2012)에 있다. 따라서 30과 210 역시 새 수치가 아니다. 본 논문이 추가하는 것은 30개 궤도의 명시적 목록과 궤도 크기 분포(5.5절)와 Fix 값이다.
- **클론.** Post (1941)는 부울 함수 집합 중 합성과 변수 식별에 닫힌 것(클론)의 격자 전체를 분류하였다(현대적 개관은 Böhler 외, 2003). 본 논문이 다루는 아핀, 단조, 자기쌍대 함수는 그 대표적인 클론이다. 이 클론들 각각의 개수는 알려져 있으나(예: 자기쌍대 단조 함수 개수는 A001206), 자기쌍대 함수의 $S_n$-궤도 수(4변수에서 32)와 아핀 함수의 궤도 수는 우리가 검색한 범위에서 문헌 값을 찾지 못했다.
- **초입방체의 대칭.** 카르노맵의 인접 그래프가 $Q_4$와 동형이므로(1.1절) 그 자기동형군은 $Q_4$의 자기동형군, 곧 부호 순열군 $B_4 = \mathbb{Z}_2^4 \rtimes S_4$ (위수 $2^4 \cdot 4! = 384$)이다. $Q_n$의 자기동형군이 위수 $2^n n!$의 초팔면체군이라는 사실은 고전적이다 (Coxeter, 1973; Harary, Hayes & Wu, 1988; Humphreys, 1990). 이 사실 자체는 새롭지 않으며, 본 논문은 카르노맵의 격자 대칭(3.2절의 $W$)이 이 군의 지표 3인 부분군임을 보인다.
- **본 논문의 기여**는 다음과 같이 한정한다. (a) 카르노맵의 격자 대칭을 $B_4$의 부분군 $W$로 식별하고 변수 배치 24가지가 3개의 동치류로 나뉨을 이 군의 지표 3으로 설명한다(정리 1). 정리 1의 "3"은 네 변수를 두 쌍으로 나누는 방법의 수와 같은 사실이며(3.3절의 주), 새로운 점은 격자 대칭을 $B_4$의 부분군으로 식별하여 이 사실을 $B_4/W$의 크기로 설명하고 6.5절의 그림 종류 계산으로 잇는 데 있다. (b) 카르노맵 그림이 배치에 따라 몇 가지로 달라지는지를 $B_4$-궤도가 $W$-궤도로 쪼개지는 수로 환원하고 전수 계산한다(정리 4). (c) 위 고전적 수치들을 한 틀(Burnside 표)에서 재현하고, 클론별 궤도 구조와 목록을 명시한다. (a), (b)는 카르노맵 모델에 특화된 내용이라 우리가 검색한 범위에서 선행 문헌을 찾지 못했다. 다만 문헌 검색은 제한적이었으므로 이는 선행 연구가 없다는 주장이 아니다.

### 1.3 논문의 구성
2장은 기호와 도구를 정의한다. 3장은 변수 배치와 격자 대칭을 다룬다. 4장은 완전 대칭 함수를 분류한다. 5장은 $S_4$ 궤도를 계산한다. 6장은 합성군과 그 궤도를 계산한다. 7장은 한계와 향후 과제를 논한다.

### 1.4 재현성
이 논문의 GitHub 저장소(github.com/inha20/7KarnaughGroupClassification)의 `scripts/`에 있는 표준 라이브러리 전용 Python 스크립트가 본문의 수치를 열거로 대조한다. 스크립트는 논문에 싣지 않았다. 본문의 "(`verify_*.py`로 확인)"은 해당 스크립트의 출력이 그 값과 일치한다는 뜻이다.

| 스크립트 | 검증 내용 |
|:---|:---|
| `verify_orbits.py` | 5장: $S_4$ 궤도 수(열거 및 Burnside) |
| `verify_tables.py` | 5장: Fix 표, 궤도 크기 분포, 안정화군의 위수, 그림 비교 |
| `verify_double_action.py` | 3, 6장: 격자 대칭과의 합성군의 크기와 궤도 수 |
| `verify_b4_table.py` | 6장: $B_4$ 켤레류 표와 전수 열거 대조 |
| `verify_pictures.py` | 3.5절: 세 배치의 그림 비교 전수 탐색 |
| `verify_extras.py` | 3.5절 명제 2, 5.5절 단조 30궤도 목록, 5.6절 $L \cap M$, 6.5절 정리 4, 7.3절 $n=5$ 예비 결과 |
| `verify_picture_criterion.py` | 6.3절 부호 순환의 점 순환 분포, 6.5절 정리 5와 따름정리 6 |
| `verify_monotone_fix.py` | 5.3절 단조 Fix 값 = 궤도 순서집합의 상집합 수 |
| `verify_stabilizer_counts.py` | 5.5절 단조 궤도 크기 분포(뫼비우스), 6.5절 그림 종류별 함수 개수(포함·배제) |
| `verify_figures.py` | 그림 1~9: 그림의 격자 값이 본문이 말하는 함수·배치·축 순서와 일치하는지 대조 |
| `verify_clone_generators.py` | 5.3절: 아핀·단조·자기쌍대 함수가 각각 XOR과 상수 1 / AND, OR와 상수 / NOT과 3입력 다수결로 생성됨 |

---

## 2. 준비: 부울 함수, 카르노맵, 군

### 2.1 부울 함수 공간
입력점 $\mathbf{x} = (x_1, x_2, x_3, x_4) \in \mathbb{Z}_2^4$는 16개이다. 부울 함수 $f: \mathbb{Z}_2^4 \to \mathbb{Z}_2$는 16개 입력점에서의 값으로 결정되므로, 16비트 정수로 표현되고 $\mathcal{F}_4$의 크기는 $2^{16} = 65{,}536$이다. 변수는 $A = x_1$, $B = x_2$, $C = x_3$, $D = x_4$로 쓴다. 민텀 $m_i$는 입력이 정수 $i$의 4비트 이진 표현($x_1$이 최상위 비트)일 때만 1인 함수이고, $m(i, j, \dots)$ 또는 $\sum m(i, j, \dots)$는 이들의 합(OR)이다. 예를 들어 $m_8 = A\thinspace\overline{B}\thinspace\overline{C}\thinspace\overline{D}$이다.

### 2.2 카르노맵 모델
2비트 Gray code는 $00 \to 01 \to 11 \to 10$이며, 이를 인덱스 $0, 1, 2, 3$에 대응시킨다. 변수 쌍 $(X, Y)$가 행을, 쌍 $(Z, W)$가 열을 담당하는 배치를 $XY/ZW$로 쓴다. 입력 $\mathbf{x}$는 셀 $(i, j)$에 놓이며, $(x_X, x_Y)$는 행 인덱스 $i$의 Gray 라벨, $(x_Z, x_W)$는 열 인덱스 $j$의 Gray 라벨이다. 인덱스 $0$과 $3$의 라벨 $00$, $10$은 한 비트만 다르므로 격자의 양끝도 인접하다. 따라서 카르노맵의 인접 구조는 토러스이다. (여기서 $W$는 변수 이름이며, 3.2절부터 쓰는 격자 대칭군 $W$와 다르다. 이 논문에서는 $L$이 아핀 함수의 집합과 4.2절의 레이어에, $D$가 자기쌍대 함수의 집합과 변수 $D$에, $C_k$가 켤레류와 순환 그래프에 쓰이며 모두 문맥으로 구분한다.)

![그림 1. 2비트 Gray code의 순환 순서](../images/fig02_gray_cycle.png)

**그림 1.** 2비트 Gray code $00 \to 01 \to 11 \to 10 \to 00$. 이웃한 라벨은 한 비트만 다르고 (화살표 위의 기호는 두 라벨이 공유하는 비트), 마지막 $10$과 처음 $00$도 한 비트만 다르다.

![그림 2. 표준 배치 AB/CD의 카르노맵](../images/fig01_kmap_exactly0.png)

**그림 2.** 표준 배치 $AB/CD$의 카르노맵 (행은 $AB$, 열은 $CD$, 라벨은 $00, 01, 11, 10$ 순서). 좌상단 칸이 입력 $0000$이다. 그림은 민텀 $m_0$만 1인 함수, 곧 4.3절의 $E_0$ (Exactly-0)의 그림이다.

### 2.3 군과 작용
- **변수 순열군** $S_4$: $\pi \in S_4$는 입력점에 $(\pi\mathbf{x})_i = x _{\pi(i)}$로 작용한다 ($|S_4| = 24$). 이 정의는 합성 순서가 뒤집히는 오른쪽 작용이지만, 궤도와 고정점의 수와 안정화군은 왼쪽 작용으로 읽어도 달라지지 않는다.
- **입력 반전군** $N = \lbrace(\mathrm{id}, c) : c \in \mathbb{Z}_2^4\rbrace \cong \mathbb{Z}_2^4$: $(\mathbf{x} \mapsto \mathbf{x} \oplus c)$.
- **부호 순열군** $B_4$ (일반의 $n$에 대해 $B_n = \mathbb Z_2^n \rtimes S_n$, 위수 $2^n n!$; 초팔면체군이라고도 한다): 위 두 가지를 합성한 사상 $(\pi, c): \mathbf{x} \mapsto (x_{\pi(1)} \oplus c_1, \dots, x_{\pi(4)} \oplus c_4)$ 전체이다. $N$은 $B_4$의 정규부분군이고 $S_4$는 $N$의 여군(complement, $N \cap S_4 = 1$이고 $N S_4 = B_4$인 부분군)이므로 $B_4 = N \rtimes S_4$, $|B_4| = 2^4 \cdot 4! = 384$이다. 이는 4차원 초입방체 $Q_4$의 자기동형군이다.
- **함수에 대한 작용**: 입력점의 치환 $g$는 $(g \cdot f)(\mathbf{x}) = f(g^{-1}\mathbf{x})$로 함수에 작용한다.
- **지표와 화환곱.** 부분군 $H \le G$의 지표는 $[G : H] = |G|/|H|$이다. 군 $A$와 $\mathbb{Z}_2$의 화환곱 $A \wr \mathbb{Z}_2$는 $A \times A$에 두 인자를 맞바꾸는 원소를 더한 군 $(A \times A) \rtimes \mathbb{Z}_2$이다.

### 2.4 번사이드 보조정리
이 보조정리는 Burnside (1897)의 교재에 실려 그의 이름이 붙었으나, 그 이전에 Cauchy와 Frobenius가 알고 있었다 (Neumann, 1979). 유한군 $G$가 유한집합 $X$에 작용할 때 궤도의 수는
$$|X / G| = \frac{1}{|G|} \sum_{g \in G} |\mathrm{Fix}(g, X)|, \qquad \mathrm{Fix}(g, X) = \lbrace x \in X : g x = x\rbrace$$
이다. $g$가 $\mathbb{Z}_2^4$의 16개 입력점에 일으키는 순환(cycle)의 개수를 $c(g)$라 하면, $g$로 불변인 함수는 각 순환 위에서 상수이므로 $|\mathrm{Fix}(g, \mathcal{F}_4)| = 2^{c(g)}$이다.

---

## 3. 변수 배치와 카르노맵의 대칭

### 3.1 변수 배치와 동치
$24$가지의 배치 $\sigma$ 각각은 입력점을 셀로 보내는 전단사 $\Phi_\sigma: \mathbb Z_2^4 \to \lbrace 0,1,2,3\rbrace^2$를 정한다. 두 배치 $\sigma, \sigma'$에 대해 어떤 격자 대칭 $w$가 존재하여 $\Phi_{\sigma'} = w \circ \Phi_\sigma$이면 $\sigma$와 $\sigma'$를 **동치**라 한다. 이는 임의의 함수 $f$에 대해 두 배치에서의 그림이 격자 대칭으로 옮겨진다는 뜻이다. 격자 대칭의 군은 다음 절에서 정의한다.

### 3.2 격자 대칭군 $W$
$\mathbb{Z}_4$ 위의 4-cycle(인덱스 $0, 1, 2, 3$이 원형으로 인접)의 자기동형군은 위수 8의 이면체군 $D_4(\mathbb{Z}_4) = \lbrace i \mapsto \pm i + k\rbrace$이다. 이를 행과 열에 독립적으로 적용하고 행과 열을 맞바꾸는 전치까지 허용한 군을
$$W = D_4(\mathbb{Z}_4) \wr \mathbb{Z}_2, \qquad |W| = 8 \cdot 8 \cdot 2 = 128$$
이라 한다. 이는 격자의 회전·반사 8개(평면 대칭 $D_4^{\mathrm{grid}}$)와 토러스 이동 $\mathbb{Z}_4 \times \mathbb{Z}_4$ (16개)가 생성하는 군 $D_4^{\mathrm{grid}} \ltimes (\mathbb{Z}_4 \times \mathbb{Z}_4)$와 같다. 생성원이 모두 $W$의 원소이므로 이 군은 $W$의 부분군이고, 토러스 이동의 군이 정규부분군이며 평면 대칭과의 교집합이 자명하므로 위수는 $8 \cdot 16 = 128 = |W|$이다.

**보조정리 1 (Gray code 위의 대칭).** 인덱스 $i \mapsto i + 1$은 라벨 $(a, b) \mapsto (b, \neg a)$로, $i \mapsto 3 - i$는 $(a, b) \mapsto (\neg a, b)$로, $i \mapsto -i$는 $(a, b) \mapsto (b, a)$로 작용한다.

*증명.* 라벨 $00, 01, 11, 10$ ($i = 0, 1, 2, 3$)에서 직접 확인한다. $i \mapsto i+1$은 $00 \to 01 \to 11 \to 10 \to 00$이고, 이는 $(a,b) \mapsto (b, \neg a)$와 일치한다. $i \mapsto 3-i$는 $00 \leftrightarrow 10$, $01 \leftrightarrow 11$이므로 $(a,b) \mapsto (\neg a, b)$이다. $i \mapsto -i$는 이 둘의 합성으로 $00 \to 00$, $01 \leftrightarrow 10$, $11 \to 11$, 곧 $(a,b) \mapsto (b,a)$이다. $\blacksquare$

보조정리 1의 $i \mapsto -i$는 변수 쌍의 두 변수를 맞바꾸는 것과 같다. 그림 3, 4는 이를 보여 준다. 행 변수 $X, Y$를 맞바꾸면 라벨 $01$과 $10$이 서로 바뀌고 $00$, $11$은 그대로이므로, 위치 $1$과 $3$의 행이 서로 바뀌고 위치 $0$, $2$의 행은 고정된다. 열 변수에서도 같다.

![그림 3. 행 변수 맞교환의 라벨 대응표](../images/fig03_swap_xy_index_table.png)

![그림 3. 행 변수 맞교환: 위치 1과 3의 행이 바뀐다](../images/fig05_swap_row_variables.png)

**그림 3.** 행 변수 $X, Y$의 맞교환. 위: $XY$와 $YX$의 라벨 대응 (표의 숫자는 라벨의 이진수 값이며, 본문의 위치 $0, 1, 2, 3$과 다르다). 아래: 같은 색은 원래 같은 행이다. $YX$ 배치(오른쪽)에서는 위치 $1$과 $3$의 행이 서로 바뀐다. 오른쪽 그림은 토러스의 이웃 관계를 보이려고 $00$ 행을 아래에 한 번 더 그렸다.

![그림 4. 열 변수 맞교환의 라벨 대응표](../images/fig04_swap_zw_index_table.png)

![그림 4. 열 변수 맞교환: 위치 1과 3의 열이 바뀐다](../images/fig06_swap_col_variables.png)

**그림 4.** 열 변수 $Z, W$의 맞교환. 그림 3과 같은 구성이며 행 대신 열이 바뀐다.

따라서 $D_4(\mathbb{Z}_4)$의 모든 원소는 2비트 라벨의 부호 순열이고, $W$의 모든 원소는 4개 입력 좌표 위의 부호 순열이다. 곧 $W \subseteq B_4$이다. 더 정확히는 다음이 성립한다.

**보조정리 2.** $W$는 $B_4$에서 좌표쌍 분할 $\lbrace\lbrace 1,2\rbrace,\lbrace 3,4\rbrace\rbrace$의 안정화군(이 분할을 보존하는 부호 순열 전체)과 같고, $[B_4 : W] = 3$이다.

*증명.* 입력 좌표를 $(x_1, x_2, x_3, x_4)$로 쓰고 행 라벨을 $(x_1, x_2)$, 열 라벨을 $(x_3, x_4)$로 한다. 칸은 (행 인덱스, 열 인덱스) $\in \mathbb{Z}_4 \times \mathbb{Z}_4$로 표시한다.

(i) **$W$는 $B_4$의 부분군이고 위수가 128이다.** $W$는 $\mathbb{Z}_4 \times \mathbb{Z}_4$ 위의 치환군으로 정의되었다. $D_4(\mathbb{Z}_4)$가 $\mathbb{Z}_4$ 위에 충실하게 작용하므로 $D_4(\mathbb{Z}_4) \wr \mathbb{Z}_2$는 $\mathbb{Z}_4 \times \mathbb{Z}_4$ 위에 충실하게 작용하고, 따라서 16개 입력점 위의 치환군으로서도 위수 $8 \cdot 8 \cdot 2 = 128$이다 (Gray 라벨링은 칸과 입력점 사이의 일대일 대응일 뿐이다). 보조정리 1에 의해 행 인덱스에 대한 $D_4(\mathbb{Z}_4)$의 원소는 행 라벨 $(x_1, x_2)$의 부호 순열이고 $x_3, x_4$를 건드리지 않는다. 열 인덱스에 대한 원소도 같은 방식으로 $(x_3, x_4)$의 부호 순열이다. 전치는 $(x_1, x_2, x_3, x_4) \mapsto (x_3, x_4, x_1, x_2)$이다. 이 원소들은 모두 좌표의 부호 순열이므로 $W \subseteq B_4$이다.

(ii) **$W$는 분할 $\lbrace\lbrace 1,2\rbrace,\lbrace 3,4\rbrace\rbrace$를 보존한다.** (i)의 생성원들은 각 쌍을 쌍으로 옮기거나(행·열 원소) 두 쌍을 맞바꾼다(전치). 그러므로 $W \subseteq \mathrm{Stab}_{B_4}(\lbrace\lbrace 1,2\rbrace,\lbrace 3,4\rbrace\rbrace)$이다.

(iii) *위수 비교.* 이 분할을 보존하는 $B_4$의 원소는 각 쌍을 제자리에 두는 원소들 ($B_2 \times B_2$, 여기서 $B_2 = \mathbb{Z}_2^2 \rtimes S_2$는 두 좌표에 대한 같은 구성이며 위수가 8이다. 따라서 위수 $8 \cdot 8 = 64$)과 두 쌍을 맞바꾸는 원소들로 이루어지고, 후자는 전자의 잉여류 하나이다 (두 쌍을 맞바꾸는 원소 하나가 있으므로). 따라서 안정화군의 위수는 128이다. (i)에서 $|W| = 128$이므로 $W$는 안정화군과 같다. 지표는 $384/128 = 3$이다. $\blacksquare$

**주 ($B_4$ 전체가 아니라 $W$를 쓰는 이유).** 카르노맵의 인접 그래프 $C_4 \thinspace\square\thinspace C_4$는 $Q_4$와 동형이므로 그래프로서의 자기동형군은 $B_4$ 전체이다. 그러나 그림의 대칭으로 인정하는 것은 그림의 행·열 구조, 곧 "행 방향의 이웃"과 "열 방향의 이웃"을 구별하는 변환뿐이다. 행·열 방향을 보존하거나 맞바꾸는 변환의 군이 $W$이고, $B_4$의 나머지 변환은 같은 16개 칸을 다른 변수 쌍 분할의 격자로 읽는 것에 해당한다. $B_4$ 전체를 허용하면 모든 변수 배치가 하나의 동치류가 되어 3.3절의 구분이 사라진다.

이 동일성은 두 군의 원소를 직접 대조하는 방식으로도 확인했다 (`verify_extras.py`의 기본 검사: 격자 대칭 생성원이 만든 군 = 좌표쌍 안정화군).

### 3.3 정리 1: 24개 배치는 정확히 3개의 동치류로 나뉜다
**정리 1.** 3.1절의 동치관계 아래에서 24가지 변수 배치는 정확히 3개의 동치류 $\lbrace AB|CD\rbrace$, $\lbrace AC|BD\rbrace$, $\lbrace AD|BC\rbrace$로 나뉘며, 각 동치류는 8개의 배치를 가진다. 여기서 $\lbrace XY|ZW\rbrace$는 행 변수 쌍과 열 변수 쌍의 비순서 분할을 뜻한다.

*증명.* ($\le 3$) 행 쌍 안의 순서를 바꾼 배치 $YX/ZW$는 행 라벨의 $(a,b) \mapsto (b,a)$, 곧 보조정리 1의 $i \mapsto -i$인 격자 반사로 $XY/ZW$와 옮겨진다. 열 쌍 안의 교환도 같다. 행 쌍과 열 쌍을 맞바꾸는 $ZW/XY$는 전치로 옮겨진다. 이 세 연산 $\tau_{\mathrm{row}}, \tau_{\mathrm{col}}, \tau_{\mathrm{trans}}$은 위수 8의 이면체군 $(\mathbb{Z}_2 \times \mathbb{Z}_2) \rtimes \mathbb{Z}_2$를 만들고 24개 배치에 자유롭게 작용하여 각 궤도의 크기는 8이므로, 동치류는 많아야 $24/8 = 3$개이다. 세 대표원은 $\lbrace AB|CD\rbrace$, $\lbrace AC|BD\rbrace$, $\lbrace AD|BC\rbrace$이다.

($\ge 3$) $W$의 모든 원소는 각 좌표를 하나의 쌍 안에서 옮기거나 두 쌍을 맞바꾸므로, 배치 $\sigma$의 행 쌍과 열 쌍으로 이루어진 분할 $\lbrace\lbrace\sigma(1),\sigma(2)\rbrace,\lbrace\sigma(3),\sigma(4)\rbrace\rbrace$은 $W$에 의한 변환에 대해 불변이다. $4$개의 변수를 두 쌍으로 나누는 비순서 분할은 $3$개이므로 동치류는 최소 $3$개이다. $\blacksquare$

**주 (직접 세기).** 같은 결과를 군 없이도 셀 수 있다. 네 변수를 행 쌍과 열 쌍으로 나누는 비순서 분할 $\lbrace\lbrace p,q\rbrace,\lbrace r,s\rbrace\rbrace$은 $\binom{4}{2}/2 = 3$가지이고, 분할마다 행·열의 역할(2가지)과 각 쌍 안의 순서($2 \times 2$가지)가 있어 $3 \times 8 = 24$가지 배치가 된다. 정리 1은 $W$ 아래에서 두 배치가 동치인 것이 정확히 같은 분할을 쓰는 것이라는 뜻이다.

**주.** 격자의 평면 대칭 $D_4^{\mathrm{grid}}$ 8개만 쓰고 토러스 이동을 쓰지 않으면 같은 24개 배치는 12개의 동치류로 나뉜다 (`verify_double_action.py`로 확인). 정리 1의 "3"은 토러스 이동까지 포함한 $W$에서만 성립한다. 이는 3.2절에서 $[B_4 : W] = 3$으로 설명되는 현상이다.

### 3.4 세 동치류의 대표원

| 동치류 | 대표원 | 포함되는 8개 배치 | 변수 쌍 분할의 성격 |
|:---:|:---:|:---|:---:|
| **I** | $AB/CD$ | $AB/CD$, $BA/CD$, $AB/DC$, $BA/DC$, $CD/AB$, $CD/BA$, $DC/AB$, $DC/BA$ | 인접 알파벳 분할 |
| **II** | $AC/BD$ | $AC/BD$, $CA/BD$, $AC/DB$, $CA/DB$, $BD/AC$, $BD/CA$, $DB/AC$, $DB/CA$ | 홀수/짝수 교차 분할 |
| **III** | $AD/BC$ | $AD/BC$, $DA/BC$, $AD/CB$, $DA/CB$, $BC/AD$, $BC/DA$, $CB/AD$, $CB/DA$ | 외곽/내부 분할 |

### 3.5 배치에 따른 카르노맵 그림
배치에 따라 그림이 어떻게 달라지는지는 함수에 따라 다르다.

**명제 1.** 완전 대칭 함수(4장)의 카르노맵 그림은 24개 배치 모두에서 동일하다. 특히 4변수 XOR의 체커보드는 어떤 배치에서도 같은 체커보드이다.

*증명.* 완전 대칭 함수는 $f(\pi\mathbf{x}) = f(\mathbf{x})$를 모든 $\pi \in S_4$에 대해 만족하고, 배치를 바꾸는 것은 입력점에 변수 순열을 적용하는 것과 같다. $\blacksquare$

**명제 2 (패리티와 체커보드).** Gray 축 순서(`00, 01, 11, 10`)의 카르노맵에서 4변수 패리티 함수 $x_1 \oplus x_2 \oplus x_3 \oplus x_4$의 그림은 체커보드, 곧 인접한 모든 두 셀(격자의 양끝 포함)의 값이 서로 반대인 그림이다. 축 순서를 이진 순서(`00, 01, 10, 11`)로 바꾸면 체커보드가 아니라 `0110 / 1001 / 1001 / 0110` 꼴(이중대각)이 된다.

*증명.* Gray 축 순서에서 인접한 두 셀의 라벨은 정확히 한 비트만 다르다 (보조정리 1의 표). 한 비트가 바뀌면 해밍 무게의 홀짝이 바뀌므로 패리티 함수의 값이 반전된다. 따라서 모든 인접 셀의 값이 다르다. 이진 순서에서는 `01`과 `10`이 이웃하지만 두 비트가 다르므로 이 논증이 적용되지 않고, 직접 계산하면 위의 이중대각 꼴이 된다. $\blacksquare$ (`verify_extras.py` [A]에서 확인)

역으로, Gray 축 순서에서 인접한 모든 칸의 값이 서로 다른 그림은 XOR 또는 XNOR의 그림뿐이다. 카르노맵의 인접 그래프는 연결 그래프이므로 한 칸의 값이 정해지면 인접한 칸의 값이 차례로 정해져 그림 전체가 결정되고, 칸 $0000$의 값이 0이면 XOR, 1이면 XNOR이기 때문이다. 따라서 $\text{Exactly-}k$ 같은 다른 대칭 함수는 Gray 축 순서에서도 체커보드가 되지 않는다.

이 명제는 체커보드가 "함수의 패리티 구조와 Gray 인접성의 결합"으로 생기는 것임을 보여준다. 명제 1에 의해 이 그림은 변수 배치와 무관하지만, 축 라벨 순서가 Gray가 아니면 달라진다. 따라서 그림이 달라지는 원인은 (i) 변수 배치와 (ii) 축 라벨 순서로 구분해야 한다.

| | Gray 축 순서 (`00, 01, 11, 10`) | 이진 축 순서 (`00, 01, 10, 11`) |
|:---:|:---:|:---:|
| **XOR** | ![XOR, Gray 축 순서: 체커보드](../images/fig13_parity_xor_gray.png) | ![XOR, 이진 축 순서: 이중대각](../images/fig14_parity_xor_binary.png) |
| **XNOR** | ![XNOR, Gray 축 순서](../images/fig15_parity_xnor_gray.png) | ![XNOR, 이진 축 순서](../images/fig16_parity_xnor_binary.png) |

**그림 5.** 4변수 XOR와 XNOR (패리티와 그 보수)의 그림. 모든 그림은 배치 $AB/CD$이며 명제 1에 의해 24개 배치에서 같다. Gray 축 순서에서는 체커보드이고 이진 축 순서에서는 이중대각이다. 그림의 값은 `verify_figures.py`로 확인했다.

배치가 그림을 바꾸는 것은 비대칭 함수에 대해서이다. 예를 들어 $f = \sum m(0, 2, 3, 5, 8)$, 곧 $\overline{A}\thinspace\overline{B}\thinspace\overline{C}\thinspace\overline{D} + \overline{A}\thinspace\overline{B}\thinspace C\thinspace\overline{D} + \overline{A}\thinspace\overline{B}\thinspace C\thinspace D + \overline{A}\thinspace B\thinspace\overline{C}\thinspace D + A\thinspace\overline{B}\thinspace\overline{C}\thinspace\overline{D}$의 세 대표 배치에서의 그림은 다음과 같다 (행과 열의 라벨은 위에서 아래, 왼쪽에서 오른쪽으로 $00, 01, 11, 10$ 순서).

```
 AB/CD      AC/BD      AD/BC
 1 0 1 1    1 0 1 0    1 1 0 0
 0 1 0 0    1 1 0 0    0 1 0 1
 0 0 0 0    0 0 0 0    0 0 0 0
 1 0 0 0    1 0 0 0    1 0 0 0
```

세 그림은 $W$의 어떤 원소로도 서로 옮겨지지 않는다. 여기서 두 그림이 같은 종류라는 것은 한 그림을 $W$의 원소(이동, 반사, 전치)로 옮기면 다른 그림이 된다는 뜻이다. 명제 1의 "동일"은 칸마다 값이 문자 그대로 같다는 더 강한 뜻이다. 전수 계산 결과, 세 대표 배치에서의 그림이 $W$ 아래 서로 구별되는 종류의 수는 다음과 같다 (`verify_pictures.py`).

| 구별되는 그림의 종류 | 함수의 개수 |
|:---:|:---:|
| 1 (세 배치의 그림이 $W$로 서로 옮겨짐) | 3,220 |
| 2 | 36,204 |
| 3 (어느 두 배치의 그림도 $W$로 옮겨지지 않음) | 26,112 |

이 세 숫자는 $B_4$-궤도가 $W$-궤도로 쪼개지는 개수로 설명된다 (6.5절 정리 4).

---

## 4. 완전 대칭 부울 함수와 Hamming Weight 레이어

### 4.1 정의
$f: \mathbb{Z}_2^4 \to \mathbb{Z}_2$가 모든 $\pi \in S_4$와 모든 $\mathbf{x}$에 대해 $f(\pi\mathbf{x}) = f(\mathbf{x})$를 만족할 때 **완전 대칭 부울 함수**라 하고, 그 집합을 $\mathcal{S}_4$로 쓴다.

### 4.2 레이어 분할
해밍 무게(입력에서 1의 개수; Hamming, 1950) $w(\mathbf{x}) = \sum x_i \in \lbrace 0, 1, 2, 3, 4\rbrace$가 같은 두 입력점 사이에는 이를 옮기는 순열이 항상 존재한다. 따라서 $f \in \mathcal{S}_4$의 값은 $w$로만 결정되고, $f$는 레이어 벡터 $\mathbf{v}_f = (v_0, \dots, v_4) \in \mathbb{Z}_2^5$와 일대일 대응한다. 그러므로
$$|\mathcal{S}_4| = 2^5 = 32$$
이다. 입력점은 레이어 $L_k = \lbrace w(\mathbf{x}) = k\rbrace$ ($k = 0, \dots, 4$)로 분할되며 크기는 $\binom{4}{k} \in \lbrace 1, 4, 6, 4, 1\rbrace$이다.

| 레이어 | 해밍 무게 | 개수 | 민텀 | 카르노맵 위치 ($AB/CD$) |
|:---:|:---:|:---:|:---|:---|
| $L_0$ | 0 | 1 | $m_0$ | 좌상단 모서리 |
| $L_1$ | 1 | 4 | $m_1, m_2, m_4, m_8$ | $L_0$ 주변 4개 셀 |
| $L_2$ | 2 | 6 | $m_3, m_5, m_6, m_9, m_{10}, m_{12}$ | 대각선 교차 격자 |
| $L_3$ | 3 | 4 | $m_7, m_{11}, m_{13}, m_{14}$ | $L_4$ 주변 4개 셀 |
| $L_4$ | 4 | 1 | $m_{15}$ | 중앙 코어 셀 |

마지막 열의 "모서리", "중앙" 같은 위치 표현은 표준 배치 $AB/CD$의 그림 6을 기준으로 한 말이다. 격자는 토러스이므로 어느 칸이든 이웃 관계는 같고, 이 표현은 그림을 읽기 위한 편의일 뿐이다.

![그림 6. 칸별 레이어](../images/fig17_layers.png)

**그림 6.** 표준 배치 $AB/CD$에서 각 칸의 레이어. 그림의 라벨 $L1, \dots, L5$는 위 표의 $L_0, \dots, L_4$ (해밍 무게 $0, \dots, 4$)에 해당한다. 한 칸의 레이어는 그 칸의 입력 라벨의 해밍 무게이다.

### 4.3 대표 함수
- 기저 함수 5개: $E_k$ = $\text{Exactly-}k$ ($k = 0, \dots, 4$). $E_0$ = NOR, $E_4$ = AND.
- 임계값 함수 4개: $\text{At-Least-}k$ ($k = 1, 2, 3, 4$). At-Least-1 $=$ OR, At-Least-3 $=$ 다수결, At-Least-4 $=$ AND.
- 패리티 2개: $(0,1,0,1,0) =$ XOR, $(1,0,1,0,1) =$ XNOR. 두 함수의 그림은 체커보드이며 명제 1에 의해 모든 배치에서 같다.
- 상수 2개: $f \equiv 0$, $f \equiv 1$.

| $E_0$ | $E_1$ | $E_2$ |
|:---:|:---:|:---:|
| ![E0: Exactly-0](../images/fig01_kmap_exactly0.png) | ![E1: Exactly-1](../images/fig18_exactly1.png) | ![E2: Exactly-2](../images/fig19_exactly2.png) |
| **$E_3$** | **$E_4$** | |
| ![E3: Exactly-3](../images/fig20_exactly3.png) | ![E4: Exactly-4](../images/fig21_exactly4.png) | |

**그림 7.** 기저 함수 $E_k$ ($k = 0, \dots, 4$)의 그림 (배치 $AB/CD$). $E_k$가 1인 칸은 레이어 $L_k$의 칸이다 (그림 6). 완전 대칭 함수이므로 명제 1에 의해 24개 배치 모두에서 같은 그림이다 (`verify_figures.py`).

### 4.4 32개 완전 대칭 함수 목록

| 번호 | 레이어 벡터 | ON-세트 크기 | 명칭 / 논리식 |
|:---:|:---:|:---:|:---|
| 0 | `(0,0,0,0,0)` | 0 | 상수 0 |
| 1 | `(1,0,0,0,0)` | 1 | Exactly-0 (NOR) |
| 2 | `(0,1,0,0,0)` | 4 | Exactly-1 |
| 3 | `(1,1,0,0,0)` | 5 | At-Most-1 |
| 4 | `(0,0,1,0,0)` | 6 | Exactly-2 |
| 5 | `(1,0,1,0,0)` | 7 | Weight $\in \lbrace 0,2\rbrace$ |
| 6 | `(0,1,1,0,0)` | 10 | Weight $\in \lbrace 1,2\rbrace$ |
| 7 | `(1,1,1,0,0)` | 11 | At-Most-2 |
| 8 | `(0,0,0,1,0)` | 4 | Exactly-3 |
| 9 | `(1,0,0,1,0)` | 5 | Weight $\in \lbrace 0,3\rbrace$ |
| 10 | `(0,1,0,1,0)` | 8 | XOR (홀수 패리티) |
| 11 | `(1,1,0,1,0)` | 9 | Weight $\in \lbrace 0,1,3\rbrace$ |
| 12 | `(0,0,1,1,0)` | 10 | Weight $\in \lbrace 2,3\rbrace$ |
| 13 | `(1,0,1,1,0)` | 11 | Weight $\in \lbrace 0,2,3\rbrace$ |
| 14 | `(0,1,1,1,0)` | 14 | $0 < \text{Weight} < 4$ |
| 15 | `(1,1,1,1,0)` | 15 | At-Most-3 (NAND) |
| 16 | `(0,0,0,0,1)` | 1 | Exactly-4 (AND) |
| 17 | `(1,0,0,0,1)` | 2 | Weight $\in \lbrace 0,4\rbrace$ (일치) |
| 18 | `(0,1,0,0,1)` | 5 | Weight $\in \lbrace 1,4\rbrace$ |
| 19 | `(1,1,0,0,1)` | 6 | Weight $\in \lbrace 0,1,4\rbrace$ |
| 20 | `(0,0,1,0,1)` | 7 | Weight $\in \lbrace 2,4\rbrace$ |
| 21 | `(1,0,1,0,1)` | 8 | XNOR (짝수 패리티) |
| 22 | `(0,1,1,0,1)` | 11 | Weight $\in \lbrace 1,2,4\rbrace$ |
| 23 | `(1,1,1,0,1)` | 12 | Weight $\ne 3$ |
| 24 | `(0,0,0,1,1)` | 5 | 다수결 (At-Least-3) |
| 25 | `(1,0,0,1,1)` | 6 | Weight $\in \lbrace 0,3,4\rbrace$ |
| 26 | `(0,1,0,1,1)` | 9 | Weight $\in \lbrace 1,3,4\rbrace$ |
| 27 | `(1,1,0,1,1)` | 10 | Weight $\ne 2$ |
| 28 | `(0,0,1,1,1)` | 11 | At-Least-2 |
| 29 | `(1,0,1,1,1)` | 12 | Weight $\ne 1$ |
| 30 | `(0,1,1,1,1)` | 15 | At-Least-1 (OR) |
| 31 | `(1,1,1,1,1)` | 16 | 상수 1 |

---

## 5. $S_4$ 작용 아래의 궤도 분류

### 5.1 $S_4$의 켤레류와 입력점 위의 순환 수
$S_4$는 순환 구조에 따라 5개의 켤레류로 나뉜다. 각 대표원이 16개 입력점에 일으키는 순환 수 $c(g)$는 순열을 직접 적용해 세면 다음과 같다.

| 켤레류 | 순환 구조 | 원소 수 | 대표원 | $c(g)$ | 입력점 위 순환의 구성 |
|:---:|:---:|:---:|:---:|:---:|:---|
| $C_1$ | $(1)^4$ | 1 | id | 16 | 고정점 16개 |
| $C_2$ | $(2)(1)^2$ | 6 | $(12)$ | 12 | 고정점 8개, 2-순환 4개 |
| $C_3$ | $(2)^2$ | 3 | $(12)(34)$ | 10 | 고정점 4개, 2-순환 6개 |
| $C_4$ | $(3)(1)$ | 8 | $(123)$ | 8 | 고정점 4개, 3-순환 4개 |
| $C_5$ | $(4)$ | 6 | $(1234)$ | 6 | 고정점 2개, 2-순환 1개, 4-순환 3개 |

### 5.2 전체 공간 $\mathcal{F}_4$
2.4절에 의해 $|\mathrm{Fix}(g, \mathcal{F}_4)| = 2^{c(g)}$이다.
$$|\mathcal{F}_4 / S_4| = \frac{1}{24}\big[1 \cdot 2^{16} + 6 \cdot 2^{12} + 3 \cdot 2^{10} + 8 \cdot 2^{8} + 6 \cdot 2^{6}\big] = \frac{65536 + 24576 + 3072 + 2048 + 384}{24} = \frac{95616}{24} = \mathbf{3{,}984}.$$
궤도의 크기 분포는 열거로 얻은 다음 표와 같다 (크기 × 궤도 수의 합 $32 + 96 + 896 + 1344 + 20160 + 43008 = 65536$, 궤도 수의 합 $32 + 32 + 224 + 224 + 1680 + 1792 = 3984$).

| 궤도 크기 | 1 | 3 | 4 | 6 | 12 | 24 |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| 궤도 수 | 32 | 32 | 224 | 224 | 1,680 | 1,792 |

크기 1인 궤도 32개는 $S_4$의 모든 원소가 고정하는 함수, 곧 4장의 완전 대칭 함수이다.

### 5.3 부분공간: 세 가지 클론
다음 세 함수 집합은 Post의 격자에서 합성에 닫힌 클론이다 (클론은 사영 함수를 포함하고 함수의 합성에 닫힌 함수의 집합이다). 이 논문의 계산에 쓰이는 것은 클론 구조 자체가 아니라 세 집합이 모두 $S_4$ 작용에 닫혀 있다는 사실이다.

- **아핀 함수** $L$: $f = c_0 \oplus c_1 x_1 \oplus \cdots \oplus c_4 x_4$ ($c_i \in \mathbb{Z}_2$), $|L| = 2^5 = 32$ (XOR과 상수 1이 생성).
- **단조 함수** $M$: $\mathbf{x} \le \mathbf{y}$ (성분별)이면 $f(\mathbf{x}) \le f(\mathbf{y})$. 상수 0과 1을 포함하며 $|M| = 168$ (4변수 Dedekind 수; AND와 OR와 상수가 생성).
- **자기쌍대 함수** $D$: $f(\neg\mathbf{x}) = \neg f(\mathbf{x})$, $|D| = 2^8 = 256$ (NOT과 3입력 다수결 $\mathrm{MAJ}_3$이 생성한다).

세 집합의 생성 연산에 관한 위 괄호 설명은 사영 함수 4개에서 출발한 4변수 함수의 닫힘을 직접 계산하여 확인했다 (`verify_clone_generators.py`). 세 집합은 모두 $S_4$ 작용으로 닫혀 있으므로 각각 $S_4$-궤도들의 분리 합집합이다. 같은 클론 안의 두 함수가 같은 궤도에 속할 필요는 없다(예: $x_1$과 $x_1 \oplus x_2$는 모두 아핀이지만 서로 다른 궤도에 있다). 각 공간에서 켤레류별 $|\mathrm{Fix}|$는 다음과 같다.

| 공간 | $C_1$ | $C_2$ | $C_3$ | $C_4$ | $C_5$ | 합 $\sum \lvert C_k \rvert \cdot \mathrm{Fix}$ | 궤도 수 |
|:---|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| 아핀 $L$ | 32 | 16 | 8 | 8 | 4 | 240 | **10** |
| 단조 $M$ | 168 | 50 | 28 | 15 | 8 | 720 | **30** |
| 자기쌍대 $D$ | 256 | 64 | 0 | 16 | 0 | 768 | **32** |

**아핀 공간의 Fix.** $\sigma$로 불변이려면 $\sigma$의 같은 순환 안의 변수는 계수가 같아야 한다. 변수 순환이 $m$개이면 자유 계수는 $c_0$와 순환별 하나씩이므로 $|\mathrm{Fix}| = 2^{m+1}$이다. $C_1, \dots, C_5$의 $m$은 $4, 3, 2, 2, 1$이므로 $32, 16, 8, 8, 4$이다.

**자기쌍대 공간의 Fix.** $\sigma$는 보수 사상 $\mathbf{x} \mapsto \neg\mathbf{x}$와 가환하므로 보수는 $\sigma$-순환들을 서로 옮긴다. 어떤 $\sigma$-순환이 보수에 대해 닫혀 있으면 그 위에서 $f$가 상수이면서 $f(\neg\mathbf{x}) = \neg f(\mathbf{x})$를 만족해야 하므로 모순이고, $\mathrm{Fix} = 0$이다. 그렇지 않으면 순환이 보수 쌍으로 짝지어지고 쌍마다 값을 하나 고르므로 $|\mathrm{Fix}| = 2^{c(g)/2}$이다. $C_3$에서는 $\mathbf{x} = (0,1,0,1)$이 $(12)(34)$로 $(1,0,1,0) = \neg\mathbf{x}$로 가고, $C_5$에서는 $(0,1,0,1)$이 $(1234)$로 $(1,0,1,0)$으로 가므로 보수에 닫힌 순환이 있어 $\mathrm{Fix} = 0$이다. $C_2$, $C_4$에서는 그런 순환이 없으므로 $2^{12/2} = 64$, $2^{8/2} = 16$이다.

**단조 공간의 Fix.** 단조 함수는 $2^{[4]}$ ($[4] = \lbrace 1,2,3,4\rbrace$의 부분집합 격자)의 상집합(up-set)과 일대일 대응한다 ($f$는 $f^{-1}(1)$에 대응). $f$가 $\sigma$로 불변인 것은 상집합 $U = f^{-1}(1)$이 $\sigma$로 불변인 것이고, 이는 $U$가 $\langle \sigma \rangle$-궤도들의 합집합임을 뜻한다. 부분집합들의 $\langle \sigma \rangle$-궤도 위에 "궤도 $O \le O'$는 어떤 $a \in O$, $a' \in O'$에 대해 $a \subseteq a'$"로 순서를 주면 ($\sigma$ 불변인 상집합은 이 순서의 상집합이다) 다음이 성립한다.

$$|\mathrm{Fix}_M(\sigma)| = \bigl|\lbrace\text{궤도 순서집합 } P_\sigma \text{의 상집합}\rbrace\bigr|.$$

각 켤레류에서 $P_\sigma$는 다음과 같이 작다.
- $C_1 = \mathrm{id}$: $P = 2^{[4]}$ (16원소). 상집합의 수는 4변수 Dedekind 수 168이다 (이미 알려진 값, Dedekind, 1897).
- $C_2 = (12)$: 궤도는 $(|S \cap \lbrace 1,2\rbrace|, x_3, x_4) \in \lbrace 0,1,2\rbrace \times \lbrace 0,1\rbrace^2$로 정해지고 순서는 성분별 순서이다. 곧 $P$는 사슬 $\mathbf{3} \times \mathbf{2} \times \mathbf{2}$의 곱이다 ($\mathbf{k}$는 $k$개 원소의 사슬이다). 사슬 $\mathbf{a} \times \mathbf{b} \times \mathbf{c}$의 상집합은 $a \times b \times c$ 상자 안의 평면분할과 일대일 대응하므로, 상집합의 수는 $3 \times 2 \times 2$ 상자 안의 평면분할 수 $PP(2,2,3) = \prod_{i \le 2, j \le 2} \frac{i + j + 2}{i + j - 1} = 4 \cdot \frac{5}{2} \cdot \frac{5}{2} \cdot 2 = 50$ (MacMahon, 1916)이다.
- $C_4 = (123)$: 궤도는 $(|S \cap \lbrace 1,2,3\rbrace|, x_4) \in \lbrace 0,1,2,3\rbrace \times \lbrace 0,1\rbrace$이고 $P = \mathbf{4} \times \mathbf{2}$이다. 상집합의 수는 두 사슬의 곱의 격자 경로 수 $\binom{4 + 2}{2} = 15$이다.
- $C_5 = (1234)$: 부분집합 16개가 6개의 궤도(원형 이진 목걸이)로 나뉜다: $\varnothing$, $\lbrace 1\rbrace$, $\lbrace 1,2\rbrace$ (인접 쌍), $\lbrace 1,3\rbrace$ (대각 쌍), $\lbrace 1,2,3\rbrace$, $\lbrace 1,2,3,4\rbrace$. $\lbrace 1,2\rbrace$와 $\lbrace 1,3\rbrace$은 크기가 같아 비교 불가능하고 나머지는 사슬이다. 곧 $P$는 $\varnothing < \lbrace 1\rbrace < \lbrace\lbrace 1,2\rbrace, \lbrace 1,3\rbrace\rbrace < \lbrace 1,2,3\rbrace < \lbrace 1,2,3,4\rbrace$ (가운데 두 원소는 비교 불가능)이다. 상집합은 위쪽 원소부터 채워지므로 다음과 같이 센다. 빈 상집합 1개, 최대 원소 $\lbrace 1,2,3,4\rbrace$만 있는 것 1개, 여기에 $\lbrace 1,2,3\rbrace$을 더한 것 1개, 거기에 가운데 두 원소를 $\lbrace 1,2\rbrace$만 / $\lbrace 1,3\rbrace$만 / 둘 다 더하는 것 3개, 다시 $\lbrace 1\rbrace$까지 더한 것 1개, 마지막으로 $\varnothing$까지 포함한 전체 1개이다. 합은 $1 + 1 + 1 + 3 + 1 + 1 = 8$이다.
- $C_3 = (12)(34)$: 궤도가 10개 ($\varnothing$, $\lbrace 1\rbrace\negthinspace\sim\negthinspace\lbrace 2\rbrace$, $\lbrace 3\rbrace\negthinspace\sim\negthinspace\lbrace 4\rbrace$, $\lbrace 1,2\rbrace$, $\lbrace 3,4\rbrace$, $\lbrace 1,3\rbrace\negthinspace\sim\negthinspace\lbrace 2,4\rbrace$, $\lbrace 1,4\rbrace\negthinspace\sim\negthinspace\lbrace 2,3\rbrace$, $\lbrace 1,2,3\rbrace\negthinspace\sim\negthinspace\lbrace 1,2,4\rbrace$, $\lbrace 1,3,4\rbrace\negthinspace\sim\negthinspace\lbrace 2,3,4\rbrace$, $\lbrace 1,2,3,4\rbrace$)인 순서집합이다. 층별로 $\varnothing$ (층 0), $a = \lbrace 1\rbrace\negthinspace\sim\negthinspace\lbrace 2\rbrace$, $b = \lbrace 3\rbrace\negthinspace\sim\negthinspace\lbrace 4\rbrace$ (층 1), $p = \lbrace 1,2\rbrace$, $q = \lbrace 3,4\rbrace$, $r = \lbrace 1,3\rbrace\negthinspace\sim\negthinspace\lbrace 2,4\rbrace$, $s = \lbrace 1,4\rbrace\negthinspace\sim\negthinspace\lbrace 2,3\rbrace$ (층 2), $t = \lbrace 1,2,3\rbrace\negthinspace\sim\negthinspace\lbrace 1,2,4\rbrace$, $u = \lbrace 1,3,4\rbrace\negthinspace\sim\negthinspace\lbrace 2,3,4\rbrace$ (층 3), $z$ (층 4)이다. 위로 가는 관계는 $p < t$, $q < u$, $r, s < t, u$, $a < p, r, s$, $b < q, r, s$이고 (추이적으로 닫는다), $a \not< q$, $b \not< p$이다. 빈 상집합이 아닌 상집합 $U$는 $z$를 포함한다. $U \cap \lbrace t, u\rbrace$로 나누어 센다.
  - $U = \lbrace z\rbrace$: 1개.
  - $t$만 포함: 층 2에서는 $p$만 넣을 수 있고 (나머지는 $u$가 필요하다), 층 1은 불가능하다. 2개.
  - $u$만 포함: 같은 이유로 $q$만 넣을 수 있다. 2개.
  - $t$, $u$ 모두 포함: 층 2의 부분집합 $W \subseteq \lbrace p, q, r, s\rbrace$를 16가지로 고른다. $a$는 $\lbrace p, r, s\rbrace \subseteq W$일 때, $b$는 $\lbrace q, r, s\rbrace \subseteq W$일 때만 넣을 수 있고, $\varnothing$은 $a$, $b$와 층 2 전부가 있을 때만 넣을 수 있다. $W = \lbrace p, q, r, s\rbrace$이면 $(a, b)$ 4가지에 $\varnothing$ 포함 1가지를 더해 5개, $W = \lbrace p, r, s\rbrace$ 또는 $\lbrace q, r, s\rbrace$이면 각각 2개, 나머지 13가지의 $W$는 각각 1개이므로 $5 + 2 + 2 + 13 = 22$개.

  빈 상집합까지 합하면 $1 + 1 + 2 + 2 + 22 = 28$이다.

이렇게 $C_2$부터 $C_5$까지는 손으로 유도되고 $C_1$은 알려진 Dedekind 수이다. 5개 값 모두 상집합 수가 정의대로 센 Fix와 일치하고 합이 $168 + 300 + 84 + 120 + 48 = 720$, 궤도 수가 $720/24 = 30$임을 `verify_monotone_fix.py`로 확인했다 (`verify_tables.py`도 같은 값을 확인한다).

### 5.4 아핀 공간의 10개 궤도
아핀 함수는 계수 벡터 $(c_1, \dots, c_4)$의 해밍 무게 $w$와 상수 $c_0$로 분류된다. 대표 함수, 궤도 크기, 안정화군은 다음과 같다.

| 궤도 | 대표 함수 | 크기 | 안정화군 $\mathrm{Stab}(f)$ (위수) | $S_4$-고정점 |
|:---:|:---|:---:|:---:|:---:|
| $O_1$ | $0$ | 1 | $S_4$ (24) | 예 |
| $O_2$ | $1$ | 1 | $S_4$ (24) | 예 |
| $O_3$ | $x_1$ | 4 | $S_3$ (6) | 아니오 |
| $O_4$ | $x_1 \oplus 1$ | 4 | $S_3$ (6) | 아니오 |
| $O_5$ | $x_1 \oplus x_2$ | 6 | $\mathbb{Z}_2 \times \mathbb{Z}_2$ (4) | 아니오 |
| $O_6$ | $x_1 \oplus x_2 \oplus 1$ | 6 | $\mathbb{Z}_2 \times \mathbb{Z}_2$ (4) | 아니오 |
| $O_7$ | $x_1 \oplus x_2 \oplus x_3$ | 4 | $S_3$ (6) | 아니오 |
| $O_8$ | $x_1 \oplus x_2 \oplus x_3 \oplus 1$ | 4 | $S_3$ (6) | 아니오 |
| $O_9$ | $x_1 \oplus x_2 \oplus x_3 \oplus x_4$ | 1 | $S_4$ (24) | 예 |
| $O_{10}$ | $x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus 1$ | 1 | $S_4$ (24) | 예 |

크기의 합은 $1+1+4+4+6+6+4+4+1+1 = 32$이다. $x_1 \oplus x_2$의 안정화군은 $\lbrace x_1, x_2\rbrace$와 $\lbrace x_3, x_4\rbrace$를 각각 보존하는 순열 $\langle (12), (34) \rangle \cong \mathbb{Z}_2 \times \mathbb{Z}_2$이다. 고정점 4개는 $0, 1$, XOR, XNOR이고 이는 $L \cap \mathcal{S}_4$이다.

### 5.5 단조 공간과 자기쌍대 공간의 궤도 구조
- **단조 공간** (168개, 30궤도): 궤도 크기의 분포는 크기 1이 6개, 크기 3이 2개, 크기 4가 9개, 크기 6이 6개, 크기 12가 7개이다 ($6 + 6 + 36 + 36 + 84 = 168$). 크기 24인 궤도는 없다. 크기 1인 6개는 $\mathcal{S}_4$와의 교집합 $M \cap \mathcal{S}_4$, 곧 임계값 함수 $\text{At-Least-}k$ ($k = 0, 1, \dots, 5$, 여기서 $k = 0$은 상수 1, $k = 5$는 상수 0)이다. 예: 크기 3은 $x_1 x_2 \lor x_3 x_4$와 $(x_1 \lor x_2)(x_3 \lor x_4)$, 크기 4는 $x_1$, $x_1 x_2 x_3$, $x_1 \lor x_2 \lor x_3$, 크기 6은 $x_1 x_2$와 $x_1 \lor x_2$, 크기 12는 $x_1 (x_2 \lor x_3)$.
- **자기쌍대 공간** (256개, 32궤도): 크기 4인 궤도 16개와 크기 12인 궤도 16개이다 ($64 + 192 = 256$). 고정점이 없다. 완전 대칭 함수에서 보수는 레이어 $L_k$를 $L_{4-k}$로 옮기므로 자기쌍대이려면 $v_{4-k} = \neg v_k$여야 하고, $k = 2$에서 $v_2 = \neg v_2$가 되어 모순이기 때문이다. 곧 $D \cap \mathcal{S}_4 = \emptyset$이다.

**단조 공간의 30개 궤도 목록.** 아래 표의 대표 함수는 최소항의 합(곱 $=$ AND, $\lor$ $=$ OR, 문자는 $A, B, C, D$)이다. 30개 대표가 모두 단조이고, 서로 다른 궤도에 있으며, 크기가 표와 같고, 궤도들의 합집합이 168개 전체임을 `verify_extras.py` [D]로 확인했다.

| 궤도 | 크기 | 대표 함수 | 궤도 | 크기 | 대표 함수 |
|:---:|:---:|:---|:---:|:---:|:---|
| $O_{1}$ | 1 | $0$ | $O_{16}$ | 4 | $D \lor BC \lor AC \lor AB$ |
| $O_{2}$ | 1 | $ABCD$ | $O_{17}$ | 4 | $D \lor C \lor B$ |
| $O_{3}$ | 1 | $\text{At-Least-}3$ | $O_{18}$ | 6 | $BCD \lor ACD$ |
| $O_{4}$ | 1 | $\text{At-Least-}2$ | $O_{19}$ | 6 | $CD$ |
| $O_{5}$ | 1 | $A \lor B \lor C \lor D$ | $O_{20}$ | 6 | $CD \lor ABD \lor ABC$ |
| $O_{6}$ | 1 | $1$ | $O_{21}$ | 6 | $CD \lor BD \lor BC \lor AD \lor AC$ |
| $O_{7}$ | 3 | $AB \lor CD$ | $O_{22}$ | 6 | $D \lor C$ |
| $O_{8}$ | 3 | $(A \lor B)(C \lor D)$ | $O_{23}$ | 6 | $D \lor C \lor AB$ |
| $O_{9}$ | 4 | $BCD$ | $O_{24}$ | 12 | $CD \lor ABD$ |
| $O_{10}$ | 4 | $BCD \lor ACD \lor ABD$ | $O_{25}$ | 12 | $CD \lor BD$ |
| $O_{11}$ | 4 | $CD \lor BD \lor AD$ | $O_{26}$ | 12 | $CD \lor BD \lor ABC$ |
| $O_{12}$ | 4 | $D$ | $O_{27}$ | 12 | $CD \lor BC \lor AD$ |
| $O_{13}$ | 4 | $CD \lor BD \lor BC$ | $O_{28}$ | 12 | $CD \lor BD \lor BC \lor AD$ |
| $O_{14}$ | 4 | $CD \lor BD \lor AD \lor ABC$ | $O_{29}$ | 12 | $D \lor BC$ |
| $O_{15}$ | 4 | $D \lor ABC$ | $O_{30}$ | 12 | $D \lor BC \lor AC$ |

크기 합은 $6 \cdot 1 + 2 \cdot 3 + 9 \cdot 4 + 6 \cdot 6 + 7 \cdot 12 = 168$이다.

**궤도 크기 분포의 유도.** 궤도의 크기는 $24 / |\mathrm{Stab}(f)|$이므로 안정화군의 위수별 함수 수가 분포를 정한다. $S_4$의 부분군 30개(궤도의 수 30과 우연히 같은 수이다) 각각에 대해 $\mathrm{Fix}(H)$ ($H$로 불변인 단조 함수의 수, 곧 $H$-궤도 순서집합의 상집합 수)를 구하고, 부분군 격자 위의 뫼비우스 반전(Hall, 1936) $N(H) = \mathrm{Fix}(H) - \sum_{K \supsetneq H} N(K)$로 안정화군이 정확히 $H$인 함수의 수 $N(H)$를 얻는다. 위수별로 합하면 위수 24가 6개, 8이 6개, 6이 36개, 4가 36개, 2가 84개이고 12, 3, 1은 0개이다 ($6 + 6 + 36 + 36 + 84 = 168$). 위수로 $24$를 나눈 크기로 다시 나누면 크기 1, 3, 4, 6, 12인 궤도가 각각 $6, 2, 9, 6, 7$개이다. 특히 안정화군이 자명한 단조 함수는 없다. 이는 30개 부분군에 대한 유한 계산이며 닫힌 식은 아니다. 30개 궤도의 대표 함수 목록 자체는 여전히 열거로 얻었다 (`verify_stabilizer_counts.py` [A], `verify_extras.py` [D]).

### 5.6 공간들의 교집합
네 공간은 포함 관계를 이루지 않는다. 완전 대칭 함수 $\mathcal{S}_4$ (32개)와의 교집합은 다음과 같다.

| 교집합 | 크기 | 내용 |
|:---|:---:|:---|
| $L \cap \mathcal{S}_4$ | 4 | $0, 1,$ XOR, XNOR |
| $M \cap \mathcal{S}_4$ | 6 | $\text{At-Least-}k$ ($k = 0, \dots, 5$) |
| $D \cap \mathcal{S}_4$ | 0 | 없음 |

예를 들어 Exactly-2는 완전 대칭이지만 아핀, 단조, 자기쌍대 어느 공간에도 속하지 않는다.

한편 아핀이면서 단조인 함수의 집합은 $L \cap M = \lbrace 0, 1, x_1, x_2, x_3, x_4\rbrace$ (6개)이다 ($x_1 \oplus x_2$는 아핀이지만 단조가 아니고, $\neg x_1 = x_1 \oplus 1$도 단조가 아니다). 이 6개는 3개의 $S_4$-궤도(크기 1, 1, 4)를 이루며, $S_4$-고정점은 상수 0과 1뿐이다 (`verify_extras.py` [E]).

---

## 6. 합성군 $\langle S_4, W \rangle = B_4$

### 6.1 문제
$S_4$는 변수의 이름을 바꾸고, $W$ (3.2절)는 카르노맵 그림의 격자를 움직인다. 두 군은 모두 16개 입력점의 치환으로 $\mathcal{F}_4$에 작용한다. 두 군이 함께 작용할 때 함수를 어떻게 분류하는가? 그리고 이 합성은 직접곱인가?

### 6.2 정리 2 (합성군의 구조)
**정리 2.** $S_4$와 격자 평면 대칭 $D_4^{\mathrm{grid}}$ (회전·반사 8개)가 생성하는 군 $G$는 다음을 만족한다.
1. $G = B_4 = \mathbb{Z}_2^4 \rtimes S_4$이고 $|G| = 384$이다. 토러스 이동까지 더해도 $G$는 변하지 않는다.
2. $G$는 $D_4^{\mathrm{grid}} \times S_4$ (위수 192)가 아니다. $D_4^{\mathrm{grid}}$와 $S_4$는 가환하지 않으며 $D_4^{\mathrm{grid}} \cap S_4$의 크기는 2이다.

*증명.* (1) 보조정리 1에 의해 격자의 모든 대칭은 $B_4$에 속하므로 $G \subseteq B_4$이다. 행 반사는 $x_1$의 반전 $(\mathrm{id}, e_1)$이고 $\in G$이다. 이를 $\pi \in S_4$로 켤레하면 $(\mathrm{id}, e_{\pi^{-1}(1)})$가 되어 모든 입력 반전이 $G$에 속한다. 따라서 $N \subseteq G$이고 $S_4 \subseteq G$이므로 $G \supseteq N S_4 = B_4$이다. 토러스 이동도 보조정리 1에 의해 $B_4$에 속하므로 추가해도 군은 변하지 않는다.
(2) $(12)\thinspace(\mathrm{id}, e_1)\thinspace(12)^{-1} = (\mathrm{id}, e_2) \ne (\mathrm{id}, e_1)$이므로 가환하지 않는다. $D_4^{\mathrm{grid}}$는 행 반사 $\rho_r$ ($i \mapsto 3 - i$, 곧 $x_1$의 반전), 열 반사 $\rho_c$ ($x_3$의 반전), 전치 $\tau = (13)(24)$가 생성하며, 그 원소는 $\rho_r^a \rho_c^b \tau^e$ ($a, b, e \in \lbrace 0, 1\rbrace$)이다. $(a, b) \ne (0, 0)$이면 원소를 $(\pi, c)$ 꼴로 썼을 때 반전 성분 $c$가 0이 아니다. 따라서 $S_4 \cap D_4^{\mathrm{grid}} = \lbrace\mathrm{id}, \tau\rbrace$이다. $\blacksquare$

### 6.3 정리 3 ($B_4$ 아래의 궤도)
**정리 3.** $B_4$ 아래에서 $\mathcal{F}_4$는 **402개**의 궤도로 분할되고, 아핀 공간 $L$은 **6개**, 자기쌍대 공간 $D$는 **7개**의 궤도로 분할된다. 단조 공간 $M$은 입력 반전에 닫혀 있지 않아 $B_4$-궤도 분해를 정의하지 않는다.

*증명.* **전체 공간.** Burnside 보조정리에 의해 궤도 수는 $\frac{1}{384} \sum_{g \in B_4} 2^{c(g)}$이다. $(\pi, c) \in B_4$에서 $\pi$를 순환으로 분해하고, 각 순환 위에서 부호 벡터 $c$의 성분을 더한 값이 0 (mod 2)이면 양의 순환, 1이면 음의 순환이라 부른다. $B_4$의 켤레류는 이 부호 순환 구조 $(\lambda; \mu)$ ($\lambda$: 양의 순환 길이들, $\mu$: 음의 순환 길이들, $|\lambda| + |\mu| = 4$)로 분류되어 20개이다 (초팔면체군의 표준 사실이다. Carter, 1972; Humphreys, 1990). 켤레류의 크기는 $384/|C_{B_4}(g)|$이고 $|C_{B_4}(g)| = \prod_\ell (2\ell)^{m_\ell} m_\ell!$ ($\lambda$, $\mu$에 대해 각각 곱함)이다. 부호 순환 하나가 자신의 좌표 $\mathbb{Z}_2^\ell$ 위에서 일으키는 점 순환의 길이 분포는 양의 $\ell$-순환에 대해 $\ell = 1, 2, 3, 4$ 순으로 $\lbrace 1^2\rbrace$, $\lbrace 1^2, 2\rbrace$, $\lbrace 1^2, 3^2\rbrace$, $\lbrace 1^2, 2, 4^3\rbrace$이고, 음의 $\ell$-순환에 대해서는 $\lbrace 2\rbrace$, $\lbrace 4\rbrace$, $\lbrace 2, 6\rbrace$, $\lbrace 8^2\rbrace$이다. 이 분포는 다음과 같이 유도된다. 부호 $\ell$-순환 $g$는 좌표를 한 칸씩 이동시키며, 음의 순환이면 이동 중 한 좌표(순환을 한 바퀴 돌 때 한 번 지나는 위치)를 반전시킨다. $k = q\ell + r$ ($0 \le r < \ell$)로 쓰면 $g^k$는 $r$칸 이동과 $q$번의 $g^\ell$의 합성이고, $g^\ell$은 양의 순환이면 항등, 음의 순환이면 이 $\ell$개 좌표 전체의 반전(보수)이다. $r$칸 이동은 좌표를 $d = \gcd(\ell, r)$ ($r = 0$이면 $d = \ell$)개의 순환으로 나누고 각 순환은 길이 $\ell/d$이며 한 바퀴에 $r/d$번 경계를 넘는다. 따라서 음의 순환에서 $g^k$가 점을 고정하려면 각 순환의 반전 횟수 $r/d + q\ell/d$가 짝수여야 하고, 그러면 $|\mathrm{Fix}(g^k)| = 2^d$, 아니면 0이다 (양의 순환은 항상 $2^d$). $\langle g \rangle$의 위수($\ell$ 또는 $2\ell$)로 이 값들을 평균하면 점 순환의 수가 나오고, 길이가 정확히 $m$인 점의 수는 $m \mid \mathrm{ord}(g)$인 $m$에 대한 $|\mathrm{Fix}(g^m)|$에 뫼비우스 반전을 적용해 얻는다. 예컨대 음의 3-순환은 $k = 0, \dots, 5$에서 $8, 0, 2, 0, 2, 0$이므로 순환이 $12/6 = 2$개이고, 길이 2의 점 2개($k = 2, 4$에서 고정)와 길이 6의 점 6개로 나뉜다. 이 8가지 분포와 공식은 모두 `verify_picture_criterion.py` [A]에서 직접 열거와 대조했다. 서로 다른 좌표 블록에는 직접곱으로 작용하므로 길이 $a$, $b$인 두 순환은 $\gcd(a, b)$개의 순환을 만든다. 이 규칙으로 $c(g)$를 얻는다.

| $(\lambda; \mu)$ | 크기 | $c(g)$ | $\lvert\mathrm{Fix}\rvert = 2^{c(g)}$ | 자기쌍대 $\lvert\mathrm{Fix}_D\rvert$ |
|:---:|:---:|:---:|:---:|:---:|
| $(\thinspace; 4)$ | 48 | 2 | 4 | 0 |
| $(\thinspace; 3,1)$ | 32 | 4 | 16 | 0 |
| $(\thinspace; 2,2)$ | 12 | 4 | 16 | 0 |
| $(\thinspace; 2,1,1)$ | 12 | 4 | 16 | 4 |
| $(\thinspace; 1,1,1,1)$ | 1 | 8 | 256 | 0 |
| $(1; 3)$ | 32 | 4 | 16 | 4 |
| $(1; 2,1)$ | 24 | 4 | 16 | 4 |
| $(1; 1,1,1)$ | 4 | 8 | 256 | 16 |
| $(2; 2)$ | 24 | 4 | 16 | 4 |
| $(2; 1,1)$ | 12 | 8 | 256 | 0 |
| $(1,1; 2)$ | 12 | 4 | 16 | 4 |
| $(1,1; 1,1)$ | 6 | 8 | 256 | 16 |
| $(3; 1)$ | 32 | 4 | 16 | 4 |
| $(2,1; 1)$ | 24 | 8 | 256 | 16 |
| $(1,1,1; 1)$ | 4 | 8 | 256 | 16 |
| $(4; \thinspace)$ | 48 | 6 | 64 | 0 |
| $(3,1; \thinspace)$ | 32 | 8 | 256 | 16 |
| $(2,2; \thinspace)$ | 12 | 10 | 1024 | 0 |
| $(2,1,1; \thinspace)$ | 12 | 12 | 4096 | 64 |
| $(1,1,1,1; \thinspace)$ | 1 | 16 | 65536 | 256 |
| **합계** | **384** | | **154,368** | **2,688** |

따라서 궤도 수는 $154{,}368/384 = \mathbf{402}$이다. 이는 문헌의 4변수 NP 동치류의 개수와 일치한다.

**아핀 공간.** $f = c_0 \oplus \mathbf{c} \cdot \mathbf{x}$에 $(\pi, e)$를 작용하면 $c_0 \oplus \mathbf{c} \cdot e \oplus \mathbf{c}_\pi \cdot \mathbf{x}$이므로 아핀으로 닫혀 있고 $\mathbf{c}$의 해밍 무게 $w$는 보존된다. $w = 0$이면 상수 $c_0$가 바뀌지 않아 상수 0과 1이 별개의 궤도 2개이다. $w \ge 1$이면 $\mathbf{c} \cdot e = 1$인 $e$로 $c_0$를 뒤집을 수 있고 $S_4$가 같은 무게의 $\mathbf{c}$를 옮기므로 무게마다 궤도가 1개로 4개이다. 합하여 $2 + 4 = 6$이다.

**자기쌍대 공간.** $(\pi, e)$는 보수 사상과 가환하므로 $D$는 닫혀 있다. 5.3절의 논증이 그대로 적용되어 $|\mathrm{Fix}_D(g)| = 0$ (보수에 닫힌 점 순환이 있을 때) 또는 $2^{c(g)/2}$이다. 위 표의 마지막 열의 가중합은 $2{,}688$이고 $2{,}688/384 = \mathbf{7}$이다. $\blacksquare$

켤레류 표의 크기와 $c(g)$, 그리고 위 합들은 384개 원소의 전수 열거로 검증되었다 (`verify_b4_table.py`).

### 6.4 해석
- 정리 2에 의해 카르노맵 격자의 대칭과 변수 순열을 함께 허용한다는 것은 입력 반전까지 허용한다는 뜻이다. 그 동치류의 수가 402이다. 입력 반전이 없는 $S_4$ 아래에서는 3,984개이고, 격자의 평면 대칭 8개만으로는 8,548개, 토러스 이동까지 포함한 $W$ 아래에서는 805개이다 (두 수는 `verify_double_action.py`의 출력이다).
- 보조정리 2에 의해 변수 배치의 3개 동치류(정리 1)는 $B_4/W$의 세 잉여류, 곧 4개의 변수를 두 쌍으로 나누는 3가지 분할과 대응한다.
- 출력 반전까지 허용하면 NPN 동치류이고 그 수는 222로 알려져 있다.

### 6.5 카르노맵 그림의 대칭과 종류

**정리 4.** (1) *(시각적 대칭)* 표준 배치의 그림이 격자 대칭 $w \in W$ 아래 불변인 것은 $f \circ w = f$, 곧 $w \in \mathrm{Stab}_W(f)$인 것과 동치이다. (2) *(그림 종류의 개수)* 함수 $f$의 그림이 24개 변수 배치(또는 세 대표 배치)에서 $W$ 아래 서로 구별되는 종류의 수는 $B_4 \cdot f$ 안에 있는 $W$-궤도의 수와 같고, 그 값은 1, 2, 3 중 하나이다.

*증명.* (1) 그림의 셀 값은 $f$의 해당 입력점의 값이고, 격자 대칭 $w$는 입력점을 치환하므로(보조정리 1) 그림이 $w$ 아래 불변인 것은 $f \circ w = f$와 같다. (2) 배치 $\sigma$의 그림은 표준 배치의 그림에 변수 순열 $\pi_\sigma \in S_4$를 합성한 $f \circ \pi_\sigma$의 그림이다. 두 그림이 $W$ 아래 같은 종류라는 것은 $f \circ \pi_\sigma$와 $f \circ \pi_{\sigma'}$가 같은 $W$-궤도에 있다는 뜻이므로, 24개 배치 전체에서 구별되는 그림 종류의 수는 $S_4 \cdot f$가 만나는 $W$-궤도의 수이다. $W$가 모든 입력 반전 $N$을 포함하므로 (행 반사 $i \mapsto 3 - i$는 $x_1$의 반전이고, 이를 행의 맞바꿈 $i \mapsto -i$ (보조정리 1에서 $x_1$과 $x_2$의 맞바꿈)로 켤레하면 $x_2$의 반전이다. 열에서도 $x_3$, $x_4$의 반전이 같은 방식으로 나온다) $W S_4 = B_4$이고 $B_4 f = W (S_4 f)$이다. 따라서 이 수는 $B_4 f$ 안의 $W$-궤도의 수와 같다. $[B_4 : W] = 3$이므로 이 수는 3 이하이다. 정리 1에 의해 동치류가 같은 배치의 그림은 $W$ 아래 같은 종류이므로 세 대표 배치만으로 모든 종류가 나온다. $\blacksquare$

**정리 5 (그림 종류 수의 판정).** $B_4$는 세 변수 쌍 분할 $\lbrace 12|34\rbrace, \lbrace 13|24\rbrace, \lbrace 14|23\rbrace$ 위에 $B_4 \to S_4 \to S_3$을 통해 작용하고 (변수 4개를 두 쌍으로 나누는 방법은 3가지이고 변수 순열이 이 3가지를 서로 바꾸므로 $S_4 \to S_3$이 생긴다. $B_4 \to S_4$는 $(\pi, c) \mapsto \pi$이다), $W$는 표준 분할의 안정화군이다. $H_f$를 $f$의 $B_4$-안정화군이라 하고 $\bar H_f \le S_3$를 그 상이라 하면, $f$의 그림 종류 수는 $\bar H_f$가 세 분할에 작용할 때의 궤도 수와 같다. 곧
- $\bar H_f = 1$이면 3종,
- $|\bar H_f| = 2$이면 2종,
- $\bar H_f \supseteq A_3$ (위수 3 또는 6)이면 1종.

*증명.* 정리 4(2)에 의해 그림 종류 수는 $B_4 f \cong B_4/H_f$ 안의 $W$-궤도의 수이고, 이는 이중 잉여류 $W \backslash B_4 / H_f$의 개수이다. 이는 $H_f$가 $B_4/W$에 왼쪽 곱으로 작용할 때의 궤도 수와 같다(역원을 취해 대응시킨다). $B_4/W$는 $g W \mapsto g \cdot \lbrace 12|34\rbrace$로 세 분할의 집합과 $B_4$-동변으로 대응하므로($W$가 표준 분할의 안정화군이고 $B_4$가 세 분할에 추이적이므로) 이 궤도 수는 $\bar H_f$의 분할 위 궤도 수이다. $S_3$의 부분군은 자명군, 위수 2의 군(호환 하나가 한 분할을 고정하고 나머지 둘을 맞바꾼다), 위수 3 이상(전체 추이적)이므로 위와 같다. $\blacksquare$

이로써 그림 종류 수가 왜 1, 2, 3 중 하나인지가 군론적으로 설명된다. 전수 열거에서 $\bar H_f$의 크기별 함수 개수는 자명(3종) 26,112, 위수 2(2종) 36,204, 위수 6(1종) 3,220이다. 402개 모든 $B_4$-궤도에서 이 기준과 정의대로 센 값이 일치함을 확인했다 (`verify_picture_criterion.py`). 위수 3인 상은 나타나지 않는데, 이는 다음 때문이다.

**따름정리 6.** $\bar H_f$의 위수는 1, 2, 6 중 하나이다. 곧 $\bar H_f \supseteq A_3$이면 $\bar H_f = S_3$이고, 이때 그림은 한 종류뿐이다.

*증명.* $\bar H_f$가 3-순환을 포함하면 $H_f$에 $S_4$ 성분이 3-순환 $\pi$인 원소 $g$가 있다. $g^3$의 $S_4$ 성분은 $\pi^3 = \mathrm{id}$이므로 $g^3$은 순수 부호 원소이고 $g^6 = \mathrm{id}$이다. 따라서 $g$의 위수는 3 또는 6이다. 6이면 $g^2$가 위수 3이고 $S_4$ 성분 $\pi^2$가 3-순환이므로, 어느 경우에나 $H_f$는 $S_4$ 성분이 3-순환 $\pi$인 위수 3의 원소 $h = (\pi, c)$를 가진다 ($c \in \mathbb{Z}_2^4$는 부호 벡터).

(1) **$h$는 순수 순열 $\pi$와 켤레이다.** $\pi$의 순환 위치를 $\lbrace a, b, d\rbrace$, 고정 위치를 $e$라 하자. $h^3 = \mathrm{id}$은 $c_a + c_b + c_d = 0$이고 $c_e = 0$임을 뜻한다. 부호 벡터 $u$로 켤레하면 $c$는 $c + u + \pi u$로 바뀐다. $u \mapsto u + \pi u$는 $\lbrace a,b,d\rbrace$ 좌표 위에서 핵이 상수 벡터인 선형사상이므로 상의 차원이 2이고, 이는 합이 0인 벡터 전체이다. 따라서 $u$를 골라 $c$를 0으로 만들 수 있다. $u \cdot f$도 같은 $B_4$-궤도에 있고 그 안정화군은 $H_f$의 켤레이며 $S_3$ 상은 같으므로, 일반성을 잃지 않고 $h = \pi$로 둘 수 있다.

(2) **$\pi$로 불변이면 호환 $(a\thinspace b)$로도 불변이다.** 세 좌표 $a, b, d$ 위의 비트열에서 순환군 $\langle \pi \rangle$의 궤도는 해밍 무게 0, 1, 2, 3인 것끼리 정확히 한 궤도씩이다 (무게 1인 세 문자열은 서로 순환 이동이고 무게 2도 같다). 이는 $S_3$의 궤도와 같다. 그러므로 $\pi$로 불변인 $f$는 $\lbrace a,b,d\rbrace$ 위에서 대칭이고, 특히 $(a\thinspace b) \in H_f$이다.

(1), (2)에서 $H_f$는 $S_3$로 가는 상이 3-순환과 호환을 모두 포함하므로 $\bar H_f = S_3$이다. $\blacksquare$

(1)의 켤레 가능성과 원소 위수 분포(3-순환 성분을 가진 128개 원소는 위수 3이 32개, 6이 96개), 그리고 (2)가 65,536개 함수 전체에서 성립함은 `verify_picture_criterion.py` [B]로 확인했다.

**그림 종류별 함수 개수의 유도.** 정리 5와 따름정리 6에 의해 세 개수는 다음 두 수로 정해진다. $N_6$은 상이 $S_3$인 함수의 수로, $S_4$ 성분이 3-순환인 128개 원소 중 어느 하나로 불변인 함수의 수와 같다 (따름정리 6). $N_{\ge 2}$는 상이 호환을 포함하는 함수의 수 ($= N_2 + N_6$)로, $S_3$ 상이 호환인 192개 원소 중 어느 하나로 불변인 함수의 수이다. 원소 $g_1, \dots, g_k$로 동시에 불변인 함수는 이들이 생성하는 군 $G$의 점 궤도 위에서 상수인 함수이므로 그 수는 $2^{\mathrm{orb}(G)}$이다. 따라서 이 원소들이 생성하는 서로 다른 순환부분군 $C_1, \dots, C_m$에 대해 포함·배제

$$\Bigl|\bigcup_i \mathrm{Fix}(C_i)\Bigr| = \sum_{\varnothing \ne S \subseteq [m]} (-1)^{|S|+1}\thinspace 2^{\mathrm{orb}(\langle C_i : i \in S \rangle)}$$

가 합집합의 크기를 준다. 부분집합 $2^m$개를 모두 나열하지 않고, 같은 군을 생성하는 부분집합들의 부호를 모아 군별 계수로 계산한다 (동적계획). 3-순환 성분 원소는 순환부분군 64개, 호환 상 원소는 108개이고, 계수가 0이 아닌 생성군은 각각 37개, 1,308개이다. 결과는 $N_6 = 3{,}220$, $N_{\ge 2} = 39{,}424$이다. 따라서 $N_2 = 39{,}424 - 3{,}220 = 36{,}204$이고 $N_3 = 65{,}536 - 39{,}424 = 26{,}112$이다. 이 유도는 함수를 세지 않고 군의 점 궤도 수만 쓰며, 앞의 열거 결과와 일치한다 (`verify_stabilizer_counts.py` [B]). 다만 포함·배제의 합 자체는 컴퓨터로 수행한 유한 계산이며 닫힌 식은 아니다.

**계산 결과.** $B_4$-궤도 402개 중 $W$-궤도 1개로 이루어진 궤도의 함수는 모두 3,220개, 2개로 쪼개지는 궤도의 함수는 36,204개, 3개로 쪼개지는 궤도의 함수는 26,112개이고, $W$-궤도의 총수는 805이다. 이 값은 3.5절에서 직접 센 "그림 종류" 개수와 정확히 일치한다 (`verify_extras.py` [C]).

**예 (시각적 대칭).** $f = m(5,6,9,10)$은 $F(A,B,C,D) = F(C,D,A,B)$를 만족하고 $|\mathrm{Stab}_W(f)| = 32$이다. $f = m(1,4,7,11,13,14)$는 $F(A,B,C,D) = F(\neg C, D, \neg A, B)$도 만족하며, 이는 전치와 두 반사의 합성인 $W$의 원소이다 ($|\mathrm{Stab}_W(f)| = 4$).

배치에 따라 그림이 달라지는 예는 다음과 같다. 그림 8은 $f = m(5,6,9,10) = (A \oplus B)(C \oplus D)$의 세 대표 배치에서의 그림이다. $AC/BD$와 $AD/BC$의 그림은 같고 $AB/CD$의 그림만 다르므로 그림 종류는 2이고, $|\mathrm{Stab}_W(f)| = 32$이다. 그림 9는 $f = m(0,6,9,15) = \overline{A \oplus D}\mkern5mu\overline{B \oplus C}$의 그림이며, $AB/CD$와 $AC/BD$의 그림이 같고 $AD/BC$만 다르다 (그림 종류 2, $|\mathrm{Stab}_W(f)| = 16$).

| $AB/CD$ | $AC/BD$ | $AD/BC$ |
|:---:|:---:|:---:|
| ![m(5,6,9,10), AB/CD](../images/fig07_xorplane_ab_cd.png) | ![m(5,6,9,10), AC/BD](../images/fig08_xorplane_ac_bd.png) | ![m(5,6,9,10), AD/BC](../images/fig09_xorplane_ad_bc.png) |

**그림 8.** $f = m(5,6,9,10)$의 세 대표 배치에서의 그림.

| $AB/CD$ | $AC/BD$ | $AD/BC$ |
|:---:|:---:|:---:|
| ![m(0,6,9,15), AB/CD](../images/fig10_xnorplane_ab_cd.png) | ![m(0,6,9,15), AC/BD](../images/fig11_xnorplane_ac_bd.png) | ![m(0,6,9,15), AD/BC](../images/fig12_xnorplane_ad_bc.png) |

**그림 9.** $f = m(0,6,9,15)$의 세 대표 배치에서의 그림. 두 함수 모두 $W$ 아래 구별되는 그림은 2종이며 (`verify_figures.py`), 정리 5에 의해 안정화군의 $S_3$ 상의 크기가 2인 경우에 해당한다.

---

## 7. 결론, 한계, 향후 과제

### 7.1 결과 요약
1. 카르노맵의 격자 대칭은 입력 반전과 변수 순열이 이루는 군 $B_4$ (위수 384)의 부분군 $W$ (위수 128, 지표 3)이다.
2. 24가지 변수 배치는 $W$ 아래 3개의 동치류로 나뉜다. 격자의 회전·반사 8개만으로는 12개이다.
3. 완전 대칭 함수의 그림은 배치에 무관하다. 그 밖의 함수는 배치에 따라 달라질 수 있다.
4. $S_4$ 아래의 궤도 수: 전체 3,984, 아핀 10, 단조 30, 자기쌍대 32. $B_4$ 아래: 전체 402, 아핀 6, 자기쌍대 7.
5. 그림의 시각적 대칭은 $W$-안정화군의 원소이다 (정리 4(1)). 함수의 그림이 세 대표 배치에서 구별되는 종류의 수는 1, 2, 3 중 하나이며(정리 4(2), 정리 5), 해당하는 함수는 각각 3,220, 36,204, 26,112개이다.

### 7.2 한계
- 3장의 격자 대칭은 표준 Gray code 모델과 격자의 회전·반사·토러스 이동을 기준으로 한다. 다른 규약의 카르노맵(예: 다른 라벨 순서)에서는 군의 구체적 표현이 달라질 수 있으나, 보조정리 1의 구조는 유지된다.
- 단조 공간의 Fix 값은 궤도 순서집합의 상집합 수로 환원하여 손 계산 또는 알려진 값(Dedekind 수)으로 유도했다. 궤도 크기 분포는 $S_4$의 부분군 30개 위의 뫼비우스 반전이라는 유한 계산으로 유도했고 닫힌 식은 아니며, 30궤도 각각의 대표 함수 목록은 열거에 의존한다. 3.5절의 그림 개수는 정리 4로 $B_4$-궤도가 $W$-궤도로 쪼개지는 수와 같음을, 정리 5로 안정화군의 $S_3$ 상의 크기와 같음을 보였고, 그 수(3,220, 36,204, 26,112)는 군의 점 궤도 수에 대한 포함·배제로 유도했다. 이 포함·배제는 컴퓨터로 수행한 유한 계산이며 닫힌 식은 아니다. 정리 3의 $c(g)$ 표는 점 순환 분포 유도(공식은 증명했고 각 값은 열거로 대조)와 20개 켤레류의 크기 계산에 기대고 있다. 재현 스크립트가 제공된다.
- 결과는 4변수에 한정된다.
- 선행 연구 조사는 웹 검색과 OEIS 조회에 한정되었다. 3,984, 402, 30, 210은 문헌 값과 일치함을 확인했으나, 정리 1·4와 클론별 궤도 구조의 선행 여부는 전문가 검토로 다시 확인해야 한다.

### 7.3 향후 과제
1. **$n$변수로의 일반화.** $n$이 짝수이면 카르노맵은 $2^{n/2} \times 2^{n/2}$ 격자(양끝이 이어진 토러스 배열)이며 변수 순열과 입력 반전이 이루는 군은 $B_n = \mathbb{Z}_2^n \rtimes S_n$ (위수 $2^n n!$)이다. 다만 $n = 4$에서는 격자 토러스의 인접 그래프가 $Q_4$와 같지만, $n \ge 6$에서는 한 비트만 다른 셀들의 그래프 $Q_n$이 격자 토러스보다 간선이 많아 두 그래프를 구별해야 한다. 격자 대칭이 $B_n$의 어떤 부분군이 되는지, 변수 배치의 동치류 수가 어떻게 일반화되는지 규명하는 것이 과제이다. $n$이 홀수이면 격자가 정사각형이 아니므로 별도의 분석이 필요하다. 참고로 변수 순열만 허용한 예비 계산에서 $n=5$는 아핀 함수 64개가 12개, 단조 함수 7,581개가 210개의 $S_5$-궤도로 나뉜다 (`verify_extras.py` [F]).
2. **닫힌 식.** 단조 궤도 크기 분포(6, 2, 9, 6, 7)와 그림 종류별 함수 개수(26,112 / 36,204 / 3,220)를 컴퓨터 계산이 아니라 $S_4$, $B_4$의 부분군 격자의 구조에서 닫힌 식으로 유도하는 것이 남은 과제이다. 30개 궤도의 대표 함수 목록을 열거 없이 얻는 방법도 열려 있다.
3. **$n$변수 일반화에서의 그림 종류.** 정리 5의 $B_n/W$ 위의 안정화군 작용 구조가 $n \ge 6$ (짝수)에서 어떤 분포를 주는지 규명한다.

---

## 참고문헌 / References

1. Böhler, E., Creignou, N., Reith, S., & Vollmer, H. (2003). Playing with Boolean blocks, part I: Post's lattice with applications to complexity theory. *ACM SIGACT News*, 34(4), 38–52.
2. Burnside, W. (1897). *Theory of Groups of Finite Order*. Cambridge University Press.
3. Carter, R. W. (1972). Conjugacy classes in the Weyl group. *Compositio Mathematica*, 25(1), 1–59.
4. Church, R. (1940). Numerical analysis of certain free distributive structures. *Duke Mathematical Journal*, 6, 732–734.
5. Coxeter, H. S. M. (1973). *Regular Polytopes* (3rd ed.). Dover Publications.
6. Dedekind, R. (1897). Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler. *Festschrift der Herzoglichen Technischen Hochschule zur Naturforscher-Versammlung*, Braunschweig. Nachdruck in: *Gesammelte mathematische Werke*, Bd. 2, 103–147.
7. Golomb, S. W. (1959). On the classification of Boolean functions. *IRE Transactions on Circuit Theory*, CT-6(5), 176–186.
8. Gray, F. (1953). Pulse code communication. U.S. Patent 2,632,058.
9. Hall, P. (1936). The Eulerian functions of a group. *Quarterly Journal of Mathematics* (Oxford), 7, 134–151.
10. Hamming, R. W. (1950). Error detecting and error correcting codes. *Bell System Technical Journal*, 29(2), 147–160.
11. Harary, F., Hayes, J. P., & Wu, H.-J. (1988). A survey of the theory of hypercube graphs. *Computers & Mathematics with Applications*, 15(4), 277–289. https://doi.org/10.1016/0898-1221(88)90213-1
12. Harrison, M. A. (1963). The number of equivalence classes of Boolean functions under groups containing negation. *IEEE Transactions on Electronic Computers*, EC-12, 559–561.
13. Harrison, M. A. (1971). Counting theorems and their applications to classification of switching functions. In A. Mukhopadhyay (Ed.), *Recent Developments in Switching Theory*. Academic Press.
14. Humphreys, J. E. (1990). *Reflection Groups and Coxeter Groups*. Cambridge University Press.
15. Karnaugh, M. (1953). The Map Method for Synthesis of Combinational Logic Circuits. *Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics*, 72(5), 593–599.
16. MacMahon, P. A. (1916). *Combinatory Analysis*, Vol. 2. Cambridge University Press.
17. McCluskey, E. J. (1956). Minimization of Boolean functions. *Bell System Technical Journal*, 35, 1417–1444.
18. Neumann, P. M. (1979). A lemma that is not Burnside's. *The Mathematical Scientist*, 4, 133–141.
19. The On-Line Encyclopedia of Integer Sequences (OEIS). A000616 (NP-equivalence classes of Boolean functions), A000370 (NPN), A003180 (classes under the symmetric group $S_n$), A003182 (inequivalent monotone Boolean functions), A001206 (self-dual monotone functions). https://oeis.org
20. Pólya, G. (1937). Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. *Acta Mathematica*, 68, 145–254.
21. Post, E. L. (1941). *The Two-Valued Iterative Systems of Mathematical Logic*. Annals of Mathematics Studies, No. 5, Princeton University Press.
22. Quine, W. V. (1952). The problem of simplifying truth functions. *American Mathematical Monthly*, 59, 521–531.
23. Shannon, C. E. (1938). A symbolic analysis of relay and switching circuits. *Transactions of the American Institute of Electrical Engineers*, 57, 713–723.
24. Slepian, D. (1953). On the number of symmetry types of Boolean functions of $n$ variables. *Canadian Journal of Mathematics*, 5, 185–193. https://doi.org/10.4153/CJM-1953-020-x
25. Stephen, T., & Yusun, T. (2012). Counting inequivalent monotone Boolean functions. arXiv:1209.4623.
26. Veitch, E. W. (1952). A chart method for simplifying truth functions. *Proceedings of the Association for Computing Machinery* (Pittsburgh Meeting, May 2–3, 1952), 127–133.