불 함수

1. 개요

불 함수는 논리 연산의 기본 요소로, 참 또는 거짓 값을 입력으로 받아 단일의 참 또는 거짓 값을 출력하는 함수이다. 불 함수는 NOT, AND, OR, XOR 등 다양한 논리 연산을 포함하며, 진리표, 이진 결정 다이어그램, 벤 다이어그램, 명제 공식 등을 사용하여 표현될 수 있다. 불 함수는 회로의 간소화, 암호학, 복잡도 이론, 디지털 컴퓨터 설계 등 다양한 분야에 응용되며, 특히 대칭키 암호 설계에서 중요한 역할을 한다.

2. 예시

기본적인 대칭 불 함수(논리 연산자 또는 논리 게이트)는 다음과 같다.

* NOT, 부정 또는 보수 - 하나의 입력을 받아 해당 입력이 거짓일 때 참을 반환한다.
* AND 또는 결합 - 모든 입력이 참일 때 참이다.
* OR 또는 분리 - 입력 중 어느 하나라도 참일 때 참이다.
* XOR 또는 배타적 분리 - 하나의 입력이 참이고 다른 입력이 거짓일 때 참이다.
* NAND 또는 셰퍼 스트로크 - 모든 입력이 참인 경우가 아닐 때 참이다.
* NOR 또는 논리 nor - 입력 중 어느 것도 참이 아닐 때 참이다.
* XNOR 또는 논리적 동일성 - 두 입력이 같을 때 참이다.

더 복잡한 함수의 예는 다수결 함수(홀수 개의 입력)이다.

3. 표현

불 함수는 다양한 방식으로 표현될 수 있다.

* 진리표: 모든 가능한 인수의 값에 대한 값을 명시적으로 나열한다.
* 마르캉드 다이어그램: 2차원 그리드에 배열된 진리표 값 (카르노 맵에 사용)
* 이진 결정 다이어그램: 이진 트리의 맨 아래에 진리표 값을 나열한다.
* 벤 다이어그램: 평면의 영역을 색칠하여 진리표 값을 묘사한다.

알파벳 순으로 기본적인 불 함수를 사용하여 명제 공식으로 표현할 수 있다.

* 부정 정규형: 인수와 보수의 AND 및 OR의 임의의 혼합
* 선언적 정규형: 인수와 보수의 AND의 OR
* 결합적 정규형: 인수와 보수의 OR의 AND
* 정규형: 함수를 고유하게 식별하는 표준화된 공식:
* 대수적 정규형 또는 제갈킨 다항식: 인수(보수 허용 안 함)의 AND의 XOR
* 전체(표준) 선언적 정규형: 각 인수 또는 보수(민텀)를 포함하는 AND의 OR
* 전체(표준) 결합적 정규형: 각 인수 또는 보수(맥스텀)를 포함하는 OR의 AND
* 블레이크 정규형: 함수의 모든 소수 함의자의 OR

불 공식은 그래프로도 표시할 수 있다.

* 명제 방향 비순환 그래프
* 디지털 회로 논리 게이트 다이어그램, 불 대수 회로
* AND-인버터 그래프: AND와 NOT만 사용

전자 회로를 최적화하기 위해 불 공식은 최소화 할 수 있으며, 퀸-맥클러스키 알고리즘 또는 카르노 맵을 사용할 수 있다.
선언 표준형과 연언 표준형이 대표적이다. 그 외에, 리드-뮬러 표준형 등이 있다.
리드-마러 표준형(:en:Algebraic normal form)은 곱(AND)의 배타적 논리합(XOR)에 의한 표준형이다.

여기서 a₀, a₁, ..., a_1,2,...,n ∈ {0,1}^* 이다.

따라서 열 a₀,a₁,...,a_1,2,...,n의 값의 열도 부울 함수를 유일하게 나타낸다. 부울 함수의 대수적 차수는 하나의 (AND) 항에 나타나는 x_i의 개수로 나타낸다. 즉, f(x₁,x₂,x₃) = x₁ + x₃의 차수는 1(선형)이고, f(x₁,x₂,x₃) = x₁ + x₁x₂x₃의 차수는 3(입방)이다.

4. 분석

