Log. äquiv. Formel finden. < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:30 Do 11.11.2010 | | Autor: | Manu87 |
| Aufgabe | Sei [mm] \phi [/mm] die Formel [mm] $((A_{0} \rightarrow A_{1}) \wedge (A_{1} \rightarrow A_{2}))$.
[/mm]
Finden Sie eine Formel in disjunktiver Normalform , die logisch äquivalent zu [mm] \phi [/mm] ist und die eine Disjunktion von höchstens drei Konjunktionen ist. |
[mm] $((A_{0} \rightarrow A_{1}) \wedge (A_{1} \rightarrow A_{2}))$ [/mm] (Auflösung der Implikation)
[mm] $\equiv ((\neg A_{0} \vee A_{1}) \wedge (\neg A_{1} \vee A_{2}))$ [/mm] (de Morgan) --> KNF
[mm] $\equiv (\neg (A_{0} \wedge\neg A_{1}) \wedge \neg (A_{1} \wedge \neg A_{2}))$ [/mm] (de Morgan)
[mm] $\equiv ((A_{0} \wedge\neg A_{1}) \vee (A_{1} \wedge \neg A_{2}))$ [/mm] --> DNF
Eigentlich sollte ich das ja schon gelöst haben.
Aber ist das nicht die definition der Transitivität?
Sollte da nicht irgendwie [mm] $(A_{0} \rightarrow A_{2})$ [/mm] bzw [mm] $(\neg A_{0} \vee A_{2})$ [/mm] rauskommen?
|
|
| |
|
Hallo Manu87,
> Sei [mm]\phi[/mm] die Formel [mm]((A_{0} \rightarrow A_{1}) \wedge (A_{1} \rightarrow A_{2}))[/mm].
>
> Finden Sie eine Formel in disjunktiver Normalform , die
> logisch äquivalent zu [mm]\phi[/mm] ist und die eine Disjunktion
> von höchstens drei Konjunktionen ist.
> [mm]((A_{0} \rightarrow A_{1}) \wedge (A_{1} \rightarrow A_{2}))[/mm]
> (Auflösung der Implikation)
> [mm]\equiv ((\neg A_{0} \vee A_{1}) \wedge (\neg A_{1} \vee A_{2}))[/mm]
> (de Morgan) --> KNF
> [mm]\equiv (\neg (A_{0} \wedge\neg A_{1}) \wedge \neg (A_{1} \wedge \neg A_{2}))[/mm] ![[ok]](/images/smileys/ok.gif "[ok]")
bis hierhin
> (de Morgan)
> [mm]\equiv ((A_{0} \wedge\neg A_{1}) \vee (A_{1} \wedge \neg A_{2}))[/mm] ![[notok]](/images/smileys/notok.gif "[notok]")
Da fehlt die Negation des Ganzen, mit de Morgan folgt aus dem Obigen doch: [mm]\ldots \ \equiv \ \neg\left[(A_{0} \wedge\neg A_{1}) \vee (A_{1} \wedge \neg A_{2})\right][/mm]
Ich meine, dass du nach dem Auflösen der Implikation mal das Distributivgesetz anwenden könntest, das liefert nach dem ganzen Aufdröseln (nach meiner schnellen überschlägigen Rechnung) eine Disjunktion von 3 2-stelligen Konjunktionen.
> --> DNF
>
> Eigentlich sollte ich das ja schon gelöst haben.
> Aber ist das nicht die definition der Transitivität?
> Sollte da nicht irgendwie [mm](A_{0} \rightarrow A_{2})[/mm] bzw
> [mm](\neg A_{0} \vee A_{2})[/mm] rauskommen?
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:44 Do 11.11.2010 | | Autor: | Manu87 |
Oh du hast recht...
[mm] $((A_{0} \rightarrow A_{1}) \wedge (A_{1} \rightarrow A_{2}))$
[/mm]
[mm] $\equiv ((\neg A_{0} \vee A_{1}) \wedge (\neg A_{1} \vee A_{2}))$
[/mm]
[mm] $\equiv ((\neg A_{0} \vee A_{1}) \wedge \neg A_{1}) \vee ((\neg A_{0} \vee A_{1}) \wedge A_{2})$
[/mm]
[mm] $\equiv (\neg A_{0}\wedge\neg A_{1})\vee( A_{1}\wedge\neg A_{1})\vee(\neg A_{0}\wedge A_{2})\vee( A_{1}\wedge A_{2})$
[/mm]
[mm] $\equiv (\neg A_{0}\wedge\neg A_{1})\vee(\neg A_{0}\wedge A_{2})\vee( A_{1}\wedge A_{2})$
[/mm]
So jetz aber... danke. Die Frage wegen der Transitivität bleibt.
|
|
|
| |
|
Hallo nochmal,
> Oh du hast recht...
>
> [mm]((A_{0} \rightarrow A_{1}) \wedge (A_{1} \rightarrow A_{2}))[/mm]
>
> [mm]\equiv ((\neg A_{0} \vee A_{1}) \wedge (\neg A_{1} \vee A_{2}))[/mm]
>
> [mm]\equiv ((\neg A_{0} \vee A_{1}) \wedge \neg A_{1}) \vee ((\neg A_{0} \vee A_{1}) \wedge A_{2})[/mm]
>
> [mm]\equiv (\neg A_{0}\wedge\neg A_{1})\vee( A_{1}\wedge\neg A_{1})\vee(\neg A_{0}\wedge A_{2})\vee( A_{1}\wedge A_{2})[/mm]
>
> [mm]\equiv (\neg A_{0}\wedge\neg A_{1})\vee(\neg A_{0}\wedge A_{2})\vee( A_{1}\wedge A_{2})[/mm] ![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
>
> So jetz aber... danke. Die Frage wegen der Transitivität
> bleibt.
Du meinst ob [mm](A_0\rightarrow A_1) \ \wedge \ (A_1\rightarrow A_2) \ \equiv \ A_0\rightarrow A_2[/mm] ist?
Nein, etwa für die Belegung [mm]A_0=0=A_2, A_1=1[/mm] ergibt sich keine Formeläquivalenz.
Oder meinst du ob [mm]\left[ \ (A_0\rightarrow A_1) \ \wedge \ (A_1\rightarrow A_2) \ \right] \ \red{\rightarrow} \ \left[ \ A_0\rightarrow A_2 \ \right][/mm] eine Tautologie ist?
Sprich: ob die logische Implikation transitiv ist?
Antwort: Ja! 
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:56 Fr 12.11.2010 | | Autor: | Manu87 |
Danke schachuzipus du bist ein Genie!
|
|
|
|
