Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Logik, Mengen & Beweistechnik » Aussagenlogik » Unzulässiger Schluss?
Autor
Universität/Hochschule Unzulässiger Schluss?
Finn0
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 30.06.2021
Mitteilungen: 54
  Themenstart: 2022-12-02

Für $p\implies (q\lor r)\vdash (p\implies q)\lor (p\implies r)$ findet sich im ProofWiki: Implication is Left Distributive over Disjunction/Formulation 1/Forward Implication Mir erscheint Schritt 11 unzulässig. Was ist davon zu halten?


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8117
Wohnort: Milchstraße
  Beitrag No.1, eingetragen 2022-12-02

Hallo, ist das Theorem denn überhaupt korrekt? Beispiel: p = der Hahn kräht auf dem Mist q = das Wetter ändert sich r = das Wetter ändert sich nicht


   Profil
Zwerg_Allwissend
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 316
  Beitrag No.2, eingetragen 2022-12-02

\quoteon(2022-12-02 10:22 - Finn0 im Themenstart) Für $p\implies (q\lor r)\vdash (p\implies q)\lor (p\implies r)$ findet sich im ProofWiki: Implication is Left Distributive over Disjunction/Formulation 1/Forward Implication Mir erscheint Schritt 11 unzulässig. Was ist davon zu halten? \quoteoff Wenn der Kalkül vollständig ist, dann stimmt es denn die linke Seite is äquivalent zu ~p v q v r and die rechte Seite zu (~p v q) v (~p v r).


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1304
Wohnort: Kiel, Deutschland
  Beitrag No.3, eingetragen 2022-12-02

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) "Wenn aus der Tatsache, dass der Hahn auf dem Mist kräht, folgt, dass das Wetter sich ändert oder dass das Wetter sich nicht ändert, dann dürfen wir folgern, dass eine der folgenden Aussagen hergeleitet werden kann: (1) Wenn der Hahn auf dem Mist kräht, ändert sich das Wetter. (2) Wenn der Hahn auf dem Mist kräht, ändert sich das Wetter nicht. (1) und (2), jeweils für sich genommen, würde ich nicht als wahre Aussagen betrachten wollen. Hier ist zudem \(q\lor r\) äquivalent zu \(\top\), und das muss im allgemeinen Fall keineswegs so sein. Also haben wir hier ein ausgezeichnetes Gegenbeispiel: wenn \(q\lor r\) äquivalent zu \(\top\) ist, dann ist der Schluss \[ p\implies (q\lor r)\vdash (p\implies q)\lor (p\implies r) \] nicht korrekt. mfg thureduehrsen [Die Antwort wurde nach Beitrag No.1 begonnen.]\(\endgroup\)


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 1304
Wohnort: Kiel, Deutschland
  Beitrag No.4, eingetragen 2022-12-02

Hmmmm... fragen wir mal Christian Gottschalls Logikrechner... Ich sage (noch) nicht, dass Schritt 11 im ProofWiki-Beweis nicht korrekt ist. Aber leicht zu lesen ist die dort angegebene Tabelle nicht unbedingt. mfg thureduehrsen


   Profil
Finn0
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 30.06.2021
Mitteilungen: 54
  Beitrag No.5, vom Themenstarter, eingetragen 2022-12-02

Die Formel scheint keine intuitionistische Tautologie zu sein. Ich mutmaße, ein Kontramodell bezüglich Kripke-Semantik gefunden zu haben, sofern mir keine Flüchtigkeitsfehler untergekommen sind. \sourceon Python \numberson def is_reflexive(W, le): return all(le(x, x) for x in W) def is_transitive(W, le): return all(not (le(x, y) and le(y, z)) or le(x, z) for x in W for y in W for z in W) def is_preorder(W, le): return (is_reflexive(W, le) and is_transitive(W, le)) def is_monotonous(sat, V, W, le): for v in V: for w in W: for wp in W: if le(w, wp) and not (not sat(w, v) or sat(wp, v)): print(w, wp, v) return False return True # V: Liste der Variablen # W: Liste der Welten # rho(w, v): Bewertung der Variable v in der Welt w # order: Quasiordnung # le(w, wp): w <= wp; die Abkürzung steht für less than or equal # sat(w, phi): w |= phi; die Abkürzung steht für satisfies # wp: w'; Abkürzung für w prime, w Strich def Kripke(V, W, rho, order): def le(w1, w2): return (w1, w2) in order def sat(w, phi): if isinstance(phi, str): return rho[(w, phi)] elif isinstance(phi, list): op = phi[0] if op == "and": return sat(w, phi[1]) and sat(w, phi[2]) elif op == "or": return sat(w, phi[1]) or sat(w, phi[2]) elif op == "=>": return all(not sat(wp, phi[1]) or sat(wp, phi[2]) for wp in W if le(w, wp)) elif op == "not": return all((not sat(wp, phi[1])) for wp in W if le(w, wp)) assert is_preorder(W, le) assert is_monotonous(sat, V, W, le) return sat # Einfacheres Beispiel: # w0 erfüllt nicht die Formel (not not p) => p def check0(): w0 = "w0"; w1 = "w1"; p = "p" W = [w0, w1] rho = {(w0, p): False, (w1, p): True} order = {(w0, w0), (w0, w1), (w1, w1)} sat = Kripke([p], W, rho, order) print(sat(w0, ["=>", ["not", ["not", p]], p])) # w0 erfüllt nicht die Formel # (p => q or r) => (p => q) or (p => r) def check1(): p = "p"; q = "q"; r = "r" w0 = "w0"; w1 = "w1"; w2 = "w2" W = ["w0", "w1", "w2"] order = {(w0, w0), (w1, w1), (w2, w2), (w0, w1), (w0, w2)} rho = { (w0, p): False, (w0, q): False, (w0, r): False, (w1, p): True, (w1, q): False, (w1, r): True, (w2, p): True, (w2, q): True, (w2, r): False } sat = Kripke([p, q, r], W, rho, order) phi = ["=>", ["=>", p, ["or", q, r]], ["or", ["=>", p, q], ["=>", p, r]]] print(sat(w0, phi)) check1() \sourceoff


   Profil