불 함수는 다음과 같은 속성들을 가질 수 있다.

* 상수: 인수에 관계없이 항상 참 또는 항상 거짓이다.
* 단조: 모든 인수 값의 조합에 대해 인수를 거짓에서 참으로 변경하면 출력만 거짓에서 참으로 바뀔 수 있으며 참에서 거짓으로 바뀔 수는 없다. 특정 변수에 대한 변경에 대해 단조이면 해당 함수는 해당 변수에 대해 단항이라고 한다.
* 선형: 각 변수에 대해 해당 변수의 값을 반전하면 진리값에 항상 차이가 있거나 전혀 차이가 없다. ( 패리티 함수 ).
* 대칭: 값은 인수의 순서에 의존하지 않는다.
* 1회 읽기: 논리곱, 논리합, 부정으로 각 변수의 단일 인스턴스로 표현할 수 있다.
* 균형: 진리표에 0과 1의 수가 동일하게 포함된 경우. 함수의 해밍 가중치는 진리표에서 1의 개수이다.
* 벤트: 미분값이 모두 균형을 이룬다(자기 상관 스펙트럼이 0).
* m차 상관 무관: 최대 m개의 인수 중 모든 (선형) 조합과 출력이 상관관계가 없는 경우.
* 회피: 함수의 평가에 항상 모든 인수의 값이 필요한 경우
* 불 함수는 (합성으로) 임의의 불 함수를 생성하는 데 사용할 수 있는 경우 셰퍼 함수이다.( 기능적 완전성 참조)
* 함수의 대수 차수는 대수적 정규 형식에서 가장 높은 차수의 단항식의 차수이다.
회로 복잡성은 불 함수를 계산할 수 있는 회로의 크기 또는 깊이에 따라 분류하려고 한다.

5. 효율적 표현

복잡한 불 함수를 효율적으로 표현하기 위한 방법들은 다음과 같다:

* 진리표: 모든 가능한 인수의 값에 대한 값을 명시적으로 나열한다.
* 마르캉드 다이어그램: 2차원 그리드에 배열된 진리표 값 (카르노 맵에 사용)
* 이진 결정 다이어그램: 이진 트리의 맨 아래에 진리표 값을 나열
* 벤 다이어그램: 평면의 영역을 색칠하여 진리표 값을 묘사한다.

알파벳 순으로 기본적인 불 함수를 사용하여 명제 공식으로 표현할 수 있다.

* 부정 정규형: 인수와 보수의 AND 및 OR의 임의의 혼합
* 선언적 정규형: 인수와 보수의 AND의 OR
* 결합적 정규형: 인수와 보수의 OR의 AND
* 정규형: 함수를 고유하게 식별하는 표준화된 공식:
* 대수적 정규형 또는 제갈킨 다항식: 인수(보수 허용 안 함)의 AND의 XOR
* 전체(표준) 선언적 정규형: 각 인수 또는 보수(민텀)를 포함하는 AND의 OR
* 전체(표준) 결합적 정규형: 각 인수 또는 보수(맥스텀)를 포함하는 OR의 AND
* 블레이크 정규형: 함수의 모든 소수 함의자의 OR

불 공식은 그래프로도 표시할 수 있다.

* 명제 방향 비순환 그래프
* 디지털 회로 논리 게이트 다이어그램, 불 대수 회로
* AND-인버터 그래프: AND와 NOT만 사용

전자 회로를 최적화하기 위해 불 공식은 최소화 할 수 있으며, 퀸-맥클러스키 알고리즘 또는 카르노 맵을 사용할 수 있다.

명제 논리의 논리식으로 표현할 수 있지만, 효율적인 표현으로는 다음과 같은 것들이 있다.

* 이진 결정 다이어그램 (BDD)
* 부정 표준형
* 명제 방향 비순환 그래프 (PDAG)

선언 표준형과 연언 표준형이 대표적이다. 그 외에, 리드-뮬러 표준형 등이 있다.
리드-마러 표준형(:en:Algebraic normal form)은 곱(AND)의 배타적 논리합(XOR)에 의한 표준형이다.

👆

좌우로 밀어서 보기

📌 열 고정 해제

수식

