1.11 논리곱(AND), 논리합(OR), 부정(NOT) 연산의 정의

1. 불 변수와 진리값

논리 연산의 정의에 앞서, 논리 연산이 적용되는 대상인 불 변수(Boolean Variable)를 정의한다. 불 변수는 참(True, 1)과 거짓(False, 0)이라는 두 개의 진리값(Truth Value) 중 정확히 하나를 취하는 변수이다. 불 변수의 값 집합은 $\mathbb{B} = \{0, 1\}$ 이다.

불 함수(Boolean Function)는 하나 이상의 불 변수를 입력으로 받아 하나의 불 값을 출력으로 산출하는 함수이다. $n$ 개의 불 변수를 입력으로 받는 불 함수는 다음과 같이 정의된다:

$f: \mathbb{B}^n \rightarrow \mathbb{B}$

논리곱, 논리합, 부정은 가장 기본적인 불 함수이며, 이들의 조합으로 모든 불 함수를 구성할 수 있다.

논리곱(AND) 연산

형식적 정의

논리곱(Conjunction)은 두 개의 불 변수를 입력으로 받아, 두 입력이 모두 참일 때에만 참을 출력하고, 그 외의 모든 경우에 거짓을 출력하는 이항 연산(Binary Operation)이다.

논리곱 연산은 $\wedge$ 기호로 표기하며, 불 대수에서는 곱셈 기호 $\cdot$ 로 표기한다. 두 불 변수 $p$ 와 $q$ 에 대한 논리곱의 정의는 다음과 같다:

$p \wedge q = \begin{cases} 1 & \text{if } p = 1 \text{ and } q = 1 \\ 0 & \text{otherwise} \end{cases}$

진리표(Truth Table)로 표현하면:

$p$	$q$	$p \wedge q$
0	0	0
0	1	0
1	0	0
1	1	1

1.1 산술적 표현

논리곱은 불 변수의 일반 산술적 곱셈과 동일하다:

$p \wedge q = p \cdot q$

이는 $p, q \in \{0, 1\}$ 일 때, $p \cdot q$ 의 산술적 결과가 논리곱의 진리표와 정확히 일치하기 때문이다.

대수적 성질

논리곱 연산은 다음의 대수적 성질을 만족한다:

교환법칙: $p \wedge q = q \wedge p$
결합법칙: $(p \wedge q) \wedge r = p \wedge (q \wedge r)$
멱등법칙: $p \wedge p = p$
항등원: $p \wedge 1 = p$ (1은 항등원)
영원소: $p \wedge 0 = 0$ (0은 영원소)
보원: $p \wedge \overline{p} = 0$

집합론적 해석

클래스(Class) 해석에서 논리곱은 두 집합의 교집합(Intersection)에 대응한다. $A$ 와 $B$ 가 두 집합일 때:

$A \cap B = \{x \mid x \in A \text{ and } x \in B\}$

원소 $x$ 가 $A \cap B$ 에 속하는 것은 $x$ 가 $A$ 에 속하고 동시에 $B$ 에 속하는 것과 동치이며, 이는 논리곱의 정의와 정확히 대응한다.

1.2 다중 입력 논리곱

논리곱의 결합법칙에 의해 $n$ 개의 불 변수에 대한 논리곱이 자연스럽게 정의된다:

$\bigwedge_{i=1}^{n} p_i = p_1 \wedge p_2 \wedge \cdots \wedge p_n$

$n$ -입력 논리곱은 모든 $p_i = 1$ 일 때에만 1을 출력하며, 하나라도 0이면 0을 출력한다.

논리합(OR) 연산

형식적 정의

논리합(Disjunction)은 두 개의 불 변수를 입력으로 받아, 하나 이상의 입력이 참일 때 참을 출력하고, 두 입력이 모두 거짓일 때에만 거짓을 출력하는 이항 연산이다.

논리합 연산은 $\vee$ 기호로 표기하며, 불 대수에서는 덧셈 기호 $+$ 로 표기한다. 형식적 정의는 다음과 같다:

