Was ist die Länge einer aussagenlogischen Formel, die n Vorkommnisse von 2-stelligen Junktoren und m Vorkommnisse eines 1-stelligen Junktors (Negation) hat? (m,n sind natürliche Zahlen einschließlich der 0)
Hinweis: Für eine Formel F seien:
l(F):Länge der Formel F;
b(F):Anzahl der Vorkommnisse 2-stelliger Junktoren in F;
und n(F):Anzahl der Vorkommnisse des Negationssymbols.
Man zeige durch Induktion über den Formelaufbau: l(F) = 4b(F) + n(F) + 1

Hi, ich versteh nicht was die 4 in dem Formelaufbau soll. Vier 2-stellige Junktoren? Warum?

kann mich da jemand erleuten?

mfg secret_student ;)

Mach Dir einfach ein Beispiel und rechne es durch: [img]http://mokrates.de/cgi-bin/texstring?(A%20%5Cland%20B)[/img] hat z.B. die Laenge 5.

und , oder , impli , biimpl

zweistellige junktoren, denke, die sollst du beweisen mit struk. induktion.

Man zeige durch Induktion über den Formelaufbau: l(F) = 4b(F) + n(F) + 1

Hi, ich versteh nicht was die 4 in dem Formelaufbau soll. Vier 2-stellige Junktoren? Warum?

Ich glaube, du hast da was falsch verstanden: "Formelaufbau"
bezieht sich nicht auf die Gleichung l(F) = 4b(F) + n(F) + 1,
sondern du sollst durch Induktion über den Formelaufbau
(und zwar den Aufbau der Formel F) beweisen, dass allgemein
die Gleichung l(F) = 4b(F) + n(F) + 1 gilt. Du sollst also
einen Zusammenhang zwischen der Länge einer Formel und der
Anzahl der in ihr vorkommenden Junktoren beweisen, und zwar
nach dem Verfahren der strukturellen Induktion.