Snl Aussagen- Und Prädikatenlogik

Front 1

Logik

Back 1

Unter Logik (von altgriechisch logiké téchnē „denkende Kunst“, „Vorgehensweise“) versteht man die Lehre des vernünftigen Schlussfolgerns.

Die theoretische Logik, auch mathematische oder symbolische Logik genannt, ist eine Ausdehnung der formalen Methode der Mathematik auf das Gebiet der Logik. Sie wendet für die Logik eine ähnliche Formelsprache an, wie sie zum Ausdruck mathematischer Beziehungen schon seit langem gebräuchlich ist.
[Hilbert und Ackermann (1928)]

Front 2

Axiom

Back 2

Da eine Beweiskette nicht endlos sein kann, muss man zu Beginn einige Sätze ohne Beweis akzeptieren und seinem System zu Grunde legen. Diese Sätze nannte Euklid Axiome oder Postulate.
Es wurde erkannt, dass das ursprünglich postulierte Euklidische Parallelenaxiom zwar für die Geometrie der Ebene gilt, dass es aber andere Geometrien gibt, wo es nicht zutrifft. Deshalb konstruiert man sich heute entsprechend dem Gegenstand, den man untersucht, jeweils ein Axiomensystem, das als Grundlage für die gewünschte mathematische Theorie am besten geeignet erscheint.

{engl. axiom}

Front 3

Theorem ...

Back 3

... auch "Satz". Widerspruchsfreie logische Aussage, die mittels eines Beweises als wahr erkannt, d.h. aus Axiomen und bereits bekannten Sätzen hergeleitet werden kann.

{engl. theorem}

Front 4

Ein Term ist ...

Back 4

... eine sinnvolle Zusammensetzung von Zahlen, Variablen, Operationszeichen und Klammern. Hat KEINEN WAHRHEITSGEHALT, ist also weder wahr noch falsch.
Bsp: a + b

{engl. term}

Front 5

Eine Aussage ...

Back 5

... beschreibt durch Worte oder Zeichen einen Sachverhalt. Eine Aussage ist entweder WAHR oder FALSCH.
Bsp: 2 + 5 = 7 (wahr)
"Mathe ist schwierig" gilt dagegen nicht als Aussage, weil nicht eindeutig wahr oder falsch.

{engl. proposition}

Front 6

Aussagenlogik

Back 6

Die Aussagenlogik ist ein Teilgebiet der Logik, das sich mit Aussagen und deren Verknüpfung befasst.
In der Aussagenlogik kann man Aussagen durch Variablen ersetzen, die für den Wahrheitswert der Aussagen stehen. Diese Variablen setzt man mit logischen Operatoren in Beziehung.

{engl. propositional calculus}

Front 7

Junktoren

Back 7

Ein Junktor ist eine logische Verknüpfung zwischen Aussagen innerhalb der Aussagenlogik, also ein logischer Operator. Die üblichsten:

Negation: ¬ P
Materiale Implikation: P → Q
Materiale Äquivalenz: P ↔ Q
Konjunktion (und): P ∧ Q
Disjunktion (einschliessendes Oder): P ∨ Q

Weitere Junktoren können komplexere Ausdrücke repräsentieren, z.B:

Kontravalenz (XOR): ⊕ oder ↮ oder ⊻ oder v mit Punkt oben drauf
A ⊕ B entspricht: ¬ (A ↔ B)

Sheffer-Funktion (NAND): | oder ↑ oder ⊼
A | B entspricht: ¬ A ∨ ¬ B

von lat. iungere „verknüpfen, verbinden“

{engl. logical connectives}

Front 8

Minimales Set von Junktoren?

Back 8

Tatsächlich kann man jeden Junktor durch ¬ und ∧ (oder auch durch ¬ und ∨) ersetzen. Beide Varianten würden für die Aussagenlogik reichen.

Es geht sogar noch einfacher: Es genügt ein einziger Junktor, der sogenannte Sheffer-Strich | (NAND). Cool weil NAND Gatter in der Digitaltechnik einfach realisierbar sind.

Front 9

Implikation
A → B

Back 9

¬ A ∨ B

bzw.
¬ (A ∧ ¬B)

Die Implikation A → B ist _falsch_ genau dann, wenn A wahr ist und B falsch ist. (Dann kann B offensichtlich nicht aus A folgen.)
In allen anderen Fällen ist sie wahr.

