Allgemeingültig, Bsp zeigen, < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:11 Do 07.04.2016 | | Autor: | sissile |
| Aufgabe | Welche der folgenden Formeln sind allgemeingültig und welche nicht? Beweisen Sie ihre Antwort.
(1) [mm] ((X\rightarrow [/mm] Z) [mm] \rightarrow [/mm] ((y [mm] \rightarrow [/mm] Z) [mm] \rightarrow [/mm] ((X [mm] \vee [/mm] Y) [mm] \rightarrow [/mm] Z)))
(2) ((X [mm] \rightarrow [/mm] Y) [mm] \rightarrow [/mm] ((X [mm] \rightarrow \neg [/mm] Y) [mm] \rightarrow \neg [/mm] X)) |
Hallo,
Verstehe ich richtig, dass X,Y,Z Variablen sind?
Eine Formel [mm] \psi [/mm] heißt allgemeingültin, wenn [mm] \beta \models \psi [/mm] für jede Belegung [mm] \beta.
[/mm]
Ich glaube ich mache das zu kompliziert! Gibt es eine einfachere Methode? Sieht man das irgendwie sofort?
Für (1)
Ich habe zuerst (1) umgeschrieben indem ich die Folgerungspfeile übersetzt habe.
[mm] \neg ((X\rightarrow [/mm] Z) [mm] \wedge \neg((Y\rightarrow Z)\rightarrow [/mm] ((X [mm] \vee [/mm] Y) [mm] \rightarrow [/mm] Z)))
[mm] \neg (\neg(X \wedge \neg [/mm] Z) [mm] \wedge \neg(\neg (Y\rightarrow [/mm] Z) [mm] \wedge \neg((X\vee [/mm] Y) [mm] \rightarrow [/mm] Z)))
[mm] \neg(\neg(X \wedge \neg [/mm] Z) [mm] \wedge \neg(\neg \neg [/mm] (Y [mm] \wedge \neg [/mm] Z) [mm] \wedge \neg \neg [/mm] ((X [mm] \vee [/mm] Y) [mm] \wedge \neg [/mm] Z)))
Frage Soll ich zwischen den Ausdrücken ein "=" setzen? Natürlich ist mir klar, dass die Ausdrücke dasselbe bedeuten - aber ich weiß nicht ob das so üblich ist.
Und nun habe ich [mm] \beta \models [/mm] (1) Schritt für Schritt übersetzt mit unseren Definitionen:
[mm] \beta \models [/mm] (1) [mm] gdw.\beta \not\models (\neg(X \wedge \neg [/mm] Z) [mm] \wedge \neg(\neg \neg [/mm] (Y [mm] \wedge \neg [/mm] Z) [mm] \wedge \neg \neg [/mm] ((X [mm] \vee [/mm] Y) [mm] \wedge \neg [/mm] Z)))
gdw. [mm] \beta \not\models (\neg [/mm] (X [mm] \wedge \neg [/mm] Z) oder [mm] \beta \not\models \neg( \neg \neg(Y \wedge \neg [/mm] Z) [mm] \wedge \neg \neg [/mm] ((X [mm] \vee [/mm] Y) [mm] \wedge \neg [/mm] Z )))
gdw. [mm] \beta \models(X \wedge \neg [/mm] z) oder [mm] \beta \models (\neg \neg [/mm] (Y [mm] \wedge \neg [/mm] Z) [mm] \wedge \neg \neg [/mm] ((X [mm] \vee [/mm] Y) [mm] \wedge \neg [/mm] Z))
gdw. [mm] [\beta \models [/mm] X und [mm] \beta \not\models [/mm] Z] oder [ [mm] \beta \models \neg \neg(y \wedge \neg [/mm] Z) und [mm] \beta \models \neg \neg [/mm] ((x [mm] \vee [/mm] Y) [mm] \wedge \neg [/mm] z))]
gdw. [mm] [\beta \models [/mm] X und [mm] \beta \not\models [/mm] Z] oder [mm] [(\beta \models [/mm] Y und [mm] \beta \not\models [/mm] Z) und [mm] (\beta \models [/mm] (x [mm] \vee [/mm] y) und [mm] \beta \not\models [/mm] Z)]
[mm] gdw.[\beta \models [/mm] X und [mm] \beta \not\models [/mm] Z] oder [mm] [(\beta \models [/mm] Y und [mm] \beta \not\models [/mm] Z) und [mm] ((\beta \models [/mm] X oder [mm] \beta \models [/mm] Y) und [mm] \beta \not\models [/mm] Z))]
gdw. [mm] [\beta \models [/mm] X und [mm] \beta \not\models [/mm] Z] oder [mm] [[\beta \models [/mm] Y und [mm] \beta \not\models [/mm] Z] und [mm] [\beta \models [/mm] X und [mm] \beta \not\models [/mm] Z]]
Also ist (1) für [mm] \beta \not\models [/mm] X falsch und deshalb nicht allgemeingültig.
Für (2) hab ich genauso gemacht und kam auf
[mm] \beta \models [/mm] (2) gdw. [mm] [\beta \models [/mm] X und [mm] \beta \not\models [/mm] Y] oder [mm] [\beta \models [/mm] X oder [mm] \beta \not\models [/mm] Y oder [mm] \beta \not\models [/mm] X]
D.h. die Formel ist allgemeingültig. Da für [mm] \beta \models [/mm] X und für [mm] \beta \models [/mm] Y die Formel gültig ist.
|
|
| |
|
Hallo sissile,
es gibt hier eine einfache Methode, die nennt sich Wahrheitstafel / -tabelle. Das funktioniert hier, weil du nur 3 bzw. 2 Variablen hast. Daraus ergeben sich 8 bzw. 4 Fälle (klar?). Das sind deine Zeilen.
Nun musst du für jeden Fall berechnen, ob der Gesamtausdruck wahr oder falsch ist. Dazu hilft es, zusätzliche Spalten für Zwischenberechnungen anzulegen. Ist der gesamte Ausdruck dann in jedem Fall wahr, so ist die Aussage allgemeingültig. Deine Tabelle ist (mit sauberen Zwischenschritten) dann gleich auch ein gültiger Beweis, da du ja nichts anderes machst, als eine vollständige Fallunterscheidung.
Zu den Gleichheitszeichen: Ich würde [mm] $\gdw$ [/mm] verwenden, also "genau dann, wenn".
Gruß,
Sandro
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:03 Fr 08.04.2016 | | Autor: | tobit09 |
Hallo sandroid!
> Zu den Gleichheitszeichen: Ich würde [mm]\gdw[/mm] verwenden, also
> "genau dann, wenn".
Das sehe ich anders: Wir haben es hier mit aussagenlogischen Formeln, also mit Zeichenreihen zu tun. Zwei Aussagen (im naiven Sinne) können sinnvoll mit "genau dann, wenn" verbunden werden, aber sicherlich nicht zwei Zeichenreihen. Es macht hingegen sehr wohl Sinn, zwei Zeichenreihen als gleich (im Falle gleicher Länge und komponentenweiser Übereinstimmung) oder verschieden zu betrachten.
Eine andere Frage ist, ob man aus Gründen der Lesbarkeit (insbesondere wenn später im Rahmen einer Prädikatenlogik auch Gleichheitszeichen innerhalb von Formeln auftreten) besser auf Gleichheitszeichen zwischen Formeln verzichtet. Man könnte alternativ schreiben: Die Formel ... ist eine abkürzende Schreibweise für die Formel ..., was wiederum für die Formel ... steht.
Viele Grüße
Tobias
|
|
|
| |
|
> Welche der folgenden Formeln sind allgemeingültig und
> welche nicht? Beweisen Sie ihre Antwort.
> (1) [mm]((X\rightarrow[/mm] Z) [mm]\rightarrow[/mm] ((y [mm]\rightarrow[/mm] Z) [mm]\rightarrow[/mm] ((X [mm]\vee[/mm] Y) [mm]\rightarrow[/mm] Z)))
Die folgenden Ausführungen zu n(1) stimmen nicht, weil ich die Klammern in Aussage (1) falsch gelesen habe.
Diese Aussage ist nicht allgemeingültig.
> (2) ((X [mm]\rightarrow[/mm] Y) [mm]\rightarrow[/mm] ((X [mm]\rightarrow \neg[/mm] Y) [mm]\rightarrow \neg[/mm] X))
Diese Aussage ist allgemeingültig.
Beweisen kannst du das, wie sandroid schon geschrieben hat, mit Hilfe einer (ausgedehnten) Wahrheitstafel.
Gegenbeispiel zu (1):
X=Die Quersumme einer Zahl ist durch 5 teilbar.
y=Die Quersumme einer Zahl ist durch 10 teilbar.
Z=Die Zahl ist durch 5 teilbar.
(X [mm] \rightarrow [/mm] Z) = Wenn die Quersumme einer Zahl durch 5 teilbar ist, dann ist die Zahl durch 5 teilbar.
Diese Aussage ist FALSCH.
(Y [mm] \rightarrow [/mm] Z) = Wenn die Quersumme einer Zahl durch 10 teilbar ist, dann ist die Zahl durch 5 teilbar.
Diese Aussage ist ebenfalls FALSCH.
((X [mm] \rightarrow [/mm] Z) [mm] \rightarrow [/mm] (Y [mm] \rightarrow [/mm] Z))= Aus (Wenn die Quersumme einer Zahl durch 5 teilbar ist, dann ist die Zahl durch 5 teilbar) folgt automatisch: (Wenn die Quersumme einer Zahl durch 10 teilbar ist, dann ist die Zahl durch 5 teilbar).
Das ist RICHTIG, denn wenn die Quersumme durch 10 teilbar ist, ist sie ja auch durch 5 teilbar.
Beide Aussagen an sich sind falsch, aber die SCHLUSSFOLGERUNG ist RICHTIG.
Wäre jetzt die Gesamtaussage (1) eine allgemeingültige Aussage, könnte man daraus folgern:
Also gilt: (Wenn die Quersumme einer Zahl durch 5 und durch 10 teilbar ist, dann ist die Zahl durch 5 teilbar).
Dieser Schluss ist aber FALSCH, obwohl die SCHLUSSFOLGERUNG oben richtig war (wobei aber die einzelnen Aussagen falsch sind).
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:53 Fr 08.04.2016 | | Autor: | tobit09 |
Hallo HJKweseleit!
> > Welche der folgenden Formeln sind allgemeingültig und
> > welche nicht? Beweisen Sie ihre Antwort.
>
> > (1) [mm]((X\rightarrow[/mm] Z) [mm]\rightarrow[/mm] ((y [mm]\rightarrow[/mm] Z)
> [mm]\rightarrow[/mm] ((X [mm]\vee[/mm] Y) [mm]\rightarrow[/mm] Z)))
>
> Diese Aussage ist nicht allgemeingültig.
Doch, diese Formel ist allgemeingültig.
> Gegenbeispiel zu (1):
>
> X=Die Quersumme einer Zahl ist durch 5 teilbar.
(mit Zahl meinst du "natürliche Zahl"?)
> y=Die Quersumme einer Zahl ist durch 10 teilbar.
> Z=Die Zahl ist durch 5 teilbar.
1. Du ignorierst offenbar den Kontext der Aufgabenstellung: In der Aufgabe wird nicht naiv mit anschaulichen Aussagebegriffen gearbeitet, sondern mit festen Definitionen von aussagenlogischen Formeln (als speziellen Zeichenreihen) und deren Allgemeingültigkeit. X, Y und Z sind Elemente der Variablenmenge und nicht selbst frei wählbare Objekte.
2. Auch im naiven Sinne stellen die von dir angegebenen Formulierungen wohl kaum Aussagen, sondern allenfalls Aussageformen dar.
> (X [mm]\rightarrow[/mm] Z) = Wenn die Quersumme einer Zahl durch 5
> teilbar ist, dann ist die Zahl durch 5 teilbar.
> Diese Aussage ist FALSCH.
Du meinst wohl: Diese Aussage ist IM ALLGEMEINEN falsch. Es gibt sehr wohl natürliche Zahlen n, für die die Aussage
"Wenn die Quersumme von n durch 5 teilbar ist, dann ist n durch 5 teilbar."
wahr ist, nämlich zum einen für alle durch 5 teilbaren natürlichen Zahlen n und zum anderen für alle natürlichen Zahlen n, deren Quersumme nicht durch 5 teilbar ist.
> (Y [mm]\rightarrow[/mm] Z) = Wenn die Quersumme einer Zahl durch 10
> teilbar ist, dann ist die Zahl durch 5 teilbar.
> Diese Aussage ist ebenfalls FALSCH.
>
> ((X [mm]\rightarrow[/mm] Z) [mm]\rightarrow[/mm] (Y [mm]\rightarrow[/mm] Z))= Aus
> (Wenn die Quersumme einer Zahl durch 5 teilbar ist, dann
> ist die Zahl durch 5 teilbar) folgt automatisch: (Wenn die
> Quersumme einer Zahl durch 10 teilbar ist, dann ist die
> Zahl durch 5 teilbar).
Anscheinend hast du in der ursprünglichen Formel gedanklich ein wenig (unberechtigterweise) umgeklammert?
> Das ist RICHTIG, denn wenn die Quersumme durch 10 teilbar
> ist, ist sie ja auch durch 5 teilbar.
>
> Beide Aussagen an sich sind falsch, aber die
> SCHLUSSFOLGERUNG ist RICHTIG.
>
> Wäre jetzt die Gesamtaussage (1) eine allgemeingültige
> Aussage, könnte man daraus folgern:
>
> Also gilt: (Wenn die Quersumme einer Zahl durch 5 und durch
> 10 teilbar ist, dann ist die Zahl durch 5 teilbar).
Nein. Ich erkenne keinen Bezug zu (1).
> Dieser Schluss ist aber FALSCH, obwohl die SCHLUSSFOLGERUNG
> oben richtig war (wobei aber die einzelnen Aussagen falsch
> sind).
Viele Grüße
Tobias
|
|
|
| |
|
Ja, du hast Recht, ich habe die Klammern bei der 1. Aussage falsch gelesen - Sorry!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:32 Fr 08.04.2016 | | Autor: | tobit09 |
Hallo sissile!
> Verstehe ich richtig, dass X,Y,Z Variablen sind?
Ja. Und zwar vermutlich paarweise verschiedene.
> Eine Formel [mm]\psi[/mm] heißt allgemeingültin, wenn [mm]\beta \models \psi[/mm]
> für jede Belegung [mm]\beta.[/mm]
Genau.
> Ich glaube ich mache das zu kompliziert! Gibt es eine
> einfachere Methode? Sieht man das irgendwie sofort?
>
> Für (1)
> Ich habe zuerst (1) umgeschrieben indem ich die
> Folgerungspfeile übersetzt habe.
Dieses Auflösen der Folgerungspfeile erscheint mir die Aufgabe zu verkomplizieren.
Ihr wisst ja aus einer anderen Aufgabe, dass [mm] $\beta\models \psi\rightarrow\phi$ [/mm] für Formeln [mm] $\psi$ [/mm] und [mm] $\phi$ [/mm] genau dann gilt, wenn gilt:
"Wenn [mm] $\beta\models\psi$, [/mm] dann [mm] $\beta\models\phi$."
[/mm]
Damit lässt sich arbeiten, ohne die Folgerungspfeile aufzulösen.
> [mm]\neg ((X\rightarrow[/mm] Z) [mm]\wedge \neg((Y\rightarrow Z)\rightarrow[/mm]
> ((X [mm]\vee[/mm] Y) [mm]\rightarrow[/mm] Z)))
> [mm]\neg (\neg(X \wedge \neg[/mm] Z) [mm]\wedge \neg(\neg (Y\rightarrow[/mm]
> Z) [mm]\wedge \neg((X\vee[/mm] Y) [mm]\rightarrow[/mm] Z)))
> [mm]\neg(\neg(X \wedge \neg[/mm] Z) [mm]\wedge \neg(\neg \neg[/mm] (Y [mm]\wedge \neg[/mm]
> Z) [mm]\wedge \neg \neg[/mm] ((X [mm]\vee[/mm] Y) [mm]\wedge \neg[/mm] Z)))
> Frage Soll ich zwischen den Ausdrücken ein "=" setzen?
> Natürlich ist mir klar, dass die Ausdrücke dasselbe
> bedeuten - aber ich weiß nicht ob das so üblich ist.
>
> Und nun habe ich [mm]\beta \models[/mm] (1) Schritt für Schritt
> übersetzt mit unseren Definitionen:
> [mm]\beta \models[/mm] (1) [mm]gdw.\beta \not\models (\neg(X \wedge \neg[/mm]
> Z) [mm]\wedge \neg(\neg \neg[/mm] (Y [mm]\wedge \neg[/mm] Z) [mm]\wedge \neg \neg[/mm]
> ((X [mm]\vee[/mm] Y) [mm]\wedge \neg[/mm] Z)))
> gdw. [mm]\beta \not\models (\neg[/mm] (X [mm]\wedge \neg[/mm] Z) oder [mm]\beta \not\models \neg( \neg \neg(Y \wedge \neg[/mm]
> Z) [mm]\wedge \neg \neg[/mm] ((X [mm]\vee[/mm] Y) [mm]\wedge \neg[/mm] Z )))
> gdw. [mm]\beta \models(X \wedge \neg[/mm] z) oder [mm]\beta \models (\neg \neg[/mm]
> (Y [mm]\wedge \neg[/mm] Z) [mm]\wedge \neg \neg[/mm] ((X [mm]\vee[/mm] Y) [mm]\wedge \neg[/mm]
> Z))
> gdw. [mm][\beta \models[/mm] X und [mm]\beta \not\models[/mm] Z] oder [
> [mm]\beta \models \neg \neg(y \wedge \neg[/mm] Z) und [mm]\beta \models \neg \neg[/mm]
> ((x [mm]\vee[/mm] Y) [mm]\wedge \neg[/mm] z))]
> gdw. [mm][\beta \models[/mm] X und [mm]\beta \not\models[/mm] Z] oder
> [mm][(\beta \models[/mm] Y und [mm]\beta \not\models[/mm] Z) und [mm](\beta \models[/mm]
> (x [mm]\vee[/mm] y) und [mm]\beta \not\models[/mm] Z)]
> [mm]gdw.[\beta \models[/mm] X und [mm]\beta \not\models[/mm] Z] oder [mm][(\beta \models[/mm]
> Y und [mm]\beta \not\models[/mm] Z) und [mm]((\beta \models[/mm] X oder [mm]\beta \models[/mm]
> Y) und [mm]\beta \not\models[/mm] Z))]
> gdw. [mm][\beta \models[/mm] X und [mm]\beta \not\models[/mm] Z] oder
> [mm][[\beta \models[/mm] Y und [mm]\beta \not\models[/mm] Z] und [mm][\beta \models[/mm]
> X und [mm]\beta \not\models[/mm] Z]]
>
> Also ist (1) für [mm]\beta \not\models[/mm] X falsch und deshalb
> nicht allgemeingültig.
Du hast dich anscheinend irgendwo unterwegs vertan. Leider habe ich keine Lust, mich hier auf die Fehlersuche zu begeben.
> Für (2) hab ich genauso gemacht und kam auf
> [mm]\beta \models[/mm] (2) gdw. [mm][\beta \models[/mm] X und [mm]\beta \not\models[/mm]
> Y] oder [mm][\beta \models[/mm] X oder [mm]\beta \not\models[/mm] Y oder
> [mm]\beta \not\models[/mm] X]
>
> D.h. die Formel ist allgemeingültig.
Ja.
> Da für [mm]\beta \models[/mm]
> X und für [mm]\beta \models[/mm] Y die Formel gültig ist.
Du meinst vermutlich: Sowohl im Falle [mm] $\beta\models [/mm] X$ als auch im Falle [mm] $\beta\not\models [/mm] X$ gilt [mm] $\beta\models [/mm] (2)$.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:53 So 17.04.2016 | | Autor: | sissile |
Danke,
Ja Wahrheitstabellen sind wirklich praktischer!
Der Fehler war eine falsche Klammernsetzung am Anfang.
LG,
sissi
|
|
|
|
