www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Diskrete Mathematik" - Relationen
Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Relationen: Hilfe, Tipp, Korrektur
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 17:57 Sa 19.04.2014
Autor: DieNase

Aufgabe
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.

auf jedenfall sind da alle kombinationen drinnen. Würde man eine Wahrheitstabelle nehmen y und z auftragen und dann sich den logischen werte von den funktionen  y und z anschauen. würde für a das folgendes bedeuten.

Teile die Menge M so auf das wenn der wert von formeln gleich ist sie eine Äquivalenzklasse bilden. Meiner meinung nach tut das genau a [mm] \gdw [/mm] b tautologie :-)

Mein problem ist wie beweis ich das? Reicht es wenn ich sage: aRa weil eine wahreitstaffel spalte zu sich selbst ist immer eine tautologie. wenn man sie a [mm] \gdw [/mm] a betrachtet oder was müsste ich da hinschreiben? muss ich was rechnen?

a [mm] \gdw [/mm] b -> b [mm] \gdw [/mm] a. Ja weil [mm] \gdw [/mm] kommutativ ist! (reicht das oder muss ich mehr sagen?

a [mm] \gdw [/mm] b ^ b [mm] \gdw [/mm] c -> a [mm] \gdw [/mm] c. Also ich sage einfach wenn a [mm] \gdw [/mm] b dann liefert a und b den selben output und b und c auch somit liefert a und c auch den selben output.

Wie gesagt mir fehlts an beweisen :-) Ich habe mir b durchgelesen aber noch net genau überlegt weil ich zuerst mal gern wissen würde wie beweise ich sowas ^^. Danach hat sich das aber doch logisch angehört was da stand ;-)

        
Bezug
Relationen: Definition Tautologie?
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
Relationen: Tautologie
Status: (Mitteilung) Reaktion unnötig Status 
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.


Bezug
                        
Bezug
Relationen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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



Bezug
                                
Bezug
Relationen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

Bezug
                                        
Bezug
Relationen: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
        
Bezug
Relationen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de