$p \vee q = \begin{cases} 0 & \text{if } p = 0 \text{ and } q = 0 \\ 1 & \text{otherwise} \end{cases}$

진리표로 표현하면:

$p$	$q$	$p \vee q$
0	0	0
0	1	1
1	0	1
1	1	1

이 정의는 포괄적 논리합(Inclusive Disjunction)이다. 두 입력이 모두 참인 경우에도 출력이 참이라는 점에서 배타적 논리합(Exclusive Disjunction, XOR)과 구별된다.

1.3 산술적 표현

논리합의 산술적 표현은 다음과 같다:

$p \vee q = p + q - p \cdot q$

이 표현은 $p, q \in \{0, 1\}$ 일 때 논리합의 진리표를 정확히 재현한다. 검증:

$p=0, q=0$ : $0 + 0 - 0 = 0$
$p=0, q=1$ : $0 + 1 - 0 = 1$
$p=1, q=0$ : $1 + 0 - 0 = 1$
$p=1, q=1$ : $1 + 1 - 1 = 1$

또는 동등하게:

$p \vee q = \max(p, q)$

1.4 대수적 성질

논리합 연산은 다음의 대수적 성질을 만족한다:

교환법칙: $p \vee q = q \vee p$
결합법칙: $(p \vee q) \vee r = p \vee (q \vee r)$
멱등법칙: $p \vee p = p$
항등원: $p \vee 0 = p$ (0은 항등원)
영원소: $p \vee 1 = 1$ (1은 영원소)
보원: $p \vee \overline{p} = 1$

1.5 집합론적 해석

클래스 해석에서 논리합은 두 집합의 합집합(Union)에 대응한다:

$A \cup B = \{x \mid x \in A \text{ or } x \in B\}$

부정(NOT) 연산

형식적 정의

부정(Negation)은 하나의 불 변수를 입력으로 받아, 그 진리값을 반전시키는 단항 연산(Unary Operation)이다. 참을 거짓으로, 거짓을 참으로 변환한다.

부정 연산은 $\neg$ 기호, 상단 막대 $\overline{\phantom{x}}$ , 또는 프라임 기호 $'$ 로 표기한다. 형식적 정의는 다음과 같다:

$\neg p = \begin{cases} 1 & \text{if } p = 0 \\ 0 & \text{if } p = 1 \end{cases}$

진리표로 표현하면:

$p$	$\neg p$
0	1
1	0

1.6 산술적 표현

부정의 산술적 표현은 다음과 같다:

$\neg p = 1 - p$

검증: $p = 0$ 이면 $1 - 0 = 1$ , $p = 1$ 이면 $1 - 1 = 0$ .

대수적 성질

부정 연산은 다음의 성질을 만족한다:

이중 부정(Double Negation): $\neg(\neg p) = p$ . 부정을 두 번 적용하면 원래 값으로 복귀한다.
보원 성질: $p \wedge \neg p = 0$ , $p \vee \neg p = 1$

집합론적 해석

클래스 해석에서 부정은 집합의 여집합(Complement)에 대응한다. 전체 집합 $U$ 에 대해:

$\overline{A} = U \setminus A = \{x \in U \mid x \notin A\}$

2. 논리곱과 논리합의 상호 관계: 분배법칙

논리곱과 논리합 사이에는 분배법칙(Distributive Law)이 성립한다:

논리곱의 논리합에 대한 분배:
$p \wedge (q \vee r) = (p \wedge q) \vee (p \wedge r)$

논리합의 논리곱에 대한 분배:
$p \vee (q \wedge r) = (p \vee q) \wedge (p \vee r)$

두 번째 법칙은 일반 산술에서 성립하지 않는 불 대수 특유의 성질이다. 일반 산술에서 $a + (b \times c) \neq (a+b) \times (a+c)$ 이나, 불 대수에서는 멱등법칙에 의해 이 등식이 성립한다.

3. 흡수법칙(Absorption Laws)

논리곱과 논리합 사이에는 흡수법칙이 성립한다:

$p \wedge (p \vee q) = p$
$p \vee (p \wedge q) = p$

