close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Männerfreizeit Männerfreizeit Männerfreizeit

EinbettenHerunterladen
Lineare Algebra f¨
ur Physiker, WS 2014/15
0 Aussagenlogik
In diesem Paragraphen sind einige grundlegende Begriffe und Zusammenh¨ange aus der sogenannten naiven Logik zusammengestellt. Auf eine pr¨azise Einf¨
uhrung der Begriffe wird dabei
verzichtet; dies geschieht in der axiomatischen Logik.
0.1 Definition. Eine (mathematische) Aussage p ist ein sinnvolles sprachliches Gebilde, das
entweder ”wahr” (w) oder ”falsch” (f) ist; eine andere M¨oglichkeit gibt es nicht (tertium non
datur, zweiwertige Logik). Statt ”p ist wahr” sagt man auch ”p gilt”, ”p trifft zu”, ”p stimmt”
oder ”p ist richtig”.
Beispiele.
7 ist Primzahl
(w)
2+3=6
(f)
1/0 = 10
keine Aussage, da 1/0 nicht definiert ist.
2π
keine Aussage, da ohne Wahrheitswert.
”Jede gerade Zahl gr¨
oßer als 2 ist Summe von zwei Primzahlen” (Goldbachsche Vermutung)
ist Aussage, deren Wahrheitswert nicht bekannt ist.
0.2 Junktoren
Seien p und q zwei Aussagen. Wir konstruieren aus p und q neue Aussagen, deren Wahrheitswerte durch die von p und q gegeben werden.
0.2.1 Negation (Verneinung): ¬p , ”nicht p”
Definition. ¬p ist wahr, wenn p falsch ist, und falsch, wenn p wahr ist.
Zum Beispiel ist die Verneinung der Aussage 2 + 3 = 5 die Aussage 2 + 3 = 5 .
Der Zusammenhang zwischen dem Wahrheitswert von p und dem von ¬p l¨aßt sich in einer
Wahrheitstafel darstellen (und ist dadurch vollst¨andig bestimmt).
¬p
f
w
p
w
f
0.2.2 Konjunktion (Und-Verkn¨
upfung): p ∧ q , ”p und q”
Definition. p ∧ q ist genau dann wahr, wenn beide Aussagen p, q wahr sind.
Zum Beispiel ist die Aussage ”9 ist ungerade und (9 ist) durch 3 teilbar ” wahr, aber die
beiden Aussagen ”7 ist ungerade und (7 ist) durch 3 teilbar ” und ”4 ist ungerade und (4 ist)
durch 3 teilbar ” sind falsch.
Die zu p ∧ q geh¨
orende Wahrheitstafel sieht folgendermaßen aus.
p
w
w
f
f
p∧q
w
f
f
f
q
w
f
w
f
1
0.2.3 Disjunktion (Oder-Verkn¨
upfung): p ∨ q , ”p oder q” (nicht-ausschließend)
Definition. p ∨ q ist genau dann wahr, wenn mindestens eine der beiden Aussagen p, q wahr
ist, d.h. wenn nur p oder nur q oder beide wahr sind.
Zum Beispiel sind die Aussagen ”9 ist ungerade oder durch 3 teilbar ” und ”7 ist ungerade
oder durch 3 teilbar ” wahr, aber die Aussage ”4 ist ungerade oder durch 3 teilbar ” ist falsch.
Die zu p ∨ q geh¨
orende Wahrheitstafel sieht folgendermaßen aus.
p
w
w
f
f
p∨q
w
w
w
f
q
w
f
w
f
Bemerkung. Das ausschließende ”entweder p oder q” hat die Form (p ∨ q) ∧ ¬(p ∧ q) .
0.2.4 Implikation (Folgerung): p ⇒ q , ”wenn p, dann q”
Definition. p ⇒ q ist genau dann falsch, wenn die Aussage p wahr und die Aussage q falsch
ist. p heißt Pr¨amisse und q Konklusion von p ⇒ q . F¨
ur p ⇒ q sagt man auch ”aus p folgt q”,
”p ist hinreichend f¨
ur q” oder ”q ist notwendig f¨
ur p”.
Zum Beispiel ist die Aussage ”wenn es regnet, dann sind die Straßen nass” wahr, auch an
Tagen, an denen die Sonne scheint und es gar nicht regnet.
Die zu p ⇒ q geh¨
orende Wahrheitstafel hat folgende Form.
p
w
w
f
f
p⇒q
w
f
w
w
q
w
f
w
f
Merke! Implikationen mit falscher Pr¨amisse sind wahr, d.h. aus etwas Falschem kann man
alles M¨ogliche folgern (ex falso quodlibet).
¨
0.2.5 Aquivalenz
(Logische Gleichwertigkeit): p ⇔ q , ”p genau dann, wenn q”
Definition. p ⇔ q ist genau dann wahr, wenn die Aussagen p und q den gleichen Wahrheitswert haben, d.h. beide wahr oder beide falsch sind. F¨
ur p ⇔ q sagt man auch ”p und q sind
logisch gleichwertig” oder ”p ist notwendig und hinreichend f¨
ur q”.
Die zu p ⇔ q geh¨
orende Wahrheitstafel sieht folgendermaßen aus.
p
w
w
f
f
p⇔q
w
f
f
w
q
w
f
w
f
2
Bei der Notation von Aussagen, die durch mehrere Junktoren zusammengesetzt sind, vereinbart man folgende Bindungspriorit¨aten:
¬ bindet st¨arker als ∧ und ∨, und diese binden st¨arker als ⇒ und ⇔ .
Wir betrachten nun die Wahrheitstafeln einiger zusammengesetzter Aussagen.
Beispiel 1. p ∨ q ⇒ ¬q
p
w
w
f
f
q
w
f
w
f
p∨q
w
w
w
f
¬q
f
w
f
w
p ∨ q ⇒ ¬q
f
w
f
w
Beispiel 2. Die Aussagen p ⇒ q , ¬p ∨ q und ¬q ⇒ ¬p sind logisch gleichwertig.
p
w
w
f
f
q
w
f
w
f
p⇒q
w
f
w
w
¬p
f
f
w
w
¬p ∨ q
w
f
w
w
¬q
f
w
f
w
¬q ⇒ ¬p
w
f
w
w
0.3 Tautologien
Beispiel 2 zeigt, dass die Aussagen (p ⇒ q) ⇔ ¬p ∨ q und (p ⇒ q) ⇔ (¬q ⇒ ¬p) unabh¨angig von den Wahrheitswerten von p und q immer wahr sind. Zusammengesetzte Aussagen
mit dieser Eigenschaft nennt man allgemeing¨
ultig oder Tautologien.
Satz. Seien p, q und r Aussagen. Dann sind folgende Aussagen Tautologien.
a)
p∧q ⇔ q∧p
Kommutativ-Gesetz (f¨
ur ∧)
b)
(p ∧ q) ∧ r ⇔ p ∧ (q ∧ r)
Assoziativ-Gesetz (f¨
ur ∧)
c)
p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)
Distributiv-Gesetz
d)
¬(p ∧ q) ⇔ ¬p ∨ ¬q
De Morgansche Regel
e)
f)
g)
h)
¬¬p
(p ⇔ q)
(p ⇒ q)
(p ⇒ q)
i)
j)
k)
l)
m)
p ∨ ¬p
(p ⇒ q) ∧ (q ⇒ r)
p ∧ (p ⇒ q)
¬(q ∧ ¬q)
(¬p ⇒ (q ∧ ¬q))
⇔
⇔
⇔
⇔
p
(p ⇒ q) ∧ (q ⇒ p)
¬p ∨ q
(¬q ⇒ ¬p)
⇒
⇒
(p ⇒ r)
q
⇒
p
Doppelte Negation
Umformung von ⇔
Umformung von ⇒
Kontraposition
M¨oglichkeit zur Fallunterscheidung
Transitivit¨at von ⇒
Abtrennungsregel
Verbotener Widerspruch
Indirekter Beweis
a’) - d’) analog zu a) - d) mit ∧ und ∨ vertauscht.
Beweis. Der Beweis erfolgt mit Wahrheitstafeln. g), h) wurden bereits bewiesen (Beispiel 2).
¨
Ahnlich zeigt man f¨
ur a) - f), dass die beiden Seiten von ⇔ immer gleiche Wahrheitswerte haben.
F¨
ur die Implikationen j), k) und m) reicht es zu zeigen: immer wenn die Pr¨amisse wahr ist, stimmt
auch die Konklusion.
3
0.4 Quantoren
0.4.1 Definition. Eine Aussageform (in einer Variablen) ist ein sprachliches Gebilde p(x)
mit einer ”freien” Variablen x und einem Objektbereich D f¨
ur x derart, dass f¨
ur jedes a aus D
p(a) eine Aussage ist (w oder f). Analog sind Aussageformen in mehreren Variablen definiert.
Beispiele. 1) F¨
ur die Aussageform q(x) = ”x ist Quadratzahl” mit D = IN ist q(9) eine
wahre und q(7) eine falsche Aussage.
2) F¨
ur die Aussageform in zwei Variablen t(x, y) = ”x teilt y” mit Dx = Dy = IN ist t(3, 6)
eine wahre und t(2, 5) eine falsche Aussage; t(x, 6) und t(2, y) sind Aussageformen.
Aus einer Aussageform erh¨alt man also durch Einsetzen der Elemente aus dem Objektbereich
in die Aussageform eine Familie von Aussagen. Die Frage, ob es in dieser Familie u
¨berhaupt wahre
Aussagen gibt oder ob sogar alle wahr sind, f¨
uhrt zu den beiden folgenden neuen Aussagen.
0.4.2 Definition. Sei p(x) eine Aussageform mit Objektbereich D .
1) Die Existenz-Aussage (Notation ∃ x ∈ D : p(x) ) ist die folgende Aussage:
Es gibt (mindestens) ein x aus D , f¨
ur das p(x) wahr ist
2) Die All-Aussage (Notation ∀ x ∈ D : p(x) ) ist die folgende Aussage:
F¨
ur alle x aus D ist p(x) wahr
Das Zeichen ∃ heißt Existenz-Quantor und das Zeichen ∀ All-Quantor. Im mathematischen
Alltag kommen die Existenz- bzw All-Aussage meist so daher: ”es existiert ein x in D mit p(x) ”
oder ”p(x) stimmt f¨
ur (mindestentens) ein x aus D ” bzw. ”f¨
ur jedes x aus D gilt p(x) ” oder
”p(x) stimmt f¨
ur (alle) x aus D ”.
Besispiel. Die Aussage ∃ x ∈ IN : 3 + x = 5 ist wahr, aber ∀ x ∈ IN : 3 + x = 5 ist falsch.
Bemerkungen. 1) In den Aussagen ∃ x ∈ D : p(x) und ∀ x ∈ D : p(x) kommt die Variable
x zwar noch vor, aber man kann nichts mehr einsetzen, sie ist ”gebunden”.
2) Die G¨
ultigkeit einer Existenz- oder All-Aussage h¨angt nicht nur von der Aussageform sondern auch von ihrem Objektbereich ab. So ist beispielsweise die Aussage ∃ x ∈ D : x + 5 = 2 f¨
ur
D = ZZ wahr aber f¨
ur D = IN falsch.
0.4.3 Satz (Negation der Existenz-/All-Aussage). Sei p(x) eine Aussageform mit
Objektbereich D. Dann gilt.
¬(∃ x ∈ D : p(x)) ⇐⇒ ∀ x ∈ D : ¬p(x)
¬(∀ x ∈ D : p(x)) ⇐⇒ ∃ x ∈ D : ¬p(x)
Beispiel. Sei p(x) die Aussageform ”x raucht ” mit dem Objektbereich D = Studentenschaft. Dann ist die Negation von ”alle Studenten rauchen ” ¨aquivalent zu ”mindestens ein
Student raucht nicht ”, und die Negation von ”es gibt einen Studenten, der raucht ” ist ¨aquivalent
zu ”alle Studenten sind Nichtraucher ”.
4
Document
Kategorie
Seele and Geist
Seitenansichten
7
Dateigröße
64 KB
Tags
1/--Seiten
melden