Logik in der Informatik

Für die Akademische Konferenz LICs, siehe Symposium über Logik in der Informatik.
Diagrammatische Darstellung des Computers Logik -Tore

Logik in der Informatik bedeckt die Überlappung zwischen dem Feld von Logik und das von Informatik. Das Thema kann im Wesentlichen in drei Hauptbereiche unterteilt werden:

  • Theoretische Grundlagen und Analyse
  • Verwendung von Computertechnologie zur Unterstützung der Logiker
  • Verwendung von Konzepten aus Logik für Computeranwendungen

Theoretische Grundlagen und Analyse

Die Logik spielt eine grundlegende Rolle in der Informatik. Einige der wichtigsten Bereiche der Logik, die besonders wichtig sind Computerbarkeitstheorie (früher als Rekursionstheorie bezeichnet), Modale Logik und Kategoriestheorie. Das Theorie der Berechnung basiert auf Konzepten, die von Logikern und Mathematikern definiert sind, wie z. Alonzo -Kirche und Alan Turing.[1][2] Die Kirche zeigte zunächst die Existenz algorithmisch unlösbarer Probleme, indem er seinen Begriff der Lambda-Definierbarkeit unterhielt. Turing ergab die erste überzeugende Analyse dessen, was als mechanisches Verfahren bezeichnet werden kann und Kurt Gödel behauptete, er fand Turings Analyse "perfekt".[3] Darüber hinaus sind einige andere wichtige Bereiche theoretischer Überlappungen zwischen Logik und Informatik:

  • Gödels Unvollständigkeitstheorem beweist, dass jedes logische System, das leistungsstark genug ist, um die Arithmetik zu charakterisieren, Aussagen enthält, die weder in diesem System bewiesen noch widerlegt werden können. Dies hat eine direkte Anwendung auf theoretische Probleme in Bezug auf die Machbarkeit, die Vollständigkeit und Richtigkeit der Software zu beweisen.[4]
  • Das Rahmenproblem ist ein grundlegendes Problem, das bei der Verwendung überwunden werden muss Logik erster Ordnung die Ziele und den Zustand eines künstlichen Intelligenzagenten darstellen.[5]
  • Das Curry -Howard -Korrespondenz ist eine Beziehung zwischen logischen Systemen und Software. Diese Theorie hat eine genaue Korrespondenz zwischen Beweisen und Programmen festgestellt. Insbesondere zeigte es, dass Begriffe in der einfach typischen Lambda-Kalkulus den Beweisen der intuitionistischen Aussagelogik entsprechen.
  • Kategoriestheorie repräsentiert eine Sichtweise der Mathematik, die die Beziehungen zwischen Strukturen hervorhebt. Es ist eng mit vielen Aspekten der Informatik verbunden: Typsysteme für Programmiersprachen, die Theorie der Übergangssysteme, Modelle der Programmiersprachen und die Theorie der Programmiersprache Semantik.[6]

Computer, die Logiker unterstützen

Eine der ersten Anwendungen für den Begriff künstliche Intelligenz war das logische Theoretiksystem, das von entwickelt wurde von Allen Newell, J. C. Shaw und Herbert Simon 1956. Eines der Dinge, die ein Logiker tut, ist, eine Reihe von Anweisungen in Logik zu nehmen und die Schlussfolgerungen (zusätzliche Aussagen) abzuleiten, die durch die Gesetze der Logik wahr sein müssen. Wenn Sie beispielsweise ein logisches System geben, das "alle Menschen sind sterblich" und "Sokrates ist menschlich" erklärt, lautet eine gültige Schlussfolgerung "Sokrates ist sterblich". Dies ist natürlich ein triviales Beispiel. In tatsächlichen logischen Systemen können die Anweisungen zahlreich und komplex sein. Es wurde früh erkannt, dass diese Art der Analyse durch die Verwendung von Computern erheblich unterstützt werden könnte. Der logische Theoretiker validierte die theoretische Arbeit von Bertrand Russell und Alfred North Whitehead in ihrer einflussreichen Arbeit an der mathematischen Logik genannt Principia Mathematica. Darüber hinaus wurden nachfolgende Systeme von Logikanern verwendet, um neue logische Theoreme und Beweise zu validieren und zu entdecken.[7]

Logikanwendungen für Computer

