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
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

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
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
StartseiteMatheForenAussagenlogikAussagenlogisches Kalkül
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Aussagenlogik" - Aussagenlogisches Kalkül
Aussagenlogisches Kalkül < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Aussagenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Aussagenlogisches Kalkül: Axiome
Status: (Frage) beantwortet Status 
Datum: 20:09 Do 25.08.2022
Autor: KarlAugust

Aufgabe
(Grenzen der Mathematik, D. Hoffmann, 2011, S.93-94)

"Axiome und Schlussregeln sind in Tabelle 2.6 zusammengefasst... Innerhalb des Kalküls existiert mit dem Modus ponens eine einzige Schlussregel.... Sie garantiert, dass eine Aussage [mm] $\psi$ [/mm] wahr sein muss, wenn wir wissen, dass [mm] $\varphi$ [/mm] wahr ist und [mm] $\psi$ [/mm] aus [mm] $\varphi$ [/mm] gefolgert werden kann.

Tabelle 2.6:

Axiom 1) [mm] $\varphi\to(\psi\to\varphi)$ [/mm]
Axiom 2) [mm] $(\varphi\to(\psi\to\chi))\to((\varphi\to\psi)\to(\varphi\to\chi))$ [/mm]
Axiom 3) [mm] $(\neg\varphi\to\psi)\to(\psi\to\varphi)$ [/mm]

Schlussregel MP: [mm] $\frac{\varphi,\varphi\to\psi}{\psi}$ [/mm]

Hallo,

in Kapitel 2.3.2 führt der Auor einen aussagenlogischen Kalkül ein, dabei werden [mm] $\varphi, \psi, \chi$ [/mm]  bis zur Einführung der Tabelle 2.6. als Aussagen bezeichnet. Aussage ist hier Synonym für aussagenlogische Formel (würde anders auch keinen Sinn ergeben oder)?

Ist es erlaubt für [mm] $\varphi$ [/mm] und [mm] $\psi$ [/mm] bel. Formeln nach Def. 2.5 zu konstruieren und bspw. in der Form von Axiom 1 in Beziehung zu setzen und dann behaupten die dadurch neu gewonnene Formel ist ein Axiom nach dem Bildungsschema 1?

z.B. [mm] $\varphi [/mm] = [mm] A_1\to A_2$ [/mm] und [mm] $\psi [/mm] = [mm] A_3\wedge [/mm] 0$, dann ist [mm] $\varphi\to(\psi\to\varphi)$ [/mm] ein Axiom? Oder ist in dem konkreten Bsp. [mm] $\varphi\to(\psi\to\varphi)$ [/mm] nur ein Axiom, falls [mm] $\varphi, \psi$ [/mm] wahr sind?


Definition 2.5:
Die Menge der aussagenlogischen Formeln über dem Variablenvorrat $ [mm] V=\{A_1,A_2,A_3,\ldots\} [/mm] $ ist rekursiv definiert:
$ [mm] \bullet [/mm] $ 0 und 1 sind Formeln.
$ [mm] \bullet [/mm] $ Jede Variable aus der Menge V ist eine Formel.
$ [mm] \bullet [/mm] $ Sind $ [mm] \phi [/mm] $ und $ [mm] \psi [/mm] $ Formeln, dann sind es auch $ [mm] (\neg\phi),(\phi\wedge\psi), (\phi\vee\psi), (\psi\to\psi), (\phi\leftrightarrow\psi), (\phi\nleftrightarrow\psi) $ Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt. [/mm]

        
Bezug
Aussagenlogisches Kalkül: Antwort
Status: (Antwort) fertig Status 
Datum: 13:17 So 28.08.2022
Autor: meili

Hallo KarlAugust,

> (Grenzen der Mathematik, D. Hoffmann, 2011, S.93-94)
>  
> "Axiome und Schlussregeln sind in Tabelle 2.6
> zusammengefasst... Innerhalb des Kalküls existiert mit dem
> Modus ponens eine einzige Schlussregel.... Sie garantiert,
> dass eine Aussage [mm]\psi[/mm] wahr sein muss, wenn wir wissen,
> dass [mm]\varphi[/mm] wahr ist und [mm]\psi[/mm] aus [mm]\varphi[/mm] gefolgert werden
> kann.
>  
> Tabelle 2.6:
>  
> Axiom 1) [mm]\varphi\to(\psi\to\varphi)[/mm]
>  Axiom 2)
> [mm](\varphi\to(\psi\to\chi))\to((\varphi\to\psi)\to(\varphi\to\chi))[/mm]
>  Axiom 3) [mm](\neg\varphi\to\psi)\to(\psi\to\varphi)[/mm]
>  
> Schlussregel MP: [mm]\frac{\varphi,\varphi\to\psi}{\psi}[/mm]
>  Hallo,
>  
> in Kapitel 2.3.2 führt der Auor einen aussagenlogischen
> Kalkül ein, dabei werden [mm]\varphi, \psi, \chi[/mm]  bis zur
> Einführung der Tabelle 2.6. als Aussagen bezeichnet.
> Aussage ist hier Synonym für aussagenlogische Formel
> (würde anders auch keinen Sinn ergeben oder)?
>  
> Ist es erlaubt für [mm]\varphi[/mm] und [mm]\psi[/mm] bel. Formeln nach Def.
> 2.5 zu konstruieren und bspw. in der Form von Axiom 1 in
> Beziehung zu setzen und dann behaupten die dadurch neu
> gewonnene Formel ist ein Axiom nach dem Bildungsschema 1?

Ich würde sagen: nein.
Man kann Formeln nach der Definition konstruieren. Man erhält dann aber
Sätze, wenn sie den Schlussregeln folgen. Sollte man Formeln finden
die äquivalent zu den Axiomen sind, kann man die Axiome durch diese
neue Menge Axiome ersetzen.

>  
> z.B. [mm]\varphi = A_1\to A_2[/mm] und [mm]\psi = A_3\wedge 0[/mm], dann ist
> [mm]\varphi\to(\psi\to\varphi)[/mm] ein Axiom? Oder ist in dem
> konkreten Bsp. [mm]\varphi\to(\psi\to\varphi)[/mm] nur ein Axiom,
> falls [mm]\varphi, \psi[/mm] wahr sind?
>  
>
> Definition 2.5:
>  Die Menge der aussagenlogischen Formeln über dem
> Variablenvorrat [mm]V=\{A_1,A_2,A_3,\ldots\}[/mm] ist rekursiv
> definiert:
>  [mm]\bullet[/mm] 0 und 1 sind Formeln.
>  [mm]\bullet[/mm] Jede Variable aus der Menge V ist eine Formel.
>  [mm]\bullet[/mm] Sind [mm]\phi[/mm] und [mm]\psi[/mm] Formeln, dann sind es auch
> [mm](\neg\phi),(\phi\wedge\psi), (\phi\vee\psi), (\psi\to\psi), (\phi\leftrightarrow\psi), (\phi\nleftrightarrow\psi)[/mm]
>  
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>  

