Boolean Algebra

 

Definition of Boolean Algebra

부울대수의 정의

Define the Boolean set B = {0,1}, B⊆Z, Z is a set of integer numbers.

정의: 정수 집합의 부분집합으로써 0 과 1을 원소로 갖는 집합 B를 부울 집합이라고 합니다.

0이 false(거짓)을 의미하고, 1이 true(참)을 의미합니다.

반도체에서는 특정 전압을 걸었을 때 전류가 흐르면 1(true) 흐르지 않으면 0(false)로 처리합니다.

 

Followings are axiom of Boolean algebra. They are definition of logical operator.

아래 항목들은 부울대수의 공리이자, 논리 연산자의 정의이기도 합니다.

a. Definition of logical product (논리곱)

(1) 0 * 0 = 0

(2) 1 * 1 = 1

(3) 0 * 1 = 1 * 0 = 0

b. Definition of logical summation (논리합)

(4) 0 + 0 = 0

(5) 1 + 1 = 1

(6) 1 + 0 = 0 + 1 = 1

c. Definition of negation (부정)

(7) x = 0 ⇒ ~x = 1 ,for x ∈ B

(8) x = 1 ⇒ ~x = 0 ,for x ∈ B

 

<Remark>Operating order (연산 순서)

(1)negation (2)logical product (3)logical summation

 

<Theorem1>Single - Variable Theorems

For each x belongs to B, Following terms are true.

(1) x * 0 = 0

(2) x * 1 = x

(3) x * x = x

(4) x * (~x) = 0

 

(5) x + 1 = 1

(6) x + 0 = x

(8) x + x = x

(9) x + (~x) = 1

 

(10). ~(~x) = x ; Double negation

 

<Theorem2> Two and Three variable Theorems

Suppose that you take any elements, called x, y, and z in the Boolean set B,

then followings are true.

a. Commutative law (교환 법칙)

(1) x * y = y * x

(2) x + y = y + x

b. Associative law (결합 법칙)

(3) x * (y * z) = (x * y) * z

(4) x + (y + z) = (x + y) + z

c. Distributive law (분배 법칙)

(5) x * (y + z) = (x * y) + (x * z)

(6) x + (y * z) = (x + y) * (x + z)

d. Absorption law (흡수 법칙)

(7) x + (x * y) = x

(8) x * (x + y) = x

e. Combining

(9) (x * y) + (x * (~y)) = x

(10) (x + y) * (x + (~y)) = x

f. DeMorgan

(11) ~(x * y) = (~x) + (~y)

(12) ~(x + y) = (~x) * (~y)

 

<Note>The operator of logical product will be skipped like the multiplication of the real number system.

 

<proof (6)>

First, right handed side,

(x + y)(x + z) = (x + y)x + (x + y)z ∵ theorem2 (5)

= x(x + y) + z(x + y) ∵ theorem2 (1)

= (xx) + (xy) + (zx) + (zy) ∵ theorem2 (5)

= x + (xy) + (zx) + (zy) ∵ theorem1 (3)

= x + (xy) + (xz) + (zy) ∵ theorem2 (1)

= (x1) + (xy) + (xz) + (zy) ∵ theorem1 (2)

= x(1 + y) + (xz) + (zy) ∵ theorem2 (5)

= x((1 + y) + z)) + (zy) ∵ theorem2 (5)

= x((y + 1) + z)) + (zy) ∵ theorem2 (1)

= x(y + (1 + z)) + (zy) ∵ theorem2 (4)

= x((y + (z + 1)) + (zy) ∵ theorem2 (1)

= x(y + 1) + (zy) ∵ theorem1 (5)

= x1 + (zy) ∵ theorem1 (5)

= x + (zy) ∵ theorem1 (2)

= x + (yz) ∵ theorem2 (1)

End of proof

 

 

 

<Exercise> Summary following terms.

1.(X+Y)(Z+X)+XYZ+X(~Y)Z+XY(~Z)

 

2. (X+Y)(X+(~Y))

 

3. XY+XZ+X(~Y)(~Z)

 

4. (~X)Y+XY+X(~Y)

 

 

 

<Solutions>

1. X+YZ

2. X

3. X

4. X+Y