www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 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
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Aussagenlogik" - struktureller Induktionsbeweis
struktureller Induktionsbeweis < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Aussagenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

struktureller Induktionsbeweis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

        
Bezug
struktureller Induktionsbeweis: Antwort
Status: (Antwort) fertig Status 
Datum: 08:11 Sa 23.04.2016
Autor: hippias

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

Bezug
                
Bezug
struktureller Induktionsbeweis: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
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.

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

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

Bezug
        
Bezug
struktureller Induktionsbeweis: Antwort
Status: (Antwort) fertig Status 
Datum: 18:04 Sa 23.04.2016
Autor: tobit09

Hallo Schmucus und auch von mir ein herzliches [willkommenvh]!


> 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

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

Bezug
                        
Bezug
struktureller Induktionsbeweis: Antwort
Status: (Antwort) fertig Status 
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] ?

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

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


Bezug
                                                
Bezug
struktureller Induktionsbeweis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                                        
Bezug
struktureller Induktionsbeweis: Antwort
Status: (Antwort) fertig Status 
Datum: 08:26 Mo 25.04.2016
Autor: hippias

Schreib Du es auf und zeige es hier; da kann man nicht viel falsch machen.

Bezug
                                                                
Bezug
struktureller Induktionsbeweis: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 17:52 So 01.05.2016
Autor: Schmucus

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

Bezug
                                                                        
Bezug
struktureller Induktionsbeweis: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:20 Di 03.05.2016
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Aussagenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]