A renamable Horn formula is a CNF formula that can be turned into a Horn formula by…
- User
A renamable Horn formula is a CNF formula that can be turned into a Horn formula by negating (all occurrences of) some of its variables. For example, (P1 ∨¬P2 ∨¬P3)∧(P2 ∨P3)∧(¬P1) can be turned into a Horn formula by negating P1 and P2. Given a CNF-formula F , show how to derive a 2-CNF formula G such that G is satisfiable if and only if F is a renamable Horn formula. Show moreover that one can derive a renaming that turns F into a Horn formula from a satisfying assignment for G.
- Assistant
To determine whether a given CNF formula ( F ) is a renamable Horn formula, we can construct a corresponding 2-CNF formula ( G ). This formula ( G ) will be satisfiable if and only if ( F ) is renamable into a Horn formula. Moreover, a satisfying assignment for ( G ) will directly provide the necessary variable renamings to transform ( F ) into a Horn formula.
Step 1: Introduce Renaming Variables
For each variable ( P ) in the CNF formula ( F ), introduce a Boolean variable ( y_P ) in ( G ):
- ( y_P = \text{true} ) indicates that ( P ) is not negated in the renaming.
- ( y_P = \text{false} ) indicates that ( P ) is negated in the renaming.
Step 2: Encode Horn Constraints
A Horn clause has at most one positive literal. To ensure that each clause in ( F ) becomes Horn after renaming, we must enforce that no clause in ( F ) contains two or more positive literals post-renaming.
For each clause ( C ) in ( F ), perform the following:
-
Identify Literals: Suppose ( C ) has literals ( l_1, l_2, \ldots, l_k ).
-
Determine Potential Positivity:
- If ( l_i ) is a positive literal (e.g., ( P )), then after renaming, ( l'_i ) is positive if ( y_P = \text{true} ), and negative otherwise.
- If ( l_i ) is a negative literal (e.g., ( \neg P )), then ( l'_i ) is positive if ( y_P = \text{false} ), and negative otherwise.
-
Add Pairwise Constraints: For every pair of literals ( (l_i, l_j) ) in ( C ), add a 2-CNF clause to ( G ) that prevents both ( l'_i ) and ( l'_j ) from being positive simultaneously. This is done as follows:
-
Determine Sign Conditions:
- If ( l_i = P ), then ( l'_i ) positive corresponds to ( y_P ).
- If ( l_i = \neg P ), then ( l'_i ) positive corresponds to ( \neg y_P ).
- Similarly for ( l_j ).
-
Formulate the Clause:
- Let ( s_i ) represent the condition under which ( l'_i ) is positive.
- Let ( s_j ) represent the condition under which ( l'_j ) is positive.
- Add the clause ( (\neg s_i \lor \neg s_j) ) to ( G ).
-
By systematically adding such clauses for every pair of literals in every clause of ( F ), ( G ) ensures that no clause in ( F ) can have more than one positive literal after renaming.
Step 3: Satisfiability and Renaming
-
If ( G ) is satisfiable:
- The satisfying assignment to the ( y_P ) variables provides a way to rename variables in ( F ) such that the resulting formula is Horn. Specifically, for each ( P ):
- If ( y_P = \text{true} ), keep ( P ) as is.
- If ( y_P = \text{false} ), replace ( P ) with ( \neg P ) throughout ( F ).
- The satisfying assignment to the ( y_P ) variables provides a way to rename variables in ( F ) such that the resulting formula is Horn. Specifically, for each ( P ):
-
If ( G ) is not satisfiable:
- There is no possible renaming of variables that can transform ( F ) into a Horn formula.
Example Illustration
Consider the CNF formula: [ F = (P_1 \lor \neg P_2 \lor \neg P_3) \land (P_2 \lor P_3) \land (\neg P_1) ] To ensure ( F ) is renamable Horn:
- Introduce variables ( y_{P_1} ), ( y_{P_2} ), and ( y_{P_3} ).
- For each clause in ( F ), add appropriate 2-CNF constraints to ( G ).
- A satisfying assignment, such as ( y_{P_1} = \text{false} ) and ( y_{P_2} = \text{false} ), will indicate that negating ( P_1 ) and ( P_2 ) transforms ( F ) into a Horn formula.
Conclusion
By constructing ( G ) as a 2-CNF formula with constraints ensuring that each clause in ( F ) has at most one positive literal after potential renamings, we can effectively determine whether ( F ) is a renamable Horn formula. Furthermore, a satisfying assignment to ( G ) directly provides the specific renaming required to achieve the Horn property.
Answer:
Introduce a Boolean variable yₚ for each variable P in F to indicate whether to negate P. Then construct G as follows: for every clause in F and for every pair of literals in that clause, add to G a 2-CNF clause ensuring that after renaming, at most one literal in the pair is positive. Specifically, for each clause C in F and each two literals l₁ and l₂ in C, add (¬s₁ ∨ ¬s₂) to G where s₁ is yₚ if l₁ is P or ¬yₚ if l₁ is ¬P, and similarly for s₂ based on l₂. This 2-CNF formula G is satisfiable exactly when F is renamable Horn. Moreover, any satisfying assignment for G specifies which variables to negate, providing the renaming that makes F a Horn formula.