Gruß
meili

Bezug
                
Bezug
Aussagenlogisches Kalkül: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:34 So 28.08.2022
Autor: KarlAugust

Hallo meili,

> Man erhält dann aber Sätze, wenn sie den Schlussregeln folgen.

Ich verstehe nicht wie du das meinst. Der Autor leitet als Beispiel die Formel [mm] $A\to [/mm] A$ in 5 Schritten ab. Dabei verwendet er im ersten Schritt Axiom 2 und zwar so dass er [mm] $\varphi [/mm] = A$, [mm] $\psi [/mm] = [mm] A\to [/mm] A$ und [mm] $\chi [/mm] = A$ setzt.

1. [mm] $\vdash (A\to((A\to A)\to A))\to((A\to(A\to A))\to(A\to [/mm] A))$ (Axiom 2)
2. [mm] $\vdash A\to((A\to A)\to [/mm] A)$ (Axiom 1)
3. [mm] $\vdash (A\to (A\to A))\to(A\to [/mm] A)$ (MP, 1, 2)
4. [mm] $\vdash A\to (A\to [/mm] A)$ (Axiom 1)
5. [mm] $A\to [/mm] A$ (MP, 3, 4)


Ebenso gut könnte ich doch [mm] $\varphi,\psi,\chi$ [/mm] bel. setzen (solange es den Bildungsregeln nach Def. 2.5 entspricht) und sagen das es dem Axiom 1 bzw. 2 genügt.

Bezug
                        
Bezug
Aussagenlogisches Kalkül: Antwort
Status: (Antwort) fertig Status 
Datum: 18:32 Mo 29.08.2022
Autor: meili

Hallo KarlAugust,

wahrscheinlich habe ich deine Frage nicht richtig verstanden und dachte
dir sei der Unterschied zwischen Axiomen und die Benutzung von
Axiome für Beweise nicht klar.

> Hallo meili,
>  
> > Man erhält dann aber Sätze, wenn sie den Schlussregeln
> folgen.
>  
> Ich verstehe nicht wie du das meinst. Der Autor leitet als
> Beispiel die Formel [mm]A\to A[/mm] in 5 Schritten ab. Dabei
> verwendet er im ersten Schritt Axiom 2 und zwar so dass er
> [mm]\varphi = A[/mm], [mm]\psi = A\to A[/mm] und [mm]\chi = A[/mm] setzt.
>
> 1. [mm]\vdash (A\to((A\to A)\to A))\to((A\to(A\to A))\to(A\to A))[/mm]
> (Axiom 2)
>  2. [mm]\vdash A\to((A\to A)\to A)[/mm] (Axiom 1)
>  3. [mm]\vdash (A\to (A\to A))\to(A\to A)[/mm] (MP, 1, 2)
>  4. [mm]\vdash A\to (A\to A)[/mm] (Axiom 1)
>  5. [mm]A\to A[/mm] (MP, 3, 4)
>  

Wenn man Axiome hat, kann man diese benutzen um etwas zu zeigen
(zu beweisen), wie in diesem Beispiel.

>
> Ebenso gut könnte ich doch [mm]\varphi,\psi,\chi[/mm] bel. setzen
> (solange es den Bildungsregeln nach Def. 2.5 entspricht)
> und sagen das es dem Axiom 1 bzw. 2 genügt.

Ja.

Gruß
meili

Bezug
                                
Bezug
Aussagenlogisches Kalkül: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:36 Di 30.08.2022
Autor: KarlAugust


> ...dachte dir sei der Unterschied zwischen Axiomen und die Benutzung von Axiome für Beweise nicht klar.

Grob gesprochen stimmt das auch. ich habe eine anschließende Versändnis Frage uner die Anwort von obias gepostet.



Bezug
        
Bezug
Aussagenlogisches Kalkül: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:17 So 28.08.2022
Autor: KarlAugust

Ich bin weiterhin an einer Antwort interessiert.

Bezug
        
Bezug
Aussagenlogisches Kalkül: Antwort
Status: (Antwort) fertig Status 
Datum: 15:04 Di 30.08.2022
Autor: tobit09

Hallo KarlAugust,

> in Kapitel 2.3.2 führt der Auor einen aussagenlogischen
> Kalkül ein, dabei werden [mm]\varphi, \psi, \chi[/mm]  bis zur
> Einführung der Tabelle 2.6. als Aussagen bezeichnet.
> Aussage ist hier Synonym für aussagenlogische Formel
> (würde anders auch keinen Sinn ergeben oder)?

Ja, ich denke, in diesem Kontext verwendet Hoffmann in der Tat den Begriff Aussage als Synonym für aussagenlogische Formel.

> Ist es erlaubt für [mm]\varphi[/mm] und [mm]\psi[/mm] bel. Formeln nach Def.
> 2.5 zu konstruieren und bspw. in der Form von Axiom 1 in
> Beziehung zu setzen und dann behaupten die dadurch neu
> gewonnene Formel ist ein Axiom nach dem Bildungsschema 1?

Genau, so ist das offenbar gemeint.

Wobei man im Kontext dieses Kalküls etwas abweichend zu Definition 2.5 z.B. Formeln der Form [mm] $\phi\vee\psi$ [/mm] als Abkürzung für die Formel [mm] $\neg\phi\rightarrow\psi$ [/mm] interpretieren muss, damit sich wirklich alle allgemeingültigen Formeln aus den Axiomen ableiten lassen, wie von Hoffmann behauptet.

> z.B. [mm]\varphi = A_1\to A_2[/mm] und [mm]\psi = A_3\wedge 0[/mm], dann ist
> [mm]\varphi\to(\psi\to\varphi)[/mm] ein Axiom?

Genau.

> Oder ist in dem
> konkreten Bsp. [mm]\varphi\to(\psi\to\varphi)[/mm] nur ein Axiom,
> falls [mm]\varphi, \psi[/mm] wahr sind?

Nein.

Es ist auch gar nicht ohne Weiteres möglich, [mm] $\varphi$ [/mm] und [mm] $\psi$ [/mm] als wahr oder falsch zu bezeichnen. Erst bei Vorgabe einer Interpretation $I$ von [mm] $\varphi$ [/mm] kann man z.B. [mm] $\varphi$ [/mm] als wahr oder falsch unter $I$ bezeichnen (was nichts anderes als eine Sprechweise für [mm] $I\models\varphi$ [/mm] bzw. [mm] $I\not\models\varphi$ [/mm] ist).

