Finden Sie Aussagenformeln ϕϕ\phi und ψψ\psi, so dass (ϕ→(ψ→(¬ψ)))(ϕ→(ψ→(¬ψ)))(\phi \rightarrow (\psi \rightarrow (¬\psi ))) ist ein Satz von L.

Question

Finden Sie Aussagenformeln ϕϕ\phi und ψψ\psi, so dass (ϕ→(ψ→(¬ψ)))(ϕ→(ψ→(¬ψ)))(\phi \rightarrow (\psi \rightarrow (¬\psi ))) ist ein Satz von L.

Logik
Mathematik
formale Beweise
Aussagenkalkül

ZZS14

Satzformeln finden $\phi$ Und $\psi$ so dass $(\phi \rightarrow (\psi \rightarrow (¬\psi)))$ ist ein Satz von L.

Jedes Axiom ist also ein Theorem von L, also dachte ich, es gäbe eine Möglichkeit, es zu schreiben $(\phi \rightarrow (\psi \rightarrow (¬\psi)))$ in Bezug auf einige Variablen $p_1, p_\ldots$ so dass es eines der Axiome ist;

(A1) $(\phi \rightarrow ( \psi \rightarrow \phi))$

(A2) $((\phi \rightarrow (\psi \rightarrow \chi))\rightarrow((\phi \rightarrow \psi)\rightarrow(\psi \rightarrow \chi)))$

(A3) $(((¬\phi) \rightarrow (¬\psi)) \rightarrow (\psi \rightarrow \phi))$

Aber ich bin mir nicht sicher, wie das geht oder ob es überhaupt der richtige Ansatz ist. Danke

Durch den Versuch, A3 zu verwenden, habe ich bekommen $((p_1 \rightarrow (p_2 \rightarrow p_3)) \rightarrow ((p_1 \rightarrow p_2) \rightarrow (p_1 \rightarrow p_3)))$ aber ich nehme an, das ist völlig falsch.

Derivat

Wenn es ein Theorem von ist

L

$L$ dann muss es immer wahr sein, mach einfach eine Wahrheitstabelle und schau, welche Bedingungen das sind

ϕ

$\phi$ befriedigen muss.

Martin Schleziak

@GitGud Ich bin mir nicht sicher, ob Sie ein Formal-Proofs- Tag erstellt haben, aber dies ist die älteste Frage, die ich gefunden habe und die dieses Tag enthält. Wenn Sie dieses Tag erstellt haben, könnten Sie sich einen Beitrag zu diesem Tag auf Meta ansehen ? Danke!

Git Gud

@MartinSleziak Ich habe es erstellt. Danke, werde ich mir ansehen.

Antworten (4)

Finden Sie Aussagenformeln ϕϕ\phi und ψψ\psi, so dass (ϕ→(ψ→(¬ψ)))(ϕ→(ψ→(¬ψ)))(\phi \rightarrow (\psi \rightarrow (¬\psi ))) ist ein Satz von L.

Wenn es ein Theorem von ist $L$ dann muss es immer wahr sein, mach einfach eine Wahrheitstabelle und schau, welche Bedingungen das sind $\phi$ befriedigen muss.
@GitGud Ich bin mir nicht sicher, ob Sie ein Formal-Proofs- Tag erstellt haben, aber dies ist die älteste Frage, die ich gefunden habe und die dieses Tag enthält. Wenn Sie dieses Tag erstellt haben, könnten Sie sich einen Beitrag zu diesem Tag auf Meta ansehen ? Danke!
@MartinSleziak Ich habe es erstellt. Danke, werde ich mir ansehen.

Mauro ALLEGRANZA · Answer 1

Axiome sind mit schematischen Buchstaben formuliert . In :

(A1) $(A→(B→A))$

$A$ Und $B$ sind in der Metasprache variabel , die für Formeln bleiben; wir können sie durch beliebige Formeln ersetzen und erhalten immer eine Instanz des Axioms.

Also wenn $\varphi$ Und $\psi$ Formeln sind, wie von Git Gud vorgeschlagen, die folgenden sind beide Instanzen von (A1) :

$\vdash (\varphi → (\psi → \varphi))$

Und

$\vdash (\lnot \psi →(\psi → \lnot \psi))$ .

Der erste wurde mit dem Subst der Formel erhalten $\varphi$ anstelle des schematischen Buchstabens $A$ und mit $\psi$ anstelle von $B$ .

Der zweite mit dem Subst der Formel $\lnot \psi$ anstelle des schematischen Buchstabens $A$ und mit $\psi$ anstelle von $B$ .

Die einzige Sorge, auf die wir achten müssen, ist, dass die Substitution einheitlich sein muss (gemäß Kommentar von Hunan Rostomyan), dh wir müssen jedes Auftreten von, sagen wir, $A$ mit der gleichen Formel.

Git Gud · Answer 2

Git Gud

Betrachtet man das erste Axiom, genügt es, dies zu fordern $\phi=\left(\neg \psi\right)$ , also lass $\phi=(\neg p)$ Und $\psi =p$ .