Es gab immer einen starken Einfluss auf die mathematische Logik auf dem Gebiet von künstliche Intelligenz (AI). Von Anfang an wurde erkannt, dass Technologie zur Automatisierung logischer Schlussfolgerungen ein großes Potenzial haben könnte, Probleme zu lösen und Schlussfolgerungen aus Fakten zu ziehen. Ron Brachman hat beschrieben Logik erster Ordnung (Fol) als Metrik, durch die alle KI Wissensrepräsentation Formalismen sollten bewertet werden. Es gibt keine allgemeinere oder leistungsfähigere Methode zur Beschreibung und Analyse von Informationen als fol. Der Grund, warum Fol selbst einfach nicht als Computersprache verwendet wird, ist, dass es tatsächlich zu ausdrucksstark ist, in dem Sinne, dass FOL leicht Aussagen ausdrücken kann, dass kein Computer, egal wie mächtig, jemals lösen könnte. Aus diesem Grund ist jede Form der Wissensrepräsentation in gewissem Sinne ein Kompromiss zwischen Ausdruck und Berechnung. Je ausdrucksvoller die Sprache ist, desto näher ist es, je mehr sie folgt, desto wahrscheinlicher ist es, dass es langsamer und anfällig für eine unendliche Schleife ist.[8]

Zum Beispiel, wenn dann Regeln verwendet in verwendet in Expertensysteme ungefähr zu einer sehr begrenzten Untergruppe von fol. Anstatt willkürliche Formeln mit dem gesamten Bereich der logischen Operatoren, der Ausgangspunkt ist einfach das, was Logiker als als bezeichnet Modus Ponens. Als Ergebnis, Regelbasierte Systeme kann eine Hochleistungsberechnung unterstützen, insbesondere wenn sie Optimierungsalgorithmen und Kompilierung nutzen.[9]

Ein weiterer wichtiger Forschungsbereich für die logische Theorie war Software Engineering. Forschungsprojekte wie die Wissensbasierter Softwareassistent und Programmierer -Lehrlingsprogramme wurden logische Theorie angewendet, um die Richtigkeit von Softwarespezifikationen zu validieren. Sie verwendeten sie auch, um die Spezifikationen in einen effizienten Code auf verschiedenen Plattformen zu verwandeln und die Äquivalenz zwischen der Implementierung und der Spezifikation zu beweisen.[10] Dieser formale transformationsgetriebene Ansatz ist oft weitaus mühsamer als die herkömmliche Softwareentwicklung. In bestimmten Bereichen mit geeigneten Formalismen und wiederverwendbaren Vorlagen hat sich der Ansatz jedoch für kommerzielle Produkte als sinnvoll erwiesen. Die entsprechenden Domänen sind in der Regel solche wie Waffensysteme, Sicherheitssysteme und Echtzeit -Finanzsysteme, bei denen das Scheitern des Systems übermäßig hohe menschliche oder finanzielle Kosten aufweist. Ein Beispiel für eine solche Domäne ist Sehr groß integriert (VLSI) Design - Der Prozess zum Entwerfen der für CPUs verwendeten Chips und andere kritische Komponenten digitaler Geräte. Ein Fehler in einem Chip ist katastrophal. Im Gegensatz zu Software können Chips nicht gepatcht oder aktualisiert werden. Infolgedessen besteht kommerzielle Rechtfertigung für die Verwendung formaler Methoden, um zu beweisen, dass die Implementierung der Spezifikation entspricht.[11]

Eine weitere wichtige Anwendung der Logik auf Computertechnologie war im Bereich von Rahmensprachen und automatische Klassifizierer. Rahmensprachen wie zum Beispiel Kl-eins eine starre Semantik haben. Definitionen in KL-One können direkt auf die festgelegte Theorie und den Prädikatkalkül zugeordnet werden. Dies ermöglicht es spezialisierte Theorem -Provers, die als Klassifizierer bezeichnet werden, um die verschiedenen Erklärungen zwischen Sets, Teilmengen und Beziehungen in einem bestimmten Modell zu analysieren. Auf diese Weise kann das Modell validiert und inkonsistente Definitionen markiert werden. Der Klassifizierer kann auch neue Informationen schließen, beispielsweise neue Sätze auf der Grundlage vorhandener Informationen definieren und die Definition vorhandener Sätze basierend auf neuen Daten ändern. Das Ausmaß der Flexibilität ist ideal, um die sich ständig verändernde Welt des Internets zu bewältigen. Die Klassifikator -Technologie basiert auf Sprachen wie dem Web -Ontologie -Sprache Um dem vorhandenen Internet ein logisches semantisches Niveau zu ermöglichen. Diese Schicht wird als die genannt Semantisches Web.[12][13]

