CNFS를 더욱 줄이기위한 알고리즘이 있습니까?

Question

CNF (Conjunctive Normal Form)에서 부울 수식이 있습니다. $ (a \ vee b \ vee c) \ 웨지 (\ vee b \ vee \nneg c) \ 웨지 (x \ vee y) $

이것은 이것이 단순화 될 수 있다는 것을 알고 있습니다. $ (a \ vee b) \ 웨지 (x \ vee y) $

a) CNF가 이미 축소 된 형태인지 여부를 결정하는 알고리즘이 있습니까?

b) 각 조항의 각 쌍을 비교하는 것보다 효율적으로 이러한 감소를 수행 할 수있는 알고리즘이 있습니까?CNF를 자동으로 줄이고 내가 빌리거나 구현할 수있는 알고리즘을 찾고 있습니다.

Answer 1

CNF 최소화는 어렵습니다. https://cstheory.stackexchange.com/q/9839/5038 를 참조하십시오.그것은 확실히 np-hard이며, 그것이 "심지어 더 힘들어"인가가 있습니다.

CNF가 만족스럽지 않으면 감소 된 양식이 "거짓"이면, 만족스럽지 않으면 감소 된 양식이 다른 것입니다.그래서, 당신이 감소 된 양식을 찾는 효율적인 방법을 가지고 있다면, 즉시 cnf가 만족 스러울 지 여부를 알릴 수있는 방법을 제공합니다 - 우리가 알고있는 일은 np-hard입니다.

https://cstheory.stackexchange.com/q/9839/5038 및 https://en.wikipedia.org/wiki/logic_optimization#circuit_minimization_in_boolean_algebra 문헌에 대한 포인트에 대한 이 작업에 대한 알고리즘.