Teaching and learning foundations of computer science : on the unusual effectiveness of logic in computer science

Abstract

In der inzwischen berühmten Arbeit "The Unreasonable Effectiveness of Mathematics in the Natural Sciences" (übersetzt etwa "Die ungewöhnliche Effektivität der Mathematik in den Naturwissenschaften") hat Physik-Nobelpreisträgers Eugene Wigner in den 1960er Jahren beschrieben, warum Mathematik von so grundlegender Bedeutung für Naturwissenschaften wie Physik und Chemie ist. Logik -- als eine der ältesten und theoretischsten Wissenschaften -- und Informatik -- als eine der jüngsten und praktischsten Wissenschaften -- scheinen auf den ersten Blick soweit voneinander entfernt zu sein wie nur möglich. Aber, wie sich herausgestellt hat, ist Logik für die Informatik genau das, was Mathematik für die Naturwissenschaften ist. Während sich dieses Verhältnis über die Entwicklung der Informatik herausgestellt hat, ist es in der bekannten, im Jahr 2001 veröffentlichten Arbeit "On the Unusual Effectiveness of Logic in Computer Science" (übersetzt etwa "Die ungewöhnliche Effektivität der Logik in der Informatik") festgestellt worden -- wobei sich der Titel natürlich auf Wigners Arbeit bezieht. Das war nicht nur eine wissenschaftliche Arbeit, sondern das Ergebnis eines Arbeitstreffens von einigen der wichtigsten Wissenschaftler ihres Feldes, unter ihnen solche aus dem Feld der Datenbanken, Programmiersprachen, Systemverifikation, Sicherheit und Komplexität. In dieser Arbeit zeigen wir die "ungewöhnliche Effektivität der Logik in der Informatik" in dem wir die verschiedenen Anwendungen der Logik in der Informatik basierend auf einheitlichen Konzepten präsentieren. Um dieses Ziel zu erreichen konzentrieren wir uns auf Einfachheit und modulare Präsentation, aber ohne Formalität (als Grundpfeiler der Logik) und konkrete Anwendungen (als Grundpfeiler der Informatik) aufzugeben. Es gibt unzählige Anwendungen von Logik in der Informatik. In dieser Arbeit präsentieren wir eine Auswahl die es erlaubt zwei Hauptsichtweisen auf die Informatik zu präsentieren. Eine ist die "Ebenensicht", die Sicht der Informatik als Ebenen von Abstraktionen. In diesem Bereich haben wir die Ebenen der Schaltkreise, der Hardware, der Software und der Datenbanken ausgewählt. In ähnlicher Weise präsentieren wir die "integrierte Sicht" der Informatik, zuerst natürlich dadurch, dass wir Logik als Weg zu vereinheitlichten Konzepten nutzen, aber strukturell in dem wir drei Bereiche präsentieren: das Modellieren von Problemen, das Konzept der Berechnung, und Komplexität.

In the now famous paper "The Unreasonable Effectiveness of Mathematics in the Natural Sciences", Nobel Prize winning physicist Eugene Wigner wrote in the 1960s on why mathematics is of such fundamental importance for sciences like physics and chemistry. Logic -- as one of the oldest and most theoretical disciplines -- and computer science -- as one of the newest and most practical disciplines -- seem at first sight as far away from each other as possible. But as it turned out, logic is to computer science what mathematics is to the natural sciences. This became apparent throughout the development of computer science, but was famously stated in the 2001 paper "On the Unusual Effectiveness of Logic in Computer Science", the title of course being a reference to Wigner's work. This was not only a paper, but the result of a workshop that included some of the most important computer scientists of their fields, among them ones working on databases, programming languages, system verification, security and computational complexity. In this work, we show the "Unusual Effectiveness of Logic in Computer Science" by presenting the diverse applications of logic in computer science based on unified concepts. To reach this goal, we focus on simplicity and modular presentation, but without sacrificing formality (as a cornerstone of logic) and concrete applications (as a cornerstone of computer science). There are countless applications of logic in computer science. This work features a selection that allows to present two major views of computer science. One is the "layered view", the view of computer science as a sequence of abstractions. We have thus selected the layer of (combinational) circuits, the one of hardware, of software and the one of databases. In a similar way, we present the "integrated view"" of computer science, first of course by using logic as a way of presenting unified concepts, but structurally by featuring three areas: the modeling of problems, the concept of computation, and computational complexity.