Ergaenzungen zu Foundations of Logic
               (c) 2001-01-28 Fabian M.Suchanek
        http://suchanek.name/texts/summaries/fol.txt


Dieses sind Ergaenzungen zu der Vorlesung "Foundations of Logic",
die im WS 2000 von Prof. Wolfgang Lenzen an der Universitaet
Osnabrueck gehalten wurde.

Durch das Weiterlesen akzeptiert der Leser, dass der Autor keinerlei
Verantwortung fuer die Richtigkeit oder Vollstaendigkeit dieser
Zusammenfassung uebernimmt. Wenn jemand einen Fehler gefunden hat, so
waere ich fuer eine Mail dankbar. Nur so habe auch ich etwas von der 
Veroeffentlichung dieser Zusammenfassung.

Meine E-Mail-Adresse ist f.m.suchanek@zweb.de, wobei das 'z' aus der
Adresse geloescht werden muss.


#DEFINE "WW" "Wahrheitswert"
#DEFINE "WWen" "Wahrheitswerten"
#DEFINE "U" "vereinigt mit"
#DEFINE "E" "Element von"

tautologische Formel: Eine logische Formel, die immer zu "wahr"
 auswertet,unabhaengig von den Werten der Variablen.

kontradiktorische Formel: Eine logische Formel, die immer zu "falsch"
 auswertet, unabhaengig von den Werten der Variablen.

logisch determiniert: tautologisch oder kontradiktorisch
kontingent: nicht logisch determiniert

~(a & b) = ~a | ~b
~(a | b) = ~a & ~b

Satzoperator: Zeichen, mit dem Saetze derart zu einem neuen Satz verknuepft
werden, dass der WW des neuen Satzes nur von den Teilsaetzem abhaengt.

Implikation: Nicht assoziativ, nicht kommutativ, aber transitiv und
reflexiv
(a => b) = ~a | b
(a => b) = (~b => ~a) (Kontrapositionsprinzip)

Folgerung: Aus A folgt B, wenn die Implikation A => B tautologisch ist

Aequivalenz: (a=b) = (a => b) & (b => a)
(a >< b) = ~(a=b)
logisch aequivalent: Zwei Saetze sind genau dann logisch aequivalent,
wenn die Aussage a = b tautologisch ist.

Vollstaendige Systeme von Satzoperatoren: Man kann bereits aus {~,&}
oder {~,=>} oder anderen Mengen von wenigen Operatoren jede beliebige
Operation auf Saetzen definieren.

Ein Schluss von Praemissen auf eine Konklusion ist dann gueltig, wenn
bei allen moeglichen Verteilungen von WWen die Konklusion wahr ist,
wenn die Praemissen wahr sind.

Die ausfuehrliche Axiomatisierung: Aufbau eines logischen Kalkuels auf
den Operatoren ~,|,&,=>.

Die Standard-Axiomatisierung: Aufbau eines logischen Kalkuels auf
den Operatoren ~,=>.

A |- B heisst man kann von A nach B uebergehen.

Deduktionsregel Modus Ponens (MP): A,(A => B) |- B
Gilt A und die Implikation A=>B, so gilt auch B

Logisches Kalkuel: Praezise formale logische Sprache
Alphabet: {p,',~,&,|,=>,(,)}
Ausdruck: Jede Folge von Zeichen aus dem Alphabet
Satzkonstanten: p,p',p'',p''' etc.
Saetze: 1. Jede Satzkonstante ist ein Satz
        2. Sind A und B Saetze, so auch ~A, (A & B), (A | B), (A => B)
Axiomenschemata: Festgelegte Saetze mit Satzvariablen A,B..., die
                 Axiome (FMS: hier: per definitionem beweisbare Saetze)
                 liefern.
Beweisbarkeit: 1. Jedes Axiom nach einem Axiomenschema ist beweisbar
               2. Ist A beweisbar und A => B beweisbar, so ist auch
                  B beweisbar (MP)
Beweis: Folge von Saetzen, fuer die gilt
        1. der letzte Satz der Folge ist der zu beweisende
        2. jeder der Saetze ist entweder ein Axiom oder wurde durch
           Anwendung des MP auf einen vorherigen Satz der Folge
           gewonnen.
Theorem: Eine Formel ist ein Theorem, wenn es einen Beweis dafuer gibt.
Metatheorem: |- A, jeder Satz der Gestalt A ist beweisbar
Ableitung: Eine Ableitung eines Satzes B aus den Annahme formeln (AF)
           A(i) ist eine Satzfolge, fuer die gilt:
           1. der letzte Satz ist B
           2. jeder Satz ist ein Axiom, mittels MP gewonnen oder mit
              einer der AF identisch
ableitbar: A(1),..A(n) |- B, wenn es eine Ableitung fuer B gibt
Deduktionstheorem: A(1),..A(n) |- B  heisst  A(1),..A(n-1) |- A(n) => B

Bewertung: Semantik der Aussagenlogik
Bewertungsfunktion: V:S->{w,f}, wobei gilt:
                    1. V(~A)=w  genau dann wenn V(A)=f
                    2. V(A&B)=w  genau dann wenn V(A)=w & V(B)=w
                    3. V(A|B)=f  genau dann wenn V(A)=f & V(B)=f
                    4. V(A=>B)=f  genau dann wenn V(A)=w & V(B)=f
Tautologisch: A ist tautologisch, wenn V(A)=w fuer alle moeglichen
              Bewertungen.
Kontradiktorisch: A ist kontradiktorisch, wenn ~A tautologisch ist
Gueltigkeit: Ein Schluss heisst gueltig, wenn fuer alle V, bei denen
             alle Praemissen wahr sind, auch V(Schluss)=w ist.

Widerspruechlichkeit: Eine Satzmenge M ist widerspruechlich
(K-inkonsistent), wenn es einen Satz B gibt mit M |- B & ~B.
Widerspruchsfreiheit: Eine Satzmenge M heisst widerspruchsfrei
(K-konsistent), wenn sie nicht K-inkonsistent ist.

Maximale Konsistenz: Eine Satzmenge M heisst maximal K-konsistent, wenn
M K-konsistent ist und fuer jeden Satz A ~E M die Menge M U {A}
K-inkonsistent ist. Dann gilt: A E M <=> M |- A. Zu jeder
K-konsistenten Satzmenge M gibt es eine maximal K-konsistente Satzmenge
M*.

Praedikatenlogik: Aussagen bestehen aus Praedikaten F,G,... angewandt
auf Namen a,b,....

Logisches Quadrat:
 Universell                                     Universell
 affirmative            <- unvertraeglich ->    verneinende
 Aussage                                        Aussage
                                 ist
    | folgt i.A.              X  Negation          | folgt i.A.
    v                            von               v

 Partikulaer                                    Partikulaer
 affirmative            <- vertraeglich ->      verneinende
 Aussage                                        Aussage