Boolean 대수와 논리 표현

참과 거짓을 계산 대상으로 보기

Boolean 대수의 값은 0과 1입니다. 이 단원에서는 AND를 ∧, OR를 ∨, NOT을 ¬로 씁니다. AND는 둘 다 1일 때만 1, OR는 적어도 하나가 1이면 1, NOT은 0과 1을 바꿉니다. 실수 대수의 덧셈 기호를 OR와 혼용하지 않겠습니다.

입력 x,y가 각각 0 또는 1이면 네 입력 행이 있습니다. 모든 입력에서 출력이 같아야 두 함수가 동치입니다. 일부 표본에서 같은 출력이 나온다는 사실과 유한 진리표 전체의 동치는 다릅니다.

진리표를 비트에 저장하기

행 순서는 (0,0),(0,1),(1,0),(1,1)이고 행 번호는 2x+y입니다. 마스크의 해당 비트가 함수 출력입니다. 마스크 6=0110₂는 가운데 두 행에서만 참이므로 XOR입니다. 높은 비트부터 쓰는 이진 문자열과 낮은 행 번호부터 표시하는 표를 혼동하지 마세요.

두 입력 Boolean 함수는 출력 네 개를 독립적으로 정할 수 있으므로 총 2⁴=16개입니다. n개 입력이면 입력 행이 2ⁿ개이고 함수는 2^(2ⁿ)개입니다. 작은 입력 차원에서도 함수 공간이 급격히 커집니다.

최소항으로 논리식 만들기

각 행만 참으로 만드는 최소항은 ¬x∧¬y, ¬x∧y, x∧¬y, x∧y입니다. F가 참인 행의 최소항들을 OR로 묶으면 언제나 F를 복원합니다. 이것이 정규 DNF입니다.

참인 행이 없으면 빈 OR의 값은 0입니다. 모든 행이 참이면 상수 함수 1입니다. 이 구성은 존재를 보장하지만 가장 짧은 식을 준다는 보장은 없습니다. 논리 최소화는 별도의 문제입니다.

De Morgan 법칙의 증명

¬(x∧y)는 x,y가 모두 참인 경우만 거짓입니다. ¬x∨¬y도 둘 중 하나라도 거짓인 경우 참이므로 같은 함수입니다. 네 입력을 모두 나열해 확인할 수 있습니다.

조건식을 부정할 때 괄호 안 연산자까지 바뀐다는 점이 중요합니다. 예를 들어 “허가됨 AND 유효함”을 부정한 것은 “허가 안 됨 OR 유효하지 않음”입니다. 두 부정의 AND가 아닙니다.

GF(2) 다항식은 다른 연산을 사용한다

GF(2)에서 덧셈은 XOR이며 1+1=0입니다. 곱셈은 AND와 일치합니다. 모든 두 입력 함수는 다음 대수적 정규형 ANF로 쓸 수 있습니다.

계수는 a₀=F(0,0), aₓ=F(1,0)⊕F(0,0), aᵧ=F(0,1)⊕F(0,0), aₓᵧ=F(0,0)⊕F(0,1)⊕F(1,0)⊕F(1,1)입니다. 표에 네 입력을 대입하면 계수 공식이 직접 유도됩니다. XOR 함수의 계수는 (0,1,1,0)이고 NAND는 (1,0,0,1)입니다.

ANF의 +를 실수 덧셈이나 OR로 읽으면 식이 달라집니다. OR는 GF(2)에서 x⊕y⊕xy입니다. x=y=1을 넣어 차이를 확인하세요.

AI에서 Boolean 식과 부드러운 근사의 차이

검색 필터, 규칙 기반 라벨, 논리 제약을 정확한 Boolean 함수로 나타낼 수 있습니다. 반면 신경망의 sigmoid 출력은 연속 확률 점수이며 Boolean 출력과 같은 대수를 자동으로 따르지 않습니다. 임계값과 결정 규칙을 명시해야 합니다.

학습 표본에서 논리식과 모델 출력이 같아도 입력 공간 전체의 동치가 보장되지는 않습니다. 이 실습은 입력 두 개의 모든 네 행을 열거할 수 있어 완전 검사가 가능합니다. 더 큰 입력 차원에서는 SAT, BDD 등 별도 검증 도구를 고려합니다.

확인 문제와 답

1. XOR와 NAND가 다른 입력 행은? 00입니다.
2. OR의 ANF는? x⊕y⊕xy입니다.
3. 마스크 0의 활성 최소항은? 없으며 함수는 상수 0입니다.
4. 실수에서 x+y−xy를 0/1 입력에 제한하면? OR입니다. GF(2) 표현과 부호 규약이 다른 이유를 설명하세요.

추가 읽기: MIT Mathematics for Computer Science. 위 계수 공식과 작은 진리표는 직접 유도한 예제입니다.