Informatik A: Rechnerstrukturen und Programmierparadigmen

Autor des Skriptes:
Prof. Dr. Wolfram Luther.

Zuletzt editiert von:
André Schaefer
mailto:andre.schaefer@uni-duisburg.de

Informatik A:
Rechnerstrukturen und Programmierparadigmen

1 Einführung in die Grundlagen der Informatik

1 Ziele der Informatik

Eine Anwendung von Informations- und Kommunikationssystemen allein ist jedoch nicht hinreichend, um Basis für den Bildungswert der Informatik zu sein.

Nun wollen wir zunächst einige der verwendeten Begriffe erklären: Bei der Kommunikation von Rechnern werden Daten oder Nachrichten ausgetauscht. Diese erhalten nach einer Interpretation den Charakter einer Information. Daten haben eine Form und einen Träger. Als Träger kommen magnetisierte Schichten, Bildschirme, elektromagnetische Felder, Schallfelder, Drähte etc. in Frage; die Form der Daten wird in der Regel in einer Sprache definiert. Sprachen bestehen aus Sätzen, diese aus Wörtern und letztere aus Zeichen aus einem Alphabet. Typische Beispiele sind die Umgangssprache, Ausdrücke aus Operatoren und ganzen Dezimalzahlen oder Programmiersprachen, wie man sie aus der Schule her kennt. Wir werden uns im Laufe der Vorlesung mit verschiedenen Sprachklassen auseinandersetzen. Sprachen genügen einer genau festgelegten textitSyntax. Nach deren Regeln kann entschieden werden, ob ein Satz zur Sprache gehört oder nicht. Die Interpretation der Wörter und Sätze einer Sprache ist im Allgemeinen durch Regeln ausdrückbar, die man Semantik der Sprache nennt. Den Übergang von einer Sprache zu einer anderen bei gleichbleibender Interpretation nennt man Übersetzung. Ein Code ist die Zuordnung zwischen Zeichen und Zeichengruppen von zwei verschiedenen oder auch gleichen Alphabeten. Geschieht diese Zuordnung zeichenweise, so spricht man auch von Chiffrierung.

Zum Problemlösen werden oft Algorithmen entwickelt und eingesetzt. Das Wort Algorithmus kommt vom Namen des persischen Mathematikers Mohammed Ibn Musa Abu Djafar Al Khowarizmi (ca. 783 - 850), der ein weit verbreitetes Lehrbuch für die ,,Berechnung durch Vergleich und Reduktion'', das bereits Lösungen von Gleichungen mit mehreren Unbekannten behandelt, geschrieben hat. In der lateinischen Übersetzung dieses Buchs, das durch die Kreuzfahrer nach Europa kam, begannen die Abschnitte jeweils mit ''Dixit algorismi'', woraus sich die Bezeichnung Algorismus für eine Rechenvorschrift ableitete.

Ein Algorithmus ist eine endliche Anweisungsfolge in einer Befehlssprache, die bei Interpretation eine Klasse von Verarbeitungsprozessen genau und vollständig beschreibt. Er enthält Operationen auf Variablen aus wohldefinierten Wertebereichen (Datentypen). Gewisse Operationen sind standardisiert und haben eine Standardinterpretation, wie zum Beispiel die Addition von Zahlen. Man kann für die Beschreibung von Algorithmen verschiedene Abstraktionsebenen wählen, eine umgangssprachliche, eine eher formale im Wortschatz eingeschränkte Sprache (Pseudocode), die typische Befehlselemente wie Zuweisungen, wiederholte oder bedingte Anweisungen enthält oder eine ''formale Programmiersprache'', deren Syntax in Regeln genau beschrieben und die von einem Interpreter am Rechner ausgeführt werden kann.

Diese Sprachen und ihre Paradigmen werden wir im Laufe der Vorlesung noch genauer betrachten. Beispiele werden jedoch schon jetzt aufgeführt. Vor der Entwicklung eines Algorithmus ist zunächst das Problem durch eine funktionale Spezifikation zu beschreiben. Dabei geht es um die Angabe der gültigen Eingabe- und möglichen Ausgabegrößen sowie den funktionalen Zusammenhang zwischen beiden. Es werden die problemspezifischen Objekte beschrieben, Konstanten, Datentypen, Funktionen, und dabei insbesondere Prädikate, das sind Funktionen, deren Ausgabewerte ''wahr'' und ''falsch'' sind. Die Eingaben genügen gewissen Vorbedingungen; bei der Ausgabe werden gewisse Leistungen des Algorithmus zugesichert. Im Allgemeinen ist der Ablauf des Algorithmus in jedem Punkt fest vorgeschrieben (Determiniertheit), jeder Schritt ist ausführbar (Effektivität) und das Verfahren endet nach endlich vielen Schritten (Terminiertheit). Es gibt allerdings Probleme, die nicht algorithmisierbar sind. Selbst wenn ein Problem algorithmisierbar ist, dann kann doch die Ausführung des Algorithmus so viele Schritte enthalten, dass die Berechnung praktisch nicht ausführbar ist (Nichteffizienz). Wichtig ist auch, dass der Algorithmus auf einer (abstrakten) Maschine ausgeführt werden kann. Diese nimmt alle oben genannten Schritte vor. Maschinen sind in verschiedenen Ausformungen in Automatenmodellen definiert worden. Die einfachste ist der endliche Automat, der bei der Abarbeitung einer Folge von Eingabezeichen eines Wortes aus einem Startzustand über Zwischenzustände in einen Endzustand übergeht. Wörter aus mächtigeren Sprachen können mit der Turingmaschine abgearbeitet werden, deren Schreiblesekopf über einem unendlichenArbeitsband frei beweglich ist. Diese Maschine ist auch Grundlage für moderne Computer, und man kann auf ihr alle bekannten zahlentheoretischen Algorithmen, wie den euklidischen, den GGT- oder einen Faktorisierungsalgorithmus ausführen.

Bis aber der Algorithmus eine Form hat, in der er auf dieser Maschine ausgeführt werden kann, sind viele Transformationen in Form von Zerlegungen und Übersetzungen erforderlich. Aus diesen Vorbetrachtungen ergeben sich die für das Grundstudium der Informatik wichtigen Inhalte:

2 Teilgebiete der Informatik

3 Rechnerentwicklung

Im Folgenden geben wir einen kurzen Überblick über die Entwicklung der Rechner: Zwischen 1623 und 1818 entstanden die ersten mechanischen Rechenmaschinen, z.B. die Schickardsche Rechenuhr, die Additionsmaschine von Blaise Pascal und eine Staffelwalzenmaschine von Leibniz, die das Zweiersystem benutzt. Daher kann man mit Fug und Recht behaupten, dass die Entwicklung von Rechnern zunächst dadurch motiviert war, die Ausführung von Rechnungen in den vier Grundrechenarten +, -, *, / zu unterstützen. Aber mit der Entwicklung eines automatischen Webstuhls von Jacquard um 1800, der mittels Lochkarten gesteuert wurde, kam bereits ein anderer Aspekt neben dem Rechnen hinzu, nämlich der des Automaten, bei dem eine gewisse Abfolge von Zuständen gesteuert durchlaufen wird.

**Figure 1.1:** Pascalsche Addiermaschine
$\includegraphics[%% width=0.75\textwidth, keepaspectratio]{pascal.eps}$

