Die Mathe-Redaktion - 20.08.2019 18:42 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 454 Gäste und 23 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Logik, Mengen & Beweistechnik » Aussagenlogik » Ein Genau-dann-wenn-Beweis. Ersetzung atomarer Formeln durch neue atomare Formeln
Druckversion
Druckversion
Autor
Universität/Hochschule J Ein Genau-dann-wenn-Beweis. Ersetzung atomarer Formeln durch neue atomare Formeln
hudiabssfsjdkfb89
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-01-17


Servus.

Die Aufgabe hier ist mir etwas unklar:

Wir bauen aus H eine neue Formel H′, indem jede atomare Formel A in H durch (¬(A1 ∧ A2)) ersetzt wird, wobei A1, A2 neue atomare Formeln sind.

Beispiel: Sei K = A ∨ ¬B. Dann ist K′ = (¬(A1 ∧ A2)) ∨ ¬(¬(B1 ∧ B2)).

Zeigen Sie: H ist genau dann erfüllbar, wenn H′ erfüllbar ist.

Ich würde beide Richtungen beweisen. Also dass H erfüllbar ist, dann muss man zeigen das H´erfüllbar ist. Und H´ ist erfüllbar, so zeigen das H erfüllbar ist.

Ich hab etwas Startschwierigkeiten. Hab mir überlegt die Beispiele für den Beweis zu verwenden. K hat ein Modell und K´ebenfalls. Aber das Modell von K ist nicht passend zu K´. Daher wollte ich eine neue Abbildung A konstruieren, die beide atomaren Formeln abdeckt.
Dann würde ich Wahrheitstabellen verwenden um zu zeigen, dass beide erfüllbar sind.

Oder ist das der falsche Ansatz? Soll ich lieber eine Fallunterscheidung machen? Also H ist gültig/unerfüllbar, also auch H´.

Danke :-)



  Profil  Quote  Link auf diesen Beitrag Link
SemiPrim4711
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 08.01.2019
Mitteilungen: 58
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-01-17


Hallo hudiabssfsjdkfb89,


fed-Code einblenden
fed-Code einblenden

..nur so als Gedanke



  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1575
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-01-17


Man kann etwas stärkeres beweisen, was obendrein auch noch simpler ist, finde ich. Nämlich:
Für jede Interpretation $I\colon V \to 2$ gibt es eine Interpretation $J: V+V \to 2$ mit $\sem M_I = \sem {M'}_J$ und
für jede Interpretation $I\colon V+V \to 2$ gibt es eine Interpretation $J: V \to 2$ mit $\sem {M'}_I = \sem M_J$.
Nachdem man jeweils ein zum $I$ passendes $J$ festgelegt hat, ist der Rest nur noch Induktion über den Formelaufbau von M.



  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2019-02-10


Servus Leute,

mir sind paar dinge unklar.

Es ist ja eine Genau-dann-wenn Beziehung. Es reicht ja also doch nicht, wenn ich eine Induktion über den Formelaufbau von H mache und für H´nicht?
Wenn ich eine Induktion über den Formelaufbau von H´ mache scheitert man doch bereites beim Induktionsanfang: Sei A eine atomare Formel so ist dieser erfüllbar unter der Belegung A´(A)=1. Aber A kann nicht durch eine Ersetzung entstanden sein, da in der Aufgabe steht, dass eine atomare Formel A durch -(A1 V A2) ersetzt wird und jedoch A steht. Also ist doch dann H leer?

 
Bei I ist V die Menge aller atomaren Formeln? Und bei J die Menge aller Paare, da wir eine atomare Formel durch zwei ersetzen. Korrekt?
Diese ->2. Damit meinst du bestimmt {0,1}?
Was meinst du genau mit dieser Schreibweise "[[M]]I=[[M′]]J"
Bei uns in der Uni nutzen wir eine andere Schreibweise.

Danke :)




  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1575
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-02-11

\(\begingroup\)\( \newcommand{\sem}[1]{[\![#1]\!]}\newcommand{\name}[1]{\ulcorner#1\urcorner}\)
2019-02-10 16:41 - hudiabssfsjdkfb89 in Beitrag No. 3 schreibt:
Servus Leute,

mir sind paar dinge unklar.

Es ist ja eine Genau-dann-wenn Beziehung. Es reicht ja also doch nicht, wenn ich eine Induktion über den Formelaufbau von H mache und für H´nicht?
Wenn ich eine Induktion über den Formelaufbau von H´ mache scheitert man doch bereites beim Induktionsanfang: Sei A eine atomare Formel so ist dieser erfüllbar unter der Belegung A´(A)=1. Aber A kann nicht durch eine Ersetzung entstanden sein, da in der Aufgabe steht, dass eine atomare Formel A durch -(A1 V A2) ersetzt wird und jedoch A steht. Also ist doch dann H leer?
Nach meinem Vorschlag sind zwei Dinge zu zeigen. Beide gehen separat über den Formelaufbau von H. H' (das ist rekursiv über den Formelaufbau definiert) ergibt sich ja dann jeweils.
Danach ist es dann ein simples Korollar, dass H erfüllbar gdw. H' erfüllbar.

Bei I ist V die Menge aller atomaren Formeln? Und bei J die Menge aller Paare, da wir eine atomare Formel durch zwei ersetzen. Korrekt?
Nein, I ist in den beiden Aussagen jeweils eine Eingabe-Interpretation und J eine dazu passende Interpretation, sodass die Gleichung gilt.

Diese ->2. Damit meinst du bestimmt {0,1}?
Mit 2 meine ich {0,1}, ja.

Was meinst du genau mit dieser Schreibweise "[[M]]I=[[M′]]J"
Bei uns in der Uni nutzen wir eine andere Schreibweise.
Ich habe es so modelliert: Für jede Menge $V$ (eigentlich beliebig) haben wir die Menge $\mathcal F(V)$ der aussagenlogischen Formeln, in denen Elemente von $V$ als Atome vorkommen dürfen. $\mathcal F(V)$ ist auf naheliegende Weise induktiv definiert.
Eine "Interpretation" $I\colon V \to 2$ wird dann auf naheliegende Weise zu einer Semantikfunktion $\sem-_I\colon \mathcal F(V) \to 2$ erweitert.
In der hier vorliegende Aufgabe geht es um Formeln $H\in\mathcal F(V)$ für ein nicht näher spezifiertes $V$, und die $H'$ kann man als Elemente von $\mathcal F(V+V)$ auffassen, wobei mit dem + disjunkte Vereinigung gemeint ist.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89 hat die Antworten auf ihre/seine Frage gesehen.
hudiabssfsjdkfb89 hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]