이항 공식을 Shannon Normal Form으로 변환하십시오.

Question

이진 공식을 Shannon Normal Form으로 변환하는 단계를 알고 싶습니다.

a⪯b⪯c⪯d - variable ordering. 
F = b&c&!d|c&d&!b|d&!c|!c&!d 

어떻게 이것을 Shannon Normal Form으로 변환 할 수 있습니까?

Answer 1

F | {a = 0} 및 F | {a = 1}을 계산하여 시작하십시오. F는 변수 a에 의존하지 않기 때문에, 당신은 두 사건에 대한 F를 얻을 것이다 : 당신은 계속

F|{a=0} = F 
F|{a=1} = F 

을 F를 계산하여 | {A = 0, B = 0}, F | {A = 0, B = 1 }, F | {a = 1, b = 0} 및 F | {a = 1, b = 1}이다. 단지 변수의 되돌리기 위해 계산

F = !a(!b(!c(!d&1+d&1)|c(!d&0+d&1))|b(!c(!d&1+d&1)|c(!d&1+d&0))| 
    a(!b(!c(!d&1+d&1)|c(!d&0+d&1))|b(!c(!d&1+d&1)|c(!d&1+d&0)) 

당신이 반대 순서를해야 할 경우 전혀 다른 얻을 수 있습니다 : 당신은 변수 C와 변수 D를 계속하고 마지막으로 당신이 얻을

F|{a=0,b=0} = F|{a=1,b=0} = c&d|d&!c|!c&!d = !c|d 
F|{a=0,b=1} = F|{a=1,b=1} = c&!d|d&!c|!c&!d = !c|!d 

당신은 얻을 것이다 결과.

여기 BDD Scout (http://biddy.meolic.com/)의 스크린 샷이 있습니다. 불행히도이 도구는 아직 보완 된 가장자리가없는 BDD를 지원하지 않습니다.