/ en / Traditional / help

Beats Biblionetz - Texte

Erfüllbarkeit

Zu finden in: The New Turing Omnibus (Seite 247 bis 254), 2001  local web 
Erste Seite des Textes (PDF-Thumbnail)
Diese Seite wurde seit 3 Jahren inhaltlich nicht mehr aktualisiert. Unter Umständen ist sie nicht mehr aktuell.

iconZusammenfassungen

A. K. Dewdney
Das Erfüllbarkeitsproblem der Booleschen Algebra scheint, zumindest auf den ersten Blick, sehr einfach zu sein: Gegeben sei ein Ausdruck wie
$$({{x}_{1}} + {{\bar{x}}_{3}} + {{x}_{4}})({{\bar{x}}_{1}} + {{\bar{x}}_{2}} + {{\bar{x}}_{4}})({{\bar{x}}_{2}} + {{x}_{3}})({{\bar{x}}_{1}} + {{x}_{2}} + {{x}_{4}})$$
und es soll eine Zuordnung von Wahrheitswerten (0 oder 1) für die Booleschen Variablen x 1, x 2, x 3, x 4 gefunden werden, so daß der gesamte Ausdruck wahr ist. Dies bedeutet, daß jede der Klauseln wie \({{x}_{1}} + {{{\bar{x}}}_{3}} + {{x}_{4}}\) wahr sein (den Wert 1 haben) muß. Wenn wir eine Zuordnung suchen, die den oben wiedergegebenen Ausdruck erfüllt, könnten wir z.B. x 1 = 1, x 2 = 1, x 3 = 1, x4 = 1 versuchen, um dann festzustellen, daß die Klausel \({{{\bar{x}}}_{1}} + {{x}_{2}} + {{x}_{4}}\) bei dieser Zuordnung den Wert 0 + 0 + 0 = 0 besitzt, was die Bedingung verletzt, daß jede der Klauseln wahr sein muß. Daher folgt hieraus, daß diese Zuordnung den Ausdruck nicht erfüllt. Wenn wir jedoch die Werte x 1 = 0, x 2 = 1, x 3 = 1, x 4 =1 versuchen, stellen wir fest, daß bei dieser Zuordnung alle Klauseln wahr sind und die Zuordnung den Ausdruck „erfüllt“. Ausdrücke, welche die obige Form besitzen, bezeichnet man als in Summenprodukt-Form.
Von A. K. Dewdney im Buch The New Turing Omnibus (2001) im Text Erfüllbarkeit

iconAnderswo finden

icon

iconVolltext dieses Dokuments

Auf dem WWW Erfüllbarkeit: Artikel als Volltext bei Springerlink (lokal: PDF, 912 kByte; WWW: Link OK )

iconAnderswo suchen  Auch im Biblionetz finden Sie nicht alles. Aus diesem Grund bietet das Biblionetz bereits ausgefüllte Suchformulare für verschiedene Suchdienste an. Biblionetztreffer werden dabei ausgeschlossen.

iconBeat und dieses Kapitel

Beat hat Dieses Kapitel während seiner Zeit am Institut für Medien und Schule (IMS) ins Biblionetz aufgenommen. Er hat Dieses Kapitel einmalig erfasst und bisher nicht mehr bearbeitet. Beat besitzt kein physisches, aber ein digitales Exemplar. Eine digitale Version ist auf dem Internet verfügbar (s.o.). Aufgrund der wenigen Einträge im Biblionetz scheint er es nicht wirklich gelesen zu haben. Es gibt bisher auch nur wenige Objekte im Biblionetz, die dieses Werk zitieren.

iconBiblionetz-History Dies ist eine graphische Darstellung, wann wie viele Verweise von und zu diesem Objekt ins Biblionetz eingetragen wurden und wie oft die Seite abgerufen wurde.