class TransformToCnf extends CnfBuilder
Plaisted transformation: used for conversion of a propositional formula into conjunctive normal form (CNF) (input format for SAT solver). A simple conversion into CNF via Shannon expansion would also be possible but it's worst-case complexity is exponential (in the number of variables) and thus even simple problems could become untractable. The Plaisted transformation results in an _equisatisfiable_ CNF-formula (it generates auxiliary variables) but runs with linear complexity. The common known Tseitin transformation uses bi-implication, whereas the Plaisted transformation uses implication only, thus the resulting CNF formula has (on average) only half of the clauses of a Tseitin transformation. The Plaisted transformation uses the polarities of sub-expressions to figure out which part of the bi-implication can be omitted. However, if all sub-expressions have positive polarity (e.g., after transformation into negation normal form) then the conversion is rather simple and the pseudo-normalization via NNF increases chances only one side of the bi-implication is needed.
- Source
- Solving.scala
- Alphabetic
- By Inheritance
- TransformToCnf
- CnfBuilder
- AnyRef
- Any
- by any2stringadd
- by StringFormat
- by Ensuring
- by ArrowAssoc
- Hide All
- Show All
- Public
- All
Instance Constructors
- new TransformToCnf(symbolMapping: SymbolMapping)
Value Members
-
final
def
!=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
final
def
##(): Int
- Definition Classes
- AnyRef → Any
-
def
+(other: String): String
- Implicit
- This member is added by an implicit conversion from TransformToCnf to any2stringadd[TransformToCnf] performed by method any2stringadd in scala.Predef.
- Definition Classes
- any2stringadd
-
def
->[B](y: B): (TransformToCnf, B)
- Implicit
- This member is added by an implicit conversion from TransformToCnf to ArrowAssoc[TransformToCnf] performed by method ArrowAssoc in scala.Predef.
- Definition Classes
- ArrowAssoc
- Annotations
- @inline()
-
final
def
==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
def
addClauseProcessed(clause: Clause): Unit
- Definition Classes
- CnfBuilder
- def apply(p: CNF.Prop): Solvable
-
final
def
asInstanceOf[T0]: T0
- Definition Classes
- Any
-
def
buildCnf: Array[Clause]
- Definition Classes
- CnfBuilder
-
def
clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( ... ) @native()
-
def
constFalse: Lit
- Definition Classes
- CnfBuilder
-
lazy val
constTrue: Lit
- Definition Classes
- CnfBuilder
- def convertSym(sym: CNF.Sym): Lit
-
def
ensuring(cond: (TransformToCnf) ⇒ Boolean, msg: ⇒ Any): TransformToCnf
- Implicit
- This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
- Definition Classes
- Ensuring
-
def
ensuring(cond: (TransformToCnf) ⇒ Boolean): TransformToCnf
- Implicit
- This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
- Definition Classes
- Ensuring
-
def
ensuring(cond: Boolean, msg: ⇒ Any): TransformToCnf
- Implicit
- This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
- Definition Classes
- Ensuring
-
def
ensuring(cond: Boolean): TransformToCnf
- Implicit
- This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
- Definition Classes
- Ensuring
-
final
def
eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
-
def
equals(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
def
finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( classOf[java.lang.Throwable] )
-
final
def
getClass(): Class[_]
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
-
def
hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
-
def
isConst(l: Lit): Boolean
- Definition Classes
- CnfBuilder
-
final
def
isInstanceOf[T0]: Boolean
- Definition Classes
- Any
-
var
literalCount: Int
- Definition Classes
- TransformToCnf → CnfBuilder
-
final
def
ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
-
def
newLiteral(): Lit
- returns
new Tseitin variable
- Definition Classes
- CnfBuilder
-
final
def
notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
-
final
def
notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
-
final
def
synchronized[T0](arg0: ⇒ T0): T0
- Definition Classes
- AnyRef
-
def
toString(): String
- Definition Classes
- AnyRef → Any
-
final
def
wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
final
def
wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
final
def
wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... ) @native()
-
def
→[B](y: B): (TransformToCnf, B)
- Implicit
- This member is added by an implicit conversion from TransformToCnf to ArrowAssoc[TransformToCnf] performed by method ArrowAssoc in scala.Predef.
- Definition Classes
- ArrowAssoc
Deprecated Value Members
-
def
formatted(fmtstr: String): String
- Implicit
- This member is added by an implicit conversion from TransformToCnf to StringFormat[TransformToCnf] performed by method StringFormat in scala.Predef.
- Definition Classes
- StringFormat
- Annotations
- @deprecated @inline()
- Deprecated
(Since version 2.12.16) Use
formatString.format(value)instead ofvalue.formatted(formatString), or use thef""string interpolator. In Java 15 and later,formattedresolves to the new method in String which has reversed parameters.
The Scala compiler and reflection APIs.