Unit 2 - Boolean Algebra - 1

Boolen algebrea - 부울 대수

1.  변수의 값이 true and false 지만, 보통 0과 1로 표현합니다. -> 0과 1은 수치적인 값이 아닙니다.
2. 주요 연산은 AND, OR, NOT이 있습니다.
3. Switching algebra와 Boolean algebra는 주로 교환 가능하게 사용됩니다.

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

Basic Operations 

• 부울 표현식은 하나 이상의 변수 또는 상수를 통해 기본 연산을 적용하여 형성됩니다.
• 상수 혹은 변수의 간단한 표현은 X, Y', 0과 같은 것을 사용합니다.
• 연산의 순서는 NOT -> AND -> OR입니다.

 

NOT(complement/Inversion)

• 0의 complement는 1입니다. 1의 complement는 0입니다. 0' = 1 and 1' = 0
• if X = 0 -> X' = 1 or if X = 1 -> X' = 0 입니다.
• NOT을 inverter로 표현하는 방법

  

AND operaton / swtiching circuits

• AND 연산은 아래 그림을 따릅니다.

  

  "."은 AND를 의미합니다.
• 이진수에서의 연산처럼 보이지만 실제로는 아닙니다. 
• C=1이라는 의미는 A = 1 && B = 1이라는 의미입니다.

OR operation

• OR 연산은 아래의 그림을 따릅니다.

  

  "+"는 OR를 의미합니다.
• C=1이라는 의미는 A = 1 || B = 1이라는 것을 의미합니다.
• inclusive - OR이라고도 불립니다.

EX) [A(C+D)]' + BE

논리 게이트 회로의 표현

IF A = B = C = 1, D = E = 0일 경우 -> [1(1+0)]' + 10 = 0 + 0 = 0

 

Literal(문자)

• 논리 표현에서의 변수, 보수입니다.
• ab'c + a'b + a'b' + b'c' -> 해당 식에 따르면 3개의 변수, 10개의 literal이 사용되었습니다.

Truth table(진리표)

• 식에서의 변수들의 모든 가능한 값을 표로 나타낸 것입니다.
• N개의 변수가 있을 때,  각각의 변수는 0,1의 값을 가질 수 있으니 총 2^N개의 조합이 나옵니다.

 

EX) AB' + C = (A + C)(B' + C) <- 중요!

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

Basic Theorems

• Operations with 0 and 1 
• Idempotent law(멱등 법칙)
• Involution law(대합 법칙)
• Law of complementarity(보수 법칙)

법칙들과 switch circuit

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

Commutative Laws for AND and OR : 교환법칙

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

Associative Laws for AND ans OR : 결합법칙

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

Truth table 과 논리 회로

EX)

1. XYZ = 1 -> X = Y = Z = 1 이여야 합니다

2. X + Y + Z = 0 -> X = Y = Z = 0 이여야 합니다.

 

Distribute Law : 교환 법칙(역방향으로 적용하는 것도 중요합니다.)

• X(Y + Z) = XY + XZ
• X + (YZ) = (X + Y)(X + Z) (Dual)
• X + (YZ) = (X + Y)(X + Z)  증명 -> XX + XZ + XY + YZ = X + XZ + XY + YZ = X(1 + Y + Z) + YZ = X + YZ

DeMorgan' Law

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

진리표를 통한 증명

Dual : 쌍대

• 완전히 괄호로 묶인 Boolean 표현이 있을때, Dual은 AND -> OR, 0 -> 1, 1 -> 0로 바꾼 표현입니다. 이때 변수나 보수는 바뀌지 않은 상태로 남아있습니다.
• Dual의 표현은 전체 표현에 보수를 취한 다음에 각각에 따라 보수를 취하면 얻을 수 있습니다.

• 

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

Therems to simplify Boolean expressions

• Uniting  :  XY + XY' = X         ,          (X + Y)(X + Y') = X (Dual)
  •  XY + XY' = X(Y + Y') = X1 = X
  • (X + Y)(X + Y') = XX + XY' + XY + YY' = X + X(Y + Y') = X + X = X
• Absorption : X + XY = X         ,        X(X + Y) = X (Dual)
  •  X + XY = X(1 + Y) = X
  • X(X + Y) = XX + XY = X + XY = X(1 + Y) = X
• Elimination : X + X'Y = X + Y           ,         X(X' + Y) = XY (Dual)
  • X + X'Y = (X + X')(X + Y) = X + Y
  • X(X' + Y) = XX' + XY = XY
• Consensus : XY + X'Z + YZ = XY + X'Z           ,        (X + Y)(X' + Z)(Y + Z) = (X + Y)(X' + Z) (Dual)
  • XY + X'Z + YZ = XY + X'Z + (X + X')YZ = XY + X'Z + XYZ + X'YZ = XY(1 + Z) + X'Z(1 + Y) = XY + X'Z

외우기보다는 증명을 이해하고 사용하는 것이 중요합니다.

 

위의 식들을 사용하면 하나의 표현을 간단하게 할 수 있습니다. 이는 논리 게이트 설계에서 중요합니다.

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

간략화 예제 :

1. Z = A'BC + A' 
   1. Z = A'(BC + 1) = A'
2. Z = [A + B'C + D + EF][A + B'C + (D + EF)']
   1. A + B'C -> X, D + EF -> Y
   2. Z = (X + Y)(X + Y') = XX + XY' + XY + YY' = X
   3. Z = A + B'C
3. Z = (AB + C)(B'D + C'E') + (AB + C)'
   1. AB + C -> X , B'D' + C'E' -> Y
   2. Z = XY + X' = (X + X')(X' + Y) = X' + Y
   3. Z = (AB + C)' + B'D' + C'E'

 

 

Sum of Product(S0P) : 논리곱의 합 형식

• 모든 product는 단일 변수의 products 입니다.
  • 이러한 형태는 전체가 곱셈전개가 완료되었을 때의 표현입니다.
  • EX) A'B + C'DE + AC'E or ABC' + DEFG + H or A + B + C + D'E
• (A + B)CD + EF 와 같은 식이 있을 때, 논리곱의 합 형식으로 표현하기 위해 곱셈 전게를 이용하면 된다.
  • (A + B)CD + EF = ACD + BCD + EF
• 곱셈 전개를 하기 전에, Second distribute law를 사용하면 많은 시간을 절약할 수 있습니다.

훨씬 간단하게 되는 모습을 볼 수 있다.

 

Product of sum(POS) : 논리합의 곱 형식

• 모든 sum은 단일 변수의 sum입니다.
• EX) (A + B')(C + D' + E)(A + C' + E') or (A + B)(C + D + E)F or AB'C'(D' + E)