Autor: Guts A.K.
Verlag: O.: Heritage
Erscheinungsjahr: 2003
Seiten: 108
ISBN 5-8239-0126-7
Lesen:
Herunterladen: matematicheskayalogika2003.djvu

ABTEILUNG DER FAKULTÄT FÜR INFORMATIONSWISSENSCHAFTEN DER STAATLICHEN UNIVERSITÄT OMSK
KYBERNETIK
A.K. Innereien
Mathematische Logik und Theorie der Algorithmen
Omsk 2003
VVK 60 UDC 53:630.11
Guts AK Mathematische Logik und Theorie der Algorithmen: Lehrbuch. -
Omsk: Heritage Publishing. Dialog-Sibirien, 2003. - 108 p.
ISBN 5-8239-0126-7
Das Lehrbuch widmet sich der Darstellung der Grundlagen der mathematischen Logik und Theorie
Algorithmen. Grundlage des Handbuchs sind die Abstracts gelesener Vorlesungen
Studenten des zweiten Jahres der Informatikabteilung von Omsk
Staatliche Universität 2002.
Für Studierende der Fachrichtung 075200 - "Computer
Sicherheit" und Fachgebiet 220100 - "Computer,
Komplexe, Systeme und Netzwerke".
ISBN 5-8239-0126-7
(c) Staatliche Universität Omsk, 2003
Inhaltsverzeichnis
Ich Logik 7
1 Klassische Logik 8
1.1. Satzlogik .................................................. 8
1.1.1. Sprüche................................ 8
1.1.2. Grundgesetze der Logik .................................... 9
1.1.3. Russells logisches Paradoxon ......... 10
1.1.4. Algebra (Logik) von Sätzen ......... 11
1.1.5. Leiterdiagramme .................................... 12
1.1.6. Äquivalente Formeln .......................... 14
1.1.7. Boolesche Algebra................................ 15
1.1.8. Wahre und gültige Formeln .......... 15
1.1.9. Das Problem der Lösbarkeit .................... 15
1.1.10. Logische Konsequenz................................. 16
1.1.11. Syllogismen .................................... 17
1.2. Prädikatenlogik .................................... 17
1.2.1. Prädikate und Formeln ......... 18
1.2.2. Interpretationen................................ 19
1.2.3. Wahrheit und Erfüllbarkeit von Formeln. Modelle,
Gültigkeit, logische Konsequenz........ 20
1.2.4. Gottlob Frege....................... 21
1.2.5. Skolem-Funktionen
und Skolemisierung von Formeln....................... 22
1.3. Auflösungsverfahren................................ 25
1.3.1. Lösungsverfahren in der Logik
Äußerungen................................ 25
1.3.2. Lösungsverfahren in der Logik
Prädikate................................ 29
3
4
Inhaltsverzeichnis
2 Formale Theorien (Kalkül) 31
2.1. Definition der formalen Theorie oder Kalkül. . 32
2.1.1. Nachweisen. Konsistenz der Theorie.
Vollständigkeit der Theorie................................ 32
2.2. Aussagenkalkül................................. 33
2.2.1. Sprache und Regeln für die Inferenz des Aussagenkalküls
............................................. 33
2.2.2. Ein Beispiel für den Beweis des Satzes................. 35
2.2.3. Vollständigkeit und Konsistenz
Aussagenkalkül .......................... 36
2.3. Prädikatenkalkül................................ 37
2.3.1. Sprache und Schlußregeln des Prädikatenkalküls 37
2.3.2. Vollständigkeit und Konsistenz
Prädikatenkalkül................................ 39
2.4. Formale Arithmetik................................ 39
2.4.1. Egalitäre Theorien................................ 39
2.4.2. Sprache und Regeln zur Ableitung der formalen Arithmetik
.............................................. 39
2.4.3. Konsistenz des Formalen
Arithmetik. Satz von Gentzen................. 40
2.4.4. Gödels Unvollständigkeitssatz................................................. 41
2.4.5. Kurt Gödel................... 42
2.5. Automatische Theoremableitung ................................ 43
2.5.1. S.Yu. Maslow................................ 43
2.6. Logikprogrammierung................................ 45
2.6.1. Logikprogramm ......................... 46
2.6.2. Logik-Programmiersprachen.... 49
3 Nicht-klassische Logiken 50
3.1. Intuitionistische Logik................................ 50
3.2. Fuzzy-Logik .................................... 51
3.2.1. Fuzzy-Teilmengen ................................ 51
3.2.2. Operationen auf Fuzzy
Teilmengen................................ 52
3.2.3. Eigenschaften der Menge von Fuzzy
Teilmengen................................ 53
3.2.4. Fuzzy-Aussagenlogik....................... 54
3.2.5. Fuzzy-Ladder-Diagramme .......... 56
3.3. Modallogik................................................ 56
3.3.1. Arten von Modalitäten .......................... 57
Inhaltsverzeichnis
5
3.3.2. Kalkül 1 und T (Feis-von Wright) ........ 57
3.3.3. Kalkül S4, S5
und Brouwer-Kalkül................................ 58
3.3.4. Formelbewertung ................................ 59
3.3.5. Semantik von Kripke ................................ 60
3.3.6. Andere Interpretationen von Modalen
Zeichen ................................... 62
3.4. Georg von Wright .................................... 62
3.5. Temporäre Logik .................................... 62
3.5.1. Pryors Timing-Logik................................. 63
3.5.2. Lemmons Timing-Logik................. 64
3.5.3. Von Wrights temporale Logik....................... 64
3.5.4. Anwendung von Timing-Logiken
zum Programmieren............................ 65
3.5.5. Pnueli Temporal Logic .................................. 67
3.6. Algorithmische Logik................................. 70
3.6.1. Konstruktionsprinzipien
1 >