Interpretationen/Modelle gehören zum semantischen Bereich, der Aussagenlogische Kalkül aus Kapitel 2.3.1 hingegen zum syntaktischen Bereich. Man versucht, beide Bereiche zunächst unabhängig voneinander zu halten.

Viele Grüße
Tobias


Bezug
                
Bezug
Aussagenlogisches Kalkül: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:40 Di 30.08.2022
Autor: KarlAugust

Hallo Tobias und danke für die Antwort.

Auf den o.g. Def. baut  Satz 2.7. auf, den ich hier gerne noch besprechen würde, weil dieser Satz die erste Anwendung des o.g. Kalküls im Buch beschreibt.

Satz 2.7 (Deduktionstheorem der Aussagenlogik):
Für bel. aussagenlogische Formeln [mm] $\varphi, \varphi_1,\ldots,\varphi_n$ [/mm] und [mm] $\psi$ [/mm] gilt: [mm] $\{\varphi_1,\ldots,\varphi_n\}\cup\{\varphi \}\vdash\psi \gdw \{\varphi_1,\ldots,\varphi_n\}\vdash\varphi\to\psi$ [/mm]

Die Bewiesrichtung von rechs nach links führt der Autor wie folgt:

Gilt [mm] $\{\varphi_1,\ldots,\varphi_n\}\vdash\varphi\to\psi$ [/mm] und insbesondere die Voraussetzung [mm] $\varphi$ [/mm] lässt sich mit der Schlussregel MP die Formel [mm] $\psi$ [/mm] aus den Zeichenketten [mm] $\vdash \varphi\to\psi$ [/mm] und [mm] $\vdash \varphi$ [/mm] ableiten. Daraus folgt [mm] $\{\varphi_1,\ldots,\varphi_n\}\cup\{\varphi \}\vdash\psi$. [/mm]

Metasprachlich gesehen verseckt sich hinter der Argumentationsstruktur ja auch der Modus Ponens im Sinne von, ist [mm] $p\to [/mm] q$ und  $p$ wahr, dann muss $q$ wahr sein unabhängig davon mit welcher Regel wir [mm] $\psi$ [/mm] aus den Zeichenketten [mm] $\vdash \varphi\to\psi$ [/mm] und [mm] $\vdash \varphi$ [/mm] ableiten würden.

In entgegengesetzter Richtung muss sich metasprachlich (meiner Auffassung nach) folgendes abspielen. Wenn man aus $p$ mit anderen Prämissen auf $q$ schließen kann, kann man aus den anderen Prämissen allein auf [mm] $p\to [/mm] q$ schließen.


Den Beweis führt der Autor wie folgt:  Ausgehend von einem Beweis für [mm] $\psi$ [/mm] aus [mm] $\{\varphi_1,\ldots,\varphi_n\}\cup\{\varphi \}$ [/mm] werden wir einen Beweis für [mm] $\varphi\to \psi$ [/mm] aus [mm] $$\{\varphi_1,\ldots,\varphi_n\}$ [/mm] konstruieren. Das heißt aus der vorhandenen Beweiskette [mm] $\chi_1,\ldots\chi_{m-1},\psi$ [/mm] erzeugen wir eine neue, in der nacheinander die Formeln [mm] $\varphi\to\chi_i$ [/mm] abgeleitet werden und am Ende die zu beweisende Behauptung [mm] $\varphi\to\psi$ [/mm] steht. Dazu unterscheidet der Autor 3 Fälle:

1) [mm] $\chi_i$ [/mm] ist ein Axiom oder eine Voraussetzung.
2) [mm] $\chi_i$ [/mm] ist die Formel [mm] $\varphi$ [/mm]
3) [mm] $\chi_i$ [/mm] wurde durch die Regel MP aus [mm] $\chi_j$ [/mm] und [mm] $\chi_j\to\chi_i$ [/mm] erzeugt.

Zu 1) [mm] $\vdash \chi_i$ [/mm]
      [mm] $\vdash \chi_i\to(\varphi\to\chi_i)$ [/mm] (Axiom 1)
      [mm] $\vdash \varphi\to\chi_i$ [/mm] (MP)

Zu 2) Funktioniert analog zu dem Beispiel in dem wir [mm] $A\to [/mm] A$ abgeleitet haben.

Zu 3) Wurde [mm] $\chi_i$ [/mm] mittels MP erzeugt, dann wissen wir, dass weier oben im Beweis die beiden Zeilen
     [mm] $\vdash \varphi\to\chi_j$ [/mm]
     [mm] $\vdash\varphi\to(\chi_j\to\chi_i)$ [/mm]
vorkommen müssen und wir folgendermaßen verfahren können:
     [mm] $\vdash (\varphi\to(\chi_j\to\chi_i))\to((\varphi\to\chi_j)\to(\varphi\to\chi_i))$ [/mm] (Axiom 2)
     [mm] $\vdash (\varphi\to\chi_j)\to(\varphi\to\chi_i)$ [/mm] (MP)
     [mm] $\vdash \varphi\to\chi_i$ [/mm] (MP)

Damit ist die Behauptung bewiesen.

Meine ertse Frage ist, wenn wir ohne die Voraussetzung [mm] $\varphi$ [/mm] arbeiten wollen, wer garantiert uns das in Fall 3 [mm] $\varphi$ [/mm] nicht Voraussetzung für die Ableitung von [mm] $\chi_j$ [/mm] diente?

Bezug
                        
Bezug
Aussagenlogisches Kalkül: Antwort
Status: (Antwort) fertig Status 
Datum: 18:52 Mi 31.08.2022
Autor: tobit09

Hallo Karl-August!

> Zu 3) Wurde [mm]\chi_i[/mm] mittels MP erzeugt, dann wissen wir,
> dass weier oben im Beweis die beiden Zeilen
>       [mm]\vdash \varphi\to\chi_j[/mm]
>      
> [mm]\vdash\varphi\to(\chi_j\to\chi_i)[/mm]
>  vorkommen müssen und wir folgendermaßen verfahren
> können:
>       [mm]\vdash (\varphi\to(\chi_j\to\chi_i))\to((\varphi\to\chi_j)\to(\varphi\to\chi_i))[/mm]
> (Axiom 2)
>       [mm]\vdash (\varphi\to\chi_j)\to(\varphi\to\chi_i)[/mm] (MP)
>       [mm]\vdash \varphi\to\chi_i[/mm] (MP)
>  
> Damit ist die Behauptung bewiesen.
>  
> Meine ertse Frage ist, wenn wir ohne die Voraussetzung
> [mm]\varphi[/mm] arbeiten wollen, wer garantiert uns das in Fall 3
> [mm]\varphi[/mm] nicht Voraussetzung für die Ableitung von [mm]\chi_j[/mm]
> diente?

