Aussagenlogik: Deduktion und Algorithmen by Prof. Dr. rer. nat. Hans Kleine Büning, Dr. rer. pol.

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

Show description

Read Online or Download Aussagenlogik: Deduktion und Algorithmen PDF

Best german_5 books

Atomkraft: Eine Einführung in die Probleme des Atomzeitalters

Dem nach der Tschernobyl-Katastrophe stark angewachsenen Informationsbedürfnis über die Möglichkeiten und Risiken der Kernkraft-Ausnutzung trägt diese Neuauflage Rechnung. In verständlicher shape wird in die technischen, militärischen, medizinischen und biologischen Probleme des Atomzeitalters eingeführt.

Numerische Mathematik 2: Eine Einführung — unter Berücksichtigung von Vorlesungen von F.L. Bauer

Dieses zweib? ndige Standardlehrbuch bietet einen umfassenden und aktuellen ? berblick ? ber die Numerische Mathematik. Dabei wird besonderer Wert auf solche Vorgehensweisen und Methoden gelegt, die sich durch gro? e Wirksamkeit auszeichnen. Ihr praktischer Nutzen, aber auch die Grenzen ihrer Anwendung werden vergleichend diskutiert.

Parallelrechner: Architekturen — Systeme — Werkzeuge

Moderne Anwendungen in vielen Bereichen der Wissenschaft und Technik erfordern den Einsatz massiver Parallelität. Die Probleme reichen von einfachen bis zu den "grand demanding situations" der Wissenschaft. Das Prinzip "Parallelität" durchdringt heute bereits in hohem Maße Forschung und Lehre in vielen Fachdisziplinen und immer mehr Anwender, die keine Hochleistungsrechner-Experten sind, wollen und werden diese Möglichkeiten für ihre Anwendung nutzen.

Extra resources for Aussagenlogik: Deduktion und Algorithmen

Sample text

0: 1) : (B ? (A ? 0: 1))). Solche Redundanz, wie das mehrfache Vorkommen eines Atoms auf einem Pfad odeI' das mehrfache Vorkommen von gleichen Teilgraphen, wird durch die folgende Definition vermieden. 9 (Reduced Ordered BDD, ROBDD) Sei Till ein BDD zu einer aussagenlogischen Formel (). Tw ist ein Reduced Ordered BDD (ROBDD), wenn Tw die folgenden Bedingungen erfullt. 1. Auf keinem Pfad von der Wurzel zu einem Blatt in Tw erscheint das gleiche Atom ofter als einmal. 2. Es gibt eine Ordnung ,,<" der Atome von () und entlang jedes Pfades von der Wurzel zu einem Blatt in Till genugen die Atome der Ordnung ,,< ".

It, wenn man in () daB Atom A mit 1 bewertet und die Formel durch Verrechnen del' Konstanten vereinfacht. ) Entsprechend erhalt man ()2, wenn man in () das Atom A mit 0 bewertet. 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.

Allerdings konnen wir nicht mehr so einfach iiber die Formelanzahl argumentieren. 6 Fur jedes Polynom p gibt es eine Formel an in HORN mit n Atomen und R = atoms (an), fur die keine zu an R-iiquivalente Formel (3 mit 1(31 < p( n) existiert. ) K i +1:= Ie U {{1I"1 V A, ... ,1I"r V A,1I"r+b .. } E K i } Offensichtlich gilt Ui>O Ki = KNF und fur jede Formel (3 E KNF mit n Atomen gilt naturlich-(3 E IC n • Nehmen wir an, es gebe ein Polynom p mit del' Eigenschaft, dafi zu jeder Horn-Formel a mit n Atomen und R = atoms (a) eine R-aquivalente Formel (3 in KNF del' Lange hochstens p( n) existiert.

Download PDF sample

Rated 4.32 of 5 – based on 47 votes