Disjunktive Normalform < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:18 Sa 21.04.2012 | | Autor: | durden88 |
| Aufgabe | Sei [mm] \partial [/mm] die Formel [mm] ((A_0->A_1)\wedge(A_1->A_2)).
[/mm]
a) Finden Sie eine Formel in disjunktiver Normalform (DNF), die logisch äquivalent zu [mm] \partial [/mm] ist und ledilich die Disjunktion von der Konjunktionen ist.
b) Finden Sie eine Formel in konjunktiver Normalform (KNF), die logisch äquivalent zu [mm] \partial [/mm] ist. |
Halli Hallo,
also bei der a)
Es gilt ja: [mm] (A->B)=(\neg A\vee [/mm] B)
So dann hab ich mal umgestellt:
[mm] ((\neg A_0\vee A_1)\wedge(\neg A_1 \vee A_2))
[/mm]
Jetzt hab ich doch eigendlich schon die Aufgabe b erfüllt oder?
Jetzt habe ich mir gedacht, ich muss ja noch irgendwie die und und oder Zeichen umdrehen. So ziehe ich als erstes aus den inneren Formel ein negatives Zeichen raus und danach aus der gesamten Formel sodass ich dann auf folgendes komme:
[mm] \neg((A_0\wedge\neg A_1)\vee (A_1\wedge \neg A_2))
[/mm]
Um die Äquivalenz zu überprüfen, würde ich dann jetzt mit ner Wahrheitstafel vorgehen. Was ist denn mit ´´lediglich die Disjunktion von drei Konjunktionen ist´´ gemeint?
Danke im Voraus!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:50 Sa 21.04.2012 | | Autor: | tobit09 |
Hallo durden,
> also bei der a)
>
> Es gilt ja: [mm](A->B)=(\neg A\vee[/mm] B)
>
> So dann hab ich mal umgestellt:
>
> [mm]((\neg A_0\vee A_1)\wedge(\neg A_1 \vee A_2))[/mm]
>
> Jetzt hab ich doch eigendlich schon die Aufgabe b erfüllt
> oder?
Genau!
> Jetzt habe ich mir gedacht, ich muss ja noch irgendwie die
> und und oder Zeichen umdrehen.
Das ist in der Tat eine sinnvolle Möglichkeit. Nutze u.a. das Distributivgesetz (Theorem 2.22).
> So ziehe ich als erstes aus
> den inneren Formel ein negatives Zeichen raus und danach
> aus der gesamten Formel sodass ich dann auf folgendes
> komme:
>
> [mm]\neg((A_0\wedge\neg A_1)\vee (A_1\wedge \neg A_2))[/mm]
Das führt nicht zum Ziel, wenn ich nichts übersehen habe.
> Um die Äquivalenz zu überprüfen, würde ich dann jetzt
> mit ner Wahrheitstafel vorgehen. Was ist denn mit
> ´´lediglich die Disjunktion von drei Konjunktionen
> ist´´ gemeint?
Eine Formel der Form
[mm] $(\gamma_1\vee\ldots\vee\gamma_n)$
[/mm]
nennt man Disjunktion von [mm] $\gamma_1$ [/mm] bis [mm] $\gamma_n$, [/mm] eine Formel der Form
[mm] $(\gamma_1\wedge\ldots\wedge\gamma_n)$
[/mm]
Konjunktion von [mm] $\gamma_1$ [/mm] bis [mm] $\gamma_n$.
[/mm]
Eine Formel in disjunktiver Normalform ist nichts anderes als eine Konjunktion von Disjunktionen von Literalen.
Viele Grüße
Tobias
|
|
|
|
