Beweis, dass es zu jeder NNF eine logisch äquivalente KNF gibt

Neue Frage »

tehtacolord Auf diesen Beitrag antworten »
Beweis, dass es zu jeder NNF eine logisch äquivalente KNF gibt
Meine Frage:
Hallo zusammen,

ich habe aktuell ein Problem mit einem Teil einer Vorlesung, in der folgendes Lemma formuliert wurde:

Zu jeder Formel in Negations-Normalform lässt sich eine logisch äquivalente Formel in Konjunktions-Normalform bilden.

Auf meine Nachfrage hin meinte die Dozentin nur, dass sei recht simpel induktiv über die Anzahl der Junktoren zu beweisen.
Ich habe jetzt mehrere Male die Vorlesungsfolien und das Kompaktskript auf der Suche nach Hinweisen dazu durchforstet, konnte aber bis jetzt keinen Ansatz entwickeln.

Könnte mir jemand auf die Sprünge helfen? Ich möchte nicht nach einer vollständigen Lösung fragen, aber grundlegende Ideen zum Lösungsansatz bekommen.

Besten Dank vorab.

Meine Ideen:
Formulierter Satz in der Vorlesung:

Es gibt aussagenlogische Formeln der Länge a(Index:n) der Länge 2n zu der jede logisch äquivalente Formel in KNF mindestens die Länge 2^n hat.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »