Axiomensystem < Prädikatenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:53 Fr 16.10.2009 | | Autor: | extasic |
| Aufgabe | Gegeben sie das formale System L mit dem Alphabet {0,1} und mit den Theoremen T(L), die gebildet werden durch das Axiom 0101 und die folgenden 4 Inferenzregeln:
1. Zwei Nullen dürfen durch eine 0 ersetzt werden (a 00 b -> a 0 b)
2. Eine Eins darf durch die Teilfolge 010 ersetzt werden (a 1 b -> a 010 b)
3. Mit Null beginnende Folgen dürfen verdoppelt werden ( 0 a -> 0 a 0 a)
4. Teilfolgen 101 dürfen invertiert werden ( a 101 b -> a 010 b)
Aufgabe a)
Beweisen oder widerlegen Sie: 010111 ist nicht ableitbar, also 010111 [mm] \not\in [/mm] T(L)
Aufgabe b)
Eine Formel dieses Systems wird als "wahr" betrachtet wenn die Anzahl der Einsen gerade ist, sonst als "falsch".
Die Menge aller wahren Formeln sei W.
Geben Sie ein einfaches formales System L' mit einem oder mehreren Axiomen sowie Inferenzregeln an, so dass die Theoreme von L' gerade mit den wahren Formeln übereinstimmen, also T(L') = W. |
Meine Überlegungen:
Zu Aufgabe a)
Das Theorem 010111 ist nicht ableitbar.
Beweisidee:
Es sind im Grundaxiom keine doppelten 1er vorhanden. Mit den gegebenen Regeln ist es nicht möglich, 2 oder mehr 1en am Stück zu erzeugen.
Beweis:
Ausgangstheorem ist das Grundaxiom von L 0101.
Die 1. Regel kann nicht angewandt werden (keine doppelten 0er).
2. Regel -> 00100 oder 010010.
=> Keine doppelten 1er. Die doppelten 0en können zwar zu Einer zusammengestrichen, aber nicht ganz entfernt werden.
3. Regel -> 0101 0101
=> Siehe 2. Regel
4. Regel -> 0010
=> Siehe 2. Regel.
Somit kann aus keiner der Grundregeln eine Form gewonnen werden, die in die Zielform umgewandelt werden kann.
Zu Aufgabe b)
Die Regeln 1. - 3. können angewandt werden, ohne dass sich der "Wahrheitswert" des Theorems ändert. R4 hingegen invertiert den Wahrheitswert.
Somit besteht das Zielsystem aus dem Grundaxiom sowie den Inferenzregel 1. - 3..
Was sagt ihr zu meinen Lösungsvorschlägen?
Vielen Dank im Voraus für eure Hilfe!
|
|
| |
|
> Gegeben sie das formale System L mit dem Alphabet {0,1} und
> mit den Theoremen T(L), die gebildet werden durch das Axiom
> 0101 und die folgenden 4 Inferenzregeln:
>
> 1. Zwei Nullen dürfen durch eine 0 ersetzt werden (a 00 b
> -> a 0 b)
> 2. Eine Eins darf durch die Teilfolge 010 ersetzt werden
> (a 1 b -> a 010 b)
> 3. Mit Null beginnende Folgen dürfen verdoppelt werden (
> 0 a -> 0 a 0 a)
> 4. Teilfolgen 101 dürfen invertiert werden ( a 101 b -> a
> 010 b)
>
> Aufgabe a)
>
> Beweisen oder widerlegen Sie: 010111 ist nicht ableitbar,
> also 010111 [mm]\not\in[/mm] T(L)
>
> Aufgabe b)
>
> Eine Formel dieses Systems wird als "wahr" betrachtet wenn
> die Anzahl der Einsen gerade ist, sonst als "falsch".
> Die Menge aller wahren Formeln sei W.
> Geben Sie ein einfaches formales System L' mit einem oder
> mehreren Axiomen sowie Inferenzregeln an, so dass die
> Theoreme von L' gerade mit den wahren Formeln
> übereinstimmen, also T(L') = W.
> Meine Überlegungen:
>
> Zu Aufgabe a)
>
> Das Theorem 010111 ist nicht ableitbar.
>
> Beweisidee:
>
> Es sind im Grundaxiom keine doppelten 1er vorhanden. Mit
> den gegebenen Regeln ist es nicht möglich, 2 oder mehr 1en
> am Stück zu erzeugen.
>
> Beweis:
>
> Ausgangstheorem ist das Grundaxiom von L 0101.
>
> Die 1. Regel kann nicht angewandt werden (keine doppelten
> 0er).
>
> 2. Regel -> 00100 oder 010010.
>
> => Keine doppelten 1er. Die doppelten 0en können zwar zu
> Einer
du meinst zu einzeln stehenden Nullen
> zusammengestrichen, aber nicht ganz entfernt werden.
>
> 3. Regel -> 0101 0101
>
> => Siehe 2. Regel
>
> 4. Regel -> 0010
>
> => Siehe 2. Regel.
>
> Somit kann aus keiner der Grundregeln eine Form gewonnen
> werden, die in die Zielform umgewandelt werden kann.
>
> Zu Aufgabe b)
>
> Die Regeln 1. - 3. können angewandt werden, ohne dass sich
> der "Wahrheitswert" des Theorems ändert. R4 hingegen
> invertiert den Wahrheitswert.
>
> Somit besteht das Zielsystem aus dem Grundaxiom sowie den
> Inferenzregel 1. - 3..
>
>
> Was sagt ihr zu meinen Lösungsvorschlägen?
Hallo extasic,
bei Aufgabe a) hast du wohl die richtige Idee gefunden.
Bei b) denke ich aber, dass wohl ein einfacheres System
gesucht ist als das, das man erhält, wenn man einfach
R4 weglässt.
Überdies wäre es ja denkbar, dass man im System L
"wahre" Formeln erzeugen kann, in deren Bildung
auch R4 verwendet wird und welche ohne R4 nicht
entstehen könnten. Ob so etwas hier wirklich möglich
ist, weiß ich allerdings (noch) nicht, denn ich habe
mich noch nicht richtig in das Ganze vertieft.
Vielleicht muss man mit den Regeln noch etwas mehr
spielen, um einen einfachen Ansatz zu finden.
LG Al-Chw.
|
|
|
| |
|
> > Gegeben sie das formale System L mit dem Alphabet {0,1} und
> > mit den Theoremen T(L), die gebildet werden durch das Axiom
A1: 0101
> > und die folgenden 4 Inferenzregeln:
> > R1: Zwei Nullen dürfen durch eine 0 ersetzt werden
(a 00 b -> a 0 b)
> > R2: Eine Eins darf durch die Teilfolge 010 ersetzt werden
(a 1 b -> a 010 b)
> > R3: Mit Null beginnende Folgen dürfen verdoppelt werden
( 0 a -> 0 a 0 a)
> > R4: Teilfolgen 101 dürfen invertiert werden
( a 101 b -> a 010 b)
> > Aufgabe b)
> >
> > Eine Formel dieses Systems wird als "wahr" betrachtet wenn
> > die Anzahl der Einsen gerade ist, sonst als "falsch".
> > Die Menge aller wahren Formeln sei W.
> > Geben Sie ein einfaches formales System L' mit einem oder
> > mehreren Axiomen sowie Inferenzregeln an, so dass die
> > Theoreme von L' gerade mit den wahren Formeln
> > übereinstimmen, also T(L') = W.
> > Meine Überlegungen:
> > Zu Aufgabe b)
> >
> > Die Regeln 1. - 3. können angewandt werden, ohne dass sich
> > der "Wahrheitswert" des Theorems ändert. R4 hingegen
> > invertiert den Wahrheitswert.
> >
> > Somit besteht das Zielsystem aus dem Grundaxiom sowie den
> > Inferenzregeln 1. - 3..
> >
> > Was sagt ihr zu meinen Lösungsvorschlägen?
>
>
> Hallo extasic,
>
> bei Aufgabe a) hast du wohl die richtige Idee gefunden.
>
> Bei b) denke ich aber, dass wohl ein einfacheres System
> gesucht ist als das, das man erhält, wenn man einfach
> R4 weglässt.
> Überdies wäre es ja denkbar, dass man im System L
> "wahre" Formeln erzeugen kann, in deren Bildung
> auch R4 verwendet wird und welche ohne R4 nicht
> entstehen könnten. Ob so etwas hier wirklich möglich
> ist, weiß ich allerdings (noch) nicht, denn ich habe
> mich noch nicht richtig in das Ganze vertieft.
siehe unten !
>
> Vielleicht muss man mit den Regeln noch etwas mehr
> spielen, um einen einfachen Ansatz zu finden.
>
>
> LG Al-Chw.
Guten Morgen !
Ich meine, eine Formel gefunden zu haben, welche:
1.) in L herleitbar ist
2.) "wahr" ist
3.) ohne die Regel R4 nicht herleitbar ist
Diese Formel ist: 010101010101
Ohne R4 kann sie nicht hergeleitet werden, denn:
A1 enthält zwei Einsen
R1 und R2 verändern die Anzahl der Einsen nicht
R3 verdoppelt die Anzahl der Einsen
Somit wird klar, dass man mittels A1,R1,R2 und R3
nur solche Folgen erzeugen kann, bei denen die
Anzahl der Einsen von der Form [mm] $\blue{2^n}$ [/mm] mit [mm] $\blue{n\in\IN}$ [/mm] ist.
Die Zahl 6 hat aber nicht diese Form.
Man kann jedoch mit Zuhilfenahme von R4 leicht
eine Herleitung obiger Formel hinschreiben.
In diesem Sinne ist also R4 notwendig, um jene
"wahren" Formeln herzuleiten, in welchen die
Anzahl der Einsen zwar gerade, aber keine Zweier-
potenz ist.
Gruß Al
|
|
|
| |
|
> Gegeben sie das formale System L mit dem Alphabet {0,1} und
> mit den Theoremen T(L), die gebildet werden durch das Axiom
> 0101 und die folgenden 4 Inferenzregeln:
>
> 1. Zwei Nullen dürfen durch eine 0 ersetzt werden (a 00 b -> a 0 b)
> 2. Eine Eins darf durch die Teilfolge 010 ersetzt werden (a 1 b -> a 010 b)
> 3. Mit Null beginnende Folgen dürfen verdoppelt werden (0 a -> 0 a 0 a)
> 4. Teilfolgen 101 dürfen invertiert werden ( a 101 b -> a 010 b)
> Aufgabe b)
>
> Eine Formel dieses Systems wird als "wahr" betrachtet wenn
> die Anzahl der Einsen gerade ist, sonst als "falsch".
> Die Menge aller wahren Formeln sei W.
> Geben Sie ein einfaches formales System L' mit einem oder
> mehreren Axiomen sowie Inferenzregeln an, so dass die
> Theoreme von L' gerade mit den wahren Formeln
> übereinstimmen, also T(L') = W.
>
> Zu Aufgabe b)
>
> Die Regeln 1. - 3. können angewandt werden, ohne dass sich
> der "Wahrheitswert" des Theorems ändert. R4 hingegen
> invertiert den Wahrheitswert.
>
> Somit besteht das Zielsystem aus dem Grundaxiom sowie den
> Inferenzregel 1. - 3..
Hallo,
soweit ich mir das bisher zurechtgelegt habe, sind die
"wahren" Formeln des Systems L' die mit den folgen-
den Eigenschaften:
1.) Am Anfang steht eine Null
2.) es kommt eine positive, gerade Anzahl von Einsen vor
3.) es gibt keine benachbarten Einsen
(die Anzahl der zusätzlichen Nullen, die man irgendwo
noch einschiebt oder am Schluss anhängt, ist einerlei)
Ich hoffe, dass ich dabei nichts wesentliches übersehen
habe.
Für die Konstruktion aller möglichen "wahren" Formeln
von L' sollte ein einfaches formales System ausreichen.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:24 Sa 17.10.2009 | | Autor: | extasic |
Danke für die vielen Antworten!
Ich bin mir nicht ganz sicher, aber könnte folgendes richtig sein?
Grundaxiom: 0
R1: 0 <-> 00 (bidirektional)
(eine 0 darf durch 2 x 0 und umgekehrt ersetzt werden)
R2: 0 -> 0101
(eine 0 darf durch 0101 ersetzt werden)
|
|
|
| |
|
> Danke für die vielen Antworten!
>
> Ich bin mir nicht ganz sicher, aber könnte folgendes
> richtig sein?
>
> Grundaxiom: 0
>
> R1: 0 <-> 00 (bidirektional)
>
> (eine 0 darf durch 2 x 0 und umgekehrt ersetzt werden)
>
> R2: 0 -> 0101
>
> (eine 0 darf durch 0101 ersetzt werden)
Hallo extasic,
so wie ich es sehe, kann man "0" im System L nicht
herleiten, also kann "0" auch kein Axiom im Raum
der "wahren" Formeln von L sein.
Eine "wahre" Formel in L muss mindestens zwei
Einsen enthalten, denn in L ist es unmöglich, eine
Formel mit weniger als einer 1 zu erzeugen, und
eine "wahre" Formel soll ja eine gerade Anzahl
von Einsen enthalten. Da diese Anzahl nicht 0
sein kann, muss sie also mindestens 2 betragen.
Die Formel "010" mit nur einer Eins ist zwar in L
herleitbar, aber nicht "wahr".
Die "wahren" Formeln sind also, wie ich es schon
früher angedeutet habe, genau jene, welche
1.) mit einer 0 beginnen
2.) eine Anzahl 2*n (mit [mm] n\in\IN) [/mm] Einsen enthalten
3.) keine benachbarten Einsen enthalten
Das kann man erreichen, wenn man vom gleichen
Axiom A1 wie vorher ausgeht:
A1: 0101
und die folgenden Inferenzregeln S1 und S2 benützt:
S1: a -> a 0101
S2: a b -> a 0 b
S1 besagt, dass man an jede (wahre) Formel "0101"
anhängen darf und damit wieder zu einer wahren
Formel kommt.
S2 besagt, dass man in jeder wahren Formel an be-
liebiger Stelle (auch zuvorderst oder zuhinterst) eine
Null einfügen kann und damit wieder eine wahre
Formel erzeugt. Bemerkung zum genaueren Verständnis:
a oder b können auch für den leeren String [mm] \{\} [/mm] stehen,
allerdings nicht beide gleichzeitig, da ja der leere String
nicht zu den herleitbaren Formeln und schon gar nicht
zu den "wahren" Formeln gehört.
LG Al-Chw.
|
|
|
|