Seien A und B beliebige Aussagen.
Dann sind A → B und ¬ A ∨ B äquivalente Aussagen.

Man sagt "A impliziert B" oder "B folgt aus A".
Man nennt A die Prämisse, B die Konklusion.

Interessanter Aspekt: Wenn A falsch ist, kann B falsch oder richtig sein, d.h. aus einer falschen Annahme kann _alles_ gefolgert werden.

{engl. implication}

Front 10

Verneinung der Implikation
¬ (A → B)

Back 10

¬ (A → B)
= ¬ (¬ A ∨ B)
= A ∧ ¬ B

Front 11

äquivalent

Back 11

↔
Man schreibt: A ↔ B
Zwei Aussagen A und B sind äquivalent wenn gilt: A ist wahr, genau dann, wenn B wahr ist.
(Anm. der Red: Das bedeutet, dass A und B unmöglich unterschiedlichen Wahrheitsgehalt haben können).
Es gilt sowohl A → B als auch B → A.

{engl. equivalent}

Front 12

A ↔ B ↔ ...

Back 12

(A → B) ^ (B → A)

Front 13

Precedence of logical operators

Back 13

From highest to lowest precedence (¬ has highest precedence):
¬
∧
∨
→
↔

Front 14

De Morgan
¬ (A ∨ B) ↔

Back 14

(¬ A) ∧ (¬ B)

Front 15

De Morgan
(¬ A) ∧ (¬ B) ↔

Back 15

¬ (A ∨ B)

Front 16

De Morgan
(¬ A) ∨ (¬ B) ↔

Back 16

¬ (A ∧ B)

Front 17

De Morgan
¬ (A ∧ B) ↔

Back 17

(¬ A) ∨ (¬ B)

Front 18

A ∨ (B ∧ C) ↔

Back 18

(A ∨ B) ∧ (A ∨ C)

Front 19

A ∧ (B ∨ C) ↔

Back 19

(A ∧ B) ∨ (A ∧ C)

Front 20

Kontraposition der Implikation
A → B

Back 20

(¬ B) → (¬ A)
d.h. A → B und (¬ B) → (¬ A) sind äquivalent.
Damit hat man die Wahl: Es ist statthaft die Kontraposition zu beweisen anstatt die Implikation (indirekter Beweis).

{engl. contraposition}

Front 21

Tautologie

Back 21

Ein Ausdruck heißt genau dann eine Tautologie, wenn er für jede Belegungsfunktion den Wert "wahr" besitzt.
Bsp: q ∨ ¬ q

Front 22

Gegenteil einer Tautologie

Back 22

Eine Kontradiktion ist in der Logik eine Aussage, welche unabhängig vom Wahrheitswert ihrer Teilaussagen immer falsch ist. Beispiel:

q ∧ ¬ q

Front 23

Wie beweist man Äquivalenz?

Back 23

Eine Äquivalenz A ↔ B beweist man im Allgemeinen so, dass man erst die eine Richtung → und dann die andere Richtung ← zeigt.

Front 24

Beweis durch Widerspruch

Back 24

Man nimmt zunächst das Gegenteil an von dem, was man eigentlich zeigen will. Dann hofft man, unter Verwendung der gegebenen Voraussetzungen des Satzes irgendwann in einen Widerspruch zu geraten. Wenn das gelingt, darf man die Annahme verwerfen und ihr Gegenteil ist bewiesen, also das ursprüngliche Ziel erreicht.

Bsp: Beweis, dass es unendlich viele Primzahlen gibt. Man nimmt das Gegenteil an, nämlich es gebe nur endlich viele Primzahlen. Man gerät in einen Widerspruch, der zeigt, dass immer noch eine neue Primzahl gefunden werden kann.

Bsp: Man will beweisen, dass Wurzel aus 2 irrational ist. Man nimmt das Gegenteil an, nämlich √2 = p/q. Dabei müssen p und q teilerfremd sein (sonst liesse sich der Bruch noch kürzen). Man kann dann herleiten, dass sowohl p als auch q gerade Zahlen sind, d.h. eben doch nicht teilerfremd sind (gemeinsamer Faktor 2).

Front 25