1833 plante Babbage den ersten programmgesteuerten Rechner, der eine Ein- und Ausgabeeinheit, eine arithmetisch- logische Einheit (ALU) zur Ausführung von Rechnungen und logischen Operationen, wie Vergleich von Zahlen, und eine Befehlseinheit zur Steuerung der Maschine vorsieht. Die zur Rechnung und Steuerung nötigen Daten werden von einem Datenträger in einen Speicher eingelesen und im Takt bearbeitet. Das Ergebnis wird sodann an einer Ausgabeeinheit angezeigt. Moderne Eingabegeräte sind Tastatur, Maus, Graphiktablett, Scanner, Ausgabegeräte dagegen Monitor, Drucker oder eine Datei.

**Figure 1.2:** Babaggerechner
$\includegraphics[%% width=0.30\textheight]{babbage.eps}$

Gebaut wurden die ersten programmgesteuerten Rechner von Zuse (1934/41) als lochstreifengesteuerte Maschine mit 2000 Relais und 64 Speichern, von Aiken 1944 in Zusammenarbeit mit IBM als Großrechenanlage MARK II mit 15 m Front und 2.5 m Höhe, bestehend aus 80 km Leitungsdraht, 700 000 Einzelteilen mit 3.5 t Gewicht. Hier kommt bereits ein anderer Aspekt ins Spiel, nämlich der Einsatz eines Rechners zu anderen Aufgaben außerhalb des Rechnens, beispielsweise zur Übernahme von Büroarbeiten und Lösung von Anwendungsproblemen, wie es schon Hollerith 1886 mit einer Lochkartenmaschine zum Einsatz bei einer Volkszählung vorgegeben hatte. In der Folgezeit setzt eine stürmische Entwicklung über die Einführung von Elektronenröhren in der ENIAC, Transistoren, Mikroschaltelementen, hoch- und höchstintegrierten Schaltkreisen ein, die in der Einführung von Mikrochips gipfelt. Während der Zuserechner die Multiplikation zweier 10stelligen Zahlen in ca. 3 sec ausführt, ist die ENIAC schon tausendmal schneller. Ein moderner Prozessor ist mit über 100 MHz getaktet, also mit über 100 Millionen Zyklen pro Sekunde. Viele Befehle werden in einem Zyklus ausgeführt. Eine Addition benötigt 3 Takte, eine Multiplikation zweier 32 Bit Zahlen 5, eine Division 18 bis 38 Takte und das Wurzelziehen 29 bis 69 Takte.

Beim INTEL P6 sind auf einer Fläche von wenigen Hundert Quadratmillimetern 20 Millionen und mehr Transistoren auf vier Ebenen platziert, die zwischen 5 und 20 Watt Leistung aufnehmen, in fünf Pipelines Befehle parallel abarbeiten können und in der Herstellung unter 500 DM kosten. Diese Chips kommen neben Spezialchips zur Organisation des Datentransfers oder von Ein- und Ausgabe insbesondere auf graphischen Terminals in modernen Personalcomputern zum Einsatz.

Parallel zur technologischen Entwicklung verläuft eine Entwicklung der Software, deren Bedeutung immer mehr zunimmt. Die nachfolgend genannten Generationen verlaufen nicht aufbauend aufeinander, sondern überlappen sich.

Diese summarische Darstellung wollen wir etwas weiter vertiefen: Jeder Prozessor besitzt eine durch seine Bauart festgelegte Programmiersprache, die er lesen und unmittelbar in Steuersignale umsetzen kann. Man bezeichnet sie als Maschinensprache. Programme in Maschinensprache werden meist in einer leichter lesbaren mnemotechnischen Notation beschrieben, der Assemblersprache. Befehle, wie das Sprachkürzel LD heißen laden, ADD addieren, ST speichern. Leider ist, obwohl schnell ausführbare Programme entstehen, die Programmierung in Assembler aufwändig, unübersichtlich und extrem maschinenabhängig. Assemblerprogramme werden daher heute nur noch für spezielle systemspezifische Programme eingesetzt, oder wenn es auf höchste Effizienz ankommt. Für alle anderen Anwendungen wird das Programmieren durch den Einsatz problemorientierter Sprachen wesentlich erleichtert.

**Figure 1.3:** Prozessor P6
$\includegraphics[%% width=0.75\textwidth]{P6.eps}$

1 Problemorientierte Programmiersprachen

Gegenüber den Assemblersprachen sind die problemorientierten Programmiersprachen nicht an einen bestimmten Rechnertyp gebunden. Problemorientierte Sprachen verwenden in weitem Maße gebräuchliche mathematische oder sonstige anwendungsorientierte Schreibweisen und erlauben eine leicht verständliche, dem Problem angepasste Formulierung von Algorithmen. Sie lassen sich deshalb besonders leicht erlernen. Programme in einer problemorientierten Sprache können ohne Rücksicht auf einen speziellen Rechnertyp formuliert werden, sie lassen sich (zumindest im Prinzip) leicht auf andere Rechner übertragen. Zur Programmierung mathematischer, naturwissenschaftlicher und technischer Probleme haben u.ä. folgende problemorientierte Sprachen zumindest zeitweise eine gewisse Verbreitung gefunden:

Ada
Ada wurde im Rahmen eines Wettbewerbs des amerikanischen Verteidigungsministeriums in den Jahren 1977 - 1980 entwickelt. Es soll durch seine universelle Einsetzbarkeit sowohl im kommerziellen als auch im technisch wissenschaftlichen Bereich dazu dienen, Wartungskosten für Software möglichst gering zu halten. Dadurch wurde Ada extrem umfangreich: neben den Konzepten von Pascal umfasst es u.Ä. die Definition von Modulen, Paketen (zusammenhängende Daten und Operationen), generischen Unterprogrammen (mit unterschiedlichen Typen) und Prozessen (für die Parallelverarbeitung).

ALGOL 60 (ALGOrithmic Language)
Die Sprache wurde in Europa gemeinsam von vielen wissenschaftlichen Institutionen aus sechs Ländern entwickelt und 1960 publiziert. Sie hat heute keine praktische Bedeutung mehr. Viele Konzepte der strukturierten Programmierung wurden aber von Algol in moderne Programmiersprachen übernommen.

BASIC (Beginners All-purpose Symbolic Instruction Code)
Ein vereinfachtes, FORTRAN-ähnliches Programmiersystem, besonders auf Kleinrechnern verbreitet. Die Entwicklung ging 1960 von J. Kemmeny und Th. Kurtz mit einem interpretierenden System aus, bei dem Linie für Linie des Programmes ausgeführt wurde, und hat heute zu Pascal-ähnlichen Programmiersystemen geführt, bei dem ein ausführbares Maschinenprogramm mittels eines Compilers erstellt wird.

COBOL (COmmon Business Orientated Language)
Die Sprache wurde Ende der 50er Jahre entwickelt und ist in der kaufmännischen Datenverarbeitung bis heute weit verbreitet.

C, C++
C wurde Ende der 70er Jahre gemeinsam mit dem Betriebssystem UNIX für Minicomputer entwickelt und hat sich seither auf Workstations, Personal-Computer und Großrechner ausgebreitet. Es stellt in mancher Hinsicht einen Kompromiss zwischen strukturierter Hochsprache und effizienter Maschinensprache dar. C-Programme neigen daher oft dazu, schwer lesbar zu sein. Da C inzwischen sehr weit verbreitet und standardisiert ist, eignet es sich gut zur Übertragung von Programmen auf unterschiedliche Rechner. Als objektorientierte Erweiterung von C setzt sich C++ seit 1986 immer weiter durch.

FORTRAN (FORmula TRANslation)
Fortran wurde 1954 als erste problemorientierte Programmiersprache von J. W. Backus entworfen, bei IBM implementiert und von internationalen Gremien in mehreren Versionen weiterentwickelt. Der aktuelle Sprachstandard Fortran 90 hat viele strukturierte Konzepte von Pascal übernommen.

