Category Archives: Appendix-Logic

Today I’m posting 2 problems relating to my student Dan Thornton’s independent study work. I’m out of town this week and next, so I have these posts set to automatically go up on Tuesday afternoon.

Dan’s independent study was based on the “Automaton Identification” problem, but to show that reduction, he needs to use a variant of 3SAT, which he shows here:

The problem: Monotone EQ SAT. This is a specific instance of Monotone SAT.

The description:
We are given a conjunction of clauses $F = \wedge_{i=1}^{l} C_{i}$ where each clause in $F$ contains all negated or non-negated variables $z_{j}$ and the number of clauses and variables are equal, is there an assignment of the variables so that $F$ is satisfied? Our instance will have $l$ clauses and variables.

Example:
Here is an $F$ that has $4$ variables and $4$ clauses.

F = $( \neg x_{1} \vee \neg x_{2} \vee \neg x_{3} \vee \neg x_{4} ) \wedge ( x_{1} \vee x_{2} \vee x_{4} ) \wedge ( \neg x_{2} \vee \neg x_{3} \vee \neg x_{4} ) \wedge ( x_{1} )$

The above $F$ may be satisfied by the following assignment:
$x_{1} \rightarrow True$
$x_{2} \rightarrow False$
$x_{3} \rightarrow False$
$x_{4} \rightarrow True$

The reduction:
We will reduce from Monotone SAT. So we are given an instance of Monotone SAT with the clauses $F = \wedge_{i=1}^{n} C_{i}$ here each clause is of the form $C_{i} = (x_{i1} \vee ... \vee x_{ik_i} )$ where each clause has all negated or non-negated variables. This is different from Monotone EQ SAT as we do not require the number of variables and clauses to be equal.
From this $F$ we must build an instance of Monotone EQ SAT.
We may transform our instance of Monotone SAT, $F$ , into one of Monotone EQ SAT by the following iterative procedure. New variables will be denoted by $z'_{j}$ and new clauses by $C'_{i}$ .

  = ;
 i = 1;
 j = 1;
 While{number of clauses != number of variables}{
   introduce two new variables ;
   If{number of variables  number of clauses}{
     Create the new clause ;
     ;
     ;
   }
   else {
     Create three new clauses:
      
      
      ;
     ;
     ;
   }
 ;
 }

The above algorithm will produce an equation $F'$ that is in Monotone EQ SAT. This may be shown by induction. Notice that before the procedure if $number \ of \ variables > number \ of \ clauses$ that we will add 2 new variables and 3 new clauses.

If $number \ of \ variables < number \ of \ clauses$ then we will add 2 new variables but only a single new clause. Either way the difference between the number of variables and clauses, $dif =| number \ of \ clauses \ - \ number \ of \ variables |$ will decrease by $1$ . So in $O(dif)$ steps we will obtain an formula where $dif$ = 0. Such a formula is an instance of Monotone EQ SAT.