Bundesamt für Bildung

TOMSK STATE UNIVERSITY OF CONTROL SYSTEMS AND FUNKELEKTRONIK (TUSUR)

Abteilung Automatisierung der Informationsverarbeitung

Ich bin damit einverstanden:

Kopf Cafe AOI

Professor

Jep. Echlakow

"__" _____________2007

Richtlinien

zur Durchführung der praktischen Arbeit am Fachgebiet

"Mathematische Logik und Theorie der Algorithmen"

für Studierende der Fachrichtung 230102 -

"Automatisierte Systeme zur Informationsverarbeitung und -kontrolle"

Entwickler:

Kunst. Dozent am Fachbereich AOI

DANN. Permitina

Tomsk - 2007

Praktische Lektion Nr. 1 "Formeln der Aussagenalgebra" 3

Praktische Lektion Nr. 2 "Äquivalente Transformationen von Formeln der Aussagenalgebra" 10

Praktische Lektion Nr. 3 "Normale Formelformen" 12

Praktische Lektion Nr. 4 "Logisches Denken" 14

Praktische Lektion Nr. 5 "Formeln der Prädikatenlogik" 18

Übung #6 Boolesche Funktionen 23

Übung #7 Teilweise rekursive Funktionen 28

Übung Nr. 8 Turing-Maschinen 34

Praktische Lektion Nr. 1 "Formeln der Aussagenalgebra"

Die Satzlehre - die Satzalgebra oder die Algebra der Logik - ist die einfachste logische Theorie. Der Atombegriff der Aussagenalgebra ist Erklärung - ein Aussagesatz, in Bezug auf den die Aussage über seine Wahrheit oder Falschheit Sinn macht.

Ein Beispiel für eine wahre Aussage: "Die Erde dreht sich um die Sonne." Ein Beispiel für eine falsche Aussage: „3 > 5“. Nicht jeder Satz ist eine Aussage; Aussagen enthalten keine Frage- und Ausrufesätze. Der Satz: „Porridge ist ein köstliches Gericht“ ist keine Aussage, da es keinen Konsens darüber geben kann, ob er wahr oder falsch ist. Der Satz „Es gibt Leben auf dem Mars“ ist als Aussage zu werten, da er objektiv entweder wahr oder falsch ist, obwohl noch niemand weiß, welcher.

Da Gegenstand des Studiums der Logik nur die Wahrheitswerte von Sätzen sind, werden für sie die Buchstabenbezeichnungen A, B, ... oder X, Y ... eingeführt.

Jede Aussage wird als wahr oder falsch betrachtet. Der Kürze halber schreiben wir anstelle des wahren Werts 1 und anstelle des falschen Werts 0. Zum Beispiel X= „Die Erde dreht sich um die Sonne“ und Y= „3 > 5“ und X=1 und Y= 0. Die Aussage kann nicht gleichzeitig wahr und falsch sein.

Anweisungen können einfach oder zusammengesetzt sein. Die Aussagen „die Erde dreht sich um die Sonne“ und „3 > 5“ sind einfach. Zusammengesetzte Aussagen werden aus einfachen mit Hilfe von natürlichen (russischen) Sprachkonnektiven NICHT, UND, ODER, WENN-DANN, DANN-UND-NUR-DANN gebildet. Bei Verwendung der alphabetischen Notation für Aussagen werden diese Konnektoren durch spezielle mathematische Symbole ersetzt, die als Symbole logischer Operationen betrachtet werden können.

