matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAussagenlogikAxiom. Kalkül für AL: Frage!
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Aussagenlogik" - Axiom. Kalkül für AL: Frage!
Axiom. Kalkül für AL: Frage! < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Aussagenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Axiom. Kalkül für AL: Frage!: (p→q) aus ¬p : axiom. Kalkül
Status: (Frage) beantwortet Status 
Datum: 23:23 Sa 15.10.2016
Autor: Logiksproessling

Aufgabe
Aufgabe 4
Versuchen Sie, im axiomatischen Kalkül AK(AL) p→q aus ¬p abzuleiten.

Hallo, liebe Leute

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

Ich sitze gerade an meinen Philosophie-Aufgaben, und stecke bei Aufgabe 4 fest. Ich habe alle möglichen Lösungswege versucht, doch es scheint alles vergebens. Lasst mich kurz die Bedingungen, die der Professor bisher an uns gestellt hat, zusammenfassen:

-------
Axiome
1. (p → (q→ p))
2. ((p→(q→r))→((p→q)→(p→r)))
3. ((¬p→¬q)→(q→p))

Grundschlussregel
Aus Sätzen (der Gestalt) A und (A → B) kann man den Satz der
Gestalt B gewinnen (Modus Ponens).
Substitutionsregel
Gleiche Satzkonstanten in einem Axiom können durch gleiche
AL-Formeln ersetzt werden.
---------------

Ich habe jetzt einfach angenommen, dass (p→(q→p)) = (¬p→¬(q→p)).

A4: (p→q) aus ¬p
1.) ¬p || Prämisse
2.) ((¬p→¬q)->(q→p)) || AXIOM 3
3.) ((¬p→¬(q→p))->((q→p)→p)) || "q" in 2 ersetzen durch (q→p)
4.) ((p→(q→p)) || AXIOM 2
5.) ((q→p)→p)) || modus ponens: 3,4

Und weiter komm ich nicht :(
Ich bin um jeden Tipp dankbar, und vielen Dank für eure Zeit.

        
Bezug
Axiom. Kalkül für AL: Frage!: Antwort
Status: (Antwort) fertig Status 
Datum: 09:07 So 16.10.2016
Autor: tobit09

Hallo Logiksproessling und herzlich [willkommenmr]!


>  Versuchen Sie, im axiomatischen Kalkül AK(AL) p→q aus
> ¬p abzuleiten.

> Ich sitze gerade an meinen Philosophie-Aufgaben, und stecke
> bei Aufgabe 4 fest. Ich habe alle möglichen Lösungswege
> versucht, doch es scheint alles vergebens. Lasst mich kurz
> die Bedingungen, die der Professor bisher an uns gestellt
> hat, zusammenfassen:
>
> -------
>  Axiome
>  1. (p → (q→ p))
>  2. ((p→(q→r))→((p→q)→(p→r)))
>  3. ((¬p→¬q)→(q→p))
>  
> Grundschlussregel
>  Aus Sätzen (der Gestalt) A und (A → B) kann man den
> Satz der
>  Gestalt B gewinnen (Modus Ponens).
>  Substitutionsregel
>  Gleiche Satzkonstanten in einem Axiom können durch
> gleiche
>  AL-Formeln ersetzt werden.
>  ---------------

Danke für die Zusammenfassung, sie ist sehr hilfreich.


> Ich habe jetzt einfach angenommen, dass (p→(q→p)) =
> (¬p→¬(q→p)).

Diese Annahme ist in zweierlei Hinsicht falsch:
1. Die beiden Formeln links und rechts vom Gleichheitszeichen sind keineswegs äquivalent! Betrachte dazu die Belegung, die p und q jeweils den Wahrheitswert falsch zuordnet. Dann erhält die linke Formel den Wahrheitswert wahr und die rechte Formel den Wahrheitswert falsch.
2. Selbst wenn die beiden Formeln äquivalent wären, wären sie noch lange nicht gleich.
Und im Kalkül, um den es in der Aufgabe geht, gibt es offenbar keine Regel, die erlauben würde, in hergeleiteten Formeln Teilformeln durch äquivalente andere Formeln zu ersetzen.
Der Schluss, wie du ihn unten unter 5.) angibst, wäre also selbst, wenn die beiden Formeln äquivalent wären, kein erlaubter Schluss im vorliegenden Kalkül.


