Biete KNF, suche DNF

Aufrufe: 126     Aktiv: 08.08.2021 um 15:05

0
Ich möchte KNF und DNF für folgende Formel finden: \( p\to(q\wedge\neg r) \)

Auf die KNF bin ich leicht gekommen mit der Definition des Implikationspfeils und dann Distributivgesetz:

\( p\to(q\wedge\neg r) \quad \equiv \quad \neg p\vee(q\wedge\neg r) \quad\equiv\quad (\neg p\vee q)\wedge(\neg p\vee\neg r) \).

Für die DNF habe ich einfach alle Variablen negiert, aus und oder und aus oder und gemacht. Leider war das wohl zu einfach, denn die Wahrheitstabelle liefert mir für die Ausgangsformel und die KNF in absteigender Reihenfolge 11110010, aber für die DNF das genaue Gegenteil 00001101 (Markierung). Die falsche DNF lautet:
\( (p\wedge\neg q)\vee(p\wedge r) \).

Meine Frage ist also, wie komme ich auf die DNF? Entweder von der KNF oder von der ursprünglichen Formel? Mein Gedanke war natürlich, einfach die DNF in eine riesige Klammer zu packen und zu negieren (wegen Markierung), doch ist das dann noch eine DNF? Theoretisch muss ich dann des Negationszeichen ja "reinziehen" und dann bin ich wieder bei der KNF...
Diese Frage melden
gefragt

Student, Punkte: 260

 
Kommentar schreiben
1 Antwort
0
In meiner Schreibweise:
\(p\rightarrow q \overline r\iff \overline p+q \overline r \iff \overline p(q+\overline q)(r+ \overline r)+q \overline r(p+ \overline p)\)
ausmultiplizieren und Dopplungen streichen
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 4.17K

 

Auch ein interessanter Ansatz. Mittlerweile habe ich herausgefunden, dass die Lösung erschreckend einfach ist und ich mir zu viel Gedanken gemacht habe. Die gesuchte DNF lautet:
\( p\to(q\wedge\neg r) \Longleftrightarrow \neg p \vee (q\wedge\neg r) \).
Das ist ja eine Disjunktion von Konjunktionen und man ist fertig.
  ─   akimboslice 08.08.2021 um 08:35

das ist aber keine disjunktive Normalform   ─   gerdware 08.08.2021 um 11:40

Ist es sehr wohl. Ist ja eine Disjunktion von Konjunktionen.   ─   cauchy 08.08.2021 um 12:11

In meinem Informatikstudium, das allerdings mehr als 30 Jahre zurückliegt (Fernuni Hagen), habe ich lernen müssen, dass in den Konjunktionen einer DNF alle Booleschen Variablen vorkommen müssen.   ─   gerdware 08.08.2021 um 14:56

Dann hast du das vermutlich falsch in Erinnerung. Das ist lediglich eine Hilfe zur Bildung der DNF, wenn man eine Wahrheitstabelle hat, weil man dann einfach die entsprechenden Belegungen, wo dann logischerweise jede Variable vorkommt, durch eine Disjunktion verbinden kann. Eine DNF ist jedoch nicht eindeutig, so dass es ausreicht, eine Disjunktion von Konjunktionen zu haben.   ─   cauchy 08.08.2021 um 15:05

Kommentar schreiben