Java
Java ist der Sprache C++ ähnlich und objektorientiert. Es wurde Anfang der neunziger Jahre von Sun entwickelt und beschreitet einen Mittelweg zwischen interpretierenden und compilierenden Sprachen. Ein Java-Compiler übersetzt ein in Java geschriebenes Programm in Code für eine virtuelle Java-Maschine, die wiederum auf allen Rechnerplattformen emuliert werden kann. Zusätzlich unterstützt es Sicherheitskonzepte für das Internet, kann in Internet-Seiten einbezogen werden und ist somit Netzwerk-geeignet.

Pascal
Pascal wurde von Kathleen Jensen und Niklaus Wirth (ETH Zürich) Anfang der 70er Jahre auf der Basis von Algol und ähnlichen Sprachen (z.B. Simula) entwickelt. Es umfasst ein erweitertes Typ-, Ausdrucks- und Anweisungskonzept, wurde aber ansonsten bewusst einfach gehalten. Pascal ist international standardisiert. Später werden die Dialekte Pascal-XSC (portabel, Erweiterungen für das wissenschaftliche Rechnen) und Turbo Pascal (Erweiterungen u.ä. für Grafik, systemnahe Programmierung, objektorientierte Konzepte) besprochen. Die Sprache ist nach dem französischen Mathematiker, Philosoph und Theologen Blaise Pascal benannt (1623 - 1662), der u.ä.\,eine der ersten mechanischen Rechenmaschinen konstruierte. Er leistete Beiträge zu zahlreichen mathematischen Gebieten (Geometrie der Kegelschnitte, Wahrscheinlichkeitsrechnung, Kombinatorik, Binomialkoeffizienten /Pascal'sches Dreieck, Prinzip der vollständigen Induktion, Ansätze zur Infinitesimalrechnung).

Modula-2
Modula-2 wurde 1978 als Weiterentwicklung der Sprache Pascal von Niklaus Wirth entworfen. Einige Sprachelemente von Pascal wurden überarbeitet und dabei zum Teil systematischer, zum Teil komplizierter. Ein Modulkonzept erlaubt die Entwicklung großer Programmpakete. Standardmodule ermöglichen z.B. systemnahe Programme und die Programmierung von Prozessen.

Oberon
Oberon wurde von N. Wirth und M. Reiser seit 1985 als Weiterentwicklung von Pascal und Modula 2 entworfen. Es stellt ein kleines Betriebssystem für PC und Workstation dar mit integrierter pascalartiger objektorientierter Programmiersprache und ist sehr sparsam im Umgang von Rechnerressourcen. Wie man an den Jahreszahlen erkennen kann, dauert es oft Jahre oder Jahrzehnte, bis sich eine neue Programmiersprache etabliert hat. Bestehende Sprachen werden immer wieder überarbeitet und aktualisiert.

In der Ausbildung ist Pascal nach wie vor hervorragend geeignet, da es die Entwicklung leistungsfähiger Programme erlaubt, also genügend universell ist, zum strukturierten Programmentwurf erzieht (im Gegensatz zu BASIC, C und Fortran) und trotzdem nicht allzu komplex ist (im Gegensatz etwa zu Fortran 90 oder Ada).

Neben den genannten gibt es eine Vielzahl weiterer Programmiersprachen, z.B. die bei Expertensystemen weitverbreitete Sprachen PROLOG und LISP, zur Prozesssteuerung die Sprache PERL. In einer prädikativen Programmiersprache wird Programmieren als Beweisen in einem System von Tatsachen und Schlussfolgerungen aufgefasst. Der Anwender gibt eine Menge von gültigen Prädikaten und Regeln zum Gewinnen neuer Fakten vor, und die Aufgabe des Rechners ist es, eine gestellte Frage mit ''Richtig'' oder ''Falsch'' zu beantworten. Funktionale Programmiersprachen verstehen Programme als Funktionen, die Mengen von Eingabewerten in Mengen von Ausgabewerten abbilden. Dabei ist eine Grundmenge von wichtigen einfachen Funktionen vorgegeben.

Im zweiten Teil dieser Veranstaltung werden wir uns mit der imperativen Programmiersprache Pascal, der prädikativen Sprache PROLOG und der funktionalen Sprache Miranda beschäftigen.

Eine Sprache muss durchaus nicht immer zum Erstellen von Programmen dienen, sondern kann wie dBASE auch zur Verwaltung einer Datenbank, TEX zur Gestaltung eines Textes, VHDL zum Beschreiben und Produzieren von elektronischen Schaltungen auf Chips oder HTML zur Gestaltung von WWW-Dokumenten dienen.

4 Grundlagen der Logik

1 Geschichtlicher Überblick

Der Wunsch, logisches Schließen zu automatisieren oder Apparate zu konstruieren, die so ähnlich wie der Mensch denken können, geht auf R. Descartes und G.W. Leibniz im siebzehnten Jahrhundert zurück. Descartes Entdeckung, dass die klassische Euklidische Geometrie allein mit algebraischen Methoden entwickelt werden kann, war für die Entwicklung von Deduktionssystemen bedeutsam. Leibniz Idee war die Entwicklung einer universellen formalen Sprache, die lingua characteristica, in der jegliche Wahrheit formuliert werden könne, und dazu eines Kalküls, dem sogenannten calculus rationator, für diese Sprache. Damit wollte er natürlichsprachige Beschreibungen auch über Sachverhalte, die nicht aus der Zahlentheorie kommen, in eine formale Sprache und einen dazugehörigen Kalkül übersetzbar machen. Seiner Vorstellung nach müsse ein solcher Kalkül mechanisierbar sein und auf diese Weise dem menschlichen Denken alle langweilige Arbeit ersparbar sein.

Moderne Logik entstand 1879 unter Gottlob Frege, insbesondere mit der Schaffung seiner Begriffsschrift. Diese enthält die erste vollständige Entwicklung desjenigen Anteils der mathematischen Logik, der heute als Prädikatenlogik erster Stufe bezeichnet wird. Durch den Gebrauch Boolescher Operatoren und die Verwendung von Quantoren, Relationen und Funktionen wurde der ganze Aufbau der Logik das erste Mal beschrieben. Als Herleitungsregel verwendete er den Modus Ponens. Zudem wurden Syntax und Semantik einer formalen Sprache das erste Mal entwickelt. Skolem beschrieb in Arbeiten von 1920 und 1928 eine systematische Vorgehensweise, wie man die Erfüllbarkeit einer beliebigen Formelmenge nachweisen kann. Ebenfalls im Jahre 1928 erschien das Buch Grundzüge der theoretischen Logik von D. Hilbert und W. Ackermann. Hier wird auch das Entscheidbarkeitsproblem eingeführt, bei dem es um die Frage geht, ob es einen Algorithmus gibt, mit dem entschieden werden kann, ob eine beliebige vorgegebene prädikatenlogische Aussage wahr oder falsch ist. Herbrand bewies in seiner Doktorarbeit 1930 den Satz, dass für einen korrekten mathematischen Satz dies mit endlich vielen Schritten nachgewiesen werden kann. Gelingt dies nicht, so gibt es zwei Möglichkeiten, entweder kann die Inkorrektheit nach endlich vielen Schritten bewiesen werden, oder das Programm terminiert nicht, und man weiß es nicht. Später zeigten Alan Turing und Alonzo Church, dass es keine allgemeine Entscheidungsprozedur dafür gibt, ob eine Aussage der Prädikatenlogik wahr ist oder nicht. Turing gelang 1936 der Beweis durch Rückführung auf das Halteproblem. Um 1950 wurde die Entwicklung des Computers vorangetrieben, und es entstand das erste Programm zur Überprüfung von Aussagen. Um 1954 veröffentlichte Robinson Ergebnisse zur Prüfung von Theoremen in Klauselform mit dem Resolutionsprinzip. In den folgenden Jahren entwickelte er diese Ideen weiter und veröffentlichte 1965 die Arbeit A machine oriented logic based on the resolution principle. Kowalski stellte dann schließlich mit seinem SLD-System einen Weg dar, der mittels Hornklauseln Wissen speichert und deklarativ wie prozedural Verwendung findet. Schließlich entwickelte Alan Colmerauer 1972 ein Logik-Programmiersystem PROLOG, das Grundlage für die Programmierung in Logik ist.

2 Aussagenlogik

Logik ist die Lehre von der Folgerichtigkeit des Denkens und Schließens. Mathematische Logik ist ein formales System, in dem gewissen Aussagen und Theoremen Wahrheitswerte zugeordnet werden können. Die einfachste Form der mathematischen Logik ist die Aussagenlogik.

Unter einer Aussage oder atomaren Formel, abgekürzt mit einem Großbuchstaben ( $A, B,\ldots$ ) versteht man einen Satz, der entweder wahr oder falsch ist, z.B. ''Heute ist Dienstag''. Man wird ihm mittels einer Interpretation einen Wahrheitswert zuordnen, wahr (

) oder falsch (

). Dieser Wert kann in einem Bit mit 1 bzw. 0 gespeichert werden. Die Menge der Wahrheitswerte wird mit $\mathcal{B}$ abgekürzt. Aussagen können miteinander verknüpft werden, und das Ergebnis dieser ''Operation'' ist wieder eine Aussage mit einem wohldefinierten Wahrheitswert. Als Negation erklärt man eine einstellige Operation $\lnot$ $\left(\overline{\phantom{x}}\right)$ , die jeder Aussage das Negat mit dem entgegengesetzten Wahrheitswert zuordnet. Atomare Formeln (Aussagenvariablen) oder deren Negate heißen Literale $L\in\left\{ A,\lnot A\right\}$ .

Nunmehr erklären wir wichtige zweistellige Operationen. Die Konjunktion mit dem Konjungator $\wedge$ (und, and) ordnet zwei Aussagen ihr Konjugat zu. Dabei hängt die Bedeutung der Junktoren nicht von den beteiligten Aussagen, sondern nur von ihren Wahrheitswerten ab. Es ergibt sich die folgende Tabelle:

Die Disjunktion mit dem Disjungator $\vee$ (oder, or) ordnet zwei Aussagen ihr Disjungat zu. Dabei ergibt sich die erste der folgenden Tabellen:

Neue Formeln

können über einen induktiven Prozess aus (atomaren) Formeln mit Hilfe der Operatoren $\lnot$ , $\vee$ , $\wedge$ gebildet werden.

Die Subjunktion mit dem Subjungator $\rightarrow$ (wenn - dann) ordnet zwei Aussagen ihr Subjungat zu. Auch hier haben wir die Tabelle notiert, aus der wir entnehmen, dass $f\rightarrow w$ bzw. $f\rightarrow f$ eine wahre Aussage ist, da aus einer falschen Aussage der Wahrheitswert der zweiten Aussage nicht geprüft werden kann.

Die Bijunktion mit dem Bijungator $\longleftrightarrow$ (genau dann - wenn) ordnet zwei Aussagen ihr Bijungat, die Antivalenz mit dem Junktor $\oplus$ bzw. $\not\!\!\!\longleftrightarrow$ (entweder - oder, xor) ordnet zwei Aussagen die Summe ihrer Wahrheitswerte modulo zwei zu.

Für die Junktoren gilt die folgenden Bindungshierarchie: $\lnot$ bindet stärker als $\wedge$ , dieses stärker als $\vee$ , $\vee$ stärker als $\rightarrow$ , $\rightarrow$ stärker als $\longleftrightarrow$ .

Wir wollen nun einige im Laufe der Vorlesung vorkommende Begriffe kurz einführen:
Eine Klausel ist eine Disjunktion von Literalen. Eine Hornklausel enthält höchstens ein positives Literal, eine Hornformel besteht nur aus Hornklauseln, die durch Konjunktion miteinander verknüpft werden, wie zum Beispiel

Sie liegt in disjunktiver Form (DF) vor, wenn sie die Disjunktion mehrerer durch Konjungatoren verknüpften Literale ist:

Aussagenvariablen werden mit den Werten aus der Menge der Wahrheitswerte belegt. Sie sind Platzhalter für Aussagen. Aus den Wahrheitswerten, den Aussagen, Aussagenvariablen und den Verknüpfungsoperatoren kann man zulässige aussagenlogische Ausdrücke bilden. Auch auf diese können wieder Operationen angewandt werden.

Jeder Formel kann für eine Belegung ein Wahrheitswert zugeordnet werden. Eine Interpretation, unter der die Formel wahr ist, heißt Modell. Eine Formel heißt erfüllbar, wenn es mindestens ein Modell gibt, ansonsten unerfüllbar. Eine Formel

heißt Tautologie, wenn sie für alle Belegungen wahr ist. Wir schreiben dann $\vDash F$ . (Es ist allgemein wahr, wie z.B. $A\vee\lnot A$ ). Die Allgemeingültigkeit kann mit Hilfe einer Wahrheitstafel, durch Anwendung von syntaktischen Umformungen bis zum Wahrheitswert

oder durch Zurückführung auf eine konjunktive Form bewiesen werden, in der in jeder Klausel mit mindestens einer Aussagenvariablen auch deren Negat vorkommt.

Beispiel 4.2
Zu zeigen ist $\vDash\left(\left(P\rightarrow Q\right)\wedge P\right)\rightarrow Q$ .

a)

