논리 함수 (Logic Function)

논리 함수는 참/거짓, 즉 1/0 값을 입력으로 받아 1 또는 0을 출력하는 함수입니다. 기본이 되는 것은 2입력 AND·OR와 1입력 NOT이며, 이들을 조합해 XOR(배타적 논리합)을 만들고, 다시 모든 디지털 계산을 만듭니다. 하드웨어에서는 각 함수를 논리 게이트로 구현하고, 게이트를 연결한 것을 논리 회로라고 합니다.

자세히 알아보기

기본 논리 함수의 진리표는 다음과 같습니다(입력 00, 01, 10, 11 순).

• AND: 0, 0, 0, 1 — 둘 다 1일 때만 1.
• OR: 0, 1, 1, 1 — 하나라도 1이면 1.
• XOR: 0, 1, 1, 0 — 서로 다를 때 1. mod 2 덧셈과 같습니다.
• NOT: 입력을 뒤집습니다.

{AND, OR, NOT}만으로 어떤 논리 함수든 만들 수 있으며(함수적 완전성), NAND 하나 또는 NOR 하나만으로도 가능합니다. 드모르간 법칙 ¬(a ∧ b) = ¬a ∨ ¬b는 회로를 바꿔 쓰는 기본 규칙입니다. 논리 함수는 같은 입력에 항상 같은 출력을 내는 결정론적 함수이며, n개의 입력을 받는 논리 함수는 2²ⁿ가지가 존재합니다. 수학적으로 더 일반적인 이름은 불 함수입니다.

블록체인·암호화폐에서는

• 해시 함수: 비트코인 채굴과 주소 생성에 쓰이는 SHA-256은 32비트 워드에 대한 논리 함수로 구성됩니다. 선택 함수 Ch(x, y, z) = (x ∧ y) ⊕ (¬x ∧ z)와 다수결 함수 Maj(x, y, z) = (x ∧ y) ⊕ (x ∧ z) ⊕ (y ∧ z)가 대표적입니다. 이더리움의 Keccak-256도 AND·NOT·XOR로 이뤄진 χ 단계가 유일한 비선형 요소입니다.
• EVM: 이더리움 가상 머신에는 AND, OR, XOR, NOT 연산 코드가 있어 스마트 컨트랙트가 비트 마스크나 플래그를 처리합니다.
• 영지식 증명과 MPC: 계산을 논리 회로(또는 산술 회로)로 표현한 뒤 그 회로의 올바른 실행을 증명하거나, 가블드 회로로 여러 당사자가 입력을 숨긴 채 함께 계산합니다. 이런 프로토콜에서는 XOR가 거의 공짜이고 AND가 비싼 경우가 많아, AND 게이트 수를 줄이는 것이 최적화의 핵심입니다.

쉽게 말하면

논리 함수는 '예/아니오' 신호를 받아 정해진 규칙대로 '예/아니오'를 내놓는 아주 작은 판단 장치입니다. 수십억 개를 엮으면 컴퓨터가 됩니다.

예시

a = 1, b = 0일 때 a AND b = 0, a OR b = 1, a XOR b = 1, NOT a = 0입니다.