첫 번째 법칙의 증명: $p \wedge (p \vee q) = (p \wedge p) \vee (p \wedge q) = p \vee (p \wedge q)$ . $p \wedge q$ 가 참이면 $p$ 도 반드시 참이므로 $p \vee (p \wedge q) = p$ .

4. 쌍대 원리(Duality Principle)

불 대수에서 임의의 항등식(Identity)이 성립하면, 그 항등식에서 $\wedge$ 와 $\vee$ 를 교환하고, 0과 1을 교환한 항등식도 성립한다. 이를 쌍대 원리(Principle of Duality)라 한다.

예를 들어:

원래 항등식: $p \wedge 1 = p$ → 쌍대: $p \vee 0 = p$
원래 항등식: $p \wedge 0 = 0$ → 쌍대: $p \vee 1 = 1$
원래 항등식: $p \wedge (q \vee r) = (p \wedge q) \vee (p \wedge r)$ → 쌍대: $p \vee (q \wedge r) = (p \vee q) \wedge (p \vee r)$

쌍대 원리는 논리곱과 논리합이 불 대수에서 완전히 대칭적인 역할을 함을 보여준다. 이 대칭성은 격자 이론(Lattice Theory)에서 만남(Meet)과 이음(Join) 연산의 쌍대성으로 일반화된다.

5. 기능적 완전성(Functional Completeness)

세 연산 $\{\wedge, \vee, \neg\}$ 는 기능적으로 완전(Functionally Complete)하다. 즉, 임의의 불 함수 $f: \mathbb{B}^n \rightarrow \mathbb{B}$ 는 논리곱, 논리합, 부정의 유한 조합으로 표현 가능하다.

이 사실의 증명은 정규형(Normal Form)의 존재에 기반한다. 임의의 불 함수는 논리합 정규형(Disjunctive Normal Form, DNF) 또는 논리곱 정규형(Conjunctive Normal Form, CNF)으로 표현 가능하다.

논리합 정규형(DNF): 최소항(Minterm)의 논리합으로 표현된다. $n$ 개의 변수에 대한 최소항은 각 변수가 원래 형태 또는 부정 형태로 정확히 한 번 나타나는 논리곱이다:

$f(x_1, \ldots, x_n) = \bigvee_{\substack{(a_1, \ldots, a_n) \in \mathbb{B}^n \\ f(a_1, \ldots, a_n) = 1}} \left( \bigwedge_{i=1}^{n} x_i^{a_i} \right)$

여기서 $x_i^{1} = x_i$ , $x_i^{0} = \neg x_i$ 로 정의한다.

이 결과는 $\{\wedge, \vee, \neg\}$ 가 모든 불 함수를 생성하기에 충분한 연산 집합임을 보장하며, 이 세 연산이 논리학의 전 체계를 구축하기 위한 기본 빌딩 블록(Building Block)으로서의 역할을 수행함을 의미한다.

파생 연산

세 가지 기본 연산으로부터 다음의 중요한 파생 연산(Derived Operation)이 정의된다:

배타적 논리합(Exclusive OR, XOR):
$p \oplus q = (p \wedge \neg q) \vee (\neg p \wedge q)$

두 입력의 값이 다를 때에만 참을 출력한다. 산술적으로 $p \oplus q = (p + q) \mod 2$ 이다.

조건문(Conditional, Implication):
$p \rightarrow q = \neg p \vee q$

$p$ 가 참이고 $q$ 가 거짓인 경우에만 거짓이며, 나머지 모든 경우에 참이다.

쌍조건문(Biconditional, Equivalence):
$p \leftrightarrow q = (p \rightarrow q) \wedge (q \rightarrow p) = (p \wedge q) \vee (\neg p \wedge \neg q)$

두 입력의 진리값이 동일할 때 참이다.

이들 파생 연산은 독립적인 원시 연산이 아니라, 논리곱, 논리합, 부정으로 환원 가능한 복합 연산이다. 그럼에도 불구하고 프로그래밍 언어, 디지털 회로 설계, 논리학적 추론에서 빈번하게 사용되므로 고유한 기호와 명칭이 부여되어 있다.