$\begin{displaymath}\begin{array}{l\vert l\vert c\vert c\vert c} P & Q & P\righta... ... & f & w\\ w & f & f & f & w\\ w & w & w & w & w\end{array}\end{displaymath}$

b)

Äquivalent sind die folgenden Formeln

$\begin{displaymath} \begin{array}{l} \left(\left(P\rightarrow Q\right)\wedge P\r... ...ot P\vee\lnot Q\right)\vee Q\\ \lnot P\vee w\\ w\end{array}\end{displaymath}$

c)

Überführung in konjunktive Form

$\begin{displaymath} \begin{array}{l} \left(\left(P\rightarrow Q\right)\wedge P\r... ...t)\wedge\left(\lnot Q\vee Q\vee\lnot P\right)\right)\end{array}\end{displaymath}$

Zwei Formeln

und

heißen äquivalent $\equiv$ , wenn sie für alle passenden Belegungen den gleichen Wahrheitswert haben: $\vDash G\longleftrightarrow F$ . Für jede Formel

gibt es eine äquivalente Formel in KF oder DF. Es gelten folgende Äquivalenzen:

Tabelle 4.3

$\begin{displaymath} \begin{array}{rclr} \left(F\wedge F\right) & \equiv & F,\hsp... ...e G\equiv F, & \text{falls }F \textrm{{Tautologie}}\end{array}\end{displaymath}$

Ist

eine Menge von Formeln oder Prämissen $\left\{ F_{1},\ldots,F_{k}\right\}$ und

eine Formel, so ist

eine logische Konsequenz von

, in Zeichen $S\vDash F$ , wenn jede Belegung von