True{Monotone SAT $\Rightarrow$ True{Monotone EQ SAT}
Here we assume that there is a truth assignment function $\theta: z_{j} \rightarrow \lbrace True,False \rbrace$ that maps every variable to a truth value, such that $F$ is satisfied. Then after we preform the above algorithm we have an instance of $F'$ , now our instance of $F'$ will be of the form $F \wedge ( \wedge_{i=1}^{k} C'_{i})$ for some $k \geq 1$ . Now notice that $\theta$ above will satisfy $F$ in $F'$ and we may trivially satisfy $\wedge_{i=1}^{k} C'_{i}$ by simply assigning all new variables $z'_{j}$ to true.
This will give us a new truth assignment function $\theta'$ that will satisfy $F'$

True{Monotone EQ SAT} $\Rightarrow$ True{Monotone SAT}
Here we assume that there is a truth assignment function $theta'$ that will satisfy $F'$ then obviously as $F' = F \wedge ( \wedge_{i=1}^{k} C'_{i})$ then $theta'$ must also satisfy $F$ .

(Back to me)

Difficulty: 3. The logical manipulations aren’t hard, but it is possible to mess them up. For example, it’s important that the algorithm above reduces the difference in variables and clauses by 1 each iteration. If it can reduce by more, you run the risk of skipping over the EQ state.

Protected: DNF Non-Tautology

Posted on May 17, 2016 | Enter your password to view comments.

Enter your password to view comments.

Posted in Appendix-Logic

Tagged 3-sat, Difficulty 2, DNF Non-Tautology, LO8, Non-Tautology

Monotone 3-Satisfiability

Posted on April 15, 2016 | 4 comments

I told Daniel when he gave me his Monotone Satisfiability reduction that the actual problem mentioned in G&J was Monotone 3-Satisfiability. So he went off and did that reduction too.
The Problem:
Monotone 3 SAT. This is a more restrictive case of Monotone SAT

The Description:
Given an formula of clauses $F' = \wedge_{i=1}^{n} C'_{i}$ where each clause in $F'$ contains all negated or non-negated variables, and each clause $C_{i}$ contains at most $3$ variables. Does there exist an assignment of the variables so that $F'$ is satisfied?

Example:

$\\ F_{1} = (x_{1} \vee x_{3}) \wedge \\ (\neg x_{2} \vee \neg x_{3} \vee \neg x_{4}) \wedge \\ (x_{3} \vee x_{2} \vee x_{4}) \wedge \\ ( \neg x_{3} \vee \neg x_{5} \vee \neg x_{1})$
the following assignment satisfies $F'_{1}$ :
$\\ x_{1} \mapsto True\\ x_{2} \mapsto False\\ x_{3} \mapsto True\\ x_{4} \mapsto True\\ x_{5} \mapsto False$
However:
$\\ F_{2} = (\neg x_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge \\ (x_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge\\ (\neg x_{1} \vee x_{2} \vee \neg x_{3})\wedge \\ (\neg x_{1} \vee \neg x_{2} \vee x_{3})\wedge\\ (x_{1} \vee x_{2} \vee \neg x_{3})\wedge\\ (\neg x_{1} \vee x_{2} \vee x_{3})\wedge\\ (x_{1} \vee \neg x_{2} \vee x_{3})\wedge\\ (x_{1} \vee x_{2} \vee x_{3})$
And the following is $F_{2}'$ in Monotone 3SAT form:
$\\ F_{2}' = (\neg x_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge \\ (\neg y_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge\\ (\neg x_{1} \vee \neg y_{2} \vee \neg x_{3})\wedge \\ (\neg x_{1} \vee \neg x_{2} \vee \neg y_{3})\wedge \\ (x_{1} \vee x_{2} \vee y_{3})\wedge\\ (y_{1} \vee x_{2} \vee x_{3})\wedge\\ (x_{1} \vee y_{2} \vee x_{3})\wedge\\ (x_{1} \vee x_{2} \vee x_{3}) \wedge \\ (y_{1} \vee x_{1}) \wedge (\neg y_{1} \vee \neg x_{1}) \wedge \\ (y_{1} \vee x_{2}) \wedge (\neg y_{2} \vee \neg x_{2})\wedge \\ (y_{1} \vee x_{3}) \wedge (\neg y_{3} \vee \neg x_{3})$
are both unsatisfiable.

The reduction:
In the following reduction we are given an instance of 3SAT,
$F = \wedge_{i=1}^{n} C_{i}$ . Here each clause is of the form:
$C_{i} = x_{i1} \vee ... \vee x_{ik_i}$ where
$k_{i} < 4$
and each $x_{ik_i}$ is a literal of the form $\neg z_{l} \ or \ z_{l}$ .
We use the following construction to build an instance of Monotone 3 SAT out of the above instance of 3SAT :
In each clause $C_{i}$ we have at most one literal, $z_{l} \ or \ \neg z_{l}$ that is not of the same parity as the rest of the literals in the clause. For every such literal, we may preform the following substitution:
$z_{l} \rightarrow \neg y_{l} \ or \ \neg z_{l} \rightarrow y_{l}$ this yields a modified clause $C'_{i}$ .
Now we must be able to guarantee that $z_{l}$ and $y_{l}$ are mapped to opposite truth values, so we introduce the new clause:
$C''_{i} \ = \ ( z_{l} \vee y_{l}) \wedge ( \neg z_{l} \vee \neg y_{l})$ and conjunct it onto our old formula $F$ producing a new formula $F'$ .

For example:
$C_{i} \ = \ (z_{l_1} \vee z_{l_2} \vee \neg z_{l_3})$ so we preform the substitution
$\neg z_{l_3} \rightarrow y_{l_3}$
so $C'_{i} \ = \ (z_{l_1} \vee z_{l_2} \vee y_{l_3})$ and $C''_{i} \ = \ (z_{l_3} \vee y_{l_3}) \wedge ( \neg z_{l_3} \vee \neg y_{l_3})$

Now repeating this procedure will result in a new formula: $F' = (\wedge_{i=1}^{n} C'_{i}) \wedge (\wedge_{k=1}^{m} C''_{k})$ .
We claim logical equivalence between the $C_{i} \wedge C''_{i}$ and $C'_{i} \wedge C''_{i}$ This is semantically intuitive as the $C''_{i}$ clause requires all substituted literal $y_{l}$ in $C'_{i}$ to take the value opposite of $z_{l}$ this was the stipulation for the substitution initially. It is also verifiable by truth table construction for:
$\\ (z_{l_1} \vee z_{l_2} \vee \neg z_{l_3}) \wedge (z_{l_3} \vee y_{l_3}) \wedge ( \neg z_{l_3} \vee \neg y_{l_3}) \Leftrightarrow \\ (z_{l_1} \vee z_{l_2} \vee y_{l_3}) \wedge (z_{l_3} \vee y_{l_3}) \wedge ( \neg z_{l_3} \vee \neg y_{l_3})$

$True_{3SAT} \Rightarrow True_{Monotone \ 3 \ SAT}$ :
If there exists a truth assignment $\phi_{F}$ that satisfies $F$ , then we may extent this truth assignment to produce $\phi_{G}$ which will satisfy
$G = F \wedge (\wedge_{k=1}^{m} C''_{k})$ by letting $\phi_{G} (z_{l}) = \phi_{F} (x_{l})$ for all $l$ and letting $\phi_{G}(y_{l}) = \neg \phi_{F}(z_{l})$ for all $l$ .
Obviously if $F$ is satisfiable $G$ must be by the above construction of $\phi_{G}$ . So by the above claim we have that $\phi_{G}$ will satisfy $F'$ .
$True_{Monotone \ 3 \ SAT} \Rightarrow True_{3SAT}$ :
Continuing from the above, if we have a truth assignment $\phi_{F'}$ that satisfies $F'$ , then by the claim above it also must satisfy $G$ . And $F$ is a sub-formula of $G$ so any truth assignment that satisfies $G$ must also satisfy $F$ .

(Back to me)

Difficulty: 4, since it’s a little harder than the regular Monotone Sat one.

4 Comments

Posted in Appendix-Logic

Tagged 3-sat, Dan's Problems, Difficulty 4, Monotone 3SAT, Monotone Sat, uncited reduction

Monotone Satisfiability

Posted on April 8, 2016 | Leave a comment

This semester I’m doing an independent study with a student, Daniel Thornton, looking at NP-Complete problems. He came up with a reduction for Monotone Satisfiability, and since I hadn’t gotten to that problem yet, I told him if he wrote it up, I’d post it.

So, here it is. Take it away, Daniel!

The Problem: Monotone SAT. This is mentioned in problem LO2 in the book.

The description:
Given an set of clauses $F' = \wedge_{i=1}^{n} C_{i}$ where each clause in F contains all negated or non-negated variables, is there an assignment of the variables so that $F'$ is satisfied?

Example:
$F' = (x_{1} \vee x_{3} \vee x_{4}) \wedge (\neg x_{2} \vee \neg x_{3} \vee \neg x_{4}) \wedge (x_{3} \vee x_{2} \vee x_{4})$
the following assignment satisfies $F'$ :
$x_{1} \mapsto False$
$x_{2} \mapsto False$
$x_{3} \mapsto False$
$x_{4} \mapsto True$

The reduction:
In the following reduction we are given an instance of SAT, with the clauses:
$F = \wedge_{i=1}^{n} C_{i}$ . Here each clause is of the form $C_{i} = x_{i1} \vee x_{i2} \vee ... \vee x_{ik_i}$ and each $x_{ij}$ is a literal of the form $\neg z_{ij} \ or \ z_{ij}$
Now we build an instance of Monotone SAT from the instance of SAT given above:
For each $C_{i}$ we construct two new clauses $\\ C'_{2i} = z_{i l_1} \vee ... \vee z_{il_k } \vee z'_{i}$ and $\ C'_{2i-1}= \neg z_{il_k+1} \vee ... \vee \neg z_{il_m} \vee \neg z'_{i}$ , such that all elements of $C'_{2i}$ are non-negated literals and all terms in $C'_{2i-1}$ are negated literals with the addition of the new special term $z'_{i}$ . Now let us build a new formula $F' = \wedge_{i'=1}^{2n} C'_{i'}$ this is our instance of Monotone SAT, clauses are either all non-negated or negated.

$True_{Monotone SAT} \Rightarrow True_{SAT}$ :
Notice how we added the extra literal $z'_{i}$ or $\neg z'_{i}$ to each of the clauses $C'_{2i}$ or $C'_{2i-1}$ respectfully. Now if there is an assignment that satisfies all of the clauses of $F'$ then as only $C_{2i}$ or $C_{2i-1}$ may be satisfied by the appended extra literal, one of the clauses must be satisfied by it’s other literals. These literals are also in $C_{i}$ so such an assignment satisfies all $C_{i} \in F$ .

$True_{SAT} \Rightarrow True_{Monotone SAT}$ :
Using an argument similar to the one above, For $F$ to be satisfied there must be at least one literal assignment say $z_{iy}$ that satisfies each clause $C_{i}$ Now $z_{iy}$ is in either $C'_{2i}$ or $C'_{2i-1}$ . This implies that at least one of $C'_{2i}$ or $C'_{2i -1}$ is also satisfied by $z_{iy}$ , so simply assign the new term $z'_{i}$ accordingly to satisfy the clause in $F'$ not satisfied by $z_{iy}$