2장 부울 대수

---

1. 서론

부울 대수에서는 0과 1을 사용하는데 보통

1 = True

0 = False 이다.

 

---

2. 기본 연산

보통 AND, OR, NOT 연산이 존재한다.

2.1 NOT 연산 (논리 부정)

“ ` “ 은 보수를 의미한다.

즉, 1 은 0으로, 0 은 1로 바뀐다.

X가 스위칭 변수라면 x = 0 일 때 x’ = 1 이다.

 

2.2 AND 연산 (논리곱)

AND 연산의 진리표는 다음과 같다.

보통 기호로는 • 을 사용하고 그림으로 표현하면 밑의 그림과 같다.

AND 연산은 논리 곱셈으로 불린다.

 

2.3 OR 연산 (논리 합)

OR 연산의 진리표는 다음과 같다.

보통 기호로는 + 를 사용하고 그림으로 표현하면 밑의 그림과 같다.

OR 연산은 논리 합으로 불린다.

 

---

3. 부울식과 진리표

논리 연산의 결과를 요약하여 나타낸 표이다.

각각의 가능한 입력 조합에 대해 해당하는 출력을 나열한다.

ex) AND 연산 진리표

 

연산을 수행할 때 순서가 지정될 필요가 있다면 괄호를 사용한다.

또한, 괄호가 없다면 보수화가 먼저 진행되고, AND, OR이 수행된다.

 

n개 변수를 가진 식에서 각 변수가 0 OR 1을 가진다면, 변수들의 서로 다른 조합의 개수는 2^n 이다.

 

---

4. 기본 정리

4.1 0과 1의 연산

• X + 0 = X, X ⋅ 1 = X
• X + 1 = 1, X ⋅ 0 = 0

 

4.2 멱등 법칙

같은 값을 여러 번 연산해도 결과가 변하지 않음

 

4.3 대합 법칙

값과 그 보수의 연산 결과를 나타낸다.

• (X)` = X

 

4.4 보수 법칙

논리 값의 보수에 대한 성질을 나타낸다.

 

---

5. 교환, 결합, 분배, 드모르간 법칙

5.1 교환 법칙

연산의 순서가 결과에 영향을 주지 않는다.

• X + Y = Y + X
• XY = YX

 

5.2 결합 법칙

연산의 그룹화가 결과에 영향을 주지 않는다.

• ( X + Y ) + Z = X + ( Y + Z ) = X + Y + Z
• (XY)Z = X(YZ) = XYZ

 

5.3 분배 법칙

하나의 연산이 다른 연산에 대해 분배되는 것을 의미한다.

• X(Y + Z) = XY + XZ
• X + YZ = (X + Y)(X + Z)

 

5.4 드모르간 법칙

• (X + Y) = XY`
• (XY) = X + Y`

 

---

6. 간략화 정리

6.1 연합

• XY + XY` = X
• (X + Y)(X + Y`) = X

 

6.2 흡수

• X + XY = X
• X(X + Y) = X

 

6.3 소거

• X + X`Y = X + Y
• X(X` + Y) = XY

 

6.4 합의

• XY + XZ + YZ = XY + XZ
• (X + Y)(X + Z)(Y + Z) = (X + Z)(X + Z)

 

6.5 곱셈전개와 인수화 정리

• (X + Y)(X + Z) = XZ + XY
• XY + XZ = (X + Z)(X + Y)

---

7. 곱셈 전개의 인수화

7.1 곱의합 (sum-of-products, SOP)

여러 개의 논리곱(AND 연산)의 결과들을 논리합(OR)연산으로 결합한 형태

즉, 합으로 이루어진 식이다.

ex) AB + CDE + AC`E

 

7.2 합의곱 (product-of-sums, POS)

여러 개의 논리합(OR 연산)의 결과들을 논리곱(AND 연산)으로 결합한 형태

즉, 곱으로 이루어진 식이다.

ex) (A + B)(C + D + E)(A + C + E)

== (A + B)(C + D + E) F

== ABC(D + E)

 

---

8. 부울식 보수화

부울식의 반전 및 보수는 드모르간 법칙을 적용하면 된다.