Zwerg_Allwissend
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 316
  Beitrag No.6, eingetragen 2022-12-02

(1) Wenn der Hahn kräht auf dem Mist, ändert sich das Wetter (2) oder es bleibt wie es ist. Ist so weit ich mich erinnere einer der Gödelsätze und geht auf eine Vermutung von Leipniz zurück.


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8117
Wohnort: Milchstraße
  Beitrag No.7, eingetragen 2022-12-02

Wer ist Leipniz? 🙃 Ich gebe aber zu, noch einen Knoten im Kopf zu haben. Einerseits ist dem nichts entgegen zu setzen: \quoteon(2022-12-02 13:21 - Zwerg_Allwissend in Beitrag No. 2) Wenn der Kalkül vollständig ist, dann stimmt es denn die linke Seite ist äquivalent zu ~p v q v r und die rechte Seite zu (~p v q) v (~p v r). \quoteoff Andererseits hier mal ein anderes Beispiel. x und y seien reelle Zahlen. Dann gilt \(x\neq y\implies (x>y\vee xy\) und \(\psi\equiv x\neq y\implies x


   Profil
Finn0
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 30.06.2021
Mitteilungen: 54
  Beitrag No.8, vom Themenstarter, eingetragen 2022-12-02

Liegt da nicht Scheinparadox mangels expliziter Quantoren vor? Die einzeln stehenden Formeln $\phi,\psi$ werden für sich bereits allquantifiziert. Bei der Formel $\phi\lor\psi$ kommt die Allquantifizierung dagegen erst nach der Oder-Verknüpfung.


   Profil
Folgende Antworten hat der Fragensteller vermutlich noch nicht gesehen.
Zwerg_Allwissend
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 316
  Beitrag No.9, eingetragen 2022-12-03

\quoteon(2022-12-02 20:16 - StrgAltEntf in Beitrag No. 7) Andererseits hier mal ein anderes Beispiel. x und y seien reelle Zahlen. Dann gilt \(x\neq y\implies (x>y\vee xy\) und \(\psi\equiv x\neq y\implies x b durch ~a v b ersetzen, s. Beitrag #2. Genauso kann man fragen: Es gilt weder a noch ~a. Wieso gilt dann a v ~a ? \quoteon(2022-12-02 21:20 - Finn0 in Beitrag No. 8) Liegt da nicht Scheinparadox mangels expliziter Quantoren vor? Die einzeln stehenden Formeln $\phi,\psi$ werden für sich bereits allquantifiziert. Bei der Formel $\phi\lor\psi$ kommt die Allquantifizierung dagegen erst nach der Oder-Verknüpfung. \quoteoff Wieso Quantoren? x und y sind in dem Beispiel Konstanten.


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8117
Wohnort: Milchstraße
  Beitrag No.10, eingetragen 2022-12-03

\quoteon(2022-12-03 00:51 - Zwerg_Allwissend in Beitrag No. 9) Wieso Quantoren? x und y sind in dem Beispiel Konstanten. \quoteoff Nein, x und y sollen freie Variablen sein.


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2686
  Beitrag No.11, eingetragen 2022-12-12

\quoteon(2022-12-02 16:05 - Finn0 in Beitrag No. 5) Die Formel scheint keine intuitionistische Tautologie zu sein. \quoteoff Das ist richtig.


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2686
  Beitrag No.12, eingetragen 2022-12-12

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}} \newcommand{\monus}{\mathbin {∸}}\) Als Ergänzung zu #11 mal ein Gegenbeispiel in Form einer Heyting-Algebra: \sourceon ASCII-Art 1 | M / \ L R \ / 0 \sourceoff Hier gelten $L \lor R = M$, $M \to L = L$, $M \to R = R$ (und natürlich $x \to x = 1$ für alle $x$), und damit $M \to L \lor R = 1 \not \le M = (M \to L) \lor (M \to R)$. Der verlinkte Beweis benutzt, soweit ich sehe, nur Regeln, die für intuitionistische Logik korrekt sind. Er muss daher fehlerhaft sein (mit klassischer Logik könnte man jedoch zeigen, was da gezeigt werden soll). Und wenn man genauer hinschaut: Ja, mindestens die Anwendung der Regel PBC in 11. ist fehlerhaft. Aber der Beweis ist auch darüber hinaus ziemlich seltsam. Durch geringstmögliche Änderungen am verlinkten "Beweis" kann man einen korrekten Beweis von $$p\implies (q\lor r)\vdash p\implies((p\implies q)\lor (p\implies r))$$ erhalten. \(\endgroup\)


   Profil

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-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]