Aussagen vom Typ ”wenn A, dann B“ (A → B) sind von grösster Bedeutung, denn mathematische Sätze sind meist genau von dieser Form. A ist die Voraussetzung, B die Behauptung des Satzes.

Den Nachweis, dass ein mathematischer Satz wahr ist, nennt man Beweis. Beweise von Sätzen können auf zwei Arten geschehen ...

Back 25

1) Man nimmt A an, und folgert daraus unter Benutzung bereits bekannter Sachverhalte die Aussage B (direkter Beweis).

2) Man nimmt A und zugleich ¬B an, und folgert daraus einen Widerspruch, d. h. man weist nach, dass A ∧ ¬B (die negierte Implikation) falsch ist.
Wir haben gezeigt, was falsch ist und wenn wir das nun negieren haben wir ¬(A ∧ ¬B) und das muss wahr sein. Das ist äquivalent zu ¬A ∨ B, was wiederum äquivalent zu A → B ist: indirekter Beweis, dass A → B wahr ist!

BEISPIEL:

Hat man n+1 Objekte in n Schubladen verteilt, so gibt es mindestens eine Schublade, in der zwei Objekte liegen.

Voraussetzung A: n + 1 Objekte sind in n Schubladen verteilt.

Behauptung B: Es gibt mindestens eine Schublade, in der mindestens zwei Objekte liegen.

Zu zeigen ist: A → B.

Indirekter Beweis: Angenommen, A und ¬B (der einzige Fall wo A → B _falsch_ ist, d.h. wir behaupten nun, dass dies stimme, was schief gehen muss).

Es sind also n + 1 Dinge in n Schubladen verteilt, aber in allen Schubladen ist höchstens ein Objekt.

Dann sind aber in allen n Schubladen zusammen höchstens n mal höchstens ein Objekt, also höchstens n Objekte. Wir waren aber von n + 1 verteilten Objekten ausgegangen, es liegt also ein Widerspruch vor. Damit ist der Beweis abgeschlossen.

Front 26

Prädikat

Back 26

[Prädikatenlogik]
"Peter" bezeichnet in der Alltagssprache einen Individualbegriff, d.h. einen Begriff, der ein einziges Individuum repräsentiert.
"Student" ist dagegen ein Allgemeinbegriff, d.h. ein Begriff, der eine Klasse repräsentiert.
"Peter ist Student" sagt aus, daß dem Individuum Peter das Prädikat Student zukommt.

Prädikate können bezeichnen:

Allgemeinbegriffe (z.B. Student, Säugetier)
"Peter ist Student"
Student(Peter)

Eigenschaftsbegriffe (z.B. klug, schnell)
"Peter ist klug"
klug(Peter)

Relationsbegriffe (z.B. größer als, gleich)
"Peter ist grösser als Maria"
grösser(Peter, Maria)
Relationen sind mehrstellige Prädikate.

Der prädikatenlogische Begriff 'Prädikat' ist nicht deckungsgleich mit dem sprachwissenschaftlichen Begriff.

[Sprachwissenschaft]
Satzaussage = Die Struktur des Satzes bestimmender Satzteil, der eine Aussage über das Subjekt macht. Z.B. Der Bauer _pflügt_ den Acker. "Bauer" ist das Subjekt, "pflügt" ist das Prädikat.

{engl. predicate}

Informally, a predicate is a statement that may be true or false depending on the values of its variables. However, predicates have many different uses and interpretations in mathematics and logic, and their precise definition, meaning and use will vary from theory to theory.

Front 27

Prädikatenlogik

Back 27

Die Prädikatenlogik ist eine Erweiterung der Aussagenlogik. Sie untersucht ebenfalls Aussagen und Aussagenverbindungen. Während die Aussagenlogik aber die Aussagen als unanalysierte Ganzheiten betrachtet, untersucht die Prädikatenlogik auch die innere Struktur von Aussagen.
Die innere Struktur von Aussagen wird bei solchen Beispielen relevant:
p: Manche Menschen sind faul.
q: Alle Faulen schlafen viel.
r: Manche Menschen schlafen viel.
p ∧ q → r stimmt zwar, ergibt sich aber keinesfalls aus den Regeln der Aussagenlogik, sondern nur, wenn man die innere Struktur von p und q untersucht.

