Conjunctive Normal Form < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:32 Fr 02.08.2019 | | Autor: | Spalding |
| Aufgabe | Transfrom the following sentences into the conjunctive normal form.
1) (A => B) => (¬A => ¬B)
2) (A => B) => ((A ∧ C) => B) |
Hallo Community,
ich habe mich an oben genannte Aufgabe gewagt und nachfolgend meine Ergebnisse dargestellt.
1)
(A => B) => (¬A => ¬B)
(¬A ∨ B) => (A ∨ ¬B)
¬(¬A ∨ B) ∨ (A ∨ ¬B)
(A ∧ ¬B) ∨ (A ∨ ¬B)
Nun frage ich mich, wie ich hier weitermachen kann?
In den Schritten oben konnte ich die Implikation-Elimination und de Morgan anwenden.
Offensichtlich ist die linke Klammer überflüssig, da ein "oder" immer vor einem "und" erfüllt ist. Nur mit welcher Begründung / welchem Gesetz lässt sich dies bewerkstelligen?
2)
(A => B) => ((A ∧ C) => B)
(¬A ∨ B) => (¬ (A ∧ C) ∨ B)
(¬A ∨ B) => (¬A ∨ ¬C ∨ B)
¬ (¬A ∨ B) ∨ (¬A ∨ ¬C ∨ B)
(A ∧ ¬B) ∨ (¬A ∨ ¬C ∨ B)
Auch hier konnte ich bereits einige Schritte mit der Implikation-Elimination und de Morgan machen.
Nun stellt sich auch hier die Frage, ob und wenn ja wie ich hier weiter vorgehen kann?
Greetz,
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:52 Fr 02.08.2019 | | Autor: | Marc |
Hallo Spalding,
> Transfrom the following sentences into the conjunctive
> normal form.
>
> 1) (A => B) => (¬A => ¬B)
> 2) (A => B) => ((A ∧ C) => B)
> Hallo Community,
>
> ich habe mich an oben genannte Aufgabe gewagt und
> nachfolgend meine Ergebnisse dargestellt.
>
> 1)
>
> (A => B) => (¬A => ¬B)
> (¬A ∨ B) => (A ∨ ¬B)
> ¬(¬A ∨ B) ∨ (A ∨ ¬B)
> (A ∧ ¬B) ∨ (A ∨ ¬B)
>
> Nun frage ich mich, wie ich hier weitermachen kann?
> In den Schritten oben konnte ich die
> Implikation-Elimination und de Morgan anwenden.
> Offensichtlich ist die linke Klammer überflüssig, da ein
> "oder" immer vor einem "und" erfüllt ist. Nur mit welcher
> Begründung / welchem Gesetz lässt sich dies
> bewerkstelligen?
Es müsste so gehen:
1. Assoziativgesetz bzgl. [mm] $\vee$:
[/mm]
$((A [mm] \wedge \neg [/mm] B) [mm] \vee [/mm] A) [mm] \vee \neg [/mm] ¬B$
2. Jetzt das Absorptionsgesetz [mm] $A\vee (A\wedge [/mm] B)=A$ anwenden
...
> 2)
>
> (A => B) => ((A ∧ C) => B)
> (¬A ∨ B) => (¬ (A ∧ C) ∨ B)
> (¬A ∨ B) => (¬A ∨ ¬C ∨ B)
> ¬ (¬A ∨ B) ∨ (¬A ∨ ¬C ∨ B)
> (A ∧ ¬B) ∨ (¬A ∨ ¬C ∨ B)
>
> Auch hier konnte ich bereits einige Schritte mit der
> Implikation-Elimination und de Morgan machen.
> Nun stellt sich auch hier die Frage, ob und wenn ja wie ich
> hier weiter vorgehen kann?
Hier würde ich auch das Assoziativgesetz bzgl. [mm] $\vee$ [/mm] anwenden und mit dem Kommutativgesetz [mm] $\neg [/mm] C$ nach hinten sortieren. Am besten mache das schon mit deiner vorletzten Zeile. Dann müsstest du das Komplementärgesetz [mm] $A\vee \neg A=\text{true}$ [/mm] anwenden können.
Viele Grüße
Marc
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:44 Sa 03.08.2019 | | Autor: | Spalding |
> Hallo Spalding,
>
> > Transfrom the following sentences into the conjunctive
> > normal form.
> >
> > 1) (A => B) => (¬A => ¬B)
> > 2) (A => B) => ((A ∧ C) => B)
> > Hallo Community,
> >
> > ich habe mich an oben genannte Aufgabe gewagt und
> > nachfolgend meine Ergebnisse dargestellt.
> >
> > 1)
> >
> > (A => B) => (¬A => ¬B)
> > (¬A ∨ B) => (A ∨ ¬B)
> > ¬(¬A ∨ B) ∨ (A ∨ ¬B)
> > (A ∧ ¬B) ∨ (A ∨ ¬B)
> >
> > Nun frage ich mich, wie ich hier weitermachen kann?
> > In den Schritten oben konnte ich die
> > Implikation-Elimination und de Morgan anwenden.
> > Offensichtlich ist die linke Klammer überflüssig, da
> ein
> > "oder" immer vor einem "und" erfüllt ist. Nur mit welcher
> > Begründung / welchem Gesetz lässt sich dies
> > bewerkstelligen?
>
> Es müsste so gehen:
> 1. Assoziativgesetz bzgl. [mm]\vee[/mm]:
> [mm]((A \wedge \neg B) \vee A) \vee \neg ¬B[/mm]
>
> 2. Jetzt das Absorptionsgesetz [mm]A\vee (A\wedge B)=A[/mm]
> anwenden
> ...
>
Bis hier hin fande ich alles sehr einleuchtend. Vielen Dank!
> > 2)
> >
> > (A => B) => ((A ∧ C) => B)
> > (¬A ∨ B) => (¬ (A ∧ C) ∨ B)
> > (¬A ∨ B) => (¬A ∨ ¬C ∨ B)
> > ¬ (¬A ∨ B) ∨ (¬A ∨ ¬C ∨ B)
> > (A ∧ ¬B) ∨ (¬A ∨ ¬C ∨ B)
> >
> > Auch hier konnte ich bereits einige Schritte mit der
> > Implikation-Elimination und de Morgan machen.
> > Nun stellt sich auch hier die Frage, ob und wenn ja wie ich
> > hier weiter vorgehen kann?
>
> Hier würde ich auch das Assoziativgesetz bzgl. [mm]\vee[/mm]
> anwenden und mit dem Kommutativgesetz [mm]\neg C[/mm] nach hinten
> sortieren. Am besten mache das schon mit deiner vorletzten
> Zeile. Dann müsstest du das Komplementärgesetz [mm]A\vee \neg A=\text{true}[/mm]
> anwenden können.
>
> Viele Grüße
> Marc
Zu der zweiten Aufgabe hätte ich nochmal eine Rückfrage.
Leider komme ich hier nicht weiter, wie genau meintest du das?
Viele Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:32 Sa 03.08.2019 | | Autor: | Marc |
> Zu der zweiten Aufgabe hätte ich nochmal eine Rückfrage.
> Leider komme ich hier nicht weiter, wie genau meintest du
> das?
Wo bist du nicht weiter gekommen bzw. wozu hast du eine Rückfrage?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:04 Sa 03.08.2019 | | Autor: | Spalding |
Um ehrlich zu sein, weiß ich nicht so recht wie ich anfangen soll.
Ich sehe einfach nicht wie der nächste Schritt wäre.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:53 Sa 03.08.2019 | | Autor: | Marc |
> Um ehrlich zu sein, weiß ich nicht so recht wie ich
> anfangen soll.
> Ich sehe einfach nicht wie der nächste Schritt wäre.
Kein Problem, dann fange ich mal beim ersten Schritt an.
Also, das Assoziativgesetz bzgl. [mm] $\vee$ [/mm] sagt aus, dass man die Klammern umsetzen darf und als weitere Folge davon weglassen kann. Zum Beispiel ist
[mm] $A\vee (B\vee C)=(A\vee B)\vee C=A\vee B\vee [/mm] C$
Das Kommutativgesetz bzgl. [mm] $\vee$ [/mm] sagt aus, dass man die Reihenfolge tauschen darf z.B. ist
[mm] $A\vee B\vee C=A\vee C\vee [/mm] B$
Hier in dem letzten Schritt ist mit $B$ das passiert, was ich in meiner ersten Antwort meinte mit [mm] "$\neg [/mm] C$ nach hinten sortieren".
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 02:10 So 04.08.2019 | | Autor: | Spalding |
Danke, anscheinend hatte ich mich missverständlich ausgedrückt.
Die beiden Gesetze kenne ich aber wenn ich das anwende komme ich auf
(A ∧ ¬B) ∨ (¬A ∨ ¬C ∨ B)
(A ∧ ¬B) ∨ ¬A ∨ B ∨ ¬C
((A ∧ ¬B) ∨ ¬A) ∨ B ∨ ¬C
Wie komme ich denn von hier aus auf (A ∨ ¬A)?
Aufgrund des ∧ in der Klammer stehe ich hier auf dem Schlauch.
Wenn ich die Zeile zuvor nehme, dann habe ich
¬ (¬A ∨ B) ∨ (¬A ∨ ¬C ∨ B)
¬ (¬A ∨ B) ∨ ¬A ∨ B ∨ ¬C
(¬(¬A ∨ B) ∨ ¬A) ∨ B ∨ ¬C
Mit der de Morgan Regel habe ich immer das Problem mit dem ∧ in der Klammer.
Viele Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:09 So 04.08.2019 | | Autor: | Marc |
Hallo spalding,
> Danke, anscheinend hatte ich mich missverständlich
> ausgedrückt.
> Die beiden Gesetze kenne ich aber wenn ich das anwende
> komme ich auf
Du hattest geschrieben, dass du den nächsten Schritt nicht siehst, der erste Schritt war aber, die Gesetze anzuwenden.
> (A ∧ ¬B) ∨ (¬A ∨ ¬C ∨ B)
> (A ∧ ¬B) ∨ ¬A ∨ B ∨ ¬C
> ((A ∧ ¬B) ∨ ¬A) ∨ B ∨ ¬C
>
> Wie komme ich denn von hier aus auf (A ∨ ¬A)?
> Aufgrund des ∧ in der Klammer stehe ich hier auf dem
> Schlauch.
> Wenn ich die Zeile zuvor nehme, dann habe ich
>
> ¬ (¬A ∨ B) ∨ (¬A ∨ ¬C ∨ B)
> ¬ (¬A ∨ B) ∨ ¬A ∨ B ∨ ¬C
> (¬(¬A ∨ B) ∨ ¬A) ∨ B ∨ ¬C
Ja, so meinte ich das, nur etwas anders geklammert:
[mm] $(\neg (\red{\neg A \vee B}) \vee (\red{\neg A \vee B})) \vee \neg [/mm] C$
Der Term in der äußersten Klammer ist von der Form
[mm] $\neg{\red{A}}\vee \red{A}$
[/mm]
Viele Grüße
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:00 So 04.08.2019 | | Autor: | Spalding |
Vielen Dank! Da kann ich ja lange versuchen die A's hin und her zu schieben.
Jetzt hab auch ich es verstanden :-D
|
|
|
|