, die ein Modell von

ist, auch ein Modell von

ist. Dies kann auch in der Form

Eine Theorie definiert zunächst eine Menge von wahren logischen Aussagen und Fakten, die Axiome. Dabei spielen die Begriffe Korrektheit, Vollständigkeit und Entscheidbarkeit eine Rolle. Sie besteht aus einer Sprache, mit deren Hilfe gewisse Sätze ausgedrückt werden können. Axiome stellen dabei die Grundsätze der Theorie dar. Aus der Menge der Axiome können neue, kompliziertere Sätze als logische Konsequenz abgeleitet werden. Dies geschieht über die oben angegebenen Interferenzregeln, wie den Modus Ponens und den Modus Tollens oder auch die Transitivitätsregel.

Für eine Theorie sollte ein korrektes (semantisch widerspruchsfreies) und vollständiges Axiomensystem zur Verfügung stehen. Ein Axiomensystem

ist korrekt, wenn jede Formel

, die aus einer Theorie

mittels der Ableitungsregeln abgeleitet wird $\left(T\vdash_{AS}F\right)$ , eine logische Konsequenz aus

ist $\left(T\vDash F\right)$ . Ein Axiomensystem

ist vollständig, wenn für jede Theorie

jede Formel, die aus der Theorie logisch folgt, auch ableitbar ist (das ist die Umkehrung).
Ist ein derartiges Axiomensystem vorhanden, so heißt es Basis der Theorie. Ein Axiomensystem darf auch nicht inkonsistent sein, d.h. es darf nicht gleichzeitig

und $\lnot F$ herleitbar sein. Ferner sollten die Axiome voneinander unabhängig sein, also nicht eines aus den anderen folgen. Eine Theorie heißt unentscheidbar, wenn es eine Formel

gibt, für die gilt, dass weder die Formel selbst noch ihre Negation aus der Theorie ableitbar ist. Der Begriff der Entscheidbarkeit kann auf Axiomensysteme als Basis einer Theorie übertragen werden. Ein Axiomensystem ist entscheidbar, wenn sich immer prüfen lässt, ob eine Theorie in AS konsistent ist oder nicht, wenn sich also von jedem Satz herleiten lässt, ob er allgemeingültig ist oder nicht. Aussagenlogik ist entscheidbar und besitzt widerspruchsfreie, vollständige und unabhängige Axiomensysteme. Ein Axiomensystem AS ist halbentscheidbar, wenn es immer möglich ist, die Inkonsistenz zu prüfen.

Aus den logischen Axiomen der Aussagenlogik (Hilbert)
AS1: $A\vee A\rightarrow A$ ,
AS2: $A\rightarrow\left(A\vee B\right)$ ,
AS3: $\left(A\vee B\right)\rightarrow\left(B\vee A\right)$ ,
AS4: $\left(A\rightarrow B\right)\rightarrow\left(\left(C\vee A\right)\rightarrow\left(C\vee B\right)\right)$ ,
der Definition $A\rightarrow B\equiv\lnot A\vee B$ , der Schlussregel (Modus Ponens) und der Ersetzungsregel

Beispiel 4.6

Wir leiten $\left(F\vee F\right)\equiv F$ bzw. $\vDash F\vee F\longleftrightarrow F$ mit Hilfe der oben angegebenen Mittel her. Dies ist äquivalent zu

$\displaystyle \vDash\left(\left(F\vee F\rightarrow F\right)\wedge\left(F\rightarrow F\vee F\right)\right)$ mit $\displaystyle A\wedge B:=\lnot\left(\lnot A\vee\lnot B\right).$

Wir zeigen somit die Allgemeingültigkeit von $\left(F\vee F\rightarrow F\right)$ und von $\left(F\rightarrow F\vee F\right)$ :

$\left(F\vee F\right)$

$\rightarrow$

AS1 .

Bemerkung:
Im vorigen Beispiel haben wir die Junktoren $\wedge$ und $\longleftrightarrow$ mit Hilfe der Junktoren $\lnot$ und $\vee$ definiert.

Die Grundresolution ist eine eingeschränkte Form der Methode von Robinson, mit deren Hilfe eine vorgegebene endliche Menge von Klauseln auf ihre Unerfüllbarkeit hin getestet werden kann.

Durch geeignete Operationen zum Vereinfachen von veroderten Formeln lassen sich die Darstellungen verkürzen: Kommt in einer Klausel eine Variable

und in einer anderen die Negation $\neg P$ vor, so lassen sich diese Klauseln unter Weglassung dieser Variablen zu einer Klausel zusammenfassen:

Dann lässt sich das Verfahren folgendermaßen beschreiben:
Es sei die Aussage

zu beweisen.
Setze das negierte Theorem $\lnot A$ zu den Formeln der Theorie, wandele sie in Klauselform um (KF) und versuche, durch Resolution die leere Klausel herzuleiten. In diesem Fall ist das Theorem

zur Theorie gehörig.

Beispiel 4.7
$T = \left\{ A \vee B, \; A \rightarrow \lnot B, \; \lnot A \right\}$ . Leite

her. Wir formen in KF um:

$\displaystyle T = \left\{ A \vee B, \; \lnot A \vee \lnot B, \; \lnot A \right\},$

oder in der Schreibweise als Klauselmenge

$\displaystyle T = \left\{ \left( A, \; B \right), \; \left( \lnot A, \; \lnot B \right), \; \lnot A \right\},$

und untersuchen die Klauselmenge

$\displaystyle \left\{ \left( A, \; B \right), \; \left( \lnot A, \; \lnot B \right), \; \lnot A, \; \lnot B \right\}$

auf Unerfüllbarkeit:

ist ein Resolvent von $\left( A, B \right)$ und $\lnot A$ . Der Resolvent von

und $\lnot B$ ist aber die leere Menge, und damit enthält die Klauselmenge die leere Menge und ist unerfüllbar. Somit ist

bewiesen.

3 Prädikatenlogik

Die gebräuchlichste Form der mathematischen Logik ist die Prädikatenlogik als Erweiterung der Aussagenlogik. Sie dient zur Formulierung von Axiomen, zum Beweis von Eigenschaften von Sätzen und Programmen. Sie bedient sich einer Menge von Objekten, Relationen und Funktionen. Wie in der Aussagenlogik werden Formeln (Symbolisierung einer sprachlichen Aussage, syntaktisches Gebilde aus Symbolen) mit Hilfe von logischen Verbindungen aus Atomen (elementaren logischen Aussagen) und anderen Formeln gebildet. Sie sind nach präzisen Regeln einer Grammatik aufgebaut. Als Atome (logisch unzerlegbarer Ausdruck, Zeichenfolgen aus Prädikaten und Operatoren, gebildet aus dem Alphabet als Menge der zugelassenen Symbole, Konstanten

, Variablen

, Prädikate

, Funktions- und Hilfszeichen

, $\rightarrow$ , $\ldots$ ) sind jedoch nicht nur Literale (Aussagenvariablen und deren Negation) sondern auch Prädikate (Eigenschaften von Objekten, $P(a_{1},\ldots,a_{n})$ ) mit Argumenttermen erlaubt. Terme sind Konstanten, Variablen oder Funktionssymbole. Prädikatenlogik erlaubt damit viel reichere Aussagen als die Aussagenlogik.

Im Allgemeinen erklären Prädikate Teilmengen von bekannten Obermengen, wie zum Beispiel die Prädikate Primzahl oder gerade Zahl in der Menge der natürlichen Zahlen. Die Mengenoperationen $\cup$ , $\cap$ , $\subset$ , Komplement korrespondieren mit den Verknüpfungen des Aussagenkalküls $\vee$ , $\wedge$ , $\rightarrow$ , $\lnot$ .

