struktureller Induktionsbeweis < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:09 Sa 23.04.2016 | | Autor: | Schmucus |
| Aufgabe | | Zeigen Sie: Für alle Teilformeln ψ von φ gilt: vars(ψ)⊆vars(φ). |
Leider hab ich gelinde gesagt einfach mal gar keinen Plan, wie ich da am besten vorgehen soll.
Naja, ich weiß immerhin, dass ich mit ner Basiswertezuordnung anfangen muss, also quasi vars( ⊤)=0, vars( ⊥)=0 und vars( Xi)=Xi mit i∈ℕ.
Aber wie geh ich am Besten weiter vor?
MfG Marcus
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.onlinemathe.de/forum/Beweis-per-struktureller-Induktion
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:11 Sa 23.04.2016 | | Autor: | hippias |
![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]")
Ich schlage vor, dass Du zunächst mitteilst, wie die Funktion $vars$ genau definiert ist und ebenso wie eine Teilformel einer Formel definiert ist. Daraus lässt sich dann ein Beweis für die Behauptung finden.
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 15:53 Sa 23.04.2016 | | Autor: | Schmucus |
Entschuldige bitte, da hätte ich natürlich selbst dran denken können... die Definitionen findet man hier:
http://stueckwerk-logik.uni-kiel.de/stuecke/induktiv-definierte-funktionen.html#ae7de6ddbe6010dc64aa5b604af1fa5e
So ist das Ganze denk ich mal deutlich übersichtlicher, als wenn ich das jetzt abschreibe.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:08 Sa 23.04.2016 | | Autor: | hippias |
Danke für den Link. Aber tatsächlich ging es mir darum, dass Du Dich ganz genau mit den Definitionen auseinandersetzt. Meistens beantworten sich Fragen dann von selbst. Ausserdem erlaubt es Dir präziser als "wie gehe ich vor?" zu fragen.
Also, unter der Annahme, dass Du die Definitionen genau kennst: worin genau besteht das Problem?
Kannst Du unter Verwendung der Definition [mm] $vars((X_{0}\vee [/mm] ( [mm] X_{1}\wedge \neg X_{0})))$ [/mm] bestimmen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:23 Sa 23.04.2016 | | Autor: | Schmucus |
Also ich versuche es erstmal:
$ [mm] vars((X_{0}\vee [/mm] ( [mm] X_{1}\wedge \neg X_{0}))) [/mm] $ = { [mm] X_{0} [/mm] } [mm] \cup [/mm] { [mm] X_{0}, X_{1} [/mm] } = { [mm] X_{0}, X_{1} [/mm] }
Das die Behauptung stimmt, kann ich schon nachvollziehen. Ich weiß nur eben nicht wie man sowas formal beweist, bzw. das will einfach bisher irgendwie nicht in meinen Kopf rein.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:04 Sa 23.04.2016 | | Autor: | tobit09 |
Hallo Schmucus und auch von mir ein herzliches !
> Zeigen Sie: Für alle Teilformeln ψ von φ gilt:
> vars(ψ)⊆vars(φ).
> Leider hab ich gelinde gesagt einfach mal gar keinen Plan,
> wie ich da am besten vorgehen soll.
Zeige per Induktion nach [mm] $\varphi$, [/mm] dass für alle Formeln [mm] $\varphi$ [/mm] gilt:
(*) Für alle Teilformeln [mm] $\psi$ [/mm] von [mm] $\varphi$ [/mm] gilt: [mm] $vars(\psi)\subseteq vars(\varphi)$.
[/mm]
Zu zeigen ist also:
1. Im Falle [mm] $\varphi=\top$ [/mm] und im Falle [mm] $\varphi=\bot$ [/mm] gilt jeweils (*).
2. Im Falle [mm] $\varphi=X_i$ [/mm] für eine natürliche Zahl i gilt (*) .
3. Im Falle [mm] $\varphi=J(\varphi_0,\ldots,\varphi_{n-1})$ [/mm] für einen n-stelligen Junktor und Formeln [mm] $\varphi_0,\ldots,\varphi_{n-1}$ [/mm] gilt: Ist für jedes [mm] $i=0,\ldots,n-1$ [/mm] die Bedingung (*) mit [mm] $\varphi_i$ [/mm] anstelle von [mm] $\varphi$ [/mm] erfüllt, so ist auch (*) erfüllt.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:23 Sa 23.04.2016 | | Autor: | Schmucus |
Danke überhaupt erstmal für eure Antworten. Ich schreib mal auf, was mir zu den von dir genannten Punkten einfällt.
1. [mm] vars(\top) [/mm] = [mm] \emptyset [/mm] = [mm] vars(\bot)
[/mm]
2 [mm] vars(X_i) [/mm] = [mm] {X_i}
[/mm]
[mm] \psi [/mm] = [mm] subf(\varphi) [/mm] = [mm] {X_i} \subseteq vars(X_i) [/mm] = [mm] {X_i}
[/mm]
3. hier ist jetzt der Punkt erreicht wo es hapert. Bei ner vollständigen Induktion würde ich hier ja einfach [mm] \varphi+1 [/mm] statt [mm] \varphi [/mm] einsetzen und ausrechnen. Aber das geht hier ja nicht.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:55 Sa 23.04.2016 | | Autor: | tobit09 |
Der Übersicht halber wiederhole ich wörtlich meinen "Beweisplan":
Zeige per Induktion nach $ [mm] \varphi [/mm] $, dass für alle Formeln $ [mm] \varphi [/mm] $ gilt:
(*) Für alle Teilformeln $ [mm] \psi [/mm] $ von $ [mm] \varphi [/mm] $ gilt: $ [mm] vars(\psi)\subseteq vars(\varphi) [/mm] $.
Zu zeigen ist also:
1. Im Falle $ [mm] \varphi=\top [/mm] $ und im Falle $ [mm] \varphi=\bot [/mm] $ gilt jeweils (*).
2. Im Falle $ [mm] \varphi=X_i [/mm] $ für eine natürliche Zahl i gilt (*) .
3. Im Falle $ [mm] \varphi=J(\varphi_0,\ldots,\varphi_{n-1}) [/mm] $ für einen n-stelligen Junktor und Formeln $ [mm] \varphi_0,\ldots,\varphi_{n-1} [/mm] $ gilt: Ist für jedes $ [mm] i=0,\ldots,n-1 [/mm] $ die Bedingung (*) mit $ [mm] \varphi_i [/mm] $ anstelle von $ [mm] \varphi [/mm] $ erfüllt, so ist auch (*) erfüllt.
> 1. [mm]vars(\top)[/mm] = [mm]\emptyset[/mm] = [mm]vars(\bot)[/mm]
Ja.
Wir wollen (*) zeigen z.B. für [mm] $\varphi=\top$. [/mm] (Der Nachweis für [mm] $\varphi=\bot$ [/mm] geht analog.)
Sei dazu [mm] $\psi$ [/mm] eine Teilformel von [mm] $\varphi=\top$. [/mm] (d.h. wie kann [mm] $\psi$ [/mm] nur aussehen nach Definition der Menge der Teilformeln von [mm] $\top$?).
[/mm]
Zu zeigen ist nun [mm] $vars(\psi)\subseteq vars(\varphi)$.
[/mm]
> 2 [mm]vars(X_i)[/mm] = [mm]\{X_i\}[/mm]
Ja. (Die geschweiften Klammern bekommst du hier im Forum sichtbar, indem du \{ bzw. \} eingibst.)
Sei dazu [mm] $\psi$ [/mm] eine Teilformel von [mm] $\varphi=X_i$. [/mm] (d.h. wie kann [mm] $\psi$ [/mm] nur aussehen nach Definition der Menge der Teilformeln von [mm] $X_i$ [/mm] ?).
Zu zeigen ist nun [mm] $vars(\psi)\subseteq vars(\varphi)$.
[/mm]
> [mm]\psi[/mm] = [mm]subf(\varphi)[/mm]
Es soll wohl heißen: [mm] $\psi\in subf(\varphi)$
[/mm]
> = [mm]\{X_i\} \subseteq vars(X_i)[/mm] = [mm]\{X_i\}[/mm]
Nicht falsch, aber nicht wirklich zielführend.
> 3. hier ist jetzt der Punkt erreicht wo es hapert. Bei ner
> vollständigen Induktion würde ich hier ja einfach
> [mm]\varphi+1[/mm] statt [mm]\varphi[/mm] einsetzen und ausrechnen. Aber das
> geht hier ja nicht.
Gelte $ [mm] \varphi=J(\varphi_0,\ldots,\varphi_{n-1}) [/mm] $ für einen n-stelligen Junktor und Formeln $ [mm] \varphi_0,\ldots,\varphi_{n-1} [/mm] $.
Gelte weiterhin (*) mit [mm] $\varphi_i$ [/mm] anstelle von [mm] $\varphi$ [/mm] für alle [mm] $i=0,\ldots,n-1$ [/mm] (also: Für alle Teilformeln [mm] $\psi$ [/mm] von jedem [mm] $\varphi_i$ [/mm] gilt:
(**) [mm] $vars(\psi)\subseteq vars(\varphi_i)$ [/mm] ).
Zu zeigen ist (*).
Wie kann [mm] $\psi$ [/mm] als Teilformel von [mm] $\varphi$ [/mm] aussehen nach Definition der Teilformeln von [mm] $\varphi=J(\varphi_0,\ldots,\varphi_{n-1})$ [/mm] ?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:41 Sa 23.04.2016 | | Autor: | Schmucus |
zu 1.
[mm] \psi \in subf(\top) [/mm] = [mm] \{\top\}
[/mm]
[mm] vars(\psi)\subseteq vars(\varphi) [/mm] enspricht also [mm] vars(\top) \subseteq vars(\top)
[/mm]
wie du schon sagst ist [mm] \varphi [/mm] = [mm] \top [/mm] analog
zu 2.
[mm] \psi \in subf(X_i) [/mm] = [mm] \{X_i\}
[/mm]
[mm] vars(\psi) [/mm] = [mm] vars\{X_i\} [/mm] = [mm] \{X_i\}
[/mm]
[mm] vars(\varphi) [/mm] = [mm] vars\{X_i\} [/mm] = [mm] \{X_i\}
[/mm]
daraus folgt [mm] \{X_i\} \subseteq \{X_i\}
[/mm]
zu 3.
[mm] \varphi [/mm] = [mm] J(\varphi_0,...,\varphi_(n-1))
[/mm]
[mm] \psi \in subf(\varphi) [/mm] = [mm] subf[J[\varphi_0,...,\varphi_(n-1)))
[/mm]
= [mm] \{J(\varphi_0,...,\varphi_(n-1))\} \cup \bigcup_{i
dann kann [mm] \psi [/mm] also auf einer der beiden "Seiten" der Vereinigung sein, also mache ich eine Fallunterscheidung:
Fall 1:
[mm] \psi \in \{J[\varphi_0,...,\varphi_(n-1))\}
[/mm]
dann ist [mm] \psi [/mm] = [mm] \varphi, [/mm] daher auch [mm] vars(\psi)\subseteq vars(\varphi)
[/mm]
Fall 2:
[mm] \psi \in \bigcup_{i
Und hier weiß ich jetzt leider wieder nicht, wie ich weiter machen soll.
Ich hoffe erstmal, dass das wenigstens nicht völliger Quatsch ist, was ich mir bis hier her zusammengereimt habe...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:19 So 24.04.2016 | | Autor: | hippias |
> zu 1.
>
> [mm]\psi \in subf(\top)[/mm] = [mm]\{\top\}[/mm]
> [mm]vars(\psi)\subseteq vars(\varphi)[/mm] enspricht also
> [mm]vars(\top) \subseteq vars(\top)[/mm]
>
> wie du schon sagst ist [mm]\varphi[/mm] = [mm]\top[/mm] analog
O.K.
>
>
> zu 2.
>
> [mm]\psi \in subf(X_i)[/mm] = [mm]\{X_i\}[/mm]
> [mm]vars(\psi)[/mm] = [mm]vars\{X_i\}[/mm] = [mm]\{X_i\}[/mm]
> [mm]vars(\varphi)[/mm] = [mm]vars\{X_i\}[/mm] = [mm]\{X_i\}[/mm]
>
> daraus folgt [mm]\{X_i\} \subseteq \{X_i\}[/mm]
Besser: weil [mm] $\{X_i\} \subseteq \{X_i\}$ [/mm] ist, folgt [mm] $vars(\psi)\subseteq vars(\phi)$.
[/mm]
>
>
> zu 3.
>
> [mm]\varphi[/mm] = [mm]J(\varphi_0,...,\varphi_(n-1))[/mm]
> [mm]\psi \in subf(\varphi)[/mm] =
> [mm]subf[J[\varphi_0,...,\varphi_(n-1)))[/mm]
> = [mm]\{J(\varphi_0,...,\varphi_(n-1))\} \cup \bigcup_{i
>
>
> dann kann [mm]\psi[/mm] also auf einer der beiden "Seiten" der
> Vereinigung sein, also mache ich eine Fallunterscheidung:
>
> Fall 1:
>
> [mm]\psi \in \{J[\varphi_0,...,\varphi_(n-1))\}[/mm]
> dann ist [mm]\psi[/mm]
> = [mm]\varphi,[/mm] daher auch [mm]vars(\psi)\subseteq vars(\varphi)[/mm]
>
> Fall 2:
> [mm]\psi \in \bigcup_{i
>
> Und hier weiß ich jetzt leider wieder nicht, wie ich
> weiter machen soll.
Genauer kannst man jetzt sagen, dass [mm] $\psi\in subf(\varphi_i)$ [/mm] für ein $i<n$ folgt. Weil [mm] $\varphi_i$ [/mm] von niedriger Stufe ist als [mm] $\varphi$, [/mm] kannst Du die Induktionsvoraussetzung auf [mm] $\psi$ [/mm] und [mm] $\varphi_{i}$ [/mm] anwenden. Damit folgt dann die Behauptung.
Statt Induktion nach dem Termaufbau könnte man hier auch Induktion nach der Länge des Terms durchführen, welche vielleicht etwas vertrauter ist. Jedoch ist Induktion nach dem Termaufbau schon wegen der Eleganz unbedingt lernenswert.
> Ich hoffe erstmal, dass das wenigstens nicht völliger
> Quatsch ist, was ich mir bis hier her zusammengereimt
> habe...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:01 So 24.04.2016 | | Autor: | Schmucus |
> Genauer kannst man jetzt sagen, dass $ [mm] \psi\in subf(\varphi_i) [/mm] $ für ein $ i<n $ folgt. Weil $ [mm] \varphi_i [/mm] $ von niedriger Stufe ist als $ [mm] \varphi [/mm] $, kannst Du die
> Induktionsvoraussetzung auf $ [mm] \psi [/mm] $ und $ [mm] \varphi_{i} [/mm] $ anwenden. Damit folgt dann die Behauptung.
Also das macht für mich immerhin schon mal Sinn, aber kannst du mir nochmal weiterhelfen wie man das formal richtig aufschreibt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:26 Mo 25.04.2016 | | Autor: | hippias |
Schreib Du es auf und zeige es hier; da kann man nicht viel falsch machen.
|
|
|
| |
|
Entschuldige bitte, dass ich mich für ein paar Tage nicht gemeldet hab.
Aber leider hatte ich in dieser Zeit noch immer keine Erleuchtung. Um ehrlich zu sein, hatte ich jetzt auch mit mehr als ein Tag überlegen noch keine Idee, wie der Schluss nun aussieht.
> Weil $ [mm] \varphi_i [/mm] $ von niedriger Stufe ist als $ [mm] \varphi [/mm] $, kannst Du die
> Induktionsvoraussetzung auf $ [mm] \psi [/mm] $ und $ [mm] \varphi_{i} [/mm] $ anwenden.
Genau an dem Schritt haperts. Mit Worten formuliert kann ich hier noch folgen, das wars dann aber auch.
Ich hoffe ich hab deine Geduld bis hierher noch nicht überstrapaziert 
MfG Marcus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Di 03.05.2016 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