ZZS14

kannst du das einfach sagen? denn anfangs dachte ich das, aber dann dachte ich nicht, dass du das kannst. so würde die Antwort lauten;

(p_{1} \to ((\neg p_{1}) \to p_{1}))

$(p_1 \rightarrow ((¬p_1) \rightarrow p_1))$ ? Oder verstehe ich es falsch?

Hunan Rostomyan

Die Axiome sind unter einheitlicher Substitution abgeschlossen, das würde also nicht funktionieren. Würde es?

Git Gud

@HunanRostomyan Ich weiß nicht, wovon du sprichst, ich habe noch nie von einheitlicher Substitution gehört.

Hunan Rostomyan

@GitGud Es bedeutet

(p \to (q \to p))

$(p \rightarrow (q \rightarrow p))$ ist eine Instanz von (A1), während

(p \to (q \to r))

$(p \rightarrow (q \rightarrow r))$ ist nicht. Mit anderen Worten, Sie können nicht einzelne Vorkommen von Variablen ersetzen, sondern müssen sie alle ersetzen.

ZZS14

@HunanRostomyan danke, könnten Sie möglicherweise zur Beantwortung der Frage beitragen??

Git Gud

@ZZS14 Ihr Beispiel funktioniert nicht, da das erste Axiom Ihnen gibt, was Sie sagen, aber Sie wollen

(p_{1} \to ((\neg p_{1}) \to (\neg (\neg p_{1}))))

$(p_1 \rightarrow ((¬p_1) \rightarrow (\neg(\neg p_1))))$ . Versuchen

(\neg p) \to (p \to (\neg p))

$(\neg p)\to (p\to (\neg p))$ stattdessen.

ZZS14

wie bist du darauf gekommen?

Git Gud

@ZZS14 Was genau?

Git Gud

@HunanRostomyan Entschuldigung für die Verzögerung, du hast Recht, aber wie mache ich nicht das, was du beschrieben hast?

ZZS14

Ich habe mich verwirrt. also möchte ich Axiom 1 verwenden? und ersetzen

ϕ

$\phi$ für

(\neg ψ)

$(¬\psi)$ ?

Hunan Rostomyan

@GitGud Versteht uns das, was du beschrieben hast, nicht:

\neg ψ \to (ψ \to \neg ψ)

$\lnot\psi \rightarrow (\psi \rightarrow \lnot\psi)$ anstatt

ϕ \to (ψ \to \neg ψ)

$\phi \rightarrow (\psi \rightarrow \lnot\psi)$ ?

Git Gud

@HunanRostomyan Du hast Recht, ich sehe einfach nicht, wie es irgendetwas von dem widerspricht, was ich gesagt habe. Wir wollen Formeln finden

ϕ

$\phi$ Und

ψ

$\psi$ so dass

(ϕ \to (ψ \to (\neg ψ)))

$(\phi \rightarrow (\psi \rightarrow (¬\psi)))$ hält. Axiom 1 mit

ϕ = \neg p

$\phi=\neg p$ Und

ψ = p

$\psi = p$ Erträge

(\underset{ϕ}{\underset{⏟}{(\neg p)}} \to (\underset{ψ}{\underset{⏟}{p}} \to \underset{ϕ = \neg ψ}{\underset{⏟}{(\neg p)}}))

$(\underbrace{(\neg p)}_{\phi}\to (\underbrace{p}_{\psi}\to \underbrace{(\neg p)}_{\phi =\neg \psi}))$ .

Hunan Rostomyan

@GitGud Das Ersetzen von nicht psi in der angegebenen Formel ergibt ein Axiom! Das ist richtig. Ich habe Sie fälschlicherweise so interpretiert, dass: Axiom 1, wenn nicht nicht für phi eingesetzt wird, ergibt die gegebene Formel. Du hast absolut recht.

Git Gud

@ ZZS14 Siehe meinen Kommentar oben. Hilft es?

ZZS14

Ja, aber ich bin jetzt verwirrt, weil du es getan hast

((\neg p) \to (p \to (\neg p)))

$((¬p) \rightarrow (p \rightarrow (¬p)))$

ZZS14

und die Frage ist

(ϕ \to (ψ \to (\neg ψ)))

$(\phi \rightarrow (\psi \rightarrow (¬\psi)))$ so sicherlich sollten wir haben

(p \to (p \to (\neg p)))

$(p \rightarrow (p \rightarrow (¬p)))$

Git Gud

@ZZS14 Ich verstehe nicht, warum du denkst, dass es so sein sollte. Denkst du

ϕ

$\phi$ kann nicht damit anfangen

\neg

$\neg$ ?

ZZS14

Ja, weil es in der Frage, die wir bekommen, keine Verneinung gibt?

Git Gud

@ZZS14 Es kann,

ϕ

$\phi$ ist eine Formel. Sie sollten wissen, bevor Sie auf dieses Problem gestoßen sind

(\neg p)

$(\neg p)$ ist eine Formel, wo

p

$p$ ist ein Vorschlagsschreiben. So können Sie zu Recht ersetzen

ϕ

$\phi$ mit

(\neg p)

$(\neg p)$ .

ZZS14

Okay, ich hatte nur etwas von der Form erwartet, die in der Frage angegeben war. Danke. Nur um meine Antwort jetzt klarzustellen ist ((¬p)

\to

$\rightarrow$ (P

\to

$\rightarrow$ (¬p))) und ich kann dies überprüfen, indem ich die Wahrheitstabelle konstruiere und sie muss in allen Zeilen den Wahrheitswert T haben, da es ein Satz von L ist, der eine Tautologie sein muss?

Git Gud

@ ZZS14 Ja, und der Vollständigkeitssatz sagt Ihnen, dass es beweisbar ist, da es sich um eine Tautologie handelt. Eine andere Möglichkeit, es zu bestätigen, um semantisch darüber nachzudenken. Wenn es falsch war, dann

(\neg p)

$(\neg p)$ wäre wahr und

((p \to (\neg p)))

$((p → (¬p)))$ wäre falsch. Aber

(\neg p)

$(\neg p)$ wahr sein bedeutet

p

$p$ ist falsch, also

(p \to (\neg p))

$(p → (¬p))$ muss wahr sein. So

(p \to (\neg p))

$(p → (¬p))$ ist sowohl wahr als auch falsch, ein Widerspruch.

ZZS14

danke für all deine Hilfe

Git Gud

@ZZS14 Gern geschehen.

Doug Spoonwood

((¬p) →(p → (¬p))) ist eine Substitutionsinstanz von (ϕ→(ψ→ϕ)) (oder man kann daraus ((¬p) →(p → (¬p))) erhalten (ϕ→(ψ→ϕ)) durch Substitution). Da die (einheitliche) Substitution aus einer wahrheitserhaltenden Transformation besteht und (ϕ→(ψ→ϕ)) ein Axiom ist, folgt aus dem Korrektheitsmetasatz, dass ((¬p) →(p → (¬p))) ist eine Tautologie.

Doug Spoonwood

Diese Antwort scheint elegant, aber sie könnte die beabsichtigte Lektion dieses Problems verfehlen.

Willem · Answer 3

Interessante Frage und ich denke, es gibt drei Möglichkeiten:

$\phi \equiv (\psi \rightarrow (¬\psi)$ (z.B. wenn $\phi$ Ist $\psi \rightarrow \lnot \psi)$ aber einfache Gleichheit ist genug.
$\lnot \phi$ ein Theorem ist, dann erhalten Sie einen unmöglichen Antezedens .
$\psi \rightarrow \lnot\psi$ ist ein Theorem, was der Fall sein wird, wenn $\lnot\psi$ ein Theorem ist, dann erhalten Sie wahre Konsequenz .

Jede dieser drei steht natürlich für eine unendliche Anzahl von Formeln, also haben Sie eine Auswahl.

Doug Spoonwood · Answer 4

Was ist "(ϕ→(ψ→(¬ψ)))"? Es ist eine Bedingung.

Was wissen wir über alle Konditionale? Sie haben einen Vorläufer und einen Nachsatz.

Was ist der Vorläufer von (ϕ→(ψ→(¬ψ))), und was ist der Nachsatz? Der Vordersatz ist ϕ und der Nachsatz ist (ψ→(¬ψ).

Wie könnten wir also (ϕ→(ψ→(¬ψ))) in einen Satz umwandeln? Nun, alle Tautologien sind Sätze nach dem Vollständigkeitssatz. Wie könnten wir also (ϕ→(ψ→(¬ψ))) zu einer Tautologie machen?

Nehmen wir an, wir haben ϕ durch (ψ→(¬ψ)) ersetzt. Wir hätten dann die wohlgeformte Formel [(ψ→(¬ψ))→(ψ→(¬ψ))]. Wir könnten also ϕ durch (p→(¬p)) und ψ durch p ersetzen, um eine Formel zu erhalten, die ein Theorem von L ist.

Finden Sie Aussagenformeln ϕϕ\phi und ψψ\psi, so dass (ϕ→(ψ→(¬ψ)))(ϕ→(ψ→(¬ψ)))(\phi \rightarrow (\psi \rightarrow (¬\psi ))) ist ein Satz von L.

ZZS14

Derivat

Martin Schleziak

Git Gud

Antworten (4)

Mauro ALLEGRANZA

Git Gud

ZZS14

Hunan Rostomyan

Git Gud

Hunan Rostomyan

ZZS14

Git Gud

ZZS14

Git Gud

Git Gud

ZZS14

Hunan Rostomyan

Git Gud

Hunan Rostomyan

Git Gud

ZZS14

ZZS14

Git Gud

ZZS14

Git Gud

ZZS14

Git Gud

ZZS14

Git Gud

Doug Spoonwood

Doug Spoonwood

Willem

Doug Spoonwood