$f(x\_1,\; x\_2,\; \backslash ldots\; ,\; x\_n)\; =\; a\_0\; +\; a\_1x\_1\; +\; a\_2x\_2\; +\; \backslash ldots\; +\; a\_nx\_n\; +\; a\_\{1,2\}x\_1x\_2\; +\; a\_\{n-1,n\}x\_\{n-1\}x\_n\; +\; \backslash ldots\; +\; a\_\{1,2,\backslash ldots,n\}x\_1x\_2\backslash ldots\; x\_n$

여기서 $a\_0,\; a\_1,\; \backslash ldots,\; a\_\{1,2,\backslash ldots,n\}\; \backslash in\; \backslash \{0,1\backslash \}^*$이다.

따라서 열 $a\_0,a\_1,\backslash ldots,a\_\{1,2,\backslash ldots,n\}$의 값의 열도 부울 함수를 유일하게 나타낸다. 부울 함수의 대수적 차수는 하나의 (AND) 항에 나타나는 $x\_i$의 개수로 나타낸다. 즉, $f(x\_1,x\_2,x\_3)\; =\; x\_1\; +\; x\_3$의 차수는 1(선형)이고, $f(x\_1,x\_2,x\_3)\; =\; x\_1\; +\; x\_1x\_2x\_3$의 차수는 3(입방)이다.

6. 간소화

불 함수를 간소화하는 방법은 다음과 같다.

* 컷 앤 트라이 법: 불 대수의 정의를 이용하여 효율적인 표현으로 변형한다.
* 벤 다이어그램: 벤 다이어그램을 이용하여 시각적으로 알기 쉬운 표현으로 한다. 이는 인간의 직관에 의한 것으로, "변환하는 방법"이라고 할 수는 없다.
* 카르노 맵: 카르노 맵을 이용하여 효율적인 표현으로 변형한다.
* 콰인-맥클러스키 방법: 콰인-맥클러스키 방법을 이용하여 효율적인 표현으로 변형한다. 계산기로 간소화하는 데 적합하다.

7. 파생 함수

불 함수는 불의 전개 정리를 사용하여 긍정적이고 부정적인 섀넌 코팩터(섀넌 전개)로 분해될 수 있으며, 이는 인수를 (0 또는 1로) 고정하여 얻은 (k-1)항 함수이다. 입력 집합(선형 부분 공간)에 선형 제약을 가하여 얻은 일반적인 (k-항) 함수를 부분 함수라고 한다.

함수의 불 미분은 선택한 입력 변수에 함수의 출력이 민감할 때 참이 되는 (k-1)항 함수이다. 이는 두 개의 해당 코팩터의 XOR이다. 미분과 코팩터는 리드-뮬러 전개에 사용된다. 이 개념은 x와 x + dx에서의 함수의 차이(XOR)로 얻은 dx 방향의 k-항 미분으로 일반화될 수 있다.

불 함수의 뫼비우스 변환(또는 불-뫼비우스 변환)은 모노미얼 지수 벡터의 함수로, 해당 다항식(대수적 정규형)의 계수 집합이다. 이는 자기 역변환이다. 이는 고속 푸리에 변환과 유사한 버터플라이 알고리즘("고속 뫼비우스 변환")을 사용하여 효율적으로 계산할 수 있다. 일치 불 함수는 뫼비우스 변환과 같으며, 즉 진리표(민텀) 값이 대수적(모노미얼) 계수와 같다. k개의 인수를 갖는 일치 함수는 2^2(k−1)개가 있다.

8. 암호학적 분석

불 함수는 암호학, 특히 대칭키 암호 설계에서 중요한 역할을 한다.

불 함수의 월시 변환은 선형 함수(월시 함수)로의 분해 계수를 제공하는 k-진 정수 값 함수이며, 이는 푸리에 변환에 의한 실수 값 함수의 조화 분해와 유사하다. 그 제곱은 전력 스펙트럼 또는 월시 스펙트럼이다. 단일 비트 벡터의 월시 계수는 해당 비트와 불 함수의 출력 간의 상관 관계를 측정하는 척도이다. 최대 (절대값) 월시 계수는 함수의 선형성이라고 한다. 모든 월시 계수가 0인 비트의 최대 개수(차수) (즉, 하위 함수가 균형을 이룸)는 복원력이라고 하며, 해당 차수에 대해 함수는 상관 면역이라고 한다. 월시 계수는 선형 암호 분석에서 핵심적인 역할을 한다.

