By Uwe Schöning

Das Buch macht den Leser mit den wesentlichen Teilgebieten der formalen Logik vertraut, die Bestandteil der Ausbildung in Theoretischer Informatik sind. Die Darstellung orientiert sich an den Bedürfnissen von Informatikstudierenden. Insbesondere werden viele mehr auf das Prinzipielle ausgerichtete Resultate der formalen Logik unter einem algorithmischen Gesichtspunkt behandelt. Diese Vorgehensweise erleichtert entscheidend den Zugang zu dem abstrakten Themengebiet. Prof. Schöning gelingt eine kompakte und verständliche Darstellung der Aussagen- und Prädikatenlogik, bei der die benötigten Begriffe präzise eingeführt und durch Beispiele veranschaulicht werden. Darauf beruhend werden Anwendungen der Logik in der Informatik, wie z. B. solution, Automatisches Beweisen und Logik-Programmierung behandelt. Zahlreiche Übungsaufgaben mit ausführlichen Lösungshinweisen erleichtern die Vertiefung des Lernstoffes.

Show description

Read Online or Download Logik für Informatiker PDF

Similar Logic books

How We Know What Isn't So: The Fallibility of Human Reason in Everyday Life

Thomas Gilovich bargains a smart and readable consultant to the fallacy of the most obvious in daily life. whilst will we belief what we believe—that "teams and gamers have profitable streaks," that "flattery works," or that "the extra those that agree, the much more likely they're to be right"—and whilst are such ideals suspect?

Critical Thinking

The 1st built-in software designed in particular for the severe considering path, Moore & Parker's serious pondering teaches scholars the talents they want which will imagine for themselves-skills they are going to name upon during this direction, in different university classes, and on this planet that awaits. The authors' functional and available process illustrates center ideas with concrete real-world examples, vast perform workouts, and a considerate set of pedagogical positive factors.

Intermediate Logic

Intermediate common sense is a perfect textual content for someone who has taken a primary direction in good judgment and is progressing to additional examine. It examines logical thought, instead of the functions of good judgment, and doesn't suppose any particular technical grounding. the writer introduces and explains every one proposal and time period, making sure readers have an organization beginning for research.

The Philosophy of Information

Luciano Floridi provides a publication that may set the time table for the philosophy of knowledge. PI is the philosophical box excited by (1) the serious research of the conceptual nature and uncomplicated rules of knowledge, together with its dynamics, utilisation, and sciences, and (2) the elaboration and alertness of information-theoretic and computational methodologies to philosophical difficulties.

Extra resources for Logik für Informatiker

Show sample text content

Dies wird im Folgenden zu diskutieren sein. Wir stellen nun diese Resolutionsrestriktioncn vor. Bei der P-Restriktion (oder P-Resolution) darf nur dann ein Resolvent zweier Klauseln K1:K2gebildet werden, sofern eine der beiden Klauseln positiv ist, additionally nur aus positrven Literalen besteht. Analog darf bei der N-Rrstriktion (oder N-Resolution) nur resolviert werden, wenn eine der beiden Eltemklauseln nur aus negativen Lrteralen besteht. Wir werden zeigen, dass P- und N- 2. four. VERFEINERUNG DER RESOLUTrON 103 solution vellständig sind. Die leere Klausel ist aus einer Klauselmenge F linear res»lvierbar; basierend auf einer Klausel okay E F, falls CS eine Folge von Klauseln (Ko,K I , . . . , I L ) gibt mit Ka = ok, ok, = und für i = 1 , 2 , . . . , n gilt [eine sogenannte Sei~enklausel)entweder ein point wobei die Klausel = okay, für ein j < i . von F ist oder Wir werden zeigen, dass die lineare solution vollständig ist, das heißt, für jede unerfüllbare Kauselrnenge F gibt es eine Klause1 okay (die Basiskiausel), so dass die leere Klausel aus F linear resolvierbar ist, basierend auf okay. Beispiel: Gegeben sei die unerfullbare Klauselmenge Eine (übliche) Resolutionsherleilung der leeren Klausel ohne Einhaltung einer dieser Restriktionen benötigt three Resolutionsschritte. Eine lineare solution dcr Ieeren Klausel aus P, basierend auf ( A ,B}, ist 2. B. gegeben durch das folgende Diagramm (dies i s t gleichzeitig auch Beispiel für eine P-Resolution). KAPITEL 2. PRÄDIKATENLOGIK 2. 6. VERFEINERUNG DER answer a hundred and five einhalt, auch ein linemer Resolutionsbeweis ist. Aber im Unterschied zur linearen answer ist die Input-Resolution nicht vollständig. Ein einfaches Gegenbeispiel ist die unerfüllbare Klauselmenge F = { { A ,B ) , 1-4,T B ) ,{ T A ,B ) , { T A ,- B ) } . Bei einer Inputresolution entsteht im ersten Schritt immer ein Resolvent mit mindestens einem Literal. Bei jedem weiteren Resolutionsschritt können wieder nur Resolventen mit mindestens einem Literal entstehen. Die leere Klausel ist bei diesem Beispiel in line with Input-Resolution additionally nrcht herleitbar. Wir werden aber später zeigen, dass die Input-Resolution vollstiindig für die Klasse der Hornfomeln ist. guy beachte, dass dieser Resolutionsbeweis four Schritte benötigt. guy kann erahnen, dass der Preis, der für die Einschränkung der Wahlmöglichkeiten bei den ResoIutionsrestriktionen bezahlt werden muss, in einer Zunahme der Beweislänge liegt. Diesen Effekt genau zu quantifizieren ist aktuelles Thema der Forschung (vgl. hierzu Ubung 87). Bei der Stiitzmengenresta'ktiun der solution muss zu der gegebenen Klauselmenge F erne Teilmenge T bekannt sein, so dass F - T erfüllbar ist. Ein Resolutionsbeweis der leeren Klausel aus F, relativ zur Stiitzmenge T, muss die Bedingung erfüllen, dass niemals zwei Klauseln aus F - T miteinander resolviert werden. Diese Einschränkung bringt vor ailem dann Vorteile, wenn T besonders klein und damit F - T besonders groß ist, z. B. bei IT I = 1. Dadurch wird eine große Zahl von potenziellen RcsoIutionsschritten (zwischen Klauseln in F - T) vermieden.

Rated 4.63 of 5 – based on 42 votes