wird formalisiert zu $Px\rightarrow Qy$ . Wichtig sind auch die Quantoren: der Existenzquantor $\left(\vee,\exists\right)$ , der Allquantor $\left(\wedge,\forall\right)$ . Der Existenzquantor erlaubt, die Existenz eines Objektes mit gewissen Eigenschaften anzunehmen, ohne es selbst zu definieren. Der Allquantor erstreckt eine Eigenschaft auf alle Objekte. Variablen werden im gemeinsamen Auftreten von Quantoren gebunden, können aber auch frei in Formeln auftreten. Die Semantik der Prädikatenlogik gibt den nach den syntaktischen Regeln geschaffenen Formeln einen Wahrheitsgehalt in einer Domäne als geschaffener Welt. Durch Interpretation wird eine Beziehung zwischen dem Alphabet der Sprache und der Domäne hergestellt. Konstanten entsprechen Objekten, Prädikaten Relationen und Funktionssymbolen Funktionen. Variablen müssen Werte zugeordnet werden.

Beispiel 4.8
Gegeben sei die Formel

$\displaystyle F: \forall x P (f(x, a), x).$

Die betrachtete Domäne sei die der natürlichen Zahlen $\mathbb{N}:= \left\{ 1, 2, 3, \ldots \right\}$ . Der Konstanten

ordnen wir die Zahl

zu. Unter der Funktion

verstehen wir die Multiplikation $x \cdot a$ . Das zweistellige Prädikat

sei als die Eigenschaft Gleichheit definiert. Damit lautet die Interpretation der Formel:

Für alle natürlichen Zahlen $x \in \mathbb{N}$ gilt $x \cdot 1 = x$ .

Ist eine Formel in einer Interpretation wahr, so ist diese Interpretation ein Modell der Formel. Eine Formel ist erfüllbar, wenn es für sie ein Modell gibt, allgemeingültig, wenn alle Interpretationen wahr sind. Auch hier wenden wir die Definition der logischen Konsequenz einer Formel

aus einer Formelmenge

an: Wenn jede Interpretation und Belegung, die ein Modell von

ist, auch ein solches von

ist, so gilt $S\vDash F$ .

Zu unseren bekannten Schlussregeln der Aussagenlogik gesellen sich weitere Schlussregeln:

Tabelle 4.9

$\displaystyle \forall x F$	$\displaystyle \vDash$	$\displaystyle \exists x F$ für eine nichtleere Domäne
$\displaystyle \forall x F \vee \forall x G$	$\displaystyle \vDash$	$\displaystyle \forall x (F \vee G)$
$\displaystyle \exists x (F \wedge G)$	$\displaystyle \vDash$	$\displaystyle \exists x F \wedge \exists x G$

Tabelle 4.10

$\displaystyle \lnot \forall x F$	$\displaystyle \equiv$	$\displaystyle \exists x \lnot F$
$\displaystyle \lnot \exists x F$	$\displaystyle \equiv$	$\displaystyle \forall x \lnot F$
$\displaystyle \forall x \forall y F$	$\displaystyle \equiv$	$\displaystyle \forall y \forall x F$
$\displaystyle \exists x \exists y F$	$\displaystyle \equiv$	$\displaystyle \exists y \exists x F$
$\displaystyle \forall x (F \wedge G)$	$\displaystyle \equiv$	$\displaystyle \forall x F \wedge \forall x G$
$\displaystyle \exists x (F \vee G)$	$\displaystyle \equiv$	$\displaystyle \exists x F \vee \exists x G$

Auch in der Prädikatenlogik können der Zeichenvorrat und syntaktische Regeln zur Ableitung von prädikatenlogischen Ausdrücken definiert werden. Auf Hilbert geht ein Axiomensystem mit sechs Axiomen zurück. Sodann sind die Ableitungsregeln zu definieren. Leider stellt es sich heraus, dass das Erfüllbarkeits- und das Allgemeingültigkeitsproblem für prädikatenlogische Formeln unentscheidbar ist. Die Wahrheitstafelmethode kann nicht übertragen werden. Immerhin können die Formeln in eine Normalform überführt werden, die sogenannte Skolemform, und ein Algorithmus angegeben werden, der bei unerfüllbaren Formeln nach endlicher Zeit mit der Ausgabe ''unerfüllbar'' stoppt.

Wir wollen nun die Peano-Axiome zur Begründung der natürlichen Zahlen und ihrer Arithmetik kennenlernen.

Axiome 4.11 (Peano-Axiome)

1.

ist eine natürliche Zahl:

Hier benötigen wir das einstellige Prädikat

ist eine natürliche Zahl.

2.

Zu jeder natürlichen Zahl gibt es eine natürliche Zahl als deren Nachfolger:

$\displaystyle \forall x \left( Px \rightarrow \exists y \left( Py \wedge Qxy \right) \right).$

Dazu definieren wir das zweistellige Prädikat

: Die natürliche Zahl

hat die natürliche Zahl

zum Nachfolger.

3.

Die Zahl 1 ist Nachfolger keiner natürlichen Zahl: $\lnot \exists x \left( Px \wedge Qx1 \right)$ .

4.

Verschiedene natürliche Zahlen haben auch verschiedene Nachfolger:

$\displaystyle \forall x_{1} \forall x_{2} \forall y_{1} \forall y_{2} \left( Px... ...y_{2} \wedge \lnot (x_{1} = x_{2}) \rightarrow \lnot (y_{1} = y_{2}) \right).$

5.

Jede Teilmenge

aus den natürlichen Zahlen, die die

und mit jedem Element auch deren Nachfolger enthält, ist mit der Menge $\mathbb{N}$ der natürlichen Zahlen identisch (vollständige Induktion):

$\displaystyle \forall M \left( M1 \wedge \forall x \forall y \left( Px \wedge P... ...ge Mx \wedge Qxy \rightarrow My \right) \rightarrow (M = \mathbb{N}) \right).$

Dazu führt man die Prädikatenvariable

ein sowie das Prädikat

ist Element von

. Ferner findet die Konstante $\mathbb{N}$ Verwendung.

Hier ist zu bemerken, dass über die Prädikatenvariable quantisiert wurde. Damit sprechen wir von der Prädikatenlogik höherer Stufe. In der ersten Stufe sind nur Quantifizierungen über Objektvariablen erlaubt.

Die Prädikatenlogik ist auch Basis einer Programmiersprache, nämlich Prolog. Dabei spielen die Hornklauseln eine wesentliche Rolle. Sie werden in der Form

Das Resolutionsverfahren erlaubt ähnlich wie in der Aussagenlogik das mechanische Beweisen von Aussagen der Prädikatenlogik, die in Klauselform vorliegen. Ein Programm besteht aus einer endlichen Menge von Klauseln. Das angewandte Schema gliedert sich in die folgenden Schritte:

Ordne Klauseln so an, dass die nicht negierten Literale links, die negierten rechts stehen. Taucht in zwei Klauseln dasselbe Literal auf entgegengesetzten Seiten auf, kann daraus eine neue Klausel gebildet werden, indem man die beiden Klauseln unter Fortlassung der entgegengesetzten Literale zu einer neuen addiert. Treffen zwei je einelementige Klauseln so aufeinander, so entsteht die leere Klausel, die Widerspruchsklausel, und das Verfahren terminiert. Somit lässt sich zwar keine Klausel ableiten, jedoch ein Widerspruchsbeweis führen, indem man das Gegenteil der Annahme als Klausel hinzufügt.

