Definition:Satisfiable

From ProofWiki
Jump to navigation Jump to search

Definition

Let $\LL$ be a logical language.

Let $\mathscr M$ be a formal semantics for $\LL$.


Satisfiable Formula

A logical formula $\phi$ of $\LL$ is satisfiable for $\mathscr M$ if and only if:

$\phi$ is valid in some structure $\MM$ of $\mathscr M$

That is, there exists some structure $\MM$ of $\mathscr M$ such that:

$\MM \models_{\mathscr M} \phi$


Satisfiable Set of Formulas

A collection $\FF$ of logical formulas of $\LL$ is satisfiable for $\mathscr M$ if and only if:

There is some $\mathscr M$-model $\MM$ of $\FF$

That is, there exists some structure $\MM$ of $\mathscr M$ such that:

$\MM \models_{\mathscr M} \FF$


Satisfiable for Boolean Interpretations

Let $\mathbf A$ be a WFF of propositional logic.


$\mathbf A$ is called satisfiable (for boolean interpretations) if and only if:

$\map v {\mathbf A} = \T$

for some boolean interpretation $v$ for $\mathbf A$.


In terms of validity, this can be rendered:

$v \models_{\mathrm{BI}} \mathbf A$

that is, $\mathbf A$ is valid in the boolean interpretation $v$ of $\mathbf A$.


Also known as

In each of the above cases, satisfiable is also seen referred to as semantically consistent.


Also see


Sources