Anschaulich gesprochen werden Eigenschaften von Individuen und deren Beziehungen untersucht. Dabei benutzt man die Aussagen „für alle Individuen gilt ..." und „es gibt ein Individuum mit ...".

{engl. predicate logic}

Front 28

Aussageform

Back 28

Eine Aussageform ist eine Aussage, die von den Werten einer oder mehrerer Variablen abhängt.
Erst wenn die Variablen durch feste Werte ersetzt werden, entsteht eine Aussage, von der feststeht, ob sie wahr oder falsch ist.

Ausageformen kann man (wie Aussagen) durch Variablen A, B usw. ersetzen, deren Wahrheitswert dann von den Variablen abhängt, die innerhalb der Aussageform vorkommen. Man schreibt beispielsweise:
R(x₁, x₂, ...)
A(x)
Student(x)

Zum Beispiel ist x = y bzw. eq(x, y) eine Aussageform.
Sie wird zu einer wahren Aussage, wenn man für x und y die gleiche Zahl einsetzt.
Wenn wir nur für x die Zahl 42 einsetzen, dann erhalten wir die neue Aussageform 42 = y (aber keine Aussage).

Eine etwas komplexere Aussageform:
Pferd(x) → Säugetier(x)
Sie wird zu einer Aussage, wenn man für x ein spezifisches Individuum einsetzt:
Pferd(Fury) → Säugetier(Fury)

{engl. propositional formula; propositional expression; sentence; sentential formula}

Front 29

Wie beweist man, dass eine Aussageform, die Implikation enthält, eine Tautologie ist (d.h. immer wahr)?

Back 29

Man zeigt, dass der einzige Fall, wo eine Implikation A(x) → B(x) falsch wäre, nicht existiert: Wenn die Kombination A=true und B=false unmöglich ist, dann kann die betreffende Implikation nie falsch sein, somit ist sie immer richtig.

Front 30

Quantifizierung von Aussageformen

Back 30

Sei A(x) eine Aussageform, die eine Variable x enthält. Dann kann A(x) auf zwei verschiedene Weisen in eine Aussage überführt (quantifiziert) werden:

1) Für alle x gilt: A(x).

2) Es gibt ein x, für das gilt: A(x).
Dabei verstehen wir ”es gibt ein x“ grundsätzlich als ”es gibt mindestens ein x“.

Front 31

[Prädikatenlogik]
∃

Back 31

Existenzaussage

{engl. existential quantification}

Front 32

[Prädikatenlogik]
∀

Back 32

Allaussage

{engl. universal quantification}

Front 33

[Prädikatenlogik]
(sei A(x) eine Aussageform mit der Variablen x)
Verneinung Existenzaussage
¬ (∃ᵪ A(x)) ↔

Back 33

∀ᵪ ¬ A(x)
Für alle x ist ¬ A(x) wahr (d.h. A(x) also falsch)

Front 34

[Prädikatenlogik]
(sei A(x) eine Aussageform mit der Variablen x)
Verneinung Allaussage
¬ (∀ᵪ A(x)) ↔

Back 34

∃ᵪ ¬ A(x)
Es gibt mindestens ein x für welches ¬ A(x) wahr ist.

Front 35

(∀ᵪ : A(x)) ↔

Back 35

¬ (∃ᵪ : ¬ A(x))

Front 36

(∃ᵪ : A(x)) ↔

Back 36

¬ (∀ᵪ : ¬ A(x))

Front 37

(∀ᵪ : A(x)) ∧ (∀ᵪ : B(x)) ↔

Back 37

∀ᵪ : (A(x) ∧ B(x))
Allquantoren können aus Konjunktionen rausgezogen werden.

Front 38

(∃ᵪ : A(x)) ∨ (∃ᵪ : B(x)) ↔

Back 38

∃ᵪ : (A(x) ∨ B(x))
Existenzquantoren können aus Disjunktionen rausgezogen werden.

Front 39

∀ᵪ : ∀ᵧ : A(x,y) ↔
∃ᵪ : ∃ᵧ : A(x,y) ↔

Back 39

∀ᵧ : ∀ᵪ : A(x,y)
Allquantoren sind untereinander vertauschbar.

∃ᵧ : ∃ᵪ : A(x,y)
Existenzquantoren sind untereinander vertauschbar.

Front 40

Verneinung der Kombination aus Quantoren und Implikation?

