절에 동일한 변수를 공유하지 않는 3-CNF 절 집합에 몇 개의 만족스러운 할당이 있습니까?

Question

어쩌면이 사이트의 범위를 벗어난 것일 수도 있지만, 여기에 충분한 사람들이 이것을 알게되어서 내가 그 장면을 제공하고 있다고 생각했습니다.

내가 3-CNF 조항

의 집합을 말해봐

S = {Clause1, Clause2} = {<x1 or x2 or not x3>, <x4 or x5 or x6>} 

{0,1}

S를 위해 얼마나 많은 만족스러운 과제가 이상 각 변수의 범위? 일반적으로 S에 대해 얼마나 많은 만족스러운 과제가 있는가? S의 크기는 k인가?

이것은 3 절 논리 구분에 대한 만족스러운 할당이 무엇인지에 관한 질문입니다.

(111),(011),(101),(110),(100),(010),(001),(000) 

그러나 이들 중 하나를 만족하는 할당 : 난 그냥 이있을 때 예를 들어, 2 ³ = 8 가능한 과제가있다?

Answer 1

변수를 공유하지 않는 절에 대해서는 계산이 매우 사소합니다.

첫 번째 절을 만족하는 각 변수 집합에 대해 두 번째 절을 충족시키는 변수 집합을 선택할 수 있습니다. 그러므로 각 조항의 과제를 만족시키는 제품을 원할뿐입니다.