> A4: (p→q) aus ¬p
>  1.) ¬p || Prämisse
>  2.) ((¬p→¬q)->(q→p)) || AXIOM 3
>  3.) ((¬p→¬(q→p))->((q→p)→p)) || "q" in 2
> ersetzen durch (q→p)

(Sicherheitshalber: Beachte, dass die Substitutionsregel nur Einsetzungen in Axiomen und nicht in beliebigen hergeleiteten Formeln erlaubt!)


>  4.) ((p→(q→p)) || AXIOM 2
>  5.) ((q→p)→p)) || modus ponens: 3,4

1.), 2.), 4) sind korrekt hergeleitet, 3.) mit der genannten Einschränkung, 5.) nicht.


> Und weiter komm ich nicht :(

Irgendwie gilt es, die Prämisse [mm] $\neg [/mm] p$ gewinnbringend ins Spiel zu bringen.
Die einzige Möglichkeit, die sich dazu anbietet, ist in diesem Kalkül der Modus Ponens.
Dazu benötigen wir eine hergeleitete Formel der Form [mm] $\neg p\rightarrow [/mm] A$ für irgendeine geeignete aussagenlogische Formel A.

Mein Vorschlag dazu:
Aus Axiom 1. erhalten wir mittels Substitutionsregel [mm] ($\neg [/mm] p$ für p eingesetzt, [mm] $\neg [/mm] q$ für q eingesetzt):
[mm] $\neg p\rightarrow(\neg q\rightarrow\neg [/mm] p)$.

Kommst du damit schon alleine weiter?


Viele Grüße
Tobias

Bezug
                
Bezug
Axiom. Kalkül für AL: Frage!: Rückfrage
Status: (Frage) beantwortet Status 
Datum: 09:47 So 16.10.2016
Autor: Logiksproessling

Hallo Tobias, danke dir für den Empfang und die Hilfe! :D dass wir z.B. Negationen für Konstanten einsetzen dürfen, wusste ich nicht mal. Vielen Dank nochmals.
Ich habe das Kalkül gerade gelöst in 8 Schritten, allerdings unter der Voraussetzung, dass, wenn wir Negationen für Konstanten einsetzen dürfen, dann auch vice versa. Das sieht bei mir jetzt so aus:

1.) ¬p || PR
2.) (p→(q→p))|| AX1
3.) (¬p→(¬q→¬p)) || p und q in 3 ersetzen durch ¬p und ¬q
4.) (¬q→¬p) || modus ponens: 1, 4
5.) (¬r→¬p) || ¬q durch ¬r ersetzen in 4
6.) (¬r→(p→q)) || ¬p durch p→q ersetzen in 5
7.) (¬p→(p→q)) || ¬r durch ¬p ersetzen in 6
8.) p→q

Nur zur besseren Illustration ^^

Bezug
                        
Bezug
Axiom. Kalkül für AL: Frage!: Antwort
Status: (Antwort) fertig Status 
Datum: 10:42 So 16.10.2016
Autor: tobit09


> dass wir z.B. Negationen für Konstanten einsetzen dürfen,
> wusste ich nicht mal.

Nur in Axiomen, nicht in beliebigen hergeleiteten Formeln!
Das liefert die Substitutionsregel.


> Ich habe das Kalkül gerade gelöst in 8 Schritten,
> allerdings unter der Voraussetzung, dass, wenn wir
> Negationen für Konstanten einsetzen dürfen, dann auch
> vice versa.

Welche Regel aus dem Kalkül sollte dir das erlauben?


> Das sieht bei mir jetzt so aus:
>
> 1.) ¬p || PR
>  2.) (p→(q→p))|| AX1

