Logik - Strukturelle Induktion

24.10.2011, 20:00

MoeMoeson

Logik - Strukturelle Induktion

Meine Frage:
Hey leute, ich muss leider ne richtige Bombe hier rauslassen, weil ich am Tag der letzten Vorlesung gefehlt habe und aus den Folien nicht schlau werde.

Zitat:

2. Beweisen Sie mittels vollst¨andiger Induktion ¨uber den Aufbau (struktureller Induktion), dass jeder
aussagenlogische Ausdruck auf eine schließende Klammer oder eine Variable endet.

In der Vorlesung fiel nichtmal das Wort Induktion.
Ich weiß was eine vollständige Induktion in Mathe ist. Aber eine Strukturelle in Logik? und wie beweis ich so eine Aussage?

Für einen Ansatz wäre ich sehr dankbar!

Meine Ideen:
Aussagenlogischer Ausdruck - De nition
i) Jede Variable pi, i 2 N, ist ein aussagenlogischer Ausdruck
uber V .
ii) Sind A und B aussagenlogische Ausdrucke uber V , so sind auch
!A, A $\begin{eqnarray*} \wedge \end{eqnarray*}$ B, A $\begin{eqnarray*} \vee \end{eqnarray*}$ B, A $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ B, A<->B.
iii)Ein Wort uber V ist nur dann ein aussagenlogischer Ausdruck uber V ,
falls dies aufgrund endlich oftmaliger Anwendung von i) und ii) der Fall ist.

Meine Idee einer Induktion wäre jetzt gewesen, zu zeigen das i) bei einer Aussage wahr ist und bei ii) wahr bleibt. Aber keine Idee, wie man das hier ummünzen kann.

24.10.2011, 20:12

galoisseinbruder

Auf diesen Beitrag antworten »

Deine Idee ist gut, siehe hier.

24.10.2011, 20:23

MoeMoeson

Auf diesen Beitrag antworten »

hab ich bereits gesehn. aber ich versteh nichtmal im ansatz wie ich damit beweisen soll, das so ein ALA immer mit einer klammer endet.

24.10.2011, 20:27

galoisseinbruder

Auf diesen Beitrag antworten »

Dazu wäre nützlich zu wissen was in der Vorlesung mit schließender Klammer gemeint ist.

24.10.2011, 20:44

MoeMoeson

Auf diesen Beitrag antworten »

so wie ich es verstanden habe wortwörtlich ein ")".

24.10.2011, 20:50

galoisseinbruder

Auf diesen Beitrag antworten »

Wo ist denn z.B. hier

Zitat:

$\begin{eqnarray*} A \Rightarrow B \end{eqnarray*}$

die schließende Klammer?
Irgendwelche Regeln zur Klammersetzung müsst ihr ja aufgeschrieben haben.

24.10.2011, 20:59

MoeMoeson

Auf diesen Beitrag antworten »

ups, meine Fehler.

Und nein haben wir nicht. Ich hab dir die Vorlesung mal per PN geschrieben, da kannst du sehen, das wir es tatsächlich nicht haben.

so wäre es richtig:

!A, (A $\begin{eqnarray*} \wedge \end{eqnarray*}$ B), (A $\begin{eqnarray*} \vee \end{eqnarray*}$ B), (A $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ B), (A<->B).

24.10.2011, 21:08

galoisseinbruder

Auf diesen Beitrag antworten »

Zitat:

Original von MoeMoeson

!A, (A $\begin{eqnarray*} \wedge \end{eqnarray*}$ B), (A $\begin{eqnarray*} \vee \end{eqnarray*}$ B), (A $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ B), (A<->B).

Genau das ist der Punkt. Hier stehen die Klammern dabei und damit ist auch definiert wann Klammern gestezt werden, jeweils bei den letzten 4 Ausdrücken.
Beachte Seite 6 des Skripts zur Behandlung des non-Operators. (Das ist meines Erachtens inkonsistent, ich würde es als $\begin{eqnarray*} (\neg A) \end{eqnarray*}$ definieren)

Damit kannst du jetzt zeigen:
Die Aussage gelten für Terme der Form i)
Erfüllen A,B die Voraussetzungen dann auch alle Terme der Form ii)

24.10.2011, 21:12

MoeMoeson

Auf diesen Beitrag antworten »

verstehe!
vielen dank smile

Neue Frage »

Antworten »

Logik - Strukturelle Induktion

Verwandte Themen