3SAT에 넣을 수없는 부울 대수 표현식이 있습니까?

Question

이것은 나에게 꽤 분명해 보입니다.하지만 나는 특별한 경우를 떠날 수도 있습니다. 1SAT (한 절에 하나의 리터럴)와 2SAT는 쉽게 3SAT로 변형 될 수 있습니다. 3 개 이상의 리터가있는 any 절이 3SAT로 변환 될 수 있음이 입증되었습니다. 그러면 질문에 다음과 같은 질문을해야합니다. 부울 대수를 모두 SAT에 넣을 수 있습니까? 또는 우리는이 연산자로 부울 대수를 정의 할 수 있습니까? AND OR NOT

Answer 1

아니요, 없습니다.

필자는 완전한 증거를 제시하지는 않지만 여기에 주요 아이디어가 있습니다. 주어진 공식을 일반적인 형태, 즉 논리적 결합의 결합으로 작성하십시오. 표현식의 변수 수에 대한 유도를 사용하십시오. n + 1 변수로 최장 서브 표현식을 선택하고, n 변수의 표현식을 남기고, 수식에 새 변수에 대한 제약 조건을 추가하고, 수식을 갖기 위해 필요한만큼 여러 번 반복합니다. 여기서 가장 긴 부분 식은 n 개의 변수를가집니다.