Bis hierhin korrekt.

>  3.) (¬p→(¬q→¬p)) || p und q in 3 ersetzen durch ¬p
> und ¬q

Das geht laut Substitutionsregel, weil 2.) ein Axiom ist, und keine beliebige hergeleitete Formel.

>  4.) (¬q→¬p) || modus ponens: 1, 4

Richtig und zielführend! [ok]


>  5.) (¬r→¬p) || ¬q durch ¬r ersetzen in 4

Keine korrekte Folgerung.

>  6.) (¬r→(p→q)) || ¬p durch p→q ersetzen in 5

Keine korrekte Folgerung.

>  7.) (¬p→(p→q)) || ¬r durch ¬p ersetzen in 6

Keine korrekte Folgerung.

>  8.) p→q

Folgerichtige Anwendung des Modus Ponens auf 1.) und 7.).


Gehe nochmal von 4.) aus.

Die einzige Möglichkeit, 4.) zu nutzen, ist in diesem Kalkül der Modus Ponens.

Das kann prinzipiell auf zwei Arten geschehen:

a) Wir leiten [mm] $\neg [/mm] q$ her und schließen zusammen mit 4.) mittels Modus Ponens auf [mm] $\neg [/mm] p$.
(Dann hätten wir nichts gewonnen, denn [mm] $\neg [/mm] p$ haben wir ja bereits als Prämisse. Außerdem werden wir [mm] $\neg [/mm] q$ nicht herleiten können. Also bleibt noch b):)

b) Wir leiten zunächst eine Formel der Gestalt [mm] $(\neg q\rightarrow\neg p)\rightarrow [/mm] A$ her und schließen dann zusammen mit 4.) mittels Modus Ponens auf $A$.

Tipp: Betrachte die Substitutionsregel angewandt auf Axiom 3.

Bezug
                                
Bezug
Axiom. Kalkül für AL: Frage!: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 14:23 So 16.10.2016
Autor: Logiksproessling

Hallo nochmals ^^

Ich denke, ich erkenne meinen Fehler: Ich nahm bis zu deinem Post (als Laie, der ich bin :D), an, dass auch das Resultat nach einem modus ponens, die übriggebliebene Teilformel des Axioms also, immer noch als "Axiom" zählt - aber das ist nicht der Fall?

Vermutlich ist meine Lösung jetzt korrekt, und ich bedanke mich jetzt schon nochmal für deine Hilfe + Ausdauer :D :

Bis Schritt 4.) alles gleich wie vorher. Jetzt:

5.) ((¬p→¬q)→(q→p)) || AX3
6.) ((¬p→¬r)→(r→p)) || ¬q, q ersetzen in 5 mit ¬r, r
7.) ((¬q→¬r)→(r→q)) || ¬p, p ersetzen in 6 mit ¬q, q
8.) ((¬q→¬p)→(p→q)) || ¬r, r ersetzen in 6 mit ¬p, p
9.) (p→q) || modus ponens: 4, 8

Bezug
                                        
Bezug
Axiom. Kalkül für AL: Frage!: Antwort
Status: (Antwort) fertig Status 
Datum: 16:18 So 16.10.2016
Autor: tobit09


> Ich denke, ich erkenne meinen Fehler: Ich nahm bis zu
> deinem Post (als Laie, der ich bin :D), an, dass auch das
> Resultat nach einem modus ponens, die übriggebliebene
> Teilformel des Axioms also, immer noch als "Axiom" zählt -
> aber das ist nicht der Fall?

Nein. Die Axiome in diesem Kalkül sind folgende Formeln und keine sonst:

> Axiome
> 1. (p → (q→ p))
> 2. ((p→(q→r))→((p→q)→(p→r)))
> 3. ((¬p→¬q)→(q→p))


> Bis Schritt 4.) alles gleich wie vorher. Jetzt:
>
> 5.) ((¬p→¬q)→(q→p)) || AX3
>  6.) ((¬p→¬r)→(r→p)) || ¬q, q ersetzen in 5 mit
> ¬r, r

