미니멀 컷셋을 구하시오 상세 페이지

T = A₁ and A₂

= (X₁ * X₂) * (X₁ + X₃)

= (X₁ * X₂ * X₁) + (X₁ * X₂ * X₃)

컷셋은 (X₁, X₂), (X₁, X₂, X₃)

미니멀 컷셋은 (X₁, X₂)

[해설]

AND 게이트는 곱, OR 게이트는 합으로 놓고 불 대수로 전개한다. 이때 멱등법칙 $X \cdot X = X$와 흡수법칙(어떤 컷셋이 다른 컷셋을 포함하면 큰 쪽은 버린다)을 적용한 결과가 미니멀 컷셋이며, 이는 정상사상을 일으키는 데 꼭 필요한 최소한의 기본사상 조합을 뜻한다.

T = A₁ · A₂ = (X₁·X₂) × (X₁ + X₃)을 전개하면 (X₁·X₂·X₁) + (X₁·X₂·X₃)이 되고, 여기서 컷셋은 (X₁, X₂)와 (X₁, X₂, X₃)이다.

앞의 항은 멱등법칙으로 X₁X₂가 되고 이것이 뒤의 항 X₁X₂X₃에 포함되므로 뒤의 항은 흡수되어 사라진다. 따라서 미니멀 컷셋은 (X₁, X₂) 하나뿐이다.