Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Beweis/ Induktion (http://www.informatikerboard.de/board/thread.php?threadid=409)

Geschrieben von newsys am 27.04.2008 um 12:24:

  Beweis/ Induktion

Hallo,

ich soll dies Beweisen grad(F) < |F|
Habe keine Ahnung wie ich das machen muss....hhhiiilllfeee


Geschrieben von Tobias am 27.04.2008 um 12:28:

 

Immer wieder gerne sage ich: Wenn ihr Fragen stellt, dann geht NICHT davon aus, dass jeder jede Definition so kennt, wie ihr sie eingeführt habt. Und auch ein bisschen Kontext wäre schön.

Also:

Was ist F, was ist grad(.), was ist |.| ?


Geschrieben von newsys am 27.04.2008 um 17:04:

 

Hier die komplette Aufgabenstellung:

Zeigen Sie durch strukturelle Induktion über den Aufbau von Formeln, dass gilt
grad(F) < |F|
Dabei bezeichnet |F| die Länge (Anzahl der Zeichen) in F.

Ich kenne den Aufbau einer Induktion aber anwenden ist wieder eine andere Sache. Induktionsanfang: für einen speziellen Wert und dann die Behauptung, dann der Ind.schritt.


Geschrieben von newsys am 27.04.2008 um 17:45:

 

Als Induktionsanfang habe ich das hier:
[latex]$A\in\mathcal{AS}_{AL}, F=A\\ grad(A)=grad_{\mathcal{AS}}(A)=0<1=\mid F\mid[/latex]

Ist das so richtig? Und wie mache ich weiter??????


Geschrieben von Tobias am 27.04.2008 um 18:27:

 

Du magst den Aufbau der Formeln kennen, ich hingegen weiß noch nichtmal, von welchen Formeln du redest. Wie ist also der Aufbau der Formeln definiert.

Was ist grad(F) einer Formel F?


Geschrieben von newsys am 27.04.2008 um 18:32:

 

Das weiß ich auch nicht. Das was ich in den Anfang geschrieben habe ist das einzige was ich darüber gefunden habe...


Geschrieben von Tobias am 27.04.2008 um 18:53:

 

Und wo hast du die Aufgabe dann her? Ist die vom Himmel gefallen? Du musst doch wenigstens wissen, um welche Formeln es sich handelt (Aussagenlogik, Prädikatenlogik, Arithmetische Formeln, ...)?

Und wie soll man ohne Definition von "grad" eine Induktion führen?


Geschrieben von newsys am 27.04.2008 um 19:52:

 

Ok also Thema Aussagenlogik weiteres weiß ich wirklich nicht. Die komplette Aufgabe habe ich hingehschrieben...


Geschrieben von Tobias am 28.04.2008 um 13:25:

 

Also irgendwie nehme ich dir das nicht ab. Immerhin hast du hier:

Zitat:
[latex]$A\in\mathcal{AS}_{AL}, F=A\\ grad(A)=grad_{\mathcal{AS}}(A)=0<1=\mid F\mid[/latex]


schon grad(A) = 0 aufgeschrieben. Wo hast du das denn her?
Noch meinem Kenntnisstand kann man grad auch durch Bratwurst oder Pommes ersetzen. Beweis mal:

Bratwurst(F) <= |F|


Forensoftware: Burning Board, entwickelt von WoltLab GmbH