SLD-Resolution ist nur für Hornklauseln definiert und spielt eine entscheidende Rolle bei der Logikprogrammierung und insbesondere bei Prolog-Programmen. Sei

Diese Form der Resolution ist vollständig für die Klasse der Hornformeln, d.h. für jede unerfüllbare Klauselmenge

gibt es eine Klausel $K\in F$ , so dass die leere Klausel durch diese lineare SLD-Resolution aus

basierend auf

hergeleitet werden kann.

4 Literatur

Uwe Schöning: Logik für Informatiker. 4. Auflage. Spektrum-Verlag, Mannheim 2000.

2 Schaltfunktionen

1 Zahldarstellung

Bei den in der Theoretischen Informatik behandelten Maschinenmodellen, wie z.B. endlicher Automat oder Turingmaschine, wird stets von zu verarbeitenden Worten über einem Alphabet

ausgegangen, die eine variable Länge haben, die auch nicht durch eine Maximallänge beschränkt sind.

Bei realen Rechnern ist dies nicht sinnvoll, da hier mit einer festen Wortlänge gearbeitet wird. Wir haben somit im Folgenden stets die generelle Voraussetzung, dass zum Alphabet

noch eine feste Konstante

hinzukommt, die die Wortlänge angibt.

Wichtige Zahlensysteme und Alphabete sind die

-adischen Zahlensysteme, die für eine natürliche Zahl

auf dem Alphabet $E_{b}=\{0,1,\dots,b-1\}$ basieren.

Beispiel 1.1

Wichtige -adische Zahlensysteme sind die folgenden:

a)

Dezimalsystem mit $E_{10} = \{0, 1, 2, \ldots, 9 \}$ , in dem wir im Allgemeinen rechnen. Eine feste Wortlänge erreichen wir hierbei, indem wir ggf. durch führende Nullen auffüllen. So ist z.B. bei einer Wortlänge als darzustellen.

b)

Dual- oder Binärsystem mit $E_2 = \{0, 1\}$ , welches im Computer zum Einsatz kommt.
Oktalsystem mit $E_8 = \{0, 1, \ldots, 7\}$ .
Hexadezimalsystem mit $E_{16} = \{0, 1, \ldots, 9, A, B, C, D, E, F\}$ . Hierbei ist $E_{16}$ eigentlich das Alphabet $\{0, 1, \ldots, 9, 10, \ldots, 15 \}$ , anstelle von Ziffern $10, 11, \ldots$ werden aber generell bei Alphabeten mit

neue, einstellige Symbole eingeführt. Gerade diese Zweierpotenzbasen haben in der Informatik eine besondere Bedeutung.

Satz 1.2 (b-adische Darstellung von Fixpunktzahlen)

Sei $b \in \mathbb{N}$ mit . Dann ist jede Fixpunktzahl (mit Vorkomma- und Nachkommastellen) mit $0 \leq z \cdot b^k \leq b^{n+k} - 1$ (und $n\in \mathbb{N}$ , $k \in \mathbb{N}_0$ ) eindeutig als Wort der Länge über darstellbar durch

$\displaystyle z = \sum_{i=-k}^{n-1} z_i b^i, \hspace{0.5em}z_i \in \{ 0, 1, \ldots b-1 \}.$

Abkürzend wird geschrieben als $z = (z_{n-1}z_{n-2} \ldots z_0.z_{-1}z_{-2} \ldots z_{-k})_b$ . Eine Einheit der letzten Stelle, also des Faktors von $b^{-k}$ , wird als 1 ulp (unit last place) bezeichnet, und gibt eine Genauigkeitsschranke des Fixpunktsystems an. Für gilt obige Darstellung insbesondere für die natürlichen Zahlen $\{0, 1, \ldots, b^{n} - 1 \}$ .

Aufgrund von physikalischen Gegebenheiten (Spannung = 0V, oder Spannung

0V bzw. Schwellwert) ist im Rechner das System für

sinnvoll. Häufig werden jedoch auch hier zur Darstellung Systeme mit

oder

verwendet, da hiermit kürzere und lesbarere Darstellungen erzielt werden. Auch arbeiten moderne Prozessoren in der Regel nicht auf Bitebene, sondern auf Wortebene, wobei hier Wortlängen von

oder

anzutreffen sind.

Für natürliche Zahlen ist auch eine we9itere Zahldarstellung möglich, die polyadische Darstellung.

Satz 1.3 (Polyadische Darstellung natürlicher Zahlen)

Es sei

$\displaystyle (b_{n})_{n\in\mathbb{N}}$

eine Folge natürlicher Zahlen mit

$\displaystyle b_{n}>1$

für alle

$\displaystyle n\in\mathbb{N}$

. Dann gibt es für jede natürliche Zahl

genau eine Darstellung der Form
$z=(z_{N}\ldots z_{0})_{PD}=\sum_{i=0}^{N}z_{i}\prod_{j=0}^{i-1}b_{j}=z_{0}+z_{1}b_{0}+z_{2}b_{1}b_{0}+\ldots+z_{N}b_{N-1}\ldots b_{0}$

mit $0\leq z_{i}<b_{i}$ für $i=0,\ldots,N$ .

1 Komplementdarstellungen

Eine weitere wichtige Zahldarstellung beim Rechnereinsatz ist die Zweierkomplementdarstellung von Fixpunktzahlen, über die eine Darstellung negativer Zahlen möglich ist. Das Zweierkomplement und andere Komplementdarstellungen sind wie folgt definiert:

Definition 1.4 (Komplementdarstellungen für n+k Fixpunktzahlen)

Sei $x=(x_{n-1}\ldots x_{0}.x_{-1}\ldots x_{-k})_{2}$ eine Dualzahl in Fixpunktdarstellung.

a)

Das Einerkomplement $K_{1}(x)$ ist definiert als

$\displaystyle K_{1}(x)=(\overline{x}_{n-1}\overline{x}_{n-2}\ldots\overline{x}_{0}.\overline{x}_{-1}\ldots\overline{x}_{-k})_{2}$

wobei $x_{i}=0\leftrightarrow\overline{x}_{i}=1$ , und $\overline{\overline{x}} _{i}=x_{i}$ .

b)

Das Zweierkomplement $K_{2}(x)$ ist definiert als

$\displaystyle K_{2}(x)=(\overline{x}_{n-1}\overline{x}_{n-2}\ldots\overline{x}_{0}.\overline{x}_{-1}\ldots\overline{x}_{-k})_{2}+1\; ulp=K_{1}(x)+1\; ulp$ (modulo $\displaystyle 2^{n})$

Das Einerkomplement erhält man also durch Invertieren aller Bits, das Zweierkomplement durch anschließendes Addieren von einer Einheit zur letzten Stelle. Da hier ggf. ein Überlauf auftreten kann (Bitmuster nur mit Einsen), ist modulo $2^{n}$ zu rechnen. Analog zum Einer- und Zweikomplement lässt sich zu jeder beliebigen Basis

das

- und

-Komplement definieren als:

Definition 1.5 (b-Komplement für n+k Fixpunktzahlen)
Sei $x=(x_{n-1}\ldots x_{0}.x_{-1}\ldots x_{-k})_{b}\in\{0,1,\ldots,b-1\}^{n+k}$ eine

Fixpunktdarstellung zur Basis

a)

Das

-Komplement $K_{b-1}(x)$ ist definiert als

