Search

Industrielle Tatigkeiten und Produktionsprozesse haben in den letzten hundert Jahren mitunter zu weitreichenden und im Einzelfall gravierenden Belastungen der Umweltmedien Boden, Wasser und Luft gefuhrt. Altstandorte der Industrie, auf denen in der Vergangenheit mit wasser- bzw. umweltgefahrdenden Stoffen umgegangen worden ist, oder Altablagerungen, wie z. B. ungesicherte Deponien, sind nicht selten fur die Freisetzung okotoxischer Substanzen verantwortlich. Verschiedenste Schadigungen der belebten Umwelt waren bzw. sind die Folge, die als Verschlechterung der Umweltqualitat und als Folge der Anreicherung von Toxinen in der Nahrungskette uber die jeweiligen Wirkungspfade Boden – Gewasser – Luft – Pflanze – Tier – Mensch in gesundheitlichen Beeintrachtigungen der biotischen Welt zum Ausdruck kommen konnen.

Ziel dieses Kapitels ist: I.Syntaktische Definition von Sprachen der Pradikatenlogik erster Stufe, in denen Objekte (Individuen) durch Terme und Aussagen uber sie durch Ausdrucke (Formeln) dargestellt werden, sowie eine mathematisch prazise Definition der inhaltlichen Bedeutung (Semantik) solcher Terme und Formeln und insbesondere des Begriffs logischer Wahrheit (Allgemeingultigkeit) der letzteren; II.Nachweis der rekursiven Aufzahlbarkeit des logischen Gultigkeitsbegriffs durch Angabe eines Kalkuls, mit dessen Hilfe alle und nur die logisch gultigen Formeln rein syntaktisch herleitbar sind.

Dieses Kapitel ist Anwendungen von in Kap. A-C vorgestellten Techniken und komplexitatstheoretischen Ergebnissen auf den Pradikatenkalkul gewidmet. Kern sind logische Beschreibungen der Wirkung von (Register-, Turing- u.a.) Programmen, aus der in gleicher Weise die rekursive Unlosbarkeit des Hilbertschen Entscheidungsproblems wie rekursive untere Komplexitatsschranken (sog. Schwerentscheidbarkeitssatze) fur entscheidbare Teilprobleme als auch der Godelsche Unvollstandigkeitssatz folgen.

Wir behandeln in diesem Kapitel die syntaktische Charakterisierung der klassischen Pradikatenlogik der ersten Stufe in der Form, wie sie Gentzen 1935 in seiner logischen Analyse derjenigen Schlusweisen gegeben hat, die das tatsachliche Vorgehen bei mathematischen Beweisfuhrungen beherrschen. Der Grundgedanke besteht darin, die Bedeutung logischer Symbole wie Junktoren und Quantoren durch Regeln festzulegen, die unmittelbar deren Gebrauch beim Ziehen von Folgerungen aus gegebenen Voraussetzungen beschreiben.

Ziel dieses Kapitels ist: I. Der Nachweis der algorithmischen Unlosbarkeit einiger scheinbar einfacher, eng mit dem Begriff von Algorithmus zusammenhangender Probleme sowie (als anspruchsvolleres Beispiel) der Frage nach der ganzzahligen Losbarkeit von Gleichungen zwischen Polynomen mit ganzzahligen Koeffizienten; II. Eine Untersuchung der Rolle logischer Ausdurcksmittel zur Bestimmung der (relativen) algorithmischen Komplexitat rekursiv unlosbarer Probleme und damit zusammenhangend verschieden starker Begriffe effektiver Reduktion von Problemen aufeinander; III. Die Analyse eines maschinenunabhangigen Komplexitatsbegriffs, der die algorithmische Kompliziertheit von Problemen durch Bewertung des zur Durchfuhrung von Losungsalgorithmen benotigten Rechenaufwands mist.

Erfahrung im Umgang mit Computern zeigt, das die dem vorhergehenden Kapitel B zugrundeliegende Klassifikation von Problemen in entscheidbare und unentscheidbare zu grob ist: viele entscheidbare Probleme sind auf Grund zu groser Zeit- oder Speicherplatzanforderungen fur die Durchfuhrung von Losungsverfahren durch Computer praktisch nicht losbar.