HÜ 3 Miniquiz

ez22
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 28. Mär 2011 14:52

HÜ 3 Miniquiz

Beitrag von ez22 » 13. Aug 2011 11:33

Hallo,

habe eine Frage zu dem Miniquiz, es geht um die Tabelle, in der Formel stehen und man muss ankreuzen ob das eine KNF oder DNF ist

r and t ist KNF und DNF
sowie
r or -s ist eine KNF und DNF

ist das aus dem Grund weil man zu den Formel eine 1 oder eine 0 zuschreiben kann (womit man quasi andere NF erreichen kann), also (r and t) or 0 (DNF) sowie (r or -s) and 1 (KNF).

Dann die Begründung warum phi zu r or -s äquivalent ist.
Der dritte Schritt, Anwendung des Distributivgesetzes: -s or (r and s) or (r and t) = ((-s or r) and (-s or s)) or (r and t). Warum wird s mit der dritten Klammer nicht ausgeklammert?

Danke im Voraus!

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: HÜ 3 Miniquiz

Beitrag von dschneid » 13. Aug 2011 16:30

Zur ersten Frage: Mit den möglichen Werten der Variablen hat das gar nichts zu tun, nur mit der Struktur: Eine Formel ist in KNF, wenn sie aus einer Konjunktion ("und") von mindestens einer Unterformel besteht, wobei die Unterformeln durch eine Disjunktion ("oder") aus jeweils mindestens einem Literal gebildet werden; für die DNF ist es andersherum.
\(r \wedge t\) ist eine Konjunktion von zwei Unterformeln, die jeweils aus der Disjunktion von nur einem Literal bestehen, also in KNF. \(r \vee \neg s\) ist eine Konjunktion einer einzigen Unterformel, die eine Disjunktion aus zwei Literalen ist, und deswegen auch in KNF. Die beiden Formeln sind aber auch in DNF, denn \(r \wedge t\) ist eine Disjunktion aus zwei Konjunktionen aus je einem Literal, und \(r \vee \neg s\) ist eine Disjunktion aus einer Unterformel, die eine Konjunktion aus zwei Literalen ist.
In der Frage geht es also um die ganz einfachen Spezialfälle, in denen entweder \(\vee\) oder \(\wedge\) gar nicht auftaucht, weil die Konjunktionen oder Disjunktionen über nur eine Formel oder nur ein Literal sind, die also nicht unbedingt so "aussehen" wie Formeln in KNF oder DNF, aber trotzdem die Definition erfüllen.

Die zweite Frage verstehe ich nicht.

ez22
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 28. Mär 2011 14:52

Re: HÜ 3 Miniquiz

Beitrag von ez22 » 13. Aug 2011 17:43

danke für die Antwort!

leider wurde die erste Frage auch missverstanden. Ich habe keine mögliche werte der variablen gemeint.

(r and q) or 0 äquivalent zu r and q //0 ist keine Belegung einer Variable
(r or-s) and 1 äquivalent zu r or -s // 1 ist ebenfalls keine Belegung

aber du hast das geschrieben was ich gemeint habe...

zweite Frage.
-s or (r and s) or (r and t) Eingangsformel, auf die Distributivgesetz angewendet wird =>
=> ((-s or r) and (-s or s)) or (r and t) Ausgangsformel nach der DG angewendet wurde.

-s wurde nur mir der ersten Klammer ausgeklammert -s or (r and s) = ((-s or r) and (-s or s))
die dritte Klammer wurde bei der ausklammerung nicht gerührt... warum?

-s or (r and s) or (r and t) = ((-s or r) and (-s or s)) or (r and t)

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: HÜ 3 Miniquiz

Beitrag von dschneid » 13. Aug 2011 19:53

Weil das Distributivgesetz allgemein von der Form \(p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)\) ist, man kann also nicht ohne weiteres in zwei Klammern "ausmultiplizieren". Dann stellt sich auch die Frage, warum du das machen willst? Der Weg, der benutzt wird, funktioniert ja. Ich empfehle bei solchen Aufgaben, bei denen die Äquivalenz von zwei aussagenlogischen Formeln überprüft werden soll, ohnehin immer, einfach für beide Formeln die Wahrheitstafeln aufzustellen und zu vergleichen. Da kann wesentlich weniger bei schiefgehen als bei solchen Umformungen (jedenfalls geht es mir so; ich bin einfach zu blöd für Formelumformungen).

ez22
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 28. Mär 2011 14:52

Re: HÜ 3 Miniquiz

Beitrag von ez22 » 13. Aug 2011 20:00

ja, wahrheitstabelle ist am sichersten...

danke für die antworten!

Antworten

Zurück zu „Archiv“