trait CNF extends PropositionalLogic
- Alphabetic
- By Inheritance
- CNF
- PropositionalLogic
- AnyRef
- Any
- by any2stringadd
- by StringFormat
- by Ensuring
- by ArrowAssoc
- Hide All
- Show All
- Public
- All
Type Members
-
trait
AbsVar extends AnyRef
- Definition Classes
- PropositionalLogic
-
final
case class
And(ops: Set[Prop]) extends Prop with Product with Serializable
- Definition Classes
- PropositionalLogic
-
final
case class
AtMostOne(ops: List[Sym]) extends Prop with Product with Serializable
- Definition Classes
- PropositionalLogic
-
final
case class
Eq(p: Var, q: Const) extends Prop with Product with Serializable
- Definition Classes
- PropositionalLogic
-
final
case class
Not(a: Prop) extends Prop with Product with Serializable
- Definition Classes
- PropositionalLogic
-
final
case class
Or(ops: Set[Prop]) extends Prop with Product with Serializable
- Definition Classes
- PropositionalLogic
-
class
Prop extends AnyRef
- Definition Classes
- PropositionalLogic
-
trait
PropMap extends AnyRef
- Definition Classes
- PropositionalLogic
-
trait
PropTraverser extends AnyRef
- Definition Classes
- PropositionalLogic
-
final
case class
Solution(model: Model, unassigned: List[Sym]) extends Product with Serializable
- Definition Classes
- PropositionalLogic
-
final
class
Sym extends Prop
- Definition Classes
- PropositionalLogic
-
trait
TypeConstExtractor extends AnyRef
- Definition Classes
- PropositionalLogic
-
trait
ValueConstExtractor extends AnyRef
- Definition Classes
- PropositionalLogic
-
trait
VarExtractor extends AnyRef
- Definition Classes
- PropositionalLogic
- class AlreadyInCNF extends AnyRef
- type Clause = Set[Lit]
-
type
Cnf = Array[Clause]
Conjunctive normal form (of a Boolean formula).
Conjunctive normal form (of a Boolean formula). A formula in this form is amenable to a SAT solver (i.e., solver that decides satisfiability of a formula).
- trait CnfBuilder extends AnyRef
-
abstract
type
Const
- Definition Classes
- PropositionalLogic
-
type
Model = Map[Sym, Boolean]
- Definition Classes
- PropositionalLogic
- final case class Solvable(cnf: Cnf, symbolMapping: SymbolMapping) extends Product with Serializable
- class SymbolMapping extends AnyRef
-
class
TransformToCnf extends CnfBuilder
Plaisted transformation: used for conversion of a propositional formula into conjunctive normal form (CNF) (input format for SAT solver).
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.
-
abstract
type
Tree
- Definition Classes
- PropositionalLogic
-
abstract
type
Type
- Definition Classes
- PropositionalLogic
-
abstract
type
TypeConst <: Const
- Definition Classes
- PropositionalLogic
-
abstract
type
ValueConst <: Const
- Definition Classes
- PropositionalLogic
-
abstract
type
Var <: AbsVar
- Definition Classes
- PropositionalLogic
Abstract Value Members
-
abstract
val
EmptyModel: Model
- Definition Classes
- PropositionalLogic
-
abstract
val
NoModel: Model
- Definition Classes
- PropositionalLogic
-
abstract
val
NullConst: Const
- Definition Classes
- PropositionalLogic
-
abstract
def
TypeConst: TypeConstExtractor
- Definition Classes
- PropositionalLogic
-
abstract
def
ValueConst: ValueConstExtractor
- Definition Classes
- PropositionalLogic
-
abstract
val
Var: VarExtractor
- Definition Classes
- PropositionalLogic
- abstract def cnfString(f: Array[Clause]): String
-
abstract
def
findAllModelsFor(solvable: Solvable, sym: Global.Symbol = NoSymbol): List[Solution]
- Definition Classes
- PropositionalLogic
-
abstract
def
findModelFor(solvable: Solvable): Model
- Definition Classes
- PropositionalLogic
-
abstract
def
prepareNewAnalysis(): Unit
- Definition Classes
- PropositionalLogic
-
abstract
def
reportWarning(message: String): Unit
- Definition Classes
- PropositionalLogic
-
abstract
def
uncheckedWarning(pos: Global.Position, msg: String, site: Global.Symbol): Unit
- Definition Classes
- PropositionalLogic
Concrete Value Members
-
object
AnalysisBudget
- Definition Classes
- PropositionalLogic
-
object
And extends Serializable
- Definition Classes
- PropositionalLogic
-
object
False extends Prop with Product with Serializable
- Definition Classes
- PropositionalLogic
-
object
Or extends Serializable
- Definition Classes
- PropositionalLogic
-
object
Sym
- Definition Classes
- PropositionalLogic
-
object
True extends Prop with Product with Serializable
- Definition Classes
- PropositionalLogic
-
final
def
!=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
final
def
##(): Int
- Definition Classes
- AnyRef → Any
- def +(other: String): String
- def ->[B](y: B): (CNF, B)
-
def
/\(props: Iterable[Prop]): Product with Serializable with Prop
- Definition Classes
- PropositionalLogic
-
final
def
==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
def
\/(props: Iterable[Prop]): Product with Serializable with Prop
- Definition Classes
- PropositionalLogic
-
final
def
asInstanceOf[T0]: T0
- Definition Classes
- Any
-
val
budgetProp: sys.Prop[String]
- Definition Classes
- PropositionalLogic
- def clause(l: Lit*): Clause
-
def
clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( ... ) @native()
- def ensuring(cond: (CNF) ⇒ Boolean, msg: ⇒ Any): CNF
- def ensuring(cond: (CNF) ⇒ Boolean): CNF
- def ensuring(cond: Boolean, msg: ⇒ Any): CNF
- def ensuring(cond: Boolean): CNF
-
final
def
eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
-
def
eqFreePropToSolvable(p: Prop): Solvable
- Definition Classes
- CNF → PropositionalLogic
-
def
equals(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
def
finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( classOf[java.lang.Throwable] )
-
def
gatherSymbols(p: Prop): Set[Sym]
- Definition Classes
- PropositionalLogic
-
def
gatherVariables(p: Prop): Set[Var]
- Definition Classes
- PropositionalLogic
-
final
def
getClass(): Class[_]
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
-
def
hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
-
final
def
isInstanceOf[T0]: Boolean
- Definition Classes
- Any
-
final
def
ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
-
final
def
notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
-
final
def
notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
-
def
propToSolvable(p: Prop): Solvable
- Definition Classes
- PropositionalLogic
-
def
removeVarEq(props: List[Prop], modelNull: Boolean = false): (Prop, List[Prop])
- Definition Classes
- PropositionalLogic
-
def
simplify(f: Prop): Prop
Simplifies propositional formula according to the following rules: - eliminate double negation (avoids unnecessary Tseitin variables) - flatten trees of same connectives (avoids unnecessary Tseitin variables) - removes constants and connectives that are in fact constant because of their operands - eliminates duplicate operands - convert formula into NNF: all sub-expressions have a positive polarity which makes them amenable for the subsequent Plaisted transformation and increases chances to figure out that the formula is already in CNF
Simplifies propositional formula according to the following rules: - eliminate double negation (avoids unnecessary Tseitin variables) - flatten trees of same connectives (avoids unnecessary Tseitin variables) - removes constants and connectives that are in fact constant because of their operands - eliminates duplicate operands - convert formula into NNF: all sub-expressions have a positive polarity which makes them amenable for the subsequent Plaisted transformation and increases chances to figure out that the formula is already in CNF
Complexity: DFS over formula tree
See http://www.decision-procedures.org/slides/propositional_logic-2x3.pdf
- Definition Classes
- PropositionalLogic
-
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): (CNF, B)
Deprecated Value Members
-
def
formatted(fmtstr: String): String
- Implicit
- This member is added by an implicit conversion from CNF to StringFormat[CNF] 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.