11. Boolean Algebra

11.1. Boolean Functions

Boolean algebra는 Set $\{0,1\}$을 다루기 위한 Opertion과 Rule을 제공한다.
주로 사용하는 Boolean algebra의 세 Operation은 Complementation, Sum, Product이다.
Element의 Complement(보수)는 Bar로 표시되며 $\bar{0}=1, \bar{1}=0$이다.
Boolean sum의 경우 $1+1=1, 1+0=1, 0+1=1, 0+0=0$으로 Notation으로 $+, OR$로 표현한다.
Boolean product의 경우 $1\cdot 1=1, 1\cdot 0=0, 0\cdot 1=0, 0\cdot 0=0$이며 Notation으로 $\cdot, AND$로 표현한다.

Proposition과 연계하여 $T=1, F=0$이며 $AND=\land, OR=\lor, \bar{p}=\lnot p$와 같이 사용 가능하다.

Boolean Expressions and Boolean Functions

$B=\{0,1\}$이라고 할 때 $B^n=\{(x_1,x_2,\dots,x_n)\mid x_i\in B \text{ for }1\leq i\leq n\}$으로 0, 1의 모든 가능한 $n$-tuple의 Set이 된다.
Variable이 0, 1만 Value로 가지게 될 경우 Boolean variable이라고 한다.
Set $B^n$에서 $B$로의 Function을 Boolean function of degree $n$이라고 한다.

Boolean funtion은 Variable과 Boolean operation으로 구성된 Expression으로 나타낼 수 있다.

$n$개의 Variable $F,G$의 Boolean funtion은 $F(b_1,b_2,\dots,b_n)=G(b_1,b_2,\dots,b_n)$일 때만 Equal이라고 표현한다.
두 Boolean expression이 동일한 Funtion일 경우 Equivalent라고 한다.
Boolean funtion $F$의 Complement는 Function $\bar{F}$로 $\bar{F}(x_1,\dots,x_n)=\overline{F(x_1,\dots,x_n)}$이다.
$F,G$를 Boolean funtion of degree $n$이라고 할 때 Boolean sum $(F+G)(x_1,\dots,x_n)=F(x_1,\dots,x_n)+G(x_1,\dots,x_n)$이고 Boolean product $(FG)(x_1,\dots,x_n)=F(x_1,\dots,x_n)G(x_1,\dots,x_n)$이다.

팁

Example

Boolean function of degree $n$의 개수

• Solution
  Set의 Product rule에 따라 $2^n$개의 서로 다른 $n$-tuple이 존재하는 데 Boolean function은 이러한 $2^n$개의 서로 다른 $n$-tuple 각각에 0, 1을 부여하므로 $2^{2^n}$임을 알 수 있다.

Identifties of Boolean Algebra

Identity	Name
$\bar{\bar{x}}=x$	Law of the double complement
$x+x=x\\x\cdot x=x$	Idempotent laws
$x+0=x\\x\cdot 1=x$	Identity laws
$x+1=1\\x\cdot 0=0$	Domination laws
$x+y=y+x\\xy=yx$	Commutative laws
$x+(y+z)=(x+y)+z\\x(yz)=(xy)z$	Associative laws
$x+yz=(x+y)(x+z)\\x(y+z)=xy+xz$	Distributive laws
$\overline{(xy)}=\bar{x}+\bar{y}\\ \overline{(x+y)}=\bar{x}\bar{y}$	De Morgan's laws
$x+xy=x\\ x(x+y)=x$	Absorption laws
$x+\bar{x}=1$	Unit property
$x\bar{x}=0$	Zero property

Duality

Boolean expression의 Dual은 Boolean sum, Boolean product를 서로 바꾸고 0, 1을 바꿔 얻을 수 있다.

Boolean expression으로 나타난 Boolean funtion $F$의 Dual은 이 Expression의 Dual로 나타낸 Funtion이 된다.
$F$의 Dual을 Notation $F^d$로 표현하고 $F$를 나타내는 특정 Boolean expression에 의존하지 않는다.
Boolean expression으로 나타낸 Function 간 Identity는 Identity 양 변에 Dual을 취할 때에도 유효하다.
이 결과를 Duality principle이라고 하며 새로운 Identity를 얻는 데 유용하다.

팁

Example

Absorption laws에 Dual을 취하여 Identity를 구성

