Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 04:42 Mo 21.04.2014 | | Autor: | tobit09 |
Hallo DieNase!
Da ich euer Skript nicht vorliegen habe, zunächst eine Nachfrage, bevor ich dir weiterhelfen kann:
Wie habt ihr definiert, wann eine logische Formel "Tautologie" heißt? Bitte poste eure Definition wörtlich.
Ich hoffe, dieser Definition kann ich dann die bei euch verwendeten Notationen entnehmen.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:54 Mo 21.04.2014 | | Autor: | Trygve08 |
Eine Tautologie ist eine Aussageform, die für alle Belegungen richtig ist.
Z.B. ist a=a für alle a richtig.
a+a=a ist nur für a=0 richtig (wahr), also gehört zu dieser Aussageform die Lösungsmenge {0}.
a=a+1 hat bei den üblichen Zahlen keine Lösung, ist ein Widerspruch.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:34 Mo 21.04.2014 | | Autor: | tobit09 |
Hallo Trygve08!
Danke für deine Mühe.
Mir ist der Begriff einer Tautologie schon geläufig. Meine Frage an DieNase dient dazu, die in seiner/ihrer Vorlesung verwendeten Notationen im Zusammenhang mit logischen Formeln in Erfahrung zu bringen, um darauf eingehen zu können.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:28 Mi 23.04.2014 | | Autor: | DieNase |
ein genauen wortlaut hab ich nicht. Ich weiß lediglich das eine tautologie immer wahr ist. Wir arbeiten hauptsächlich mit wahrheitstaffeln und schreiben dabei so:
z |y|Tautologie|ergebnis1|ergebnis2
W |F|W | F | F
W |F|W | F | W
F |W|W | F | W
F |W|W | W | W
jetzt wollte ich folgendes machen in diesem Beispiel:
Die menge m ist eine kombination aus logischen aussagen von y und z so wie ich das verstanden habe sind alle möglichen kombinationen drin. Jetzt wollte ich so rangehen das in fall a) das bedeutet wenn 2 logische kombinationen das selbe ergebnis erbringen wird das ergebnis der Relation zur tautologie.
Nach meiner auffassung muss es daher [mm] 2^{4} [/mm] = 16 äquivalenzklassen geben.
jedoch ist bei mir jetzt das problem wie beweise ich nun das alles stimmt? Ich dachte mir so naja a<->a --> stimmt weil a aus M ist und a sicherlich die selbe wahrheitstafel haben wird.
a<->b dann auch b<->a Hier wollte ich drauf argumentieren das der operator <-> kommutativ ist (wird auf diesem übungsblatt in einem beispiel vorher gezeigt) das wollte ich also hier anwenden und sagen ja das stimmt da der operator kommutativ ist.
a<->b und b<->c dann a<->c
Hier wollte ich wieder auf die wahrheitstafel verweisen wenn a und b gleich sind und b gleich c ist so sind alle ergebnisse in der selben äquivalenzklasse. bsp b habe ich mir ähnlich überlegt. und Für c hätte ich so argumentiert:
Solange die repräsentaten nicht aus der selben äquivalenzklasse sind ändert sich nichts.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:54 Do 24.04.2014 | | Autor: | tobit09 |
> ein genauen wortlaut hab ich nicht. Ich weiß lediglich das
> eine tautologie immer wahr ist.
??? Du hast weder ein Skript noch schreibst du in der Vorlesung mit? Dann würde ich das dringend ändern!
> Wir arbeiten hauptsächlich
> mit wahrheitstaffeln und schreiben dabei so:
>
> z |y|Tautologie|ergebnis1|ergebnis2
> W |F|W | F | F
> W |F|W | F | W
> F |W|W | F | W
> F |W|W | W | W
Offenbar habt ihr schon definiert, was logische Formeln sind und wann logische Formeln Tautologie heißen.
(Beachte, dass z.B. [mm] $y\vee [/mm] z$ und [mm] $y\vee(y\vee [/mm] z)$ verschiedene logische Formeln sind, obwohl die dazugehörigen Wahrheitstafeln übereinstimmen.)
Da du mir offenbar eure Definition einer Tautologie nicht geben kannst, gebe ich dir nun eine (auch auf die Gefahr hin, dass meine Notationen nicht zu euren passen):
Für eine Belegung [mm] $\beta\colon\{y,z\}\to\{W,F\}$ [/mm] sei [mm] $\overline{\beta}(a)$ [/mm] für logische Formeln $a$ in den Variablen $y$ und $z$ wie folgt rekursiv definiert:
[mm] $\overline{\beta}(x):=\beta(x)$ [/mm] für [mm] $x\in\{y,z\}$.
[/mm]
[mm] $\overline{\beta}(\neg a):=\begin{cases}W,&\text{ falls }\overline{\beta}(a)=F\\F,&\text{sonst}\end{cases}$
[/mm]
[mm] $\overline{\beta}(a\vee b):=\begin{cases}W,&\text{ falls }\overline{\beta}(a)=W\text{ oder }\overline{\beta}(b)=W\\F,&\text{sonst}\end{cases}$
[/mm]
[mm] $\overline{\beta}(a\wedge b):=\begin{cases}W,&\text{ falls }\overline{\beta}(a)=W\text{ und }\overline{\beta}(b)=W\\F,&\text{sonst}\end{cases}$
[/mm]
[mm] $\overline{\beta}(a\rightarrow b):=\begin{cases}W,&\text{ falls gilt: Wenn }\overline{\beta}(a)=W\text{, dann }\overline{\beta}(b)=W\\F,&\text{sonst}\end{cases}$
[/mm]
[mm] $\overline{\beta}(a\Leftrightarrow b):=\begin{cases}W,&\text{ falls }\overline{\beta}(a)=\overline{\beta}(b)\\F,&\text{sonst}\end{cases}$.
[/mm]
Dann heißt eine logische Formel $a$ Tautologie, falls [mm] $\overline{\beta}(a)=W$ [/mm] für alle Belegungen [mm] $\beta\colon\{y,z\}\to\{W,F\}$ [/mm] gilt.
> jetzt wollte ich folgendes machen in diesem Beispiel:
> Die menge m ist eine kombination aus logischen aussagen
> von y und z so wie ich das verstanden habe sind alle
> möglichen kombinationen drin. Jetzt wollte ich so rangehen
> das in fall a) das bedeutet wenn 2 logische kombinationen
> das selbe ergebnis erbringen wird das ergebnis der Relation
> zur tautologie.
Ja. Für logische Formeln $a$ und $b$ ist [mm] $a\Leftrightarrow [/mm] b$ genau dann eine Tautologie, wenn [mm] $\overline{\beta}(a\Leftrightarrow [/mm] b)=W$ für alle Belegungen [mm] $\beta\colon\{y,z\}\to\{W,F\}$ [/mm] gilt, also nach Definition von [mm] $\overline{\beta}$ [/mm] genau dann, wenn [mm] $\overline{\beta}(a)=\overline{\beta}(b)$ [/mm] für alle Belegungen [mm] $\beta\colon\{y,z\}\to\{W,F\}$ [/mm] gilt.
Diese Überlegung, dass [mm] $a\Leftrightarrow [/mm] b$ genau dann Tautologie ist, wenn [mm] $\overline{\beta}(a)=\overline{\beta}(b)$ [/mm] für alle Belegungen [mm] $\beta\colon\{y,z\}\to\{W,F\}$ [/mm] gilt, ist entscheidend für die Aufgabenteile a) und c).
> Nach meiner auffassung muss es daher [mm]2^{4}[/mm] = 16
> äquivalenzklassen geben.
Es gibt in der Tat genau [mm] $2^4=16$ [/mm] Äquivalenzklassen.
> jedoch ist bei mir jetzt das problem wie beweise ich nun
> das alles stimmt? Ich dachte mir so naja a<->a --> stimmt
> weil a aus M ist und a sicherlich die selbe wahrheitstafel
> haben wird.
Ja. Formal: Sei [mm] $a\in [/mm] M$ beliebig vorgegeben. Für jede Belegung [mm] $\beta$ [/mm] gilt dann natürlich [mm] $\overline{\beta}(a)=\overline{\beta}(a)$. [/mm] Damit ist nach obiger Überlegung [mm] $a\Leftrightarrow [/mm] a$ eine Tautologie; also $aRa$. Da [mm] $a\in [/mm] M$ beliebig vorgegeben war, ist also $R$ reflexiv.
> a<->b dann auch b<->a Hier wollte ich drauf argumentieren
> das der operator <-> kommutativ ist (wird auf diesem
> übungsblatt in einem beispiel vorher gezeigt) das wollte
> ich also hier anwenden und sagen ja das stimmt da der
> operator kommutativ ist.
Zu zeigen ist, dass im Falle [mm] $a\Leftrightarrow [/mm] b$ eine Tautologie für gewisse [mm] $a,b\in [/mm] M$ auch [mm] $b\Leftrightarrow [/mm] a$ eine Tautologie ist. Nun habt ihr offenbar [mm] $\overline{\beta}(a\Leftrightarrow b)=\overline{\beta}(b\Leftrightarrow [/mm] a)$ für alle Belegungen [mm] $\beta\colon\{y,z\}\to\{W,F\}$ [/mm] gezeigt.
Seien nun [mm] $a,b\in [/mm] M$ mit [mm] $a\Leftrightarrow [/mm] b$ eine Tautologie, also [mm] $\overline{\beta}(a\Leftrightarrow [/mm] b)=W$ für alle Belegungen [mm] $\beta\colon\{y,z\}\to\{W,F\}$. [/mm] Dann mit dem von euch gezeigten für alle Belegungen [mm] $\beta\colon\{y,z\}\to\{W,F\}$:
[/mm]
[mm] $\overline{\beta}(b\Leftrightarrow a)=\overline{\beta}(a\Leftrightarrow [/mm] b)=W$.
Somit ist auch [mm] $b\Leftrightarrow [/mm] a$ eine Tautologie.
Damit ist gezeigt, dass $R$ symmetrisch ist.
> a<->b und b<->c dann a<->c
> Hier wollte ich wieder auf die wahrheitstafel verweisen
> wenn a und b gleich sind und b gleich c ist so sind alle
> ergebnisse in der selben äquivalenzklasse.
Seien [mm] $a,b,c\in [/mm] M$ mit [mm] $a\Leftrightarrow [/mm] b$ und [mm] $b\Leftrightarrow [/mm] c$ Tautologien. Es gilt also für alle Belegungen [mm] $\beta\colon\{y,z\}\to\{W,F\}$:
[/mm]
[mm] $\overline{\beta}(a)=\overline{\beta}(b)=\overline{\beta}(c)$.
[/mm]
Somit ist auch [mm] $a\Leftrightarrow [/mm] c$ eine Tautologie.
Also ist $R$ transitiv.
> bsp b habe ich
> mir ähnlich überlegt.
Falls du eine Korrektur wünschst, müsstest du deine Überlegungen posten... 
> und Für c hätte ich so
> argumentiert:
> Solange die repräsentaten nicht aus der selben
> äquivalenzklasse sind ändert sich nichts.
Vermutlich ist dir hier ein "nicht" zu viel "hereingerutscht" und du meintest eigentlich:
"Solange die Repräsentanten aus der selben Äquivalenzklasse sind, ändert sich nichts."
Genau das ist zu zeigen.
Seien [mm] $a,a'\in [/mm] A$ Repräsentanten von $A$ und [mm] $b,b'\in [/mm] B$ Repräsentanten von $B$.
Zu zeigen ist, dass im Falle [mm] $a\rightarrow [/mm] b$ eine Tautologie auch [mm] $a'\rightarrow [/mm] b'$ eine Tautologie ist.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 06:57 Do 24.04.2014 | | Autor: | tobit09 |
> 30. Sei M die Menge aller logischen Formeln in den
> Variablen y und z.
> (a) Man zeige, dass folgende Relation mit a, b [mm]\in[/mm] M eine
> Äquivalenzrelation ist: aRb genau dann, wenn a [mm]\gdw[/mm] b
> eine Tautologie ist.
> (b) Sei N die Menge der Äquivalenzklassen der obigen
> Äquivalenzrelation und A, B [mm]\in[/mm] N. Weiters sei a [mm]\in[/mm] M
> ein Repräsentant von A und b [mm]\in[/mm] M ein Repräsentant von
> B. Man zeige, dass folgende Relation eine Ordnungsrelation
> auf N ist:
> ARB genau dann, wenn a [mm]\to[/mm] b eine Tautologie ist .
> (c) Man zeige, dass sich diese Ordnung nicht ändert,
> wenn andere Reprasentanten gewählt werden
> Also ich hab mir das zu a) mal so überlegt. M ist also
> eine Menge aus logischen kombination von y und z. Also da
> ist sowas wie [mm]y^z,[/mm] aber auch nicht y [mm]\gdw[/mm] z drinen.
Etwas ungünstig ist, dass bei (a) und (b) verschiedene Relationen mit dem gleichen Buchstaben $R$ bezeichnet werden.
Aus meiner Sicht müsste (c) vor (b) stehen, denn in (c) wird erst gezeigt, dass die Relation aus (b) überhaupt wohldefiniert ist.
|
|
|
|