Back 40

When we negate a quantified statement, we negate all the quantifiers first, from left to right (keeping the same order), then we negate the statement.
For example, let's negate ∀ᵪ:
¬ ∀ᵪ (P(x) → Q(x))
∃ᵪ ¬ (P(x) → Q(x))
∃ᵪ (P(x) ∧ ¬ Q(x))

Es existiert eine rationale Zahl q für die gilt: q² = 2
Verneinung:
Für alle rationalen Zahlen q gilt: q² ≠ 2

Front 41

deduction

Back 41

"top-down"
Deduction, starts out with a general statement, or hypothesis, and examines the possibilities to reach a specific, logical conclusion. The scientific method uses deduction to test hypotheses and theories.

In deductive reasoning, if something is true of a class of things in general, it is also true for all members of that class. For example, "All men are mortal. Harold is a man. Therefore, Harold is mortal."

Front 42

induction

Back 42

"bottom-up"
Inductive reasoning is the opposite of deductive reasoning. Inductive reasoning makes broad generalizations from specific observations. Even if all of the premises are true in a statement, inductive reasoning allows for the conclusion to be false. Example: "Harold is a grandfather. Harold is bald. Therefore, all grandfathers are bald." The conclusion does not follow logically from the statements.

Inductive reasoning has its place in the scientific method. Scientists use it to form hypotheses and theories. Deductive reasoning allows them to apply the theories to specific situations.

Front 43

A ⇔ B

A ↔ B

Back 43

Das Symbol steht normalerweise für materiale Äquivalenz. Wird innerhalb der Aussagenlogik verwendet und verknüpft einfach zwei Aussagen zu einer neuen, welche selbst wiederum wahr oder falsch sein kann.

"A genau dann, wenn B", kurz "A gdw. B"
"A dann und nur dann, wenn B"
"A if and only if B", short "A iff B"

Beides sind sinnvolle Aussagen:
(A → B) ↔ (¬ A ∨ B)
(A ∧ B) ↔ (A ∨ B)
Die erste Aussage ist eine Tautologie (d.h. wahr für alle möglichen Wahrheitswerte von A und B).
Die zweite Aussage ist je nach Belegung von A und B wahr (z.B. für A = B = 1) oder falsch (z.B. für A = 0, B = 1).

{engl. material equivalence}

Front 44

A ≡ B

Back 44

Das Symbol steht normalerweise für semantische Äquivalenz und steht für die Behauptung - gewissermassen ausserhalb der Aussagenlogik - dass die linke und die rechte Seite für alle Wahrheitswerte der Teilaussagen denselben Gesamt-Wahrheitswert hat.

Angenommen F und G seien Aussagen (allenfalls aus Teilaussagen zusammengesetzt). Dann gilt also F ≡ G genau dann, wenn F ↔ G eine Tautologie ist, d.h. für alle möglichen Wahrheitswerte der Teilaussagen von F und G wahr ist.

Somit wäre dies eine korrekte Behautpung:
(A → B) ≡ (¬ A ∨ B)

Aber diese Behauptung ist einfach falsch:
(A ∧ B) ≡ (A ∨ B)

Front 45

Drei Arten, wie aus einer Aussageform eine Aussage wird.

Back 45

Aussageform:

x ist gerade → 3x ist gerade

1) Aussage durch Einsetzen:

17 ist gerade → 3 · 17 ist gerade
(Listigerweise ist diese Aussage wahr, denn es handelt sich um eine Implikation, wo einzig "wahr → falsch" als falsch definiert ist. Mit 17 haben wir aber "falsch → falsch" und das ist als wahr definiert für Implikation.)

2) Aussage durch Allaussage:
∀ᵪ ∈ ℕ : x ist gerade → 3x ist gerade
(Wahre Aussage)

3) Aussage durch Existenzaussage:
∃ᵪ ∈ ℕ : x ist gerade → 3x ist gerade
(Wahre Aussage)

Front 46

Modus ponens

Back 46

(A ∧ (A ⇒ B)) ⇒ B

Das ist eine Tautologie. Spielt in mathematischen Beweisen und beim Argumentieren in einer Diskussion eine wichtige Rolle:
Wenn A gilt, und wenn B aus A folgt (wenn also A ⇒ B gilt), dann gilt auch B.