명제논리와 Bool 대수

By | November 19, 2016

19세기는 수학이 극도로 추상화되고 정제되는 시점이었다. Hilbert는 Euclid의 기하학 공리를 개선하여 새로운 기하학의 공리를 만들었으며, 그 공리들로부터 Descartes의 좌표를 이용한 Euclid 평면 \(\mathbb{R} ^2\)가 만들어질 수 있음을 보였다. Dyck과 Cayley는 기존의 군(group)의 개념을 정제하여 공리적으로 군을 정의하였다.

이 시기에 George Bool은 사고의 법칙을 정제하여 대수적 공리로 변환하고자 노력하였다. 즉 Bool은 논리와 대수의 공통점과 차이점을 비교하고 그들을 통합할 방법을 모색하였다. 여기서는 Bool 대수의 개념을 살펴보고 명제논리, Bool 대수, Bool 환 사이에 어떠한 관계가 있는지 살펴보자.

Bool 대수의 정의

Bool 대수를 정의할 때, 두 명제가 논리적으로 동등하면 두 명제는 서로 같은 것으로 여긴다. 또한 명제 논리에서는 기본결합자로서 \(\neg\)와 \(\rightarrow\)를 사용했지만 Bood 대수에서는 \(\vee,\) \(\wedge,\) \( ' \)을 사용한다. [이 세 결합자를 사용하는 이유는 이들이 대수에서 보통 성립하는 결합법칙, 교환법칙, 분배법칙을 만족시키기 때문이다.]

정의 1. 집합 \(B\)에 이항연산 \(\vee,\) \(\wedge\)와 일항연산 \( ' \) 그리고 상수 \(0,\) \(1\)이 주어져 있으며 다음 7개의 공리를 만족시킬 때 \( (B ,\, \vee ,\, \wedge ,\, ' ,\, 0 ,\, 1)\)을 Bool 대수(Boolean algebra)라고 부른다.

  • 결합법칙 : \(x \vee (y \vee z) = (x \vee y) \vee z ,\,\) \( x \wedge (y \wedge z ) = (x \wedge y) \wedge z \)
  • 교환법칙 : \(x \vee y = y \vee x ,\,\) \( x \wedge y = y \wedge x \)
  • 멱등법칙 : \(x \vee x = x ,\,\) \(x \wedge x = x\)
  • 흡수법칙 : \(x \vee ( x \wedge y) = x = x \wedge ( x \vee y\)
  • De Morgan의 법칙 : \( (x \vee y) ' = x ' \wedge y ' ,\,\) \( (x \wedge y) ' = x ' \vee y ' \)
  • 항등원법칙 : \(x \vee 0 = x ,\,\) \(x \wedge 1 = x\)
  • 보법칙 : \(x \vee y = 1\)일 필요충분조건은 \(y = x ' \)인 것이다.
    \(x \wedge y = 0\)일 필요충분조건은 \(y = x ' \)인 것이다.

물론 이들 공리가 서로 독립인 것은 아니다. 예를 들어 항등원법칙과 보법칙을 이용하면 \(0 ' = 1\)과 \(1 ' =0\)이며 보법칙과 교환법칙을 이용하면 \( (x ' ) ' = x \)를 얻는다. 이것을 이용하면 De Morgan의 법칙 중 하나를 이용하여 다른 하나를 이끌어낼 수 있다.

Bool 대수와 명제논리의 비교

이제 명제변수의 집합 \(P\)가 주어졌다고 가정하고, 그 집합 내에서의 모든 명제논리식의 집합을 생각하자. 두 논리식 \(\phi\)와 \(\psi\)가 논리적으로 동등하다(logically equivalent)는 것은 임의의 값매김 \(v\)에 대하여 \(v( \phi ) = v( \psi )\)가 성립하는 것을 의미한다. 두 논리식이 논리적으로 동등하다는 관계는 동등관계(equivalent relation)이다. 따라서 논리식 \(\phi\)의 동등류 \([\phi ]\)를 생각할 수 있다. 이 동등류들에 대하여 대수연산을 다음과 같이 정의한다. \[ \begin{eqnarray} [ \phi ] \vee [ \psi ] &:=& [ ( \phi \vee \psi ) ] , \\[6pt] [ \phi ] \wedge [ \psi ] &:=& [ ( \phi \wedge \psi ) ] , \\[6pt] [ \phi ] ' &:=& [( \neg \phi )] . \end{eqnarray} \] 또한 \(1\)을 토톨로지의 동등류로 정의하고 \(0\)을 모순의 동등류로 정의한다. 이때 집합 \(P\)에 위와 같은 대수연산과 \(1,\) \(0\)이 주어진 계를 \(B(P)\)로 나타낸다. 이와 같은 명제논리식의 대수를 Bool의 명제연산(propositional calculus)이라고 부른다.

다음 정리는 진리표를 이용하면 쉽게 증명된다.

정리 2. \(B(P)\)에 주어진 대수 연산은 잘 정의된 연산이며, 이들 연산에 대하여 \(B(P)\)는 Bool 대수가 된다.

모든 Bool 대수가 이와 같은 방식으로 만들어지는 것은 아니다. 즉 다른 방식으로 Bool 대수를 만들 수도 있다. \(U\)가 집합일 때 \(\mathcal{P} (U)\)에서의 연산을 다음과 같이 정의한다. \[ \begin{eqnarray} x \vee y &:=& x \cup y , \\[6pt] x \wedge y &:=& x \cap y , \\[6pt] x ' &:=& U \setminus x , \\[6pt] 1 &:=& U , \\[6pt] 0 &:=& \varnothing . \end{eqnarray} \] 이와 같은 연산이 주어진 집합 \(\mathcal{P} (U)\)는 Bool 대수가 되는데, 이러한 Bool 대수를 집합대수(algebra of sets)라고 부른다.

Bool 대수 \(B(P)\)는 \(\mathcal{P}(U)\)의 부분대수인 것으로 생각할 수도 있다. \(P\)가 명제변수의 집합이고 \(V(P)\)가 값매김들의 모임이라고 하자. 즉 \(P\)로부터 \(\left\{ \mathrm{T} ,\, \mathrm{F} \right\}\)로의 함수들의 모임을 \(V(P)\)라고 하자. 논리식 \(\phi\)에 대하여 함수 \(e_{\phi}\)를 다음과 같이 정의한다. \[e_{\phi} : V(P) \rightarrow \left\{\mathrm{T} ,\, \mathrm{F} \right\}, \,\, e_{\phi} (v) := v(\phi ) .\] 이때 \(e_{\phi}\)를 진릿값계산함수(evaluation function)라고 부른다. 정의에 의하여 동등한 논리식은 동일한 진릿값계산함수를 유도한다. 그러므로 논리식들의 동등류는 \(V(P)\)로부터 \(\left\{ \mathrm{T} ,\, \mathrm{F} \right\}\)로의 함수에 의하여 결정되는데, 정의역의 원소 중 함숫값이 \(\mathrm{T}\)인 것들만 모은 집합을 그 함수와 동일한 것으로 생각하면, 논리식들의 동등류는 결국 \(V(P)\)의 부분집합에 의하여 결정된다. 이와 같은 방법에 의한 논리식 \(\phi\)의 부분집합을 \(x_{\phi}\)라고 하자. 그러면 \[ \begin{eqnarray} v \in x_{(\phi \vee \psi )} & \,\, \Longleftrightarrow \,\, & v(( \phi \vee \psi )) = \mathrm{T} \\[6pt] & \,\, \Longleftrightarrow \,\, & v(\phi ) = \mathrm{T} \,\, \mathrm{o r} \,\, v(\psi ) = \mathrm{T} \\[6pt] & \,\, \Longleftrightarrow \,\, & v \in x_{\phi} \,\, \mathrm{o r} \,\, v \in x_{\psi} \\[6pt] & \,\, \Longleftrightarrow \,\, & v \in x_{\phi} \cup x_{\psi} \end{eqnarray} \] 이므로 \[x_{( \phi \vee \psi )} \,=\, x_{\phi} \cup x_{\psi}\] 를 얻는다. 같은 방법으로 다음 등식들을 얻는다. \[ \begin{eqnarray} x_{(\phi \wedge \psi )} & \,=\, & x_{\phi} \cap x_{\psi} , \\[6pt] x_{(\neg \phi )} & \,=\, & V(P) \setminus x_{\phi} , \\[6pt] x_1 & \,=\, & V(P) , \\[6pt] x_0 & \,=\, & \varnothing . \end{eqnarray} \] 그러므로 대응 \([ \phi ] \mapsto x_{\phi} \)는 논리식의 동등류들의 집합의 Bool 대수로부터 Bool 대수 \(\mathcal{P}(V(P))\)의 부분대수로의 준동형사상이 된다. 이러한 대응이 항상 위에로의 함수(onto)가 되는 것은 아니다. 그러나 \(P\)가 유한집합인 경우 이러한 대응은 위에로의 함수가 된다. \( |P| = n \)이면 \(|V(P)| = 2^n\)이며 Bool 대수의 기수는 \(2^{2^n}\)이다. 이제 \(p_1 ,\) \(p_2 ,\) \(\cdots ,\) \(p_n \)이 명제변수라고 하자. 임의의 값매김 \(v\)에 대하여 그에 대응되는 논리식 \(\tau_{v}\)를 정의하자. 먼저 \[ q_i := \begin{cases} p_i & \quad \mathrm{i f} \,\, v( p_i ) = \mathrm{T} , \\[10pt] (\neg p_i ) & \quad \mathrm{i f} \,\, v( p_i ) = \mathrm{F} . \end{cases} \] 그리고 \[\tau _v \, := \, ( q_1 \wedge q_2 \wedge \cdots \wedge q_n ) \] 으로 정의한다. 그러면 \(v ' \ne v \)인 임의의 \(v ' \)에 대하여 \(v( \tau _v ) = \mathrm{T} \)이고 \(v ' ( \tau _v ) = \mathrm{F} \)가 성립한다. 이제 \(x\)가 \(V(P)\)의 부분집합이고 공집합이 아니라고 하자. 그리고 \[\phi_x \,:=\, \bigvee _{v \in x} \tau_v \] 라고 정의하자. [위 등식의 우변과 같이 논리곱으로 표현된 논리식들의 논리합으로 나타나는 표현을 논리합 정규형태(disjunctive normal form)라고 부른다.] 그러면 \(v( \phi _x ) = \mathrm{T} \)일 필요충분조건은 \(v \in x\)가 된다. 따라서 \([\phi _x ]\)는 준동형사상에 의하여 \(x\)에 대응된다. 또한 모순은 공집합에 대응된다. 그러므로 준동형사상에 의하여 논리식들의 모임은 \(\mathcal{P}(V(P))\) 전체에 대응된다.

지금까지 논의한 내용을 정리하면 다음과 같다.

정리 3. \(P\)가 명제변수의 집합이라고 하자. 그러면 \(B(P)\)는 \(\mathcal{P}(V(P))\)의 부분대수와 동형이다. 특히 \(P\)가 유한집합이면 \( B(P) \cong \mathcal{P}(V(P))\)이다.

참고로, \(P\)가 가부번집합이면 \(P\)를 변수로 하여 만들어진 명제논리식들의 집합도 가부번집합이며 \(B(P)\)도 가부번집합이다. 이때 Cantor의 정리에 의하여 \[ | \mathcal{P} (V(P)) | > | V(P) | = | \mathcal{P}(P) | > |P| \] 이므로 \(B(P)\)와 \(\mathcal{P} (V(P))\)는 동형이 될 수 없다.

Bool 대수와 Bool 환의 비교

Bool 대수를 이용하면 환(ring)을 구성할 수 있으며, 역으로 환이 적절한 조건을 만족시키면 그러한 환을 이용하여 Bool 대수를 구성할 수 있다.

\((R ,\, + ,\, \cdot )\)가 단위원을 가진 환이고 임의의 \(x \in R\)에 대하여 \(x^2 =x\)를 만족시킬 때 \((R ,\, + ,\, \cdot )\)를 Bool 환(Boolean ring)이라고 부른다. Bool 대수와 Bool 환은 다음과 같은 관계를 가진다.

정리 4. Bool 대수와 Bool 환의 관계.

(ⅰ) \(B\)가 Bool 대수라고 하자. \(B\) 위에서의 두 연산 \(+,\) \(\cdot\)을

  • \(x+y \,:=\, (x \vee y) \wedge (x \wedge y) ' ,\)
  • \(x \cdot y \,:=\, x \wedge y \)

로 정의하면 \((B ,\, + ,\, \cdot )\)는 Bool 환이 된다. 이때 \(0\)은 덧셈에 대한 항등원이고 \(1\)은 곱셈에 대한 항등원이 된다.

(ⅱ) \(R\)가 Bool 환이라고 하자. \(R\) 위에서의 세 연산 \(\vee,\) \(\wedge,\) \( ' \)을

  • \(x \vee y \,:=\, x+y+xy ,\)
  • \(x \wedge y \,:=\, xy ,\)
  • \(x ' \,:=\, 1+x \)

로 정의하고 덧셈에 대한 항등원을 \(0 ,\) 곱셈에 대한 항등원을 \(1\)로 나타내면 \(R\)는 이 연산과 항등원에 대하여 Bool 대수가 된다.

(ⅲ) Bool 대수 \(B\)에서 시작하여 (ⅰ)의 방법으로 Bool 환을 만든 뒤 다시 (ⅱ)의 방법으로 Bool 대수를 만들면 그것은 \(B\)와 동일하다. 또한 Bool 환 \(R\)에서 시작하여 (ⅱ)의 방법으로 Bool 대수를 만든 뒤 다시 (ⅰ)의 방법으로 Bool 환을 만들면 그것은 \(R\)와 동형이다.

증명. (ⅰ) 진리표를 이용하면 \(B\)에서의 두 연산 \(+,\) \(\cdot\)이 환의 모든 조건을 만족시키고, 임의의 \(x\in B\)에 대하여 \(x^2 = x\)가 성립함이 증명된다. 먼저 \(x\)와 \(y\)의 값이 다를 때, 즉 \((x,\,y)\)의 값이 \((1,\,0)\)이거나 \((0,\,1)\)일 때에만 \(x \vee y = 1\)이고 그 외에는 \(x \vee y = 0\)이다. 이 사실을 이용하면 \(+\)에 대한 교환법칙이 성립한다는 사실과 \(0\)이 덧셈에 대한 항등원이라는 사실이 증명된다. 또한 다음 진리표를 이용하면 덧셈에 대한 결합법칙이 성립한다는 사실이 증명된다.

\(x\) \(y\) \(z\) \(x+y\) \(y+z\) \((x+y)+z\) \(x+(y+z)\)
1 1 1 0 0 1 1
1 1 0 0 1 0 0
1 0 1 1 1 0 0
1 0 0 1 0 1 1
0 1 1 1 0 0 0
0 1 0 1 1 1 1
0 0 1 0 1 1 1
0 0 0 0 0 0 0

곱셈에 대한 교환법칙과 결합법칙은 \(\wedge\)의 교환법칙과 결합법칙으로부터 직접 유도된다. 한편 \(x(y+z)\)와 \(xy+xz\)는 모두 \((x,\,y,\,z) = (1,\,1,\,0)\)이거나 \((x,\,y,\,z) = (1,\,0,\,1)\)일 때에만 \(1\)의 값을 가진다. 즉, 분배법칙이 성립한다.

끝으로 \(x \cdot x = x \wedge x = x\)이므로 \((B ,\, + ,\, \cdot )\)는 Bool 환이다.

(ⅱ) \(x\)와 \(y\)가 \(R\)의 원소일 때 다음이 성립한다. \[ \begin{eqnarray} x+y &\,=\,& (x+y)^2 \\[6pt] &\,=\,& x^2 + xy + yx = y^2 \\[6pt] &\,=\,& x+xy+yx+y \end{eqnarray} \] 이 등식과 덧셈에 대한 소거법칙을 이용하면 \(xy + yz = 0\) 즉 \(yx = -xy\)를 얻는다. 여기에 \(y=x\)를 대입하면 \(x^2 + x^2 = 0\) 즉 \(x+x=0\)이므로 \(x =-x\)를 얻는다. 이것은 임의의 \(x\)에 대하여 성립하므로 \[ yx = -xy = xy \] 를 얻는다. 따라서 곱셈에 대한 교환법칙이 성립한다. 즉 Bool 환은 단위원을 가진 가환환이다. 이 사실을 이용하면 세 연산 \(\vee,\) \(\wedge ,\) \( ' \)과 \(1,\) \(0\)이 주어진 집합 \(R\)가 Bool 대수의 조건을 만족시킴이 증명된다.

(ⅲ)은 (ⅰ)과 (ⅱ)에 의하여 자명하다.

Bool은 위와 같은 방법을 통해 명제논리의 이론을 대수학의 환 이론으로 변환하고자 하였다. 특히 Bool 환 \(B(P)\)의 값매김이 환 이론으로 이식되는 과정은 다음과 같다.

\(v\)가 값매김이면 \(v\)는 논리식들의 집합으로부터 \(\left\{ \mathrm{T} ,\, \mathrm{F} \right\}\)로의 함수이다. 이때 서로 동등한 논리식은 같은 진릿값에 대응되므로 \(v\)는 \(B(P)\)로부터 \(\left\{ \mathrm{T} ,\, \mathrm{F} \right\}\)로의 함수를 유도한다. 두 원소 \(\mathrm{T}\)와 \(\mathrm{F}\)를 각각 Bool 환 \(R_2 := \mathbb{Z} / 2\mathbb{Z} \)의 원소 \(1\)과 \(0\)과 같은 것으로 간주하면 값매김 \(v\)는 다음을 만족시킨다. \[ \begin{eqnarray} v(1) &=& 1 , \\[6pt] v(0) &=& 0 , \\[6pt] v(x+y) &=& v(x) + v(y) , \\[6pt] v(xy) &=& v(x) v(y) . \end{eqnarray} \] 즉 \(v\)는 준동형사상이다. 역으로 \(B(P)\)로부터 \(R_2\)로의 임의의 준동형사상에 대하여 그 준동형사상을 유도하는 값매김이 존재한다.

요컨대 \(P\)를 논리변수로 하는 논리식들의 집합에서 정의된 값매김은 \(B(P)\)로부터 \(R_2\)로의 준동형사상들과 일대일로 대응되므로 값매김에 대하여 연구하는 것은 곧 준동형사상을 연구하는 것과 같다.

Leave a Reply