$\displaystyle K_{b-1}(x)$	$\displaystyle =$	$\displaystyle (\tilde{x}_{n-1}\tilde{x}_{n-2}\ldots\tilde{x}_{0}.\tilde{x}_{-1}\ldots\tilde{x}_{-k})_{b},$
$\displaystyle \tilde{x}_{i}$	$\displaystyle :=$	$\displaystyle (b-1)-x_{i},\hspace{0.5em}i=-k,\ldots,n-1.$

b)

Das

-Komplement $K_{b}(x)$ ist definiert als

$\displaystyle K_{b}(x)=(\tilde{x}_{n-1}\tilde{x}_{n-2}\ldots\tilde{x}_{0}.\tilde{x}_{-1}\ldots\tilde{x}_{-k})_{b}+1\; ulp$

Für die Darstellung von ganzen Zahlen werden im Rechner im Allgemeinen Zweierkomplementdarstellungen (mit

) verwendet. Bei Komplementdarstellungen ist aber zu beachten, dass diese generell bzgl. einer festen Wortlänge gebildet werden. Mit der Komplementdarstellung kann man nun negative Zahlen nach folgender Idee darstellen. Gehen wir von einer Registerlänge von

Bit aus, so gibt es $N=2^{n}$ verschiedene Bitmuster.

Zur Ausführung einer Subtraktion der Form

ist im Zweierkomplement lediglich $K_{2}(y)$ zu bestimmen und zu

zu addieren. Ein eventuell auftretender Übertrag wird ignoriert. Ist das höchstwertige Bit des Ergebnisses wieder gesetzt, so handelt es sich um einen negativen Wert, der ebenfalls im Zweierkomplement dargestellt ist.

2 Darstellung von Gleitpunktzahlen nach IEEE 754/854

Zum Abschluss des ersten Abschnittes wollen wir noch kurz auf die Darstellung ,,reeller`` Zahlen in Form einer Gleitkommadarstellung zur Basis

eingehen, wie sie im Standard IEEE 754/854 festgelegt ist. Eine Gleitkommazahl besteht dabei aus einem Vorzeichen

Bit zur Darstellung des Exponenten und

Bit zur Darstellung der Mantisse. Die Mantisse ist dabei bei normalisierten Zahlen, die im Allgemeinen verwendet werden, so dargestellt, dass diese eine führende 1 vor dem Dezimalpunkt besitzt, die dann in der Regel nicht kodiert wird. Wir erhalten somit die folgende Darstellung für eine Gleitkommazahl:

$\begin{displaymath}\begin{array}{rl} \textrm{Exponentencharakteristik:} & E=(e_{... ...tisse:}} & M=(f_{m-1}f_{m-2}\ldots\ldots f_{1}f_{0})\end{array}\end{displaymath}$

$\begin{displaymath}\begin{array}{lll} {\textrm{Dargestellte Zahl:}}\\ (-1)^{S}... ...} & E=2\cdot E_{Bias}+1, M\neq0 & \hbox{NotaNumber}\end{array}\end{displaymath}$

Die Konstanten

und

bestimmen die Genauigkeit, der Summand $E_{Bias}$ dient zur Verschiebung des Exponentenwertes, um auch negative Exponenten zu erhalten. Dadurch ist es nicht erforderlich, den Exponenten in Zweierkomplementdarstellung zu schreiben, was einen Vergleich von Exponenten erleichtert.

Die im IEEE Standard festgelegten Genauigkeiten ,,single`` und ,,double`` haben folgende Parameter:

Beispiel 1.8
Die Darstellung der Zahl

ergibt sich also in normalisierter Darstellung wie folgt:
single

$\displaystyle 1.0 = 1.0 * 2^0 = 1.0 * 2^{127-127}$	$\displaystyle \hat=$	$\displaystyle 0 \overbrace{01111111}^{\textrm{Exponent}} \overbrace{00000000000000000000000}^{\textrm{Mantisse}}$
	$\displaystyle =$	$\displaystyle \texttt{\$3F800000}$

double

$\displaystyle 1.0 = 1.0 * 2^0 = 1.0 * 2^{1023-1023}$	$\displaystyle \hat=$	$\displaystyle 0 \overbrace{01111111111}^{\textrm{Exponent}} \underbrace{\overbrace{00000...............00000}^{\textrm{Mantisse}}}_{\textrm{52 Nullen}}$
	$\displaystyle =$	$\displaystyle \texttt{\$3FF0000000000000}$

Bei dieser Zahl sieht man, dass die Mantisse identisch Null sein kann, ohne dass die Zahl selbst Null ist. Will man eine beliebige Zahl normalisiert darstellen, so transformiert man sie erst in den Bereich

durch Division durch eine geeignete Zweierpotenz und verfährt wie unten gezeigt:

$\displaystyle 6.5$	$\displaystyle =$	$\displaystyle 2^2 \cdot 1.625$
	$\displaystyle =$	$\displaystyle 2^2 \cdot \left( 1 + \frac{1}{2} + \frac{0}{2^2} + \frac{1}{2^3} \right)$
	$\displaystyle =$	$\displaystyle 2^{129 - 127} \cdot \left( 1 + \frac{1}{2} + \frac{0}{2^2} + \frac{1}{2^3} \right)$
	$\displaystyle =$	$\displaystyle 2^{129 - 127} \cdot \left( 1.101 \right)_2$
	$\displaystyle \hat=$	$\displaystyle 0 10000001 10100000000000000000000$
	$\displaystyle =$	$\displaystyle \texttt{\$40D00000}.$

2 Boolesche Algebra

Von den angegebenen Beispielen

-adischer Zahlsysteme ist der Fall

aus der Sicht der Schaltungstechnik ausgezeichnet. Diesen Fall kann man leicht als ,,wahr - falsch`` bzw. ,,Strom - kein Strom`` interpretieren. Wir wollen daher das Alphabet $E_{2}=\{0,1\}$ mit

bezeichnen, in Erinnerung an den Mathematiker George Boole, der sich mit den folgenden Strukturen aus mathematischer Sicht beschäftigt hat.

BEWEISIDEE: Da

hier nur zwei Elemente besitzt, kann der Beweis über Wertetafeln erfolgen. Für die Regel c) erhält man dabei exemplarisch:

Im Folgenden wollen wir die Verknüpfungen der Booleschen Algebra wie folgt identifizieren: Maximum $\cup$ mit der Addition

(logisch OR) und Minimum $\cap$ mit der Multiplikation $\cdot$ (logisch AND).

Bemerkung:
Die Potenzmenge ${\mathcal{P}}(A)$ einer Menge

, d.h. die Menge aller Teilmengen von

, ist mit den Mengenoperationen $\cup$ , $\cap$ und $\overline{\phantom{x}}={\mathcal{C}}=$ Komplement,

$\displaystyle F_{1}$	$\displaystyle =$	$\displaystyle \left(A\vee B\vee\lnot C\right)\wedge\left(\lnot B\vee C\right)\textrm{ KF}$
$\displaystyle F_{2}$	$\displaystyle =$	$\displaystyle \left(A\wedge B\wedge\lnot C\right)\vee\left(\lnot B\wedge C\right) \textrm{DF}.$

$\displaystyle x\cup y$	$\displaystyle :=$	Max $\displaystyle (x,y),$
$\displaystyle x\cap y$	$\displaystyle :=$	Min $\displaystyle (x,y),$
$\displaystyle \overline{x}$	$\displaystyle :=$	$\displaystyle 1-x,$

Argumente			linke Seite	rechte Seite
x	y	$x\cup y$	$\left(x\cup y\right)\cap x$	x
0	0	0	0	0
0	1	1	0	0
1	0	1	1	1
1	1	1	1	1