불 함수의 자기 상관은 입력의 특정 변경 집합과 함수 출력 간의 상관 관계를 제공하는 k-진 정수 값 함수이다. 주어진 비트 벡터의 경우 해당 방향의 도함수의 해밍 가중치와 관련이 있다. 최대 자기 상관 계수(절대값)는 절대 지표라고 한다. 특정 비트 수에 대해 모든 자기 상관 계수가 0인 경우 (즉, 도함수가 균형을 이룸) 함수는 해당 차수에 대해 전파 기준을 만족한다고 하며, 모두 0인 경우 함수는 벤트 함수이다. 자기 상관 계수는 차분 암호 분석에서 핵심적인 역할을 한다.

불 함수의 월시 계수와 자기 상관 계수는 비너-킨친 정리와 동등한 관계를 가지며, 이는 자기 상관과 전력 스펙트럼이 월시 변환 쌍임을 나타낸다.

이러한 개념은 출력 비트(좌표)를 개별적으로 고려하거나, 더 자세하게는 출력 비트의 모든 선형 함수의 집합, 즉 해당 구성 요소를 살펴봄으로써 벡터 불 함수로 자연스럽게 확장될 수 있다. 구성 요소의 월시 변환 집합은 선형 근사표 (LAT) 또는 상관 행렬로 알려져 있으며, 입력 및 출력 비트의 다양한 선형 조합 간의 상관 관계를 설명한다. 구성 요소의 자기 상관 계수 집합은 자기 상관표이며, 구성 요소의 월시 변환을 통해 입력 및 출력 비트의 차이 간의 상관 관계를 나열하는 더 널리 사용되는 차분 분포표 (DDT)와 관련이 있다(참고: S-box).

9. 실수 다항식 형태

모든 불 함수 $f(x):\; \backslash \{0,1\backslash \}^n\; \backslash rightarrow\; \backslash \{0,1\backslash \}$는 $\backslash mathbb\{R\}^n$의 다중선형 다항식으로 고유하게 확장(보간)될 수 있으며, 이는 진리표 값에 라그랑주 다항식의 지표 다항식을 곱하여 합산하여 구성된다.
:$$f^*(x)\; =\; \backslash sum\_\{a\; \backslash in\; \{\backslash \{0,1\backslash \}\}^n\}\; f(a)\; \backslash prod\_\{i:a\_i=1\}\; x\_i\; \backslash prod\_\{i:a\_i=0\}\; (1-x\_i)$$
예를 들어, 이진 XOR 함수 $x\; \backslash oplus\; y$의 확장은 다음과 같다.
:$$0(1-x)(1-y)\; +\; 1x(1-y)\; +\; 1(1-x)y\; +\; 0xy$$
이것은 다음과 같다.
:$$x\; +\; y\; -2xy$$
다른 예로는 부정($1-x$), AND($xy$) 및 OR($x\; +\; y\; -\; xy$)가 있다. 모든 피연산자가 독립적일 때(변수를 공유하지 않음) 함수의 다항식 형태는 불리언 수식에서 연산자의 다항식을 반복적으로 적용하여 찾을 수 있다. 계수를 모듈러 산술로 계산하면 대수적 정규형(제갈킨 다항식)을 얻는다.

다항식의 계수에 대한 직접적인 표현은 적절한 미분을 통해 파생될 수 있다.
:
f^*(01) & = & (\partial_1f^*)(00) & = & -f(00) + f(01) \\
f^*(10) & = & (\partial_2f^*)(00) & = & -f(00) + f(10) \\
f^*(11) & = & (\partial_1\partial_2f^*)(00) & = & f(00) -f(01)-f(10)+f(11) \\
\end{array}
이는 비트 벡터의 뫼비우스 변환으로 일반화된다.
:$$f^*(m)\; =\; \backslash sum\_\{a\; \backslash subseteq\; m\}\; (-1)^$$