Direkt zum Inhalt

Lexikon der Mathematik: erfüllbarer Boolescher Ausdruck

ein Boolescher Ausdruck \(w\in {{\mathfrak{A}}}_{n}\), der eine Boolesche Funktion φ(w) darstellt (Boolescher Ausdruck), für die es wenigstens eine Variablenbelegung α ∈ {0, 1}n mit \begin{eqnarray}\phi (w)({\alpha }_{1},\ldots,{\alpha }_{n})=1\end{eqnarray} gibt.

Die ON-Menge der Booleschen Funktion φ(w) heißt Erfüllbarkeitsmenge des Booleschen Ausdrucks w. Ein Verfahren, das entscheidet, ob die Erfüllbarkeitsmenge eines Booleschen Ausdrucks w nicht leer ist, wird Erfüllbarkeitstest genannt.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos