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
Best german_5 books
Relationale Datenbanken: Eine Einführung für die Praxis
Die Fachbrosch}re gibt eine umfassende Einf}hrung in das Gebiet der relationalen Datenbanken. Bei der Datenmodellierung werden Abbildungsregeln zum ]berf}hren eines Entit{ten-Beziehungsmodells in ein relationales Datenbankschema behandelt, Normalformen diskutiert und ein unternehmensweites Datenmodell veranschaulicht.
- Über den Bau der Atome
- Lastmanagement bei zeitvariabler Elektrizitätspreisbildung in Industriebetrieben
- Meß- Steuerungs- Regelungstechnik: Formeln, Daten und Begriffe
- UNIX: Einstieg für DOS-Anwender
- Mathematische Behandlung einer angenäherten quasilinearen Potentialgleichung der ebenen kompressiblen Strömung
Extra resources for Aussagenlogik: Deduktion und Algorithmen
Example text
Der einfachste Algorithmus flir den Erfiillbarkeitstest ist sicherlich die Uberpriifung aller Bewertungen einer Formel. Besitzt eine Formel aber n Atome, so bedarf es eventuell einer Folge von 2n Tests, wodurch wir eine exponentielle Laufzeit erhalten. Zur Klassifizierung der Komplexitat des Erflillbarkeitsproblems und anderer Probleme werden die Komplexitatsklassen P, NP, coNP und D P verwendet. An dieser Stelle wollen wir nur sehr knapp die flir unsere Zwecke notigen Begriffe einflihren. Fiir eine ausflihrliche Beschreibung (insbesondere des Konzeptes der Turingmaschinen) verweisen wir auf [GaJo 79, BaDiGa 88, Joh 90].
Jeder dieser sogenannten Minterme ist fiir genau die ihn definierende Bewertung ~ wahr und fiir sonst keine Bewertung. Also ist die so gebildete Disjunktive Normalform logisch aquivalent zur Ausgangsformel. ,a) in DNF. Der Beweis dieser einfachen Folgerung (Induktion iiber den Formelaufbau) bleibt dem Leser iiberlassen. 3 (Duale Formel) Zu einer aussagenlogischen Formel definieren wir induktiv die duale Formel d( a) zu a durch: 1. 2. 3. 4. 1st a 1st a 1st a 1st a ein Atom, so sei d( a) := a. ,d(fj)).
Auch bei den Einsetzungen wird del' Vorteil von BDDs, also einer Reprasentation als DAG, deutlich. Wenn sichergestellt ist, daB jeweils nur ein Blatt existiert, das mit 0, und eines, das mit 1 gekennzeichnet ist, muB auch bei del' Konjunktion odeI' Disjunktion nm jeweils ein BDD angehangt werden und die mit 0 bzw. 1 markierten Blatter idelltifiziert werden. Dies ist mit polynomiellen Aufwalld moglich. 46 2 Datenstrukturen und Normalformen Wie man an dem Beispiel del' Formelfamilie mit IFn I = O( n) sieht, kann die Einsparung exponentiell sein.