Soweit aus meiner Sicht nicht zielführend, aber korrekt.


>  7.) ((¬q→¬r)→(r→q)) || ¬p, p ersetzen in 6 mit
> ¬q, q

Nicht schon wieder...
Ersetzung (=Substitution) ist in diesem Kalkül nur auf die drei Axiome anwendbar!!!
6.) ist kein Axiom.


>  8.) ((¬q→¬p)→(p→q)) || ¬r, r ersetzen in 6 mit
> ¬p, p

Gleicher Fehler.


> 9.) (p→q) || modus ponens: 4, 8  

Folgerichtig.

Du hast korrekt erkannt, dass es hilft, 8.) herzuleiten, um daraus wie von dir vorgeschlagen 9.) zu erhalten.

Du kannst 8.) direkt mit einer Substitution aus dem dritten Axiom erhalten.

Bezug
                                                
Bezug
Axiom. Kalkül für AL: Frage!: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:49 So 16.10.2016
Autor: Logiksproessling

Hallo Tobias!

Du hast natürlich Recht mit der Folgerung von 5.) auf 8.) (manchmal sieht man den Wald vor lauter Bäumen nicht...), und ich habs sofort korrigiert ^^ zu meiner Rechtfertigung aber, die Substitutionen in den Zwischenschritten habe ich nicht "ohne zu überlegen" vorgenommen, sondern mich an das Muster des Professors gehalten. Ich kopiers dir:

-----------------
2. Ableitung von p→r aus p→(q→r) und q in AK(AL)
Axiome von AK(AL):
1. (p → (q→ p))
2. ((p→(q→r))→((p→q)→(p→r)))
3. ((¬p→¬q)→(q→p))

1. (p→ (q → r)) || Prämisse
2. q || Prämisse
3. ((p→(q→r))→((p→q)→(p→r))) || Axiom 2
4. (p→q)→(p→r) || 1., 3., modus ponens
5. p→ (q→ p) || Axiom 1
6. r→ (q→ r) || “p” in 5. durch “r” ersetzen
7. r→ (p→ r) || “q” in 6. durch “p” ersetzen
8. q→ (p→ q) || “r” in 7. durch “q” ersetzen
9. p→q || 2., 8., modus ponens
10. p→r || 4., 9., modus ponens
---------------

Stimmt in diesem Fall die Lösung des Professors etwa auch nicht?



Bezug
                                                        
Bezug
Axiom. Kalkül für AL: Frage!: Antwort
Status: (Antwort) fertig Status 
Datum: 18:24 So 16.10.2016
Autor: tobit09


> Du hast natürlich Recht mit der Folgerung von 5.) auf 8.)
> (manchmal sieht man den Wald vor lauter Bäumen nicht...),
> und ich habs sofort korrigiert ^^ zu meiner Rechtfertigung
> aber, die Substitutionen in den Zwischenschritten habe ich
> nicht "ohne zu überlegen" vorgenommen, sondern mich an das
> Muster des Professors gehalten. Ich kopiers dir:
>
> -----------------
>  2. Ableitung von p→r aus p→(q→r) und q in AK(AL)
>  Axiome von AK(AL):
>  1. (p → (q→ p))
>  2. ((p→(q→r))→((p→q)→(p→r)))
>  3. ((¬p→¬q)→(q→p))
>  
> 1. (p→ (q → r)) || Prämisse
>  2. q || Prämisse
>  3. ((p→(q→r))→((p→q)→(p→r))) || Axiom 2
>  4. (p→q)→(p→r) || 1., 3., modus ponens
>  5. p→ (q→ p) || Axiom 1
>  6. r→ (q→ r) || “p” in 5. durch “r” ersetzen
>  7. r→ (p→ r) || “q” in 6. durch “p” ersetzen
>  8. q→ (p→ q) || “r” in 7. durch “q” ersetzen
>  9. p→q || 2., 8., modus ponens
>  10. p→r || 4., 9., modus ponens
>  ---------------
>  
> Stimmt in diesem Fall die Lösung des Professors etwa auch
> nicht?