Niemand. Die Formel [mm] $\varphi$ [/mm] kann durchaus in die Ableitung von [mm] $\chi_j$ [/mm] "eingegangen" sein (oberhalb von [mm] $\chi_j$ [/mm] Bestandteil des alten Beweises sein).

Das ändert aber nichts an Hoffmanns Argument. Er benutzt ja nur, dass die Formel [mm] $\varphi\rightarrow\chi_j$ [/mm] (und nicht etwa [mm] $\chi_j$ [/mm] selbst) im neuen Beweis auftaucht.

Viele Grüße
Tobias

Bezug
                                
Bezug
Aussagenlogisches Kalkül: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:48 Do 01.09.2022
Autor: KarlAugust


> Er benutzt ja nur, dass die Formel $ [mm] \varphi\rightarrow\chi_j [/mm] $ (und nicht etwa $ [mm] \chi_j [/mm] $ selbst) im neuen Beweis auftaucht.

Ok und wie macht er das? Wenn [mm] $\chi_i$ [/mm] durch MP aus [mm] $\chi_j$ [/mm] und  [mm] $\chi_j\to\chi_i$ [/mm] erzeugt wurde, dann wissen wir, dass weiter oben im Beweis die beiden Zeilen [mm] $\vdash \varphi\to\chi_j$ [/mm] und [mm] $\vdash \varphi\to(\chi_j\to\chi_i)$ [/mm] vorkommen. Das heißt er braucht diese beiden Zeichenketten für den neuen Beweis. Bei genauerer Betrachtung von [mm] $\vdash \varphi\to\chi_j$ [/mm] fällt mir nur folgende Ableiungsregel ein:

       [mm] $\vdash \chi_j$ [/mm]
       [mm] $\vdash\chi_j\to(\varphi\to\chi_j)$ [/mm] (Axiom 1)
       [mm] $\vdash \varphi\to\chi_j$ [/mm]  (MP)

Deshalb kann meiner Auffassung nach [mm] $\vdash \varphi\to\chi_j$ [/mm] im Beweis nicht vor  [mm] $\vdash \chi_j$ [/mm] abgeleiet werden, somit nicht weiter oben im Beweis stehen.

Bezug
                                        
Bezug
Aussagenlogisches Kalkül: Antwort
Status: (Antwort) fertig Status 
Datum: 08:35 So 04.09.2022
Autor: tobit09

Jetzt komme ich endlich zum Antworten.


Die von Hoffmann beschriebene Idee ist folgende:

Wir erzeugen aus dem alten Beweis bestehend aus [mm] $\chi_1,\ldots,\chi_m$ [/mm] (mit [mm] $\chi_m=\psi$) [/mm] SCHRITTWEISE einen neuen Beweis, der unter anderem [mm] $\varphi\rightarrow\chi_1,\ldots,\varphi\rightarrow\chi_m$ [/mm] enthält (und nicht [mm] $\varphi$ [/mm] als Voraussetzung braucht).

Dazu beginnen wir mit [mm] $\chi_1$ [/mm] und konstruieren gemäß Fällen 1), 2) oder 3) einen Beweis, der [mm] $\varphi\rightarrow\chi_1$ [/mm] enthält.
Dann erweitern wir diesen im ersten Schritt konstruierten Beweis wiederum mit der Vorgehensweise aus den Fällen 1), 2) oder 3) um weitere Beweisschritte, die [mm] $\varphi\rightarrow\chi_2$ [/mm] enthalten.
Dann erweitern wir diesen im zweiten Schritt konstruierten Beweis wiederum mit der Vorgehensweise aus den Fällen 1), 2) oder 3) um weitere Beweisschritte, die [mm] $\varphi\rightarrow\chi_3$ [/mm] enthalten.
Und so weiter...

Daher dürfen wir im Schritt, in dem wir den Beweis u.a. um eine Formel der Form [mm] $\varphi\rightarrow\chi_i$ [/mm] erweitern, annehmen, dass wir bereits einen Beweis mit allen Formeln der Form [mm] $\varphi\rightarrow\chi_j$ [/mm] für $j<i$ vorliegen haben.
Und dies nutzt Hoffmann in Fall 3).


Formalisieren lässt sich diese Idee durch einen Induktionsbeweis. Man könnte dazu z.B. eine geeignete Induktion nach der Beweislänge $m$ führen.

Bezug
                                                
Bezug
Aussagenlogisches Kalkül: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 02:20 Mo 05.09.2022
Autor: KarlAugust


> Wir erzeugen aus dem alten Beweis bestehend aus $ [mm] \chi_1,\ldots,\chi_m [/mm] $ (mit $ [mm] \chi_m=\psi [/mm] $) SCHRITTWEISE einen neuen Beweis, der unter anderem $ [mm] \varphi\rightarrow\chi_1,\ldots,\varphi\rightarrow\chi_m [/mm] $ enthält (und nicht $ [mm] \varphi [/mm] $ als Voraussetzung braucht).

Soweit kann ich folgen, allerdings bereiten mir die Details Schwierigkeiten.

Die Formulierung: "wäre $ [mm] \beta [/mm] $ das Ergebnis aus $ [mm] \alpha [/mm] $ und $ [mm] \alpha\to\beta$ [/mm] durch Anwendung von MP", bewerkstelligt, dass wir die Zeichenkette [mm] $\vdash \alpha\to\beta$ [/mm] als vorgegeben betrachten, insbesondere [mm] $\vdash\alpha$, [/mm] somit auch [mm] $\beta$ [/mm] eine im Kalkül ableitbare Formel in Zeichen [mm] $\{\alpha\}\vdash\beta$ [/mm] ist.

Da Hoffmann nun ausgehend von der Zeichenkette [mm] $\{\alpha\}\vdash\beta$ [/mm] sagt, das bedeutet im Fall 3 "wäre $ [mm] \beta [/mm] $ das Ergebnis aus $ [mm] \alpha [/mm] $ und $ [mm] \alpha\to\beta$ [/mm] durch Anwendung von MP". Dann hat er den Beweisschritt ja schon längst vollbracht. Weil daraus die entscheidende Zeichenkette $ [mm] \vdash\alpha\to\beta$ [/mm] produziert wird und sie gilt per Voraussetzung / Definition. Nun ist auch nicht mehr wichtig wie Formeln bezeichnet und aufgebaut sind. Somit sind die metasprachlichen Definitionen von $ [mm] \vdash\alpha\to\beta$ [/mm] und [mm] $\{\alpha\}\vdash\beta$ [/mm] bereits äquivalent. Und man kann auf beiden Seiten beliebig viele Voraussetzungen hinzufügen im Sinne von [mm] $\{\varphi_1,\ldots,\varphi_n\}\cup\{\alpha\}\vdash\beta$ [/mm] <=> $ [mm] \{\varphi_1,\ldots,\varphi_n\} \vdash\alpha\to\beta$ [/mm]