Zeitliche Logik wird zum Denken in verwendet Gleichzeitige Systeme.[14]

Siehe auch

Verweise

  1. ^ Lewis, Harry R. (1981). Elemente der Berechnungstheorie. Prentice Hall.
  2. ^ Davis, Martin (11. Mai 1995). "Einflüsse der mathematischen Logik auf die Informatik". In Rolf Herken (Hrsg.). Die universelle Turing -Maschine. Springer Verlag. ISBN 9783211826379. Abgerufen 26. Dezember 2013.
  3. ^ Kennedy, Juliette (2014-08-21). Godel interpretieren. Cambridge University Press. ISBN 9781107002661. Abgerufen 17. August 2015.
  4. ^ Hofstadter, Douglas R. (1999-02-05). Gödel, Escher, Bach: Ein ewiges goldenes Geflecht. Grundbücher. ISBN 978-0465026562.
  5. ^ McCarthy, John; P. J. Hayes (1969). "Einige philosophische Probleme vom Standpunkt der künstlichen Intelligenz" (PDF). Maschineninformation. 4: 463–502.
  6. ^ Barr, Michael; Charles Wells (1998). Kategoriestheorie für die Computerwissenschaft (PDF). Center de recherches mathématiques.
  7. ^ Newell, Allen; J. C. Shaw; H.C. Simon (1963). "Empirische Erkundungen mit der logischen Theoriemaschine". In Ed Feigenbaum (Hrsg.). Computer und Gedanken. McGraw Hill. pp.109–133. ISBN 978-0262560924.
  8. ^ Levesque, Hector; Ronald Brachman (1985). "Ein grundlegender Kompromiss bei Wissensrepräsentation und Argumentation". In Ronald Brachman und Hector J. Levesque (Hrsg.). Lesen in der Wissensrepräsentation. Morgan Kaufmann. p.49. ISBN 0-934613-01-x. Die gute Nachricht bei der Reduzierung des KR -Dienstes auf den Satz beweist, dass wir jetzt eine sehr klare, sehr spezifische Vorstellung davon haben, was das KR -System tun sollte. Das schlechte Neue ist, dass es auch klar ist, dass die Dienste nicht erbracht werden können ... Die Entscheidung, ob ein Satz in FOL ein Satz ist oder nicht ... ist unlösbar.
  9. ^ Forgy, Charles (1982). "RETE: Ein schneller Algorithmus für das Problem der vielen Muster/viele Objektmuster übereinstimmen*" (PDF). Künstliche Intelligenz. 19: 17–37. doi:10.1016/0004-3702 (82) 90020-0. Archiviert von das Original (PDF) Am 2013-12-27. Abgerufen 25. Dezember 2013.
  10. ^ Reich, Charles; Richard C. Waters (November 1987). "Das Programmierer -Lehrlingsprojekt: Eine Forschungsübersicht" (PDF). IEEE -Experte. Archiviert von das Original (PDF) Am 2017-07-06. Abgerufen 26. Dezember 2013.
  11. ^ Stavridou, Victoria (1993). Formale Methoden im Schaltungsdesign. Press -Syndikat der Universität von Cambridge. ISBN 0-521-443369. Abgerufen 26. Dezember 2013.
  12. ^ MacGregor, Robert (Juni 1991). "Verwenden eines Beschreibung Klassifizierer zur Verbesserung der Wissensrepräsentation". IEEE -Experte. 6 (3): 41–46. doi:10.1109/64.87683. S2CID 29575443.
  13. ^ Berners-Lee, Tim; James Hendler; Ora Lassila (17. Mai 2001). "Das semantische Web Eine neue Form von Webinhalten, die für Computer von Bedeutung ist, wird eine Revolution neuer Möglichkeiten auslösen". Wissenschaftlicher Amerikaner. 284: 34–43. doi:10.1038/ScientificAmerican0501-34. Archiviert von das Original am 24. April 2013.
  14. ^ Colin Stirling (1992). "Modal und zeitliche Logik". In S. Abramsky; D. M. Gabbay; T. S. E. Maibaum (Hrsg.). Handbuch der Logik in der Informatik. Vol. II. Oxford University Press. S. 477–563. ISBN 0-19-853761-1.

Weitere Lektüre

Externe Links