FT도가 다음과 같을 때 최소 패스 셋(minimal path set)을 모두 구하시 상세 페이지

㉠ 최소패스셋은 FT도를 반대로 변환 후 미니멀 컷셋을 구한다.

㉡ G1 = G2×G3

㉢ G2 = ④+G4 = ④+(③×G6) = ④+[③×(②+③)] = ④+(③×②)+(③×③) (A×A=A) = ④+(③×②)+③ = ④ + [(②+1)×③] (A+1=1) = ④+③

㉣ G3 = ①+G5 = ①+(③×⑤)

㉤ G1 = G2×G3 = (④+③)×[①+(③×⑤)] = ①×④ + ①×③ + ④×③×⑤ + ③×③×⑤ (A×A=A) = ①×④ + ①×③ + ④×③×⑤ + ③×⑤ (밑줄은 ③×⑤로 묶음) = ①×④ + ①×③ + [(④+1)×(③×⑤)] (A+1=1) = ①×④ + ①×③ + ③×⑤

㉥ 미니멀 컷셋 : (①, ④) (①, ③) (③, ⑤)

[해설]

최소 패스셋은 FT도의 AND 게이트와 OR 게이트를 서로 바꾼 쌍대(dual) 고장수목을 만든 뒤 그 최소 컷셋을 구하면 되며, 그렇게 얻은 집합이 원래 나무의 최소 패스셋이 된다.

쌍대 나무에서 G2 = ④+③(②+③) = ④+③, G3 = ①+③⑤ 이므로 G1 = (④+③)(①+③⑤) = ①④+①③+③⑤+④③⑤ 가 되고, 멱등법칙 $A \times A = A$와 흡수법칙 $A + AB = A$로 ④③⑤가 ③⑤에 흡수된다.

정리하면 남는 항은 세 개뿐이므로 최소 패스셋은 (①, ④), (①, ③), (③, ⑤)다.