AK Ausdrücke DNF,KNF

Neue Frage »

Gast Auf diesen Beitrag antworten »
AK Ausdrücke DNF,KNF
Hi

ich habe folgendes Problem. Ich weis nicht wie ich diese Aufgabe lösen soll

Aufgabe: Stellen Sie für den AK Ausdruck mit Hilfe der Normalformen DNF/KNF fest ob sie allgemeingültig oder kontradiktorisch sind

(P u. Q) --> (P v Q )


Danke
Gastgeber Auf diesen Beitrag antworten »

Hallo lieber Gast,

was ist denn AK, DNF und KNF? Was heißt allgemeingültig und was heißt kontradiktorisch? Ich weiß das, aber andere vielleicht nicht, und ich möchte sehen, ob du es weißt. (Die Frage ist daher ausschließlich an den Gast gerichtet!)

Soweit ich mich erinnere, könnte ein erster Schritt darin bestehen, die Implikation durch die Operatoren und,oder,nicht aufzulösen.
Danach kannst du unter anderem de Morgans Regeln anwenden, um die gewünschte NF zu bekommen.
 
 
Gast Auf diesen Beitrag antworten »

Hi

Also KNF bedeutet Konjuktive Normalform, also als Hauptverknüpfung (Und)

Beispiel:

(a oder b) und (a oder c) und (c oder b)

DNF ist genau anderst herum, also mit oder verknüpft

Allgemeingültig bedeutet das immer Wahr raus kommt, egal welchen Wert die einzelnen Terme haben

A oder nicht A

Kontradiktorisch bedeutet das immer falsch rauskommt

A und nicht A

so ich hoffe, damit ist alles geklärt.

Ich habe die Implikation aufgelöst und komme auf das Ergebnis

nicht(p und q) oder (p oder q)

und jetzt ?
Gast Auf diesen Beitrag antworten »

nicht(p und q) oder (p oder q) <-- (da bei p oder q) ein "oder" statt einem "und" steht liegt keine dnf Form vor und wir müssen er mit der KNF Form versuchen


Denke ich
Gast Auf diesen Beitrag antworten »

es müßte so weitergehen

nicht( P und Q ) oder ( P oder Q )

--> (nicht P "und" nicht Q) oder ( P oder Q)

--> nicht P v (P oder Q) und nicht Q v ( P oder Q )

klammern weglassen

da nicht P und P bzw. nicht Q und Q so vorkommt ist diese Aussage Allgemeingültig
Gastgeber Auf diesen Beitrag antworten »

Gut so.

Du hast die Aussage richtig umgeformt zu:
nicht(p und q) oder (p oder q)

Wende nun im ersten Teil die de Morgansche Regel an (und zwar richtig, deine Anwendung im vorigen Beitrag ist leider falsch), und lass die weglassbaren Klammern weg. Damit erhältst du die DNF, die du noch verkürzen kannst zu "wahr".

Wie man hier formal auf eine KNF kommt, sehe ich gerade nicht, aber die fertige KNF sollte auch "wahr" sein.
Gast Auf diesen Beitrag antworten »

Du hast die Aussage richtig umgeformt zu:
nicht(p und q) oder (p oder q)

[nicht P v nicht Q) v (P v Q )

was muss ich jetzt machen ?
Gastgeber Auf diesen Beitrag antworten »

(nicht P oder nicht Q) oder (P oder Q )
Richtig.

Lass nun die weglassbaren Klammern weg - "oder" ist assoziativ und kommutativ. Du erhältst
(nicht P) oder (nicht Q) oder P oder Q

Das ist eine disjunktive Normalform.
Gast Auf diesen Beitrag antworten »

um auf die KNF Form zu kommen würde ich wiefolgt weitergehen


Ausgangsgleichung (nicht P) oder (nicht Q) oder P oder Q

nicht( nicht nicht P "und" nicht nicht Q "und" nicht P "und" nicht Q

--> nicht ( P und Q und nicht P und nicht Q )

--> nicht P und nicht Q und P und Q passt das ?
AoG Auf diesen Beitrag antworten »

Hallo Gast

In diesem Fall brauchen wir gar nicht mehr weiter machen, nur noch schönschreiben:

Ausgangspunkt: (nicht P) oder (nicht Q) oder P oder Q

nun ordenen wir das ganze

( (nicht P) oder P ) oder ( ( nicht Q oder Q )

( nicht Q oder Q ) = Tautologie, also immer Wahr
( nicht P oder P ) = Tautologie, also auch immer Wahr

(( immer wahr ) oder ( immer wahr) ) = immer Wahr

oder Mathematisch

wenn ...

ag1( nicht Q oder Q ) oder ag2( nicht P oder P ),

dann gilt ag( ag1 oder ag2 )

ag bedeutet Allgemeingültige Aussage (Tautologie) Tanzen
Gastgeber Auf diesen Beitrag antworten »

Die Umformung von
(nicht P) oder (nicht Q) oder P oder Q
zu
nicht( nicht nicht P "und" nicht nicht Q "und" nicht P "und" nicht Q)
ist korrekt, ebenso wie der Schritt zu
--> nicht ( P und Q und nicht P und nicht Q )
Aber der nächste Schritt ist falsch:
--> nicht P und nicht Q und P und Q
Denn du kannst selbst feststellen, dass die letzte Aussage kontradiktorisch ist, also nicht zu der allgemeingültigen Aussage vom Anfang äquivalent sein kann.

Du hast das de Morgansche Gesetz falsch angewandt - merke dir gut, dass bei seiner Anwendung die Operatoren "und" und "oder" getauscht werden!
Gast Auf diesen Beitrag antworten »

Ist elementare Aussagelogik in der HM nicht deplaziert?
Gastgeber Auf diesen Beitrag antworten »

Wird elementare Aussagenlogik - unter Rückführung auf eine axiomatische Theorie - in der Schule behandelt? Bei mir nicht, nicht mal im Mathe-Grundstudium der Uni! (Erst in Informatik- oder speziellen Logik-Vorlesungen.)
AoG Auf diesen Beitrag antworten »

sehe ich genauso wie Gastgeber.

Hey Gastgeber, hast du Infos zum Thema: Whitehead Russel'schen Axiomensystem ?
Balacheso Auf diesen Beitrag antworten »

Tja, einem Informatiker mag das wie höhere Mathematik vorkommen...
Ben Sisko Auf diesen Beitrag antworten »

Die Abgrenzungen der Unterforen sind hier nicht scharf, deswegen kann man bei manchem Thread drüber streiten, wo er hingehört.
Ich finde diesen in HöMa aber angemessen, deswegen bleibt er hier Augenzwinkern

Gruß vom Ben
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »