Die Aussagenlogik ist eine ganz grundlegende Logik, die quasi als Teillogik in den meisten anderen Logiken enthalten ist. So werden z.B. in der Aussagenlogik einfache Verknüpfungen wie nicht, und und oder eingeführt, die man in den meisten anderen Logiken auch haben möchte. Ferner werden in der Aussagenlogik wichtige Konzepte und Begriffe eingeführt, die dann in andere Logiken übernommen werden. Sie ist daher auch hervorragend zum Einüben dieser Konzepte geeignet. Ferner, und für uns besonders interessant, spielt das Erfüllbarkeitsproblem der Aussagenlogik, d.h. die Frage, gegeben eine Formel der Aussagenlogik, kann diese zu wahr ausgewertet werden, eine zentrale Rolle in der Komplexitätstheorie und wird uns dort wieder begegnen.

Wir werden zunächst die Syntax der Aussagenlogik einführen, d.h. wir werden formal einführen, wie die Formeln der Aussagenlogik eigentlich aussehen dürfen, was wir also hinschreiben dürfen. Im Anschluss werden wir die Semantik der Aussagenlogik einführen, d.h. wir werden definieren, wann eine Formel wahr und wann eine Formel falsch ist und wie wir zu diesen Werten kommen. Nachfolgend geht es dann um Beziehungen zwischen Formeln. Hier führen wir die Begriffe der Folgerbarkeit und der Äquivalenz ein. Es wird dann viel darum gehen Formeln auf diese Eigenschaft zu prüfen und darauf, ob sie wahr gemacht werden können. Wir werden sehen, dass dies zwar gemacht werden kann, aber mit den nahe liegenden Verfahren zu aufwändig ist. Daher werden wir uns noch mit weiteren Verfahren wie z.B. der Resolution beschäftigen.