Beweis, dass es zu jeder NNF eine logisch äquivalente KNF gibt |
12.11.2016, 11:39 | tehtacolord | Auf diesen Beitrag antworten » |
Beweis, dass es zu jeder NNF eine logisch äquivalente KNF gibt 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|