TheoLog
TheoLog copied to clipboard
knowsys
Vorlesungsunterlagen "Theoretische Informatik und Logik", Fakultät Informatik, TU Dresden
In [lecture.tex-18](https://github.com/knowsys/TheoLog/blob/master/Vorlesungen/lecture-18.tex), namely line 244 (see: [here](https://github.com/knowsys/TheoLog/blob/master/Vorlesungen/lecture-18.tex#L244)) is a minor typo, instead of 'ersetzten' it should be 'ersetzen', as also mentioned in the lecture while explaining the procedure (see: [Substitution...
### Problem Im vereinfachten Beweis des 1. Unvollständigkeitssatzes wird die Gödel-Formel F mit dem Inhalt „F ist wahr genau dann wenn F nicht beweisbar ist“ eingeführt. In Zeile 216 wird...
Bei den Konventionen zur Vereinfachung der Syntax könnte auch die Konvention „unäre Junktoren (Negation und Quantoren) binden stärker als binäre Junktoren“ mit aufgeführt werden. Diese scheint später implizit verwendet zu...
In VL17 Zeile 460 steht ein Äquivalenzsymbol `\equiv` zwischen einer Formel und ihrer Skolemisierung. Aus dem Rest der Vorlesung geht zwar eindeutig hervor, dass Skolemisierung nicht äquivalenzerhaltend ist, dies kann...
Um NP-Vollständigkeit von „Unabhängige Menge“ zu zeigen, muss Enthaltensein in NP und NP-Schwere gezeigt werden. Die Reduktion auf Clique zeigt nur Enthaltensein. Dieselbe Funktion (Graphen auf Komplementgraphen abbilden) funktioniert natürlich...
P.S.: I (Andrej Bereza) changed my GitHub username to anbereza, so please update the link on https://iccl.inf.tu-dresden.de/web/Formale_Systeme_(WS2020).
"Ein Problem Q ist PSpace-schwer wenn für jedes Problem P in PSpace ein polynomielle Reduktion P ≤p Q existiert." sollte wahrscheinlich "**eine** polynomielle Reduktion" heißen.
Das Thema Unifikation wurde schon in der Vorlesung "Programmierung" von Prof. Dr. Vogler behandelt. Ich bin der Meinung, dass es in der TheoLog Vorlesung gut etwas kürzer gefasst werden könnte....
Ich fände es sinnvoll, wenn man in der [3. Folie](https://iccl.inf.tu-dresden.de/w/images/c/c2/TheoLog2018-Vorlesung-02-overlay.pdf) mal eine Mehrband-Turingmaschine (als Beispiel) zeigen könnte, damit man weiß, wie das (formal / als "Automat") aufzuzeichnen ist. Ich selbst...
Im Foliensatz zur 9. Vorlesung, Folie 18 heißt es "Durch direkte Reduktion auf das Wortproblem von polynomiell zeitbeschränkten NTMs". Ist es nicht genau anders herum, dass wir das Wortproblem auf...