• Solution
  Absorption laws는 $x(x+y)=x$을 Dual을 취하면 $x+(xy)=x$라는 Identity가 생성된다.

The Abstract Definition of a Boolean Algebra

Boolean algebra는 두 개의 Binary Operation $\land, \lor$과 Element 0, 1, Unary operation $\bar{ }$ 을 가지는 Set $B$로 다음의 Property들이 모든 $x,y,z$에 대해 성립해야 한다.

• Identity laws
• Complement laws
• Associative laws
• Commutative laws
• Distributive laws

11.2. Representing Boolean Functions

Sum-of-Products Expansions

Literal은 Boolean variable이나 그의 Complement이다.
Boolean variable $x_1,x_2,\dots,x_n$의 Minterm은 $y_1y_2\cdots y_n$의 Boolean product로 $x_i=y_i$일 때 $x_i=1$이고 $\bar{x_i}=y_i$일 때 $x_i=0$이다.

서로 다른 Minterm의 Boolean sum을 취함으로써 특정 Value set을 갖는 Boolean expression을 구축 가능하다.
Minterm의 Boolean sum은 Boolean sum에 있는 Minterm 중 정확히 하나가 Value가 1일 때만 1을 갖고 다른 모든 Variable value combination에 대해서는 0을 갖는다.
따라서 주어진 Boolean funtion에 대해 이 Boolean funtion의 Value가 1일 때 1, 0일 때 0을 가지는 Minterm의 Boolean sum을 형성할 수 있다.
이 Boolean sum의 Minterm의 Sum은 Sum of products expansion이나 Disjunctive normal form이라고 한다.

팁

Example

$F(x,y,z)=(x+y)\bar{z}$의 Sum of products expansion