> Dazu beginnen wir mit $ [mm] \chi_1 [/mm] $ und konstruieren gemäß Fällen 1), 2) oder 3) einen Beweis, der $ [mm] \varphi\rightarrow\chi_1 [/mm] $ enthält.

Ok. Im Fall 1 und 2 komme ich soweit mit. Denn egal welchen Aufbau [mm] $\chi_1$ [/mm] hat, lässt sich die Formel [mm] $\varphi\to\chi_1$ [/mm] ableiten (in Zeichen [mm] $\vdash \varphi\to\chi_1$) [/mm] ohne [mm] $\varphi$ [/mm] als Voraussetzung heranzuziehen. Fall 3 macht mir Probleme. Denn [mm] $\chi_1$ [/mm] wäre Ergebnis aus [mm] $\alpha$ [/mm] und [mm] $\alpha\to\chi_1$ [/mm] durch Anwendung von MP. Und wir wissen nicht ob in der Beweiskette für [mm] $\alpha$ [/mm] (und damit auch für [mm] $\chi_1$) [/mm] in einem Ableitungsschritt [mm] $\varphi$ [/mm] eine Rolle gespielt hat. Auch wenn sich diese Ableitungsschritte in dem alten Beweis abgespielt haben, muss sich [mm] $\alpha$ [/mm] auch im neuen Beweis ableiten lassen, damit wir [mm] $\varphi\to\alpha$ [/mm] ableiten können um damit auch [mm] $\vdash \varphi\to\chi_1$ [/mm] zu beweisen.Weil man doch folgende Ableitungskette auch im neuen Beweis vollziehen muss:

   [mm] $\vdash\alpha$ [/mm]
   [mm] $\vdash \alpha\to(\varphi\to\alpha)$ [/mm]
   [mm] $\vdash \varphi\to\alpha$ [/mm]


Der Fall 3 hat für meine Begriffe eine rekursive Argumentationsstrucktur, also muss es einen Anfang geben. Das heißt wir müssen bei einem Axiom oder einer Voraussetzung starten. Nennen wir diesen Anfang oBdA [mm] $\alpha$. [/mm] Dann lässt sich auch im neuen Beweis [mm] $\vdash \varphi\to\alpha$ [/mm] ableiten. Wollen wir darüber hinaus wie Hoffmann gezeigt hat [mm] $\vdash \varphi\to\chi_1$ [/mm] ableiten, brauchen wir [mm] $\vdash \varphi\to(\alpha\to\chi_1)$. [/mm] Dieser Teil lässt sich analog zu oben durch

   [mm] $\vdash \alpha\to\chi_1$ [/mm]
   [mm] $\vdash (\alpha\to\chi_1)\to(\varphi\to(\alpha\to\chi_1))$ [/mm]
   [mm] $\vdash \varphi\to(\alpha\to\chi_1)$ [/mm]

gewinnen. Der Witz ist doch, dass  wir [mm] $\vdash \alpha\to\chi_1$ [/mm] voraussetzen bzw. aus dem alten Beweis hernehmen. Der alte Beweis hat allerdings die Menge $ [mm] \{\varphi_1,\ldots,\varphi_n\}\cup\{\varphi \} [/mm] $ als Voraussetzung, somit kann man nicht ausschließen das [mm] $\alpha$ [/mm] auch [mm] $\varphi$ [/mm] sein kann. Also begünstigt unsere metasprachliche Formulierung $ [mm] \chi_1 [/mm] $ wäre Ergebnis aus $ [mm] \alpha [/mm] $ und $ [mm] \alpha\to\chi_1 [/mm] $ durch Anwendung von MP, den Umbau der Zeichenkette von [mm] $\{\varphi \} \vdash$ [/mm] nach [mm] $\vdash\varphi\to\chi_1$. [/mm] Oder in Worten "Wenn [mm] $\{\varphi\}\vdash$ [/mm] dann [mm] $\vdash\varphi\to\chi_1$.". [/mm] Und das für belibieges [mm] $\chi_1$, [/mm] also auch einem [mm] $\chi_1$ [/mm] das nicht ableitbar wäre. Nur für die Rückrichtung ist dann wichtig das [mm] $\chi_1$ [/mm] ableitbar ist, damit metasprachlich nicht aus einer Voraussetzung p ist wahr und (p folgt q) ist wahr eine falsche (nicht ableitbare) Formel q als Konsequenz hat.


Bezug
                                                        
Bezug
Aussagenlogisches Kalkül: Antwort
Status: (Antwort) fertig Status 
Datum: 07:54 Mo 05.09.2022
Autor: tobit09


> Die Formulierung: "wäre [mm]\beta[/mm] das Ergebnis aus [mm]\alpha[/mm] und
> [mm]\alpha\to\beta[/mm] durch Anwendung von MP", bewerkstelligt,
> dass wir die Zeichenkette [mm]\vdash \alpha\to\beta[/mm] als
> vorgegeben betrachten, insbesondere [mm]\vdash\alpha[/mm], somit
> auch [mm]\beta[/mm] eine im Kalkül ableitbare Formel in Zeichen
> [mm]\{\alpha\}\vdash\beta[/mm] ist.

Hier kann ich leider nicht folgen. Wo kommen auf einmal [mm] $\alpha$ [/mm] und [mm] $\beta$ [/mm] her?

Auf alle Fälle gilt: Wenn [mm] $\alpha,\beta$ [/mm] aussagenlogische Formeln sind mit [mm] $\vdash\alpha$ [/mm] und [mm] $\vdash\alpha\to\beta$, [/mm] dann gilt auch [mm] $\vdash\beta$ [/mm] (und somit erst recht [mm] $\{\alpha\}\vdash\beta$), [/mm] wie man sich im Wesentlichen durch einmalige Anwendung des Modus Ponens überlegen kann.


> Da Hoffmann nun ausgehend von der Zeichenkette
> [mm]\{\alpha\}\vdash\beta[/mm] sagt, das bedeutet im Fall 3 "wäre
> [mm]\beta[/mm] das Ergebnis aus [mm]\alpha[/mm] und [mm]\alpha\to\beta[/mm] durch
> Anwendung von MP".

Hier habe ich den Eindruck, dass du irgendwie [mm] $\chi_j$ [/mm] und [mm] $\varphi$ [/mm] aus Hoffmanns Beweis durcheinander bringst.