Unten in Tabelle 1 gibt es Varianten von Symbolen zur Bezeichnung von Verknüpfungen und die Namen der entsprechenden logischen Operationen.

Verweigerung (Umkehrung) Aussagen X ist eine Aussage, die genau dann wahr ist, wenn X falsch (bezeichnet oder Auf ihr steht „nicht X“ oder „Das stimmt nicht X”).

Verbindung
von zwei Aussagen heißt eine Aussage, die genau dann wahr ist, wenn beide Aussagen wahr sind X und Y. Diese logische Operation entspricht der Verknüpfung von Aussagen mit der Vereinigung „und“.

Disjunktion
zwei Sätze X und Y Eine Aussage heißt genau dann falsch, wenn beide Aussagen X und Y FALSCH. In der Umgangssprache entspricht diese logische Operation der Vereinigung „oder“ (nicht exklusives „oder“).

Implikation zwei Sätze X und Y ist eine Aussage, die genau dann falsch ist, wenn X wahr, und Y- falsch (bezeichnet
; liest " X beinhaltet Y", "Wenn X, dann Y“). Die Operanden dieser Operation haben spezielle Namen: X- Paket, Y- Fazit.

Gleichwertigkeit zwei Sätze X und Y heißt eine Aussage, die genau dann wahr ist, wenn die Wahrheit einen Wert hat X und Y sind gleich (Zeichen:
).

Tabelle 1. Logische Operationen

Die Operanden logischer Operationen können nur zwei Werte annehmen: 1 oder 0. Daher kann jede logische Operation , &, , ,  einfach mithilfe einer Tabelle spezifiziert werden, die den Wert des Ergebnisses der Operation abhängig von den Werten angibt der Operanden. Eine solche Tabelle heißt Wahrheitstabelle (Tabelle 2).

Tabelle 2. Wahrheitstabelle logischer Operationen

Mit Hilfe der oben definierten logischen Operationen ist es möglich, aus einfachen Aussagen zu bauen Aussagenlogische Formeln verschiedene zusammengesetzte Anweisungen darstellen. Die logische Bedeutung einer zusammengesetzten Aussage hängt von der Struktur der Aussage ab, die durch die Formel ausgedrückt wird, und den logischen Werten der elementaren Aussagen, die sie bilden.

Für das systematische Studium von Formeln, die Aussagen ausdrücken, werden variable Aussagen eingeführt P, P 1 , P 2 , ..., P N, wobei Werte aus der Menge (0, 1) genommen werden.

Formel der Aussagenlogik F (P 1 , P 2 ,..., P N) heißt Tautologie bzw identisch wahr wenn sein Wert für alle Werte P 1 , P 2 ,..., P N ist 1 (wahr). Formeln, die für mindestens einen Satz von Variablenlisten als wahr ausgewertet werden, werden aufgerufen machbar . Es werden Formeln aufgerufen, die für beliebige Werte der Variablen den Wert „false“ annehmen Widersprüche (identisch falsch, unmöglich).

Das vorgeschlagene Lehrbuch (2. Aufl., Stereotyp) bildet die Grundlage eines Satzes für den Kurs der mathematischen Logik und der Theorie der Algorithmen, der auch eine Sammlung von Problemen enthält (Igoshin V.I. Aufgaben und Übungen in der mathematischen Logik und der Theorie der Algorithmen) .

Die Grundlagen der Theorie werden ausführlich beschrieben, die Richtungen des Eindringens der Logik in die Grundlagen der Algebra, Analysis, Geometrie werden gezeigt, das Material des Schulmathematikkurses wird für seine logische Analyse verwendet, die Beziehung der mathematischen Logik zu Computern, Informatik und Systeme der künstlichen Intelligenz ist gekennzeichnet.

Einführung. Mathematische Logik im System der modernen Bildung.
Logik und Intuition. Logik traditionelle und mathematische Logik. Ein bisschen Geschichte. Mathematische Logik - Logik oder Mathematik? Mathematische Logik im Mathematikunterricht. Mathematische Logik und moderne Computer.
Kapitel I. Algebra der Aussagen.
§ 1. Aussagen und Operationen auf ihnen.
Der Begriff der Äußerung. Verneinung der Aussage. Verbindung zweier Sätze. Disjunktion zweier Aussagen. Implikation von zwei Aussagen. Äquivalenz zweier Aussagen. Vereinigungen der Sprache und logische Operationen (Sprache und Logik). Gesamtansicht der logischen Operationen.
§2. Formeln der Aussagenalgebra.
Aufbau komplexer Sätze. Das Konzept einer Aussagenalgebra-Formel. Die logische Bedeutung einer zusammengesetzten Aussage. Zusammenstellung von Wahrheitstabellen für Formeln. Klassifizierung von Formeln der Aussagenalgebra. Denken und mathematische Logik
§ 3. Tautologien der Aussagenalgebra.
Zur Bedeutung von Tautologien. Grundlegende Tautologien. Grundregeln zum Erhalten einer Tautologie.
§ 4. Logische Äquivalenz von Formeln.
Das Konzept der Äquivalenz von Formeln. Äquivalenzzeichen von Formeln. Beispiele für äquivalente Formeln. Äquivalente Transformationen von Formeln. Äquivalenzen in der Logik und Identitäten in der Algebra.
§ 5. Normalformen für Formeln der Aussagenalgebra.
Der Begriff der Normalformen. Perfekte Normalformen. Darstellung von Formeln der Aussagenalgebra durch perfekte disjunktive Normalformen (CDN). Darstellung von Formeln der Aussagenalgebra durch perfekte konjunktive Normalformen (SKN). Zwei Möglichkeiten, eine Formel der Aussagenalgebra auf die perfekte Normalform zu reduzieren
§ 6. Logisches Folgen von Formeln.
Das Konzept einer logischen Konsequenz. Zeichen einer logischen Konsequenz. Zwei Eigenschaften von logischer Konsequenz. Folgen und Äquivalenz von Formeln. Regeln des logischen Denkens. Eine andere Möglichkeit, das logische Folgen zu überprüfen. Konsequenzen aus diesen Prämissen ziehen. Prämissen für diese Untersuchung finden.
§ 7. Anwendung der Aussagenalgebra auf die logisch-mathematische Praxis.
Direkte und inverse Sätze. Notwendige und hinreichende Bedingungen. Gegenteil und Umkehrung des Gegenteilsatzes. Das Gesetz der Gegenposition. Modifikation der Struktur des mathematischen Theorems. Methoden zum Beweis mathematischer Theoreme. Deduktives und induktives Denken. Richtiges und falsches deduktives Denken. Logische Probleme lösen. Das Prinzip der vollständigen Disjunktion. Eine Verallgemeinerung des Prinzips der vollständigen Disjunktion.
Kapitel II. Boolesche Funktionen.
§acht. Mengen, Relationen, Funktionen.
Das Konzept einer Menge. Inklusion und Gleichheit von Mengen. Operationen an Sets. Binäre Beziehungen und Funktionen. Das Konzept einer Lar-Beziehung.
§ 9. Boolesche Funktionen mit einem und zwei Argumenten.
Ursprung boolescher Funktionen. Boolesche Funktionen aus einem Argument. Boolesche Funktionen zweier Argumente. Eigenschaften von Disjunktion, Konjunktion und Negation. Eigenschaften von Äquivalenz, Implikation und Negation. Ausdrücken einiger boolescher Funktionen durch andere
§ 10. Boolesche Funktionen von n Argumenten.
Das Konzept einer Booleschen Funktion. Die Anzahl der booleschen Funktionen. Ausdruck boolescher Funktionen durch Konjunktion, Disjunktion und Negation. Boolesche Funktionen und Formeln der Aussagenalgebra. Normalformen boolescher Funktionen.
§ 11. Systeme Boolescher Funktionen.
Komplette Systeme boolescher Funktionen. Spezielle Klassen von booleschen Funktionen. Satz von Post über die Vollständigkeit eines Systems boolescher Funktionen
§ 12. Anwendung boolescher Funktionen auf Relaiskontaktschaltungen.
Anwendungsidee. Zwei Hauptaufgaben der Theorie der Relaiskontaktschaltungen.
§ 13. Relaiskontaktschaltungen in Computern.
Binärer Halbaddierer. Binärer Einzelbit-Addierer. Encoder und Decoder.
§ 14. Über einige andere Anwendungen der Theorie der Booleschen Funktionen.
Diagnose (Erkennung) von Krankheiten. Mustererkennung.
Kapitel III. Formalisierter Aussagenkalkül.
§ 15. Das Axiomensystem und die Theorie des formalen Schlusses.
Der Beginn der axiomatischen Aussagentheorie: Anfangsbegriffe, Axiomensystem, Schlußregel. Der Begriff der Inferenz und seine Eigenschaften. Der Deduktionssatz und seine Konsequenzen. Anwendung des Deduktionssatzes. Abgeleitete Inferenzregeln
§ 16. Vollständigkeit und andere Eigenschaften des formalisierten Aussagenkalküls
Beweisbarkeit einer Formel und ihrer identischen Wahrheit (Syntax und Semantik). Ableitungslemma. Vollständigkeit des formalisierten Aussagenkalküls. Das Angemessenheitstheorem. Konsistenz des formalisierten Aussagenkalküls. Entscheidbarkeit des formalisierten Aussagenkalküls
§ 17. Unabhängigkeit des Axiomensystems des formalisierten Aussagenkalküls.
Das Konzept der Unabhängigkeit. Unabhängigkeit des Axioms (A1). Unabhängigkeit des Axioms (A2). Axiom Unabhängigkeit (A3). Unabhängigkeit des Axiomensystems
Kapitel IV. Prädikatenlogik.
§ 18. Grundbegriffe der Prädikate.
Der Begriff eines Prädikats. Klassifizierung von Prädikaten. Die Wahrheitsmenge des Prädikats. Äquivalenz und folgende Prädikate
§ 19. Logische Operationen auf Prädikaten.
Prädikatsverneinung. Konjunktion zweier Prädikate. Design, um zur dicat-Seite zu gelangen. Eigenschaften von Negation, Konjunktion und Disjunktion. Implikation und Äquivalenz zweier Prädikate.
§ 20. Quantifiziereroperationen auf Prädikaten.
Allgemeiner Quantifizierer. Existenzquantifizierer. Numerische Quantifizierer. Begrenzte Quantifizierer. Logisches Quadrat
§ 21. Formeln der Prädikatenlogik.
Das Konzept einer prädikatenlogischen Formel. Klassifikation prädikatenlogischer Formeln. Tautologien der Prädikatenlogik
§ 22. Äquivalente Umformungen von Formeln und logische Folgerung von Formeln der Prädikatenlogik
Das Konzept der Äquivalenz von Formeln. Reduzierte Form für prädikatenlogische Formeln. Prenex-Normalform für prädikatenlogische Formeln. Logisches Folgen prädikatenlogischer Formeln
§ 23. Auflösungsprobleme für die Gültigkeit und Erfüllbarkeit von Formeln.
Darstellung des Problems und seiner Unlösbarkeit im Allgemeinen. Lösung des Problems für Formeln auf endlichen Mengen. Ein Beispiel für eine Formel, die auf einer unendlichen Menge zulässig und auf keiner endlichen Menge zulässig ist. Erfüllbarkeitsauflösungsproblem: Einfluss von Mengenkardinalität und Formelstruktur. Lösung des Problems für Formeln, die nur einstellige Prädikatvariablen enthalten. Das Problem der Lösung der Gültigkeit und Kardinalität der Menge, auf der die Formel betrachtet wird. Problemlösung für V-Formeln und 3-Formeln
§ 24. Anwendung der Prädikatenlogik auf die logisch-mathematische Praxis.
Aufzeichnung in der Sprache der logischen Prädikate verschiedener Sätze. Vergleich von Prädikatenlogik und Aussagenlogik. Die Struktur mathematischer Theoreme. Argumentationsmethoden: Aristotelische Syllogistik. Aristotelische Syllogistik und Prädikatenlogik. Mengentheoretische Interpretation der aristotelischen Syllogistik. Über andere Argumentationsmethoden. Das Prinzip der vollständigen Disjunktion in Prädikatenform. Methode der (vollständigen) mathematischen Induktion Notwendige und hinreichende Bedingungen. Prädikatenlogik und Mengenalgebra.
§ 25. Formalisierter Prädikatenkalkül.
Grundbegriffe (Sprache des formalisierten Prädikatenkalküls). Das Axiomensystem der Prädikatenrechnung. Widerrufsrecht. Theorie des formalen Schließens.
Kapitel V. Informelle axiomatische Theorien.
§ 26. Axiomatische Methode in der Mathematik und axiomatische Theorien.
Das Konzept der axiomatischen Theorie. Wie axiomatische Theorien entstehen. Beispiele für axiomatische Theorien. Interpretationen und Modelle der axiomatischen Theorie.
§ 27. Eigenschaften axiomatischer Theorien.
Konsistenz. Kategorisch. Unabhängigkeit des Axiomensystems. Vollständigkeit.
Kapitel VI. Formale axiomatische Theorien.
§ 28. Über formale axiomatische Theorien.
Zur Geschichte der Idee einer formalen axiomatischen Theorie. Das Konzept der formalen axiomatischen Theorie. Sprache und Metasprache, Theoreme und Metatheoreme der Formalen Theorie. Interpretationen und Modelle der formalen Theorie. semantische Ausgabe. Metamathematik (Eigenschaften formaler axiomatischer Theorien). Formalisierter Aussagenkalkül als formale axiomatische Theorie Formalisierung der Theorie der aristotelischen Syllogismen.
§ 29. Eigenschaften des formalisierten Prädikatenkalküls.
Begründung der Axiomatisierung Konsistenz des formalisierten Prädikatenkalküls. Gödels Theorem über die Existenz eines Modells. Vollständigkeit und Angemessenheit des formalisierten Prädikatenkalküls. Unvollständigkeit des formalisierten Prädikatenkalküls im absoluten und engen Sinn Kompaktheitssatz.
§ 30. Formale Theorien erster Ordnung.
Theorien erster Ordnung mit Gleichheit. Über formale Mengentheorien. Zur formalen Arithmetik. Zur formalen Theorie der Zahlensysteme Zur formalen Geometrie. Zur formalen mathematischen Analysis. Allgemeine Betrachtung des Formalisierungsprozesses der mathematischen Theorie, Über die Grenzen der axiomatischen Methode, der Formalisierungsmethode und der Logik.
Kapitel VII. Elemente der Theorie der Algorithmen.
§31. Intuitives Verständnis von Algorithmen.
Algorithmen um uns herum. Ein informeller Begriff eines Algorithmus. Die Notwendigkeit, das Konzept eines Algorithmus zu klären.
§ 32. Turingmaschinen.
Definition einer Turing-Maschine Anwendung von Turing-Maschinen auf Wörter. Konstruktion einer Turing-Maschine. Turing-berechenbare Funktionen. Korrekte Berechenbarkeit von Funktionen auf einer Turingmaschine. Aufbau von Turingmaschinen. Turings These (eine grundlegende Vermutung in der Theorie der Algorithmen). Turingmaschinen und moderne elektronische Computer.
§ 33. Rekursive Funktionen.
Ursprung rekursiver Funktionen. Grundbegriffe der Theorie rekursiver Funktionen und Churchs These. Primitive rekursive Funktionen. Primitive Rekursivität von Prädikaten. Turing Berechenbarkeit primitiver rekursiver Funktionen. Ackermann-Funktionen. Minimierungsoperator. Allgemeine rekursive und teilweise rekursive Funktionen. Turing Berechenbarkeit von teilweise rekursiven Funktionen. Partielle Rekursivität von Turing-berechenbaren Funktionen.
§34. Normale Markov-Algorithmen.
Markov-Ersetzungen. Normale Algorithmen und ihre Anwendung auf Wörter. Normal berechenbare Funktionen und das Markov-Normalisierungsprinzip. Koinzidenz der Klasse aller normal berechenbaren Funktionen mit der Klasse aller Turing-berechenbaren Funktionen. Äquivalenz verschiedener Theorien von Algorithmen.
§ 35. Entscheidbarkeit und Aufzählbarkeit von Mengen.
§ 36. Unlösbare algorithmische Probleme.
Algorithmus-Nummerierung. Turingmaschinennummerierung. Existenz nicht berechenbarer Turing-Funktionen. Probleme der Anerkennung von Selbstanwendbarkeit und Anwendbarkeit. Algorithmisch unlösbare Probleme in der allgemeinen Theorie der Algorithmen. Satz von Rice. Weitere Beispiele algorithmischer Unentscheidbarkeit.
§ 37. Satz von Gödel über die Unvollständigkeit der formalen Arithmetik.
Formale axiomatische Theorien und natürliche Zahlen. Formale Arithmetik und ihre Eigenschaften. Gödels Unvollständigkeitssatz. Gödel und seine Rolle in der mathematischen Logik des 20. Jahrhunderts. .
Kapitel VIII. Mathematische Logik und Computer, Informatik, künstliche Intelligenz.
* § 38. Mathematische Logik und Computersoftware.
Die Theorie der Algorithmen und der mathematischen Logik ist die grundlegende Grundlage der Programmierung. Beschreibung von Computerprogrammen, die mathematische Logik verwenden. Beschreibung der Programmierung und Analyse ihrer Konzepte unter Verwendung mathematischer Logik. Verifikation (Korrektheitsnachweis) von Programmen mittels mathematischer Logik.
§ 39. Anwendung von Computern zum Beweis von Sätzen der mathematischen Logik.
Das Programm "Logik-Theoretiker" und Programme in seiner Nähe. Resolutionsverfahren zum Beweis von Theoremen im Aussagenkalkül und Prädikatenkalkül.
§ 40. Von der mathematischen Logik zur logischen Programmierung.
Die Entstehung der PROLOG-Sprache und ihre Entwicklung. Allgemeine Eigenschaften der Sprache PROLOG. Kurze Beschreibung der PROLOG-Sprache und Beispiele. Anwendungsbereiche der Sprache PROLOG.
§41. Mathematische Logik und Informatik.
Allgemeines Konzept der Datenbank. Relationale Datenbank und Abfragelogik darin.
§ 42. Mathematische Logik und Systeme der künstlichen Intelligenz Entwicklungsgeschichte und Gegenstand der künstlichen Intelligenz als Wissenschaft. Repräsentation von Wissen in Systemen der künstlichen Intelligenz. Expertensysteme. PROLOG-Sprache in Systemen der künstlichen Intelligenz. Kann eine Maschine denken.
Fazit: Ist die Logik allmächtig im Wissen um die Gesetze des Denkens?
Referenzliste.

Logik und Intuition.
Menschliche geistige Aktivität ist ein komplexer und vielschichtiger Prozess, der sowohl auf der bewussten als auch auf der unbewussten (unterbewussten) Ebene stattfindet. Dies ist die höchste Stufe des menschlichen Wissens, die Fähigkeit, Objekte und Phänomene der Realität angemessen zu reflektieren, d.h. um die Wahrheit zu finden.

Logik und Intuition sind zwei gegensätzliche und untrennbar miteinander verbundene Eigenschaften des menschlichen Denkens. Logisches (deduktives) Denken unterscheidet sich dadurch, dass es immer zu einer wahren Schlussfolgerung aus wahren Prämissen führt, ohne sich auf Erfahrung, Intuition und andere externe Faktoren zu verlassen. Intuition (von lat. intuitio – „genau hinsehen“) ist die Fähigkeit, die Wahrheit durch direkte Beobachtung ohne Begründung mit Hilfe logisch strenger Beweise zu erfassen. Intuition ist also eine Art Antipode, ein Gegengewicht zu Logik und Strenge.

Der logische Teil des Denkprozesses findet auf der Ebene des Bewusstseins statt, der intuitive Teil - auf der unterbewussten Ebene.
Die Entwicklung der Naturwissenschaften und insbesondere der Mathematik ist ohne Intuition undenkbar. Es gibt zwei Arten von Intuition in der wissenschaftlichen Erkenntnis1: Intuition-Urteil und Intuition-Vermutung. Intuitionsurteil (oder philosophisches Intuitionsurteil) zeichnet sich dadurch aus, dass in diesem Fall die direkte Wahrnehmung der Wahrheit, der objektive Zusammenhang der Dinge nicht nur ohne logisch strengen Beweis erfolgt, sondern ein solcher Beweis für diese Wahrheit nicht existiert und kann grundsätzlich nicht bestehen. Intuitionsbeurteilung wird als ein einziger (einmaliger) synthetischer ganzheitlicher Akt verallgemeinernder Natur durchgeführt. Diese Natur logisch unbeweisbarer Aussagen haben die in der Theorie der Algorithmen betrachteten Thesen von Turing, Church und Markov.

Kostenloser E-Book-Download in einem praktischen Format, ansehen und lesen:
Laden Sie das Buch Mathematische Logik und Theorie der Algorithmen, Igoshin VI, 2008 – fileskachat.com, schnell und kostenlos herunter.

11.1. Das Konzept des Algorithmus und die Theorie der Algorithmen

Intuitiv versteht man unter einem Algorithmus den Prozess der sequentiellen Lösung eines Problems, der in diskreter Zeit abläuft, so dass zum jeweils nächsten Zeitpunkt das System der Objekte des Algorithmus nach einem bestimmten Gesetz aus dem System der vorhandenen Objekte gewonnen wird zum vorherigen Zeitpunkt. Intuitiv, weil das Konzept eines Algorithmus streng genommen mit dem Konzept einer Menge verwandt ist, die nicht definierbar ist.

In Übereinstimmung mit GOST 19781-74 „Rechenmaschinen. Software. Begriffe und Definitionen" Algorithmus ist eine exakte Vorschrift, die den Rechenprozess definiert, der von variablen Ausgangsdaten zum gewünschten Ergebnis führt. Dies setzt das Vorhandensein eines Algorithmus-Ausführers voraus – ein Objekt, das „weiß, wie“ diese Aktionen auszuführen sind.

Das Wort "Algorithmus" soll vom Namen des zentralasiatischen (usbekischen) Mathematikers des XIII. Jahrhunderts Al Khorezmi (Abu Abdallah Muhammad ibn Musa al Khorezmi al Medjusi) stammen - "Algorithmi" in lateinischer Transkription, der zum ersten Mal formulierte die Regeln (Verfahren) für die Durchführung von vier arithmetischen Operationen im Dezimalzahlensystem.

Solange die Berechnungen einfach waren, bestand kein besonderer Bedarf an Algorithmen. Als mehrere Schritt-für-Schritt-Verfahren erforderlich waren, tauchte die Theorie der Algorithmen auf. Aber bei noch größerer Kompliziertheit der Aufgaben stellte sich heraus, dass einige von ihnen nicht algorithmisch gelöst werden können. Das sind zum Beispiel viele Aufgaben, die der „Bordcomputer“ des Menschen – das Gehirn – löst. Die Lösung solcher Probleme basiert auf anderen Prinzipien – diese Prinzipien werden von einer neuen Wissenschaft genutzt – der Neuromathematik und den entsprechenden technischen Mitteln – Neurocomputern. In diesem Fall werden die Prozesse des Lernens, des Versuchs und des Irrtums angewendet - das ist, was wir derzeit tun.

Die Qualität eines Algorithmus wird durch seine Eigenschaften (Ausprägungen) bestimmt. Die Haupteigenschaften des Algorithmus sind:

1. Massencharakter. Es wird davon ausgegangen, dass der Algorithmus zur Lösung aller Probleme dieser Art geeignet sein kann. Beispielsweise sollte ein Algorithmus zum Lösen eines Systems linearer algebraischer Gleichungen auf ein System anwendbar sein, das aus einer beliebigen Anzahl von Gleichungen besteht.

2. Effizienz. Diese Eigenschaft bedeutet, dass der Algorithmus in endlich vielen Schritten zu einem Ergebnis führen muss.

3. Sicherheit. Die im Algorithmus enthaltenen Anweisungen müssen präzise und verständlich sein. Diese Eigenschaft stellt die Eindeutigkeit des Ergebnisses des Rechenverfahrens für gegebene Anfangsdaten sicher.

4. Diskretion. Diese Eigenschaft bedeutet, dass der durch den Algorithmus beschriebene Prozess und der Algorithmus selbst in einzelne elementare Schritte unterteilt werden können, deren Möglichkeit der Benutzer auf einem Computer durchführen kann, ohne Zweifel.

Heute steht das „digitale Jahrtausend“ vor der Tür und man könnte den Eindruck gewinnen, dass jegliche Aufgaben Algorithmen unterworfen sind. Es stellt sich heraus, dass viele Probleme nicht algorithmisch gelöst werden können. Dies sind die sogenannten algorithmisch unlösbaren Probleme.

Um die algorithmische Lösbarkeit oder Unlösbarkeit von Problemen zu beweisen, werden mathematisch strenge und präzise Mittel benötigt. Mitte der 30er Jahre des letzten Jahrhunderts wurden Versuche unternommen, das Konzept eines Algorithmus zu formalisieren, und verschiedene Modelle von Algorithmen wurden vorgeschlagen: rekursive Funktionen; "Maschinen" - Turing, Post; normale Markov-Algorithmen.

Anschließend wurde festgestellt, dass diese und andere Modelle in dem Sinne äquivalent sind, dass die Problemklassen, die sie lösen, übereinstimmen. Diese Tatsache wird Church's These genannt. Mittlerweile ist dies allgemein akzeptiert. Die formale Definition des Begriffs eines Algorithmus schuf bereits vor der Entwicklung der ersten Computer die Voraussetzungen für die Entwicklung der Theorie eines Algorithmus. Der Fortschritt der Computertechnik regte die Weiterentwicklung der Theorie der Algorithmen an. Neben der Feststellung der algorithmischen Lösbarkeit von Problemen befasst sich die Theorie der Algorithmen auch mit der Abschätzung der Komplexität von Algorithmen hinsichtlich der Anzahl der Schritte (Zeitkomplexität) und des benötigten Speichers (Raumkomplexität) und entwickelt effiziente Algorithmen in dieser Sinn.

Für die Implementierung einiger Algorithmen kann es unter physikalisch vernünftigen Annahmen über die Geschwindigkeit der Ausführung von Elementarschritten mehr Zeit in Anspruch nehmen, als nach modernen Ansichten das Universum existiert, oder mehr Speicherzellen als die Atome bilden den Planeten Erde.

Daher besteht eine weitere Aufgabe der Algorithmentheorie darin, das Problem der Eliminierung der Aufzählung von Optionen in kombinatorischen Algorithmen zu lösen. Die Komplexität von Algorithmen abzuschätzen und sogenannte effiziente Algorithmen zu erstellen, ist eine der wichtigsten Aufgaben der modernen Algorithmentheorie.