trait CNF extends PropositionalLogic
- Alphabetic
- By Inheritance
- CNF
- PropositionalLogic
- AnyRef
- Any
- by any2stringadd
- by StringFormat
- by Ensuring
- by ArrowAssoc
- Hide All
- Show All
- Public
- Protected
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
- sealed abstract 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
- abstract type Lit <: LitApi
- trait LitApi extends AnyRef
- trait LitModule extends AnyRef
- 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 def Lit: LitModule
- 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 hasModel(solvable: Solvable): Boolean
- 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 java.io.Serializable
- Definition Classes
- PropositionalLogic
- case object False extends Prop with Product with Serializable
- Definition Classes
- PropositionalLogic
- object Or extends java.io.Serializable
- Definition Classes
- PropositionalLogic
- object Sym
- Definition Classes
- PropositionalLogic
- case 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]): Prop
- Definition Classes
- PropositionalLogic
- final def ==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- val ArrayOfFalse: Array[Clause]
- val NoClauses: Array[Clause]
- def \/(props: Iterable[Prop]): Prop
- Definition Classes
- PropositionalLogic
- final def asInstanceOf[T0]: T0
- Definition Classes
- Any
- def clause(ls: IterableOnce[Lit]): Clause
- def clause(l: Lit, l2: Lit, ls: Lit*): Clause
- def clause(l: Lit, l2: Lit): Clause
- def clause(l: Lit): Clause
- def clause(): Clause
- def clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.CloneNotSupportedException]) @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: AnyRef): Boolean
- Definition Classes
- AnyRef → Any
- def finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.Throwable])
- def formatted(fmtstr: String): String
- def gatherSymbols(p: Prop): Set[Sym]
- Definition Classes
- PropositionalLogic
- def gatherVariables(p: Prop): Set[Var]
- Definition Classes
- PropositionalLogic
- final def getClass(): Class[_ <: AnyRef]
- 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 https://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(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException]) @native()
Deprecated Value Members
- def →[B](y: B): (CNF, B)
- Implicit
- This member is added by an implicit conversion from CNF toArrowAssoc[CNF] performed by method ArrowAssoc in scala.Predef.
- Definition Classes
- ArrowAssoc
- Annotations
- @deprecated
- Deprecated
(Since version 2.13.0) Use
->instead. If you still wish to display it as one character, consider using a font with programming ligatures such as Fira Code.
The Scala compiler and reflection APIs.