> Dann hat er den Beweisschritt ja schon
> längst vollbracht. Weil daraus die entscheidende
> Zeichenkette [mm]\vdash\alpha\to\beta[/mm] produziert wird und sie
> gilt per Voraussetzung / Definition.

Deinen Punkt verstehe ich nicht. Ich glaube es liegt daran, dass mir unklar ist, was [mm] $\alpha$ [/mm] und [mm] $\beta$ [/mm] sein sollen.


> Somit sind die metasprachlichen Definitionen von
> [mm]\vdash\alpha\to\beta[/mm] und [mm]\{\alpha\}\vdash\beta[/mm] bereits
> äquivalent.

Man kann (mit der von Hoffmann beschriebenen Idee) zeigen, dass diese Äquivalenz gilt.
Trivial ist diese Äquivalenz nicht.


> > Dazu beginnen wir mit [mm]\chi_1[/mm] und konstruieren gemäß
> > Fällen 1), 2) oder 3) einen Beweis, der
> > [mm]\varphi\rightarrow\chi_1[/mm] enthält.

[...]

> Fall 3 macht mir Probleme.
> Denn [mm]\chi_1[/mm] wäre Ergebnis aus [mm]\alpha[/mm] und [mm]\alpha\to\chi_1[/mm]
> durch Anwendung von MP.

Genau. Im alten Beweis würden eine aussagenlogische Formel [mm] $\alpha$ [/mm] und auch [mm] $\alpha\to\chi_1$ [/mm] oberhalb von [mm] $\chi_1$ [/mm] stehen. Das kann aber nicht sein, weil [mm] $\chi_1$ [/mm] ja die ERSTE Formel im alten Beweis ist. Daher kann Fall 3) im ERSTEN Schritt zur Konstruktion des neuen Beweises noch nicht auftreten.

> Und wir wissen nicht ob in der
> Beweiskette für [mm]\alpha[/mm] (und damit auch für [mm]\chi_1[/mm]) in
> einem Ableitungsschritt [mm]\varphi[/mm] eine Rolle gespielt hat.

Wie gesagt: [mm] $\chi_1$ [/mm] ist der erste Beweisschritt im alten Beweis. Daher kann dieser Schritt noch kein Modus Ponens sein.


> Auch wenn sich diese Ableitungsschritte in dem alten Beweis
> abgespielt haben, muss sich [mm]\alpha[/mm] auch im neuen Beweis
> ableiten lassen,

Nein, aus [mm] $\{\varphi_1,\ldots,\varphi_n\}\cup\{\varphi\}\vdash\alpha$ [/mm] folgt im Allgemeinen NICHT [mm] $\{\varphi_1,\ldots,\varphi_n\}\vdash\alpha$. [/mm]


> damit wir [mm]\varphi\to\alpha[/mm] ableiten
> können um damit auch [mm]\vdash \varphi\to\chi_1[/mm] zu
> beweisen.

> Weil man doch folgende Ableitungskette auch im
> neuen Beweis vollziehen muss:
>  
> [mm]\vdash\alpha[/mm]
> [mm]\vdash \alpha\to(\varphi\to\alpha)[/mm]
>     [mm]\vdash \varphi\to\alpha[/mm]

Deine Idee funktioniert im Allgemeinen nicht, weil [mm] $\vdash\alpha$ [/mm] im Allgemeinen nicht gelten wird. Wir brauchen daher wohl schon Hoffmanns  Vorgehensweise.


> Der Fall 3 hat für meine Begriffe eine rekursive
> Argumentationsstrucktur,

Ja.

> also muss es einen Anfang geben.

Den Anfang stellt einfach die erste Formel des alten Beweises [mm] $\chi_1$ [/mm] dar.


> Das heißt wir müssen bei einem Axiom oder einer
> Voraussetzung starten. Nennen wir diesen Anfang oBdA
> [mm]\alpha[/mm].

Diese erste Formel des alten Beweises hatten Hoffmann und ich mit [mm] $\chi_1$ [/mm] bezeichnet. Du möchtest also nun [mm] $\chi_1$ [/mm] mit [mm] $\alpha$ [/mm] bezeichnen?

> Dann lässt sich auch im neuen Beweis [mm]\vdash \varphi\to\alpha[/mm]
> ableiten.

Ja, wenn $n=0$ (d.h. [mm] $\{\varphi\}\vdash\alpha$) [/mm] gilt. Das zeigt Hoffmann in den Fällen 1) und 2).

> Wollen wir darüber hinaus wie Hoffmann gezeigt
> hat [mm]\vdash \varphi\to\chi_1[/mm] ableiten, brauchen wir [mm]\vdash \varphi\to(\alpha\to\chi_1)[/mm].
> Dieser Teil lässt sich analog zu oben durch
>
> [mm]\vdash \alpha\to\chi_1[/mm]
>     [mm]\vdash (\alpha\to\chi_1)\to(\varphi\to(\alpha\to\chi_1))[/mm]
>  
>    [mm]\vdash \varphi\to(\alpha\to\chi_1)[/mm]
>  
> gewinnen.

Deine Idee funktioniert nicht, weil im Allgemeinen nicht [mm] $\vdash\alpha\to\chi_1$ [/mm] gelten wird.


> Der Witz ist doch, dass  wir [mm]\vdash \alpha\to\chi_1[/mm]
> voraussetzen bzw. aus dem alten Beweis hernehmen.

Wenn im alten Beweis [mm] $\alpha\to\chi_1$ [/mm] auftaucht, taucht im neuen Beweis im Allgemeinen NICHT [mm] $\alpha\to\chi_1$ [/mm] auf, sondern [mm] $\varphi\to(\alpha\to\chi_1)$. [/mm]


> Der alte
> Beweis hat allerdings die Menge
> [mm]\{\varphi_1,\ldots,\varphi_n\}\cup\{\varphi \}[/mm] als
> Voraussetzung, somit kann man nicht ausschließen das
> [mm]\alpha[/mm] auch [mm]\varphi[/mm] sein kann.

Wenn [mm] $\alpha=\varphi$ [/mm] gilt und [mm] $\varphi$ [/mm] im alten Beweis vorkommt, kommt [mm] $\varphi\to\varphi$ [/mm] im neuen Beweis vor.


Schritt 1:
[mm] $\chi_1$ [/mm] ist wie gesagt die erste Formel des alten Beweises. Demzufolge kann [mm] $\chi_1$ [/mm] noch nicht durch Modus Ponens gewonnen sein.
Auf alle Fälle können wir unseren neuen Beweis mit einer Herleitung von [mm] $\varphi\to\chi_1$ [/mm] starten und dabei mit den Voraussetzungen [mm] $\varphi_1,\ldots,\varphi_n$ [/mm] auskommen.