• Solution
  $F(x,y,z)$의 Sum of products expansion을 찾는 두 가지 방법이 있다.
  첫 째로 Boolean identity를 사용하여 Product를 전개하고 단순화 한다.
  $F(x,y,z)=(x+y)\bar{z}\\=x\bar{z}+y\bar{z} \because \text{Distributive law}\\=x1\bar{z}+1y\bar{z} \because \text{Identity law}\\=x(y+\bar{y}\bar{z}+(x+\bar{x})y\bar{z} \because \text{Unit property}\\=xy\bar{z}+x\bar{y}\bar{z}+xy\bar{z}+\bar{x}y\bar{z}\because \text{Distributive law}\\=xy\bar{z}+x\bar{y}\bar{z}+\bar{x}y\bar{z} \because \text{Idempotent law}$
  두 번째로 x,y,z에 가능한 Value에 대해 $F$의 Value를 결정하여 Sum of products expansion을 구할 수 있다.
  
  위 표를 참고하여 $F(x,y,z)=xy\bar{z}+x\bar{y}\bar{z}+\bar{x}y\bar{z}$임을 알 수 있다.

Functional Completeness

모든 Boolean funtion은 Minterm의 Boolean sum으로 표현 가능하다.
각 Minterm은 Boolean variable이나 그 Complement의 Boolean product이므로 모든 Boolean operator를 사용하여 표현할 수 있음을 보여준다.

모든 Boolean funtion이 이러한 Operator를 사용하여 표현될 수 있기에 Set $\{\cdot,+,\bar{\ }\}$가 Functionally complete라고 한다.
Set의 세 Operator 중 하나가 나머지 두 개의 Operator로 표현될 수 있다면 더 작은 Functionally complete set을 찾을 수 있다.
이를 위해 De Morgan's law를 사용하여 모든 Boolean sum을 제거할 수 있는 Identity($x+y=xy$)를 양 변에 Double complementation law를 적용하여 $\{\cdot,\bar{\ }\}$가 Functionally complete임을 알 수 있다.

$\{+,\bar{\ }\}$역시 Functionally complete이나 $\{+,\cdot\}$은 $F(x)=\bar{x}$를 $\bar{\ }$ 없이 표현할 수 없기에 Functionally complete가 아니다.

다른 더 작은 Functionally complete set은 $\{|, \downarrow\}$($NAND, NOR$)도 존재한다.

11.3. Logic Gates

Boolean algebra는 Electronic device의 Circuit를 Modeling하는 데 사용된다.
각 Input, Output은 $\{0,1\}$의 Member이다.
Circuit의 Basic element를 Gate라고 부른다.

여러 Input을 받아들여 어떠한 작업을 하는 Memory capability 기능이 없는 Circuit의 모음을 Combinational circuit, Gating network라고 한다.

위 $(a),(b),(c)$는 각각 Inverter(NOT), OR, AND이다.

OR, AND는 또 여러 Input을 받아 결과를 나타낼 수 있다.

$n$ Input의 AND gate는 Boolean product의 Output을, OR gate는 Boolean sum의 Output을 가진다.

Combinations of Gates

Combinational circuit은 Inverter, OR, AND gate의 Combination으로 나타낼 수 있으며 일부 Gate는 Input을 공유할 수 있다.
Circuit의 Depiction을 나타내기 위해 특정 Input을 사용하는 모든 Gate를 나타내는 Branching을 사용하거나 각 Gate에 대한 Input을 별도로 표시해 줄 수 있다.

팁

Example

$(a):\ (x+y)\bar{x},(b):\ \bar{x}\overline{(y+\bar{z})},(c):\ (x+y+z)(\bar{x}\bar{y}\bar{z})$이 Output인 Circuit

• Solution\

Examples of Circuits

팁

Example

세 명으로 구성된 위원회가 조직의 문제의 찬반을 결정할 때 제안이 통과되기 위해 두 표의 찬성이 필요할 때 제안 통과 여부를 결정하는 Circuit

• Solution
  
  한 명을 각각 $x,y,z$로 놓고 1일 때 찬성, 0일 때 반대로 구성할 경우 두 개 이상이 1일 때 1을 출력하는 Circuit을 만들어야 하며 이는 위 $xy+xz+yz$와 같다.

Adder

$x, y$ Bit를 더하는 $x+y$를 찾을 수 있는 Circuit을 구출할 때 Input은 $x,y$이며 값은 0, 1 중 하나이다.
Output의 경우 Sum bit $s$와 Carry bit $c$로 구성된 두 Bit로 Output을 표현할 수 있다.
이 때 이 Circuit은 Multiple output circuit이라고 부르며 하나 이상의 Output을 가지고 있음을 의미한다.
간단히 두 Bit에 대한 Sum bit는 $s=x\bar{y}+\bar{x}y=(x+y)\overline(xy)$로 표현할 수 있고 Carry bit는 $c=xy$이다.

Carry에 관한 값을 고려하지 않는 Circuit을 Half adder라 표현하고, 두 Bit와 Carry를 추가할 때 Sum bit와 Carry bit를 고려할 경우 Full adder라고 한다.
Full adder의 Input은 $x, y, c_i$이며 Output의 경우 $s, c_{i+1}$이 되게 된다.

Full adder를 처음부터 설계하는 대신 Half adder를 사용하여 원하는 Output을 생성한 후 Full adder에서 사용할 수 있으며 아래의 그림은 두 개의 3-bit integer의 Sum, $(x_2x_1x_0)_2+(y_2y_1y_0)_2=(s_3s_2s_1s_0)_2$를 나타내기 위한 Circuit이다.

$s_3$의 경우 Carry bit인 $c_2$로 결정된다.

11.4. Minimization of Circuits

Combinational circuit의 Efficiency(효율성)은 Gate 수와 배치에 따라 달라진다.
Expansion of sum-of-products를 사용하여 이 Circuit을 구현할 Logic gate set을 찾을 수 있다.
Expansion of sum-of-products는 필요 이상으로 많은 Term을 포함할 수 있기에 서로 다른 하나의 Variable이 다르고(한 Term에는 Variable이, 다른 Term에는 그 Variable의 Complement)일 때 Term 자체가 결합될 수 있다.

위 Circuit은 $x=y=z=1 \land(x=z=1 \land y=0)$일 때 1이 된다.
$xyz+x\bar{y}z=(y+\bar{y}(xy)=1\cdot(xz)=xz$이므로 위 Circuit을 아래 Circuit으로 Minimization 가능하다.

Minimization of the boolean function이란 Boolean function의 Represent 중 Boolean product 중 가장 적은 Literal을 가진 Boolean sum을 찾는 것이다.
Boolean function의 Minimization을 찾는다면 최소한의 Gate와 최소한의 Input으로 Circuit을 구성할 수 있다.

많은 Variable을 가진 Boolean function을 Minimization하는 것은 NP-complete probolem이다.
아래에서 다룰 Karnaugh maps와 Quine-McCluskey method는 Variable 수가 커질수록(Quine-McCluskey method의 경우 Literal 수가 10을 초과자히 않을 때만 사용 가능) 사용할 수 없거나 복잡해진다.

Karnaugh Maps

Boolean expression에서 Circuit을 나타내는 Term의 수를 줄이기 위해 Combine 할 Term을 찾아야 한다.
비교적 적은 수의 Variable을 포함하는 Boolean function의 Term을 결합하는 Graphical method로 Karnaugh map(K-map)이 존재한다.
이 방법의 경우 일반적으로 Function이 여섯 개 이하의 Variable을 포함할 때만 적용한다.
K-map의 경우 Sum-of-products를 단순화하는 Visual method를 제공하나 Process 자체를 Mechanizing하는 데에 적합하지 않다.

두 Variable $x,y$에 대한 Boolean function의 Sum-of-product에 네 가지 가능한 Minterm이 존재한다($xy,x\bar{y},\bar{x}y,\bar{x}\bar{y}$).
이 두 Variable의 Boolean function에 대한 K-map은 네 개의 Cell로 구성되며 이 MinTerpm이 Expansion에서 존재할 경우 해당 Cell에 1을 배치한다.
Cell은 대표하는 Minterm이 정확히 하나의 Literal에서 차이가 날 경우 Adjacent하다고 한다.

팁

Example

$(a)xy+\bar{x}y,(b)x\bar{y}+\bar{x}y,(c)x\bar{y}+\bar{x}y+\bar{x}\bar{y}$의 K-map

• Solution\

K-map에서 Combine 가능한 Minterm을 식별 가능하다.
K-map에서 Adjacent한 두 Cell에 1이 존재할 때 이 Cell들이 나타내는 Minterm은 하나의 Variable만을 포함하는 Product로 결합할 수 있다($x\bar{y}+\bar{x}\bar{y}=(x+\bar{x})\bar{y}=\bar{y}$).
모든 Cell에 1이 존재할 때 모든 Minterm의 경우 1로 Combine될 수 있다.
Combine할 때 가능한 한 가장 큰 Block부터 사용하여야 한다.

팁

Example

$(a)xy+\bar{x}y,(b)x\bar{y}+\bar{x}y,(c)x\bar{y}+\bar{x}y+\bar{x}\bar{y}$의 Sum-of-product의 Minimal expansion

• Solusion
  
  위와 같기에 $(a)y,(b)x\bar{y}+\bar{x}y,(c)\bar{x}+\bar{y}$가 된다.

세 Variable에 대한 K-map은 여덟 개의 Cell로 나누어 진 직사각형이다.
이 Cell들은 세 Variable에서 가능한 여덟 개의 Minterm을 나타내며 두 Cell은 나타내는 Minterm이 정확히 하나의 Literal에서 다를 경우 Adjacent라고 한다.

위 $(a)$ 같이 표현하며 사실은 $2\times 2\times 2$이기에 $(b)$와 같이 Cylinder에 놓인 것 처럼 이해하는 것이 좋다.

$1\times 2,2\times 1, 2\times 2, 4\times 1, 4\times 2$ Block들이 나타내는 Sum-of-product는 아래 그림과 같다.

K-map에서 모든 1의 Block에 해당하는 Literal의 Product를 Function의 Implicant라고 한다.
이 Block이 더 적은 Literal의 Product을 나타내는 더 큰 Block에 포함되지 않는 경우 이를 Prime implicant라고 한다.
Map에서 가장 큰 Block을 식별한 후 가장 큰 Block을 먼저 사용하여 최소한의 Block으로 모든 1을 덮는 것이 목표이다.
K-map에서 1을 포함하는 유일한 Block인 경우 반드시 선택하여야 하며 이 Block을 Essential prime implicant라고 한다.
모든 1을 Prime implicant에 해당하는 Block으로 덮음으로 Sum-of-product를 Prime implicant의 Sum으로 표현 가능하다.

팁

Example

$(a)xy\bar{z}+x\bar{y}\bar{z}+\bar{x}yz+\bar{x}\bar{y}\bar{z}\\(b)x\bar{y}z+x\bar{y}\bar{z}+\bar{x}yz+\bar{x}\bar{y}z+\bar{x}\bar{y}\bar{z}\\(c)xyz+xy\bar{z}+x\bar{y}z+x\bar{y}\bar{z}+\bar{x}yz+\bar{x}\bar{y}z+\bar{x}\bar{y}\bar{z}\\(d)xy\bar{z}+x\bar{y}\bar{z}+\bar{x}\bar{y}z+\bar{x}\bar{y}\bar{z}$
일 때 위 Sum-of-product expansion의 K-map을 활용하여 Minimize

• Solution
  
  위 K-map에 따라 $(a)x\bar{z}+\bar{y}\bar{z}+\bar{x}yz,(b)\bar{y}+\bar{x}z,(c)x+\bar{y}+z,(d)x\bar{z}+\bar{x}\bar{y}$가 된다.

4개의 Variable을 가진 K-map은 16개의 Cell로 나누어진 정사각형이다.
16개의 Minterm을 나타내며 4개의 Variable을 가진 K-map을 형성하는 방법 중 하나는 아래의 그림과 같다.

$2\times 2\times 2\times 2$이므로 각 Cell은 네 개의 Cell과 Adjacent이다(Common boundary를 갖는 Torus(원환면)).

Sum-of-product Expansion의 Minimization은 2, 4, 8, 16 Cell의 Block들을 식별하여 수행된다.

앞 2, 3개의 Variable과 마찬가지로 가장 큰 Block을 식별한 후 최소 Block을 사용하여 모든 1을 덮는 것이 목적이다.

팁

Example

$(a)wxyz+wxy\bar{z}+wx\bar{y}\bar{z}+w\bar{x}yz+w\bar{x}\bar{y}z+w\bar{x}\bar{y}\bar{z}+\bar{w}x\bar{y}z+\bar{w}\bar{x}yz+\bar{w}\bar{x}y\bar{z}\\(b)wx\bar{y}\bar{z}+w\bar{x}yz+w\bar{x}y\bar{z}+w\bar{x}\bar{y}\bar{z}+\bar{w}x\bar{y}\bar{z}+\bar{w}\bar{x}y\bar{z}+\bar{w}\bar{x}\bar{y}\bar{z}\\(c)wxy\bar{z}+wx\bar{y}\bar{z}+w\bar{x}yz+w\bar{x}y\bar{z}+w\bar{x}\bar{y}\bar{z}+\bar{w}xyz+\bar{w}xy\bar{z}+\bar{w}x\bar{y}\bar{z}+\bar{w}x\bar{y}z+\bar{w}\bar{x}y\bar{z}+\bar{w}\bar{x}\bar{y}\bar{z}$
위 Sum-of-product expansion의 K-map을 활용하여 Minimization

• Solution
  
  위 K-map에 따라
  $(a)wyz+wx\bar{z}+w\bar{x}\bar{y}+\bar{w}\bar{x}y+\bar{w}x\bar{y}z\\(b)\bar{y}\bar{z}+w\bar{x}y+\bar{x}\bar{z}\\(c)\bar{z}+\bar{w}x+w\bar{x}y$
  가 된다.

요약하여Gray code와 유사한 형태의 Adjacent relation을 확인하여 Minimization한다.

Don't Care Conditions

일부 Circuit에서 특정 Input value의 Combination에 대한 Output만을 고려한다.
이 때 원하는 Output을 가진 간단한 Circuit을 만들 수 있으며 다른 Input value에 대한 내용은 Don't care condition(무시할 수 있는 조건)이 된다.
K-map에서 이러한 Variable value의 Combination에 대해 Function의 Value를 임의로 할당할 수 있음을 나타내기 위해 $d$로 표현한다.
Minimization step에서 K-map에서 가장 큰 Block을 형성하는 Input value의 Combination에 대해 1을 Value로 할당 가능하다.

팁

Example

Decimal expansion을 Bit로 Incoding하는 것은 각 Decimal expansion의 Binary expansion을 4 Bit로 사용하는 것이다.
예시로 873을 $100001110011_{(2)}$로 Incoding할 수 있다.
위 과정을 Binary coded decimal expansion이라고 한다.
4Bit block은 총 16개를 표현할 수 있으나 Decimal expansion의 각 자릿수는 총 10개이므로 Incoding에 사용되지 않는 4Bit의 Combination이 6개 존재하게 된다.
만약 Decimal expansion이 5 이상일 경우 1, 아닐 경우 0을 출력하는 Circuit을 만들고자 할 때 Inverter, OR, AND Gate를 최소한 사용하여 구축할 수 있는가?

• Solution
  위 Decimal expansion이 5 이상일 경우 1을 반환하는 Circuit을 Function $F(w,x,y,z)$로 나타낼 수 있다(총 4Bit이므로 Variable은 네 개).
  $F$의 K-map은 Don't care condition이 존재하며 이를 $d$로 놓을 수 있다.
  
  위 그림에서 가장 Minimization하기 쉬운 Condition대로 $d$를 1이나 0으로 놓을 수 있기에 $d$를 모두 1로 놓은 상태일 때 Simplest sum-of-product expansion이 가능해지므로 $F(x,y,z)=w+xy+xz$가 답이 된다.

The Quine-McCluskey Method

K-map을 사용하여 Boolean function의 Minimization expansion을 Boolean product의 Boolean sum으로 생성 가능하나 Variable의 수가 증가함에 따라 K-map을 사용하기 불편해진다.
위와 같은 이유로 Mechanizing으로 수행할 수 있는 Sum-of-product expansion을 Minimization하는 Procedure가 필요하다.
이 Method를 Quine-McCluskey method라고 한다.

1. 각 Minterm을 $n$개의 Variable(Bit string)로 표현하고 $x_i$가 발생하면 $i$번째 위치에 1을, $\bar{x_i}$의 경우 $i$번째 위치에 0을 둔다.
2. Bit string을 1의 개수에 따라 Grouping한다.
3. 이전 Step에서 찾은 Minterm의 Boolean sum을 통해 $n-1$개의 Variable로 형성할 수 있는 모든 Product를 결정한다.
   Combine 가능한 Minterm은 정확히 한 위치에서 다른 Bit string으로 표현된다.
   이러한 Product를 $n-1$개의 Variable로 표현할 때 $x_i$가 발생하면 $i$번째에 1을, 그렇지 않을 경우 0을 두며 해당 Literal이 없는 경우 Dash를 둔다.
4. 이전 단계에서 찾은 $n-1$개의 Variable로 된 Product를 Boolean sum을 통해 $n-2$개의 Variable로 형성할 수 있는 모든 Product를 결정한다.
   Combine 가능한 $n-1$개의 Variable로 된 Product는 동일한 위치에 Dash가 있고 정확히 한 위치에서 다른 Bit string으로 표현된다.
5. 가능할 때 까지 반복하여 Boolean product를 더 적은 Variable로 Combine한다.
6. 한 개의 Literal이 줄어든 Boolean product를 형성하는 데 사용되지 않은 모든 Boolean product를 찾는다.
7. 위 Boolean product의 가장 작은 Set을 찾아 이 Sum-of-product가 Boolean function을 나타내도록 한다.
   어떤 Minterm이 Product로 Cover되는 지 보여주는 Table을 작성하여 모든 Minterm은 하나의 Product로 Cover되어야 한다.
   이 Table을 사용하는 Step
   1. 모든 Essential prime implicant를 찾는다.
   2. 각 Essential prime implicant는 하나의 Minterm을 Cover하는 유일한 Implicant이기에 반드시 포함되어야 한다.
   3. Essential prime implicant를 찾은 후 Covered minterm의 Column을 제거하여 Table을 Simplify한다.
   4. 다른 Essential prime implicant로 Cover된 Minterm의 Subset을 Cover하는 Essential prime implicant를 제거할 수 있다.
   5. Essential prime implicant를 식별하여 중복 Essential prime implicant를 제거하며 무시할 수 있는 Minterm을 식별하는 과정을 Table이 변하지 않을 때 까지 반복한다.
      (Backtracking을 통해)

팁

Example

Quine-McCluskey method를 사용하여 $xyz+x\bar{y}z+\bar{x}yz+\bar{x}\bar{y}z+\bar{x}\bar{y}\bar{z}$와 Equivalent 한 Minimal expansion 찾기

• Solution
  Variable은 총 세 개이다($x,y,z$).
  Bit string의각 위치가 ($x,y,z$)일 경우 1, ($\bar{x},\bar{y},\bar{z}$) 일 경우 0이 된다.
  즉 위 Expression은 $xyz = 111,x\bar{y}z=101,\bar{x}yz=011,\bar{x}\bar{y}z=001,\bar{x}\bar{y}\bar{z}=000$이 된다.
  Combine 가능한 Minterm은 정확히 하나의 Literal에서만 차이가 나는 것이다.
  두 개의 Minterm이 Product가 발생하지 않는 Variable을 나타내기 위해 Dash로 표현하게 된다.
  예시로 $x\bar{y}z$와 $\bar{x}\bar{y}z$는 Bit string으로 $101, 001$이며 $\bar{y}z$로 표현할 수 있고 Bit string으로 $-01$fh 표시한다는 뜻이다.
  즉 처음을 Bit string으로 나눠서 각 Step을 진행한다면 $(1) 111,(2)101,(3)011,(4)001,(5)000$를 Step 1에서 $(1,2)$를 $1-1$, $(1,3)$을 $-11$, $(2,4)$를 $-01$, $(3,4)$를 $0-1$로, $(4,5)$를 $00-$로 줄일 수 있다.
  Step 2에서 $((1,3),(2,4))$를 $--1$로 나타낼 수 있다.
  더 적은 Literal로 Product를 형성하는 데 사용된 Term을 $X$표시한다.
  $X$표시가 되어있는 경우 각 Original minterm을 Cover한 것이다.
  각 Original minterm을 Cover하는 Product term을 최소한 하나 포함하여야 한다.
  Table에 $X$가 하나만 있는 경우 이 $X$가 있는 Colum에 해당하는 Product term을 반드시 사용하여야 한다.
  즉 아래의 표들을 참고하여 결과는 $z+\bar{x}\bar{y}$임을 알 수 있다.

Term	Bit string	Step 1 term	Step 1 string	Step 2 erm	Step 2 string
$xyz$	111	(1,2)$xz$	1-1	(1,2,3,4)$z$	--1
$x\bar{y}z$	101	(1,3)$yz$	-11
$\bar{x}yz$	011	(2,4)$\bar{y}z$	-01
$\bar{x}\bar{y}z$	001	(3,5)$\bar{x}z$	0-1
$\bar{x}\bar{y}\bar{z}$	000	(4,5)$\bar{x}\bar{y}$	00-

$z$	$xyz$	$x\bar{y}z$	$\bar{x}yz$	$\bar{x}\bar{y}z$	$\bar{x}\bar{y}\bar{z}$
$z$	X	X	X	X
$\bar{x}\bar{y}$				X	X

팁

Example

Quine-McCluskey method를 사용하여 $wxy\bar{z}+w\bar{x}yz+w\bar{x}y\bar{z}+\bar{w}xyz+\bar{w}x\bar{y}z+\bar{w}\bar{x}yz+\bar{w}\bar{x}\bar{y}z$의 Sum-of product expansion의 Simplify

• Solution
  아래 Table을 참고하여 $\bar{w}z+wy\bar{z}+w\bar{x}y$나 $\bar{w}z+wy\bar{z}+\bar{x}yz$가 된다.

Term	Bit string	Step 1 term	Step 1 string	Step 2 term	Step 2 string
$wxy\bar{z}$	1110	(1,4)$wy\bar{z}$	1-10	(3,5,6,7)$\bar{w}z$	0--1
$w\bar{x}yz$	1011	(2,4)$w\bar{x}y$	101-
$\bar{w}xyz$	0111	(2,6)$\bar{x}yz$	-011
$w\bar{x}y\bar{z}$	1010	(3,5)$\bar{w}xz$	01-1
$\bar{w}x\bar{y}z$	0101	(3,6)$\bar{w}yz$	0-11
$\bar{w}\bar{x}yz$	0011	(5,7)$\bar{w}\bar{y}z$	0-01
$\bar{w}\bar{x}\bar{y}z$	0001	(6,7)$\bar{w}\bar{x}z$	00-1

	$wxy\bar{z}$	$w\bar{x}yz$	$\bar{w}xyz$	$w\bar{x}y\bar{z}$	$\bar{w}x\bar{y}z$	$\bar{w}\bar{x}yz$	$\bar{w}\bar{x}\bar{y}z$
$\bar{w}z$			X		X	X	X
$wy\bar{z}$	X			X
$w\bar{x}y$		X		X
$\bar{x}yz$		X				X