Hi
ich hab ein problem mit der DNF.
ich möchte eine formel in eine DNF umwandeln. ich weiss aber nicht, ob bei einer DNF eine disjunktion nur als hauptoperator vorkommen darf oder ob beliebig viele vorkommen dürfen so lange keine konjunktion über einer disjunktion steht.
mit anderen worten darf die disjunktion nur in der obersten ebene stehen oder dürfte sie theoretisch auch in der 2. stehen?

ich weiss aber nicht, ob bei einer DNF eine disjunktion nur als hauptoperator vorkommen darf oder ob beliebig viele vorkommen dürfen so lange keine konjunktion über einer disjunktion steht.

Letzteres.

Es ist so:

Eine DNF besteht aus Disjunktionen von Konjunktionen.

Beispiel: ((A und B und C) oder (D und F))

Aber: Auch (A und B) ist eine DNF ,
da es ja äquivalent ist zu ((A und B) oder (A und B)).

Entsprechend wäre (A oder B) auch eine Disjunktion,
da man es auch schreiben kann als ((A und A) oder (B und B))

naja mit äquivalent würde ich da nicht argumentieren,
denn
(A und (B oder B)) ist auch äquivalent zu ((A und B) oder (A und B)),
aber keine DNF ;)

es ist ganz einfach die Definition:
über einem 'oder' darf kein 'und' stehen, fertig,
trifft auf alle Spezialfälle zu

Na ja klar.
Die Definiton aus dem Skript muss man schon wissen, ich wollte nur die Einzelfälle mal zeigen, weil die nicht im Skript stehen.

Logisch: Wenn Du unter ein "oder" ein weiteres "oder" packst, dann darfst Du die Klammern weglassen:

oder, um es in EBNF auszudruecken: eine DNF sieht folgendermassen aus:
DNF ::= '(' KONJ { 'oder' KONJ } ')' | WERT KONJ ::= '(' WERT { 'und' WERT } ')' | WERT WERT ::= Literal
MoKrates

jo, danke. dann hab ich es mir mit der dnf die ganze zeit komplizierter gemacht, als es eigentlich ist…

Logisch: Wenn Du unter ein "oder" ein weiteres "oder" packst, dann darfst Du die Klammern weglassen:
MoKrates

Gilt das auch für das "und" bei KNF?

ja das gilt für 'und' und 'oder' in jeder Formel

also gemeint ist:

(X und ((A -> C) und Z)) ist äquivalent zu (X und (A -> C) und Z)