Danke für das Beispiel. Du hast völlig Recht damit, dass du analog zum Professor vorgegangen bist.


Warum da die Schritte 6.) und 7.) auftauchen, ist mir ein Rätsel. Sie sind genau so überflüssig wie gewisse Schritte bei dir es waren: 8.) ergibt sich direkt aus der Substitutionsregel angewandt auf Axiom 1.


Die Begründungen für 6., 7. und 8. kann ich nicht als korrekt erkennen.
Ich wäre gespannt, ob und wie der Professor sie rechtfertigen könnte.
Entweder ich habe den Kalkül missverstanden oder das Vorgehen des Professors ist tatsächlich nicht korrekt.

Fest steht jedenfalls: Würde ein Kalkül zulassen, innerhalb einer Herleitung beliebige Ersetzungen vorzunehmen, so wäre dieser Kalkül nicht korrekt: Dann ließe sich z.B. aus der Prämisse p die Konklusion q ziehen (oder noch extremer: die Konklusion [mm] $\neg [/mm] p$), was natürlich keine korrekten logischen Schlüsse sind.

Die einzige denkbare Rechtfertigung des Professors, die mir in den Sinn kommt, wäre eine Substitutionsregel, die etwas "stärker" als die von mir angenommene, aber "schwächer" als das Zulassen beliebiger Substitutionen ist.

Bezug
                                                                
Bezug
Axiom. Kalkül für AL: Frage!: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:03 So 16.10.2016
Autor: Logiksproessling

So, die Aufgaben wären geschafft ^^ Da ich gleich morgen Logik habe, werde ich demnach den Professor in der Vorlesung fragen. 2 der Dinge, die du mir oben erklärt hast, hat er im Formel-1-Tempo tatsächlich während des Unterrichts erwähnt , der Ersatz mit Negationen in Axiomen war mir aber ganz neu - ich möchte ihn auch fragen, warum er dies unerwähnt liess. (Vielleicht hielt ers für selbstverständlich lol)

Ich hau mich mal aufs Ohr ^^ danke dir zum dritten Mal für alles, und einen schönen Abend noch!

Bezug
                                                                        
Bezug
Axiom. Kalkül für AL: Frage!: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:40 So 16.10.2016
Autor: tobit09


> So, die Aufgaben wären geschafft ^^ Da ich gleich morgen
> Logik habe, werde ich demnach den Professor in der
> Vorlesung fragen.

Würde mich freuen, wenn du hier das Ergebnis des Gesprächs posten könntest.


> 2 der Dinge, die du mir oben erklärt
> hast, hat er im Formel-1-Tempo tatsächlich während des
> Unterrichts erwähnt , der Ersatz mit Negationen in Axiomen
> war mir aber ganz neu - ich möchte ihn auch fragen, warum
> er dies unerwähnt liess. (Vielleicht hielt ers für
> selbstverständlich lol)

Das steckt in der Tat in der Substitutionsregel mit drin und aus meiner Sicht kann man diese Möglichkeit demnach als selbstverständlich ansehen, auch wenn das ein oder andere Beispiel sicherlich hilfreich ist.


> Ich hau mich mal aufs Ohr ^^ danke dir zum dritten Mal für
> alles, und einen schönen Abend noch!  

Danke und gute Nacht! :-)

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Aussagenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


Alle Foren
Status vor 28m 1. sancho1980
ULinAEw/Eigenwerte und Matrix
Status vor 3h 33m 9. Ataaga
SGeradEbene/Abstand eines Punktes
Status vor 8h 48m 4. leduart
IntTheo/mehrdim. part. Int., Doppelint
Status vor 22h 53m 3. HJKweseleit
GraphTheo/Zusammenhängender Zufallsgraph
Status vor 1d 4h 01m 6. HJKweseleit
ULinAAb/Kern und Bild bestimmen
^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]