Schritt 2:
Die zweite Formel [mm] $\chi_2$ [/mm] des alten Beweises kann ebenfalls noch nicht durch Modus Ponens gewonnen sein, weil dazu mindestens zwei Formeln oberhalb stehen müssten.
Wie in Hoffmanns Fällen 1) und 2) beschrieben erweitern wir unseren in Schritt 1 gestarteten Beweis um eine Herleitung von [mm] $\varphi\to\chi_2$ [/mm] (wieder nur mit den Voraussetzungen [mm] $\varphi_1,\ldots,\varphi_n$). [/mm]

Schritt 3:
Nehmen wir zur Veranschaulichung als Beispiel nun an, [mm] $\chi_3$ [/mm] sei im alten Beweis durch Modus Ponens aus [mm] $\chi_1$ [/mm] und [mm] $\chi_2=\chi_1\to\chi_3$ [/mm] gewonnen.
Dann HABEN wir in Schritt 1 und 2 unseren neuen Beweis bereits u.a. mit den Formeln [mm] $\varphi\to\chi_1$ [/mm] und [mm] $\varphi\to(\chi_1\to\chi_3)$ [/mm] begonnen.
Wir können nun diesen begonnenen neuen Beweis wie von Hoffmann in Fall 3) beschrieben erweitern um weitere Zeilen hin zu [mm] $\chi_3$ [/mm] (in meinem Beispiel ist $j=1$ und $i=3$).

Bezug
                                                                
Bezug
Aussagenlogisches Kalkül: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 04:39 Di 06.09.2022
Autor: KarlAugust


> Auf alle Fälle gilt: Wenn $ [mm] \alpha,\beta [/mm] $ aussagenlogische Formeln sind mit $ [mm] \vdash\alpha [/mm] $ und $ [mm] \vdash\alpha\to\beta [/mm] $, dann gilt auch $ [mm] \vdash\beta [/mm] $ (und somit erst recht $ [mm] \{\alpha\}\vdash\beta [/mm] $), wie man sich im Wesentlichen durch einmalige Anwendung des Modus Ponens überlegen kann.

Das beschreibt ja den Beweis von rechts nach links für die folgende Aussage:

Für beliebige aussagenlogische Formeln [mm] $\alpha$ [/mm] und [mm] $\beta$ [/mm] gilt:  $ [mm] \{\alpha\}\vdash\beta \gdw\ \vdash\alpha\to\beta$. [/mm]

Für links nach rechts folgt man der Definition der Zeichenkette  $ [mm] \{\alpha\}\vdash\beta$. [/mm] Nämlich, dass wir [mm] $\beta$ [/mm] mit einer Formelkette [mm] $\alpha_1 [/mm] , [mm] \ldots ,\alpha_n$ [/mm] ableiten können, die nach folgendem Schema aufgebaut ist:

1) [mm] $\alpha_i$ [/mm] ist ein Axiom oder eine Formel aus der Menge [mm] $\{\alpha\}$ [/mm]
2) Oder [mm] $\alpha_i$ [/mm] entsteht aus den vorangegangen Gliedern der Beweiskette durch die Anwendung einer Schlussregel (in unserem Fall kommt nur eine Schlussregel in Frage, nämlich MP).

Fall 3 ist ja der Teil aus Punkt 2. Dank deiner Erklärungen kann ich nun dem WIE (es funktioniert) folgen. Das WARUM (beschreibt man den Kalkül ausgerechnet so) verschließt sich mir noch.  

Grundsätzlich scheint man ja sagen zu wollen, dass der Kalkül so zu funktionieren hat, damit es für den MP eine Rückrichtung gibt. Wenn man aus $ [mm] \varphi [/mm] $ mit anderen Prämissen [mm] $\{\varphi_1 , \ldots ,\varphi_n\}$ [/mm] auf $ [mm] \psi [/mm] $ schließen kann, kann man aus den anderen Prämissen allein auf $ [mm] \varphi \to \psi [/mm] $ schließen. Statt schließen sagt man ableiten.

Würde man eine weitere Regel entwerfen die diesen Schluss zulässt, liese sich dann der Kalkül weiter verschlanken, also würde man dann mit weniger Axiomen auskommen? Ziel ist doch, dass die Zerlegung / Zusammensetzung (Ableitung) von Formeln dem Wesen einer aussagenlogischen Implikation entsprechen, also die Wahrheitstafel erfüllen.

Speziell die Kalküle von Hilbert und Ackermann, Rosser und Kleene scheinen mir noch komplizierterer zu sein. Stehen aber für die gleiche Sache. Oder sind es die kleinst möglichen Kalküle. Im Sinne der Anzahl von Regeln und Axiomen?

Bezug
                                                                        
Bezug
Aussagenlogisches Kalkül: Antwort
Status: (Antwort) fertig Status 
Datum: 06:19 Do 08.09.2022
Autor: tobit09


> Grundsätzlich scheint man ja sagen zu wollen, dass der
> Kalkül so zu funktionieren hat, damit es für den MP eine
> Rückrichtung gibt. Wenn man aus [mm]\varphi[/mm] mit anderen
> Prämissen [mm]\{\varphi_1 , \ldots ,\varphi_n\}[/mm] auf [mm]\psi[/mm]
> schließen kann, kann man aus den anderen Prämissen allein
> auf [mm]\varphi \to \psi[/mm] schließen. Statt schließen sagt man
> ableiten.
>
> Würde man eine weitere Regel entwerfen die diesen Schluss
> zulässt, liese sich dann der Kalkül weiter verschlanken,
> also würde man dann mit weniger Axiomen auskommen?

Mir fallen hier Kalküle des natürlichen Schließens ein, die üblicherweise völlig ohne Axiome auskommen, dafür aber deutlich mehr Schlussregeln haben.

Diese Kalküle gefallen mir, weil sie der alltäglichen mathematischen Praxis sehr nahe kommen. Allerdings scheint es aufwändiger zu sein, damit metamathematische Überlegungen anzustellen.


> Ziel
> ist doch, dass die Zerlegung / Zusammensetzung (Ableitung)
> von Formeln dem Wesen einer aussagenlogischen Implikation
> entsprechen, also die Wahrheitstafel erfüllen.

Zentrales Ziel wohl jeder Definition von [mm] $\vdash$ [/mm] ist, die Äquivalenz von [mm] $\Sigma\vdash\psi$ [/mm] (syntaktischem Folgerungsbegriff) und [mm] $\Sigma\models\psi$ [/mm] (semantischem Folgerungsbegriff) für alle Formelmengen [mm] $\Sigma$ [/mm] und Formeln [mm] $\psi$ [/mm] zu erreichen.

Die Implikation [mm] $\Sigma\vdash\psi\Rightarrow\Sigma\models\psi$ [/mm] (für alle Formelmengen [mm] $\Sigma$ [/mm] und Formeln [mm] $\psi$) [/mm] nennt man auch Korrektheit des Kalküls; die Implikation [mm] $\Sigma\models\psi\Rightarrow\Sigma\vdash\psi$ [/mm] nennt man Vollständigkeit des Kalküls.

> Speziell die Kalküle von Hilbert und Ackermann, Rosser und
> Kleene scheinen mir noch komplizierterer zu sein. Stehen
> aber für die gleiche Sache.

Mit diesen Kalkülen kenne ich mich nicht aus. Wichtiger als die Einzelheiten dieser Kalküle finde ich, dass grundsätzlich für die klassische Aussagenlogik oder auch die klassische Prädikatenlogik der ersten Stufe korrekte und vollständige syntaktische Kalküle existieren.

> Oder sind es die kleinst
> möglichen Kalküle. Im Sinne der Anzahl von Regeln und
> Axiomen?

Auch da bin ich überfragt. Ich vermute, dass die Kalküle keine Axiome und Regeln enthalten, die ersatzlos überflüssig sind. Wenn man Untersuchungen über minimale Anzahlen von Regeln/Axiomenschemata anstellen wollte, müsste man wohl erst einmal festlegen, welche Art Regeln und Axiomenschemata zulässig sind.

Bezug
                                                                                
Bezug
Aussagenlogisches Kalkül: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 20:49 Do 08.09.2022
Autor: KarlAugust


> ...Kalküle des natürlichen Schließens ein... Zentrales Ziel wohl jeder Definition von $ [mm] \vdash [/mm] $ ist, die Äquivalenz von $ [mm] \Sigma\vdash\psi [/mm] $ (syntaktischem Folgerungsbegriff) und $ [mm] \Sigma\models\psi [/mm] $ ...

Ich meinte eher das Ziel des Satzes 2.7. Beim Kalkül des natürlichen Schließens gibt es tatsächlich eine Regel für die Beweisrichtung die wir hier ausführlich diskutiert haben, nämlich die Implikationseinführung, welche sich durch das Deduktionstheorem begründet. David Hilbert, Paul Bernays formulierten das in Grundlagen der Mathematik, Band 2, Berlin: 1939, Seite 387 so: "Wenn aus einer Formel A eine Formel B in solcher Weise ableitbar ist [...], dann ist die Formel A [mm] $\to$ [/mm] B ohne Benutzung der Formel A ableitbar.“ Das heißt doch, wenn ich diese Schlussregel dem besprochenen Kalkül hinzufüge, dann ist die Beweisrichtung von links nach rechts ebenso trivial wie umgekehrt. Und meine Frage zeilte darauf ab ob man bei Hinzunahme dieser Regel evtl. mit weniger Axiomen zurechtkommt.


> ...Mit diesen Kalkülen kenne ich mich nicht aus.... Auch da bin ich überfragt. Ich vermute, dass die Kalküle keine Axiome und Regeln enthalten, die ersatzlos überflüssig sind. Wenn man Untersuchungen über minimale Anzahlen von Regeln/Axiomenschemata anstellen wollte, müsste man wohl erst einmal festlegen, welche Art Regeln und Axiomenschemata zulässig sind.

Hoffmann bemerkt abschließend im Kapitel, dass diese Kalküle eine alternative Axiomatisierung der Aussagenlogik bilden. Ebenso sind diese Kalküle korrekt und vollständig.

Bezug
                                                                                        
Bezug
Aussagenlogisches Kalkül: Antwort
Status: (Antwort) fertig Status 
Datum: 11:06 Sa 24.09.2022
Autor: tobit09


> Ich meinte eher das Ziel des Satzes 2.7. Beim Kalkül des
> natürlichen Schließens gibt es tatsächlich eine Regel
> für die Beweisrichtung die wir hier ausführlich
> diskutiert haben, nämlich die Implikationseinführung,
> welche sich durch das Deduktionstheorem begründet. David
> Hilbert, Paul Bernays formulierten das in Grundlagen der
> Mathematik, Band 2, Berlin: 1939, Seite 387 so: "Wenn aus
> einer Formel A eine Formel B in solcher Weise ableitbar ist
> [...], dann ist die Formel A [mm]\to[/mm] B ohne Benutzung der
> Formel A ableitbar.“ Das heißt doch, wenn ich diese
> Schlussregel dem besprochenen Kalkül hinzufüge, dann ist
> die Beweisrichtung von links nach rechts ebenso trivial wie
> umgekehrt. Und meine Frage zeilte darauf ab ob man bei
> Hinzunahme dieser Regel evtl. mit weniger Axiomen
> zurechtkommt.

Jetzt hatte ich endlich Zeit, mir dies zu überlegen.

Vorweg: Wenn wir diese Implikationseinführung in unseren Kalkül aufnehmen (und somit zusammen mit dem Modus Ponens quasi einen Kalkül des natürlichen Schließens für eine Aussagenlogik nur mit Implikation als Junktor erhalten), ändert sich der Aufbau von Beweisen grundsätzlich: Während bei Hoffmanns Kalkül ein Beweis einfach nur eine endliche Folge von Formeln ist, muss ein Kalkül mit dieser Implikationseinführung wohl zu jeder Zeile festhalten, welche Formeln als Voraussetzung dieser Zeile dienen.

Ich habe nun nachgeprüft: Die Instanzen der Axiome (A.1) und (A.2) von Hoffmann sind mit der genannten Implikationseinführung und Modus Ponens herleitbar, wären also in einem wie von dir angedeuteten Kalkül überflüssig.

Die Instanzen von Hoffmanns Axiom (A.3) sind hingegen i.A. NICHT durch die Implikationseinführung und Modus Ponens allein herleitbar. Das sollte anschaulich nicht überraschen, weil (A.3) eine Aussage über Negationen trifft und Implikationseinführung und Modus Ponens nicht explizit Negationen thematisieren.

(Formal beweisen lässt sich meine Behauptung, dass (A.3) i.A. nicht durch Implikationseinführung und Modus Ponens herleitbar ist, grob skizziert z.B. mithilfe einer alternativen Semantik, die [mm] $\neg\varphi$ [/mm] als gleichbedeutend mit [mm] $\varphi$ [/mm] interpretiert (für jede Formel [mm] $\varphi$). [/mm] Auch für diese Semantik ist ein Kalkül, der nur aus Implikationseinführung und Modus Ponens besteht, korrekt. Es gibt jedoch Instanzen von (A.3), die im Sinne dieser alternativen Semantik nicht allgemeingültig sind. Also können diese Instanzen auch nicht mit dem Kalkül aus Implikationseinführung und Modus Ponens hergeleitet werden.)

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


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]