Zeigen Sie, dass TAUT entscheidbar ist.

Question

Kann jemand mir bei diese Aufgabe helfen? Ich brauche dringende Hilfe. Ich muss die Aufgabe am Montag präsentiere aber ich weiß nicht, wie es geht.

Sei   TAUT:= {⟨F⟩| F∈ L ist eine Tautologie}

Zeigen Sie, dass TAUT entscheidbar ist.

Comments

Was ist ⟨F⟩?

Was ist L?

---

L ist die Sprache von Aussagenlogische Formeln und <F> ist  eine Klasse, die alle Tautologien enthält

---

L kommt aus Language

---

<F> ist eine Klasse, die alle Tautologien enthält

Und was hat diese Klasse mit F zu tun? Wie unterscheiden sich zum Beispiel ⟨F⟩ und ⟨G⟩ wenn F und G verschiedene Tautologien sind.

---

Weiß ich leider nicht, kannst du bitte es erklären?

---

Nein, ich kann es nicht erklären. Ich weiß es auch nicht. Es sollte aber in deinen Unterlagen stehen.

---

<F> ist eine Kodierung von F und F ist eine aussagenlogische Formel

---

Sie unterscheiden sich z.B. in Ihrer Länge

---

Grundsätzliche Herangehensweise an mathematische Aufgaben:

1. Die Bedeutung aller in der Aufgabenstellung vorkommenden Fachbegriffe und Symbole klären
2. Denken
   
3. Lösung hinschreiben
   

Punkt 1. hättest du schon machen sollen bevor du deine Frage überhaupt hier veröffentlicht hast.

Es ist sinnlos, mit Punkt 2. anzufangen so lange man mit Punkt 1. noch nicht fertig ist.

Answer 1

Der Beweis hängt entscheidend davon ab, welche Probleme schon als entscheidbar nachgewiesen wurden. Wenn zum Beispiel schon bewiesen wurde, dass SAT entscheidbar ist, dann ist der Beweis einfach:

F ist eine Tautologie genau dann wenn ¬F unerfüllbar ist. Weil SAT entscheidbar ist, ist deshalb auch TAUT entscheidbar.

Comments

Soll ich erstmal zeigen, dass F eine Tautologie ist, obwohl es in der Aufgabe steht, dass F Tautologie ist.

---

In der Aufgabe steht nicht, dass F eine Tautologie ist.

---

Versteht man von diesem Satz nicht, dass F eine Tautologie ist?

TAUT:= {⟨F⟩| F∈ L ist eine Tautologie}

---

Stelle dir einen Raum vor.

Du darfst mit allen Objekten, die sich in dem Raum befinden, Mathematik betreiben.

Der Raum ist leer.

Sei TAUT:= {⟨F⟩| F∈ L ist eine Tautologie}

In dem Raum befindet sich jetzt eine Menge.

Die Menge heißt TAUT.

Seit ich wusste, was ⟨▢⟩ bedeutet, weiß ich auch, welche Elemente die Menge TAUT enthält.

Insbesondere befindet sich in dem Raum kein Objekt, das F heißt.