By Prof. Dr. rer. nat. Hans Kleine Büning, Dr. rer. pol. Theodor Lettmann (auth.)
"... Dieses Lehrbuch ... stellt die Grundlagen dieses Gebiets ausführlich und umfassend ... dar." P. Schmitt. Internationale Mathematische Nachrichten, Wien
Read or Download Aussagenlogik: Deduktion und Algorithmen PDF
Similar german_5 books
Die Kunst zu überzeugen: Faire und unfaire Dialektik
Dieses Buch fasst das knowledge moderner Dialektik in verst? ndlicher und praxisbezogener shape zusammen. Der Grundlagenteil bietet die Voraussetzungen erfolgreicher Argumentation. In den weiterf? hrenden Abschnitten zu konkreten Anwendungssituationen erfahren Sie, wie Sie Ihre ? berzeugungsf? higkeit in schwierigen Gespr?
- Ein Beitrag zur Planung und Bewertung Neuer Arbeitsstrukturen in NE-Metallgießereien: Dargestellt am Beispiel der Fertigungsinsel
- Probleme? Höhere Mathematik!: Eine Aufgabensammlung zur Analysis, Vektor- und Matrizenrechnung
- Imaging: Bildverarbeitung und Bildkommunikation
- Einführung in die Numerische Mathematik I: unter Berücksichtigung von Vorlesungen von F.L. Bauer
- Fehlertoleranzverfahren
Extra resources for Aussagenlogik: Deduktion und Algorithmen
Example text
Die Frage, ob es zu einem Problem einen polynomiellen deterministischen Algorithmus gibt, ist demnach fUr M' mindestens so schwer zu beantworten wie fiir M, da sich aus einem solchen Verfahren fiir M' mithilfe del' Transformation leicht ein polynomielles Verfahren fiir M gewinnen lafit. Ein Problem M' E NP ist NP-vollstiindig, falls jedes Problem M aus NP polynomiell auf M' reduzierbar ist. ) Aus der polynomiellen Losbarkeit eines NPvollstandigen Problem wiirde dann sofort die Gleichheit P = NPfolgen.
AnschlieBend werden in der Reprasentation von (A ? ()1 : ()2) als BDD die Mehrfachvorkommen von Teilgraphen und Vorkommen von Teilgraphen del' Form (A ? ()1 : ()1) eliminiert. 4). B. in [BRB 90]. Wie man leicht sieht, ist ein zu einer unerfiillbaren Formel aquivalenter ROBDD gleich 0 und ein zu einer Tautologie aquivalenter ROBDD gleich 1. Indem man also einen zu einer Formel ~ aquivalenten ROBDD bildet und dies en mit der Reprasentation von 0 vergleicht, kann man entscheiden, ob ~ erftillbar ist.
Da jede Formel 11" E KNF mit n Atomen in Kn liegt, mufi es eine ~ = atoms ( 11" )-aquivalente Formel in KNF mit einer Lange von maximal p( 2n) + 2n geben. 5, daher ist die Annahme falsch und das Lemma damit bewiesen. • Ausgehend von der Anzahl der Atome oder einer beliebigen Struktur konnen wir also im allgemeinen keine "kurze" Darstellung in KNF angeben. Wir wollen anschliefiend zeigen, dafi wir selbst bei Vorliegen einer Konjunktiyen Normalform im allgemeinen nicht einmal die Klausellange reduzieren konnen.