MaLo etest Answers for course 1- 9 NMD PDF

Preview

Summary

MaLo etest Etest 1 Eine Formel heißt nicht-trivial, wenn sie erfüllbar aber keine Tautologie ist. Gibt es nicht-triviale Formeln, deren Negation nicht nicht-trivial ist? （falsch） Sei φ =( X → Y ) und ψ =(¬ X →¬ Y ). Dann gilt: （ φ und ψ sind erfüllbarkeitsäquivalent (beide erfüllbar oder beide unerf...

Description

MaLo etest Etest 1 1. Eine Formel heißt nicht-trivial, wenn sie erfüllbar aber keine Tautologie ist. Gibt es nicht-triviale Formeln, deren Negation nicht nicht-trivial ist? （falsch） 2. Sei

φ=(X→Y)

und

ψ=(¬X→¬Y).

Dann gilt: （

φ

und

ψ

sind

erfüllbarkeitsäquivalent (beide erfüllbar oder beide unerfüllbar)） 3. Die Formel

(X→Y)∧¬(Y→X) ist erfüllbar.（Wahr）

4. Welche

der

folgenden

Interpretationen

sind

passend

für

ϕ=(¬Z∨(B→X))?（B↦1,X↦0,Z↦1 ，passend 只要满足题干 中给出的字母在答案中都有出现就行，不需要结果为真） 5. Sei

Φ:={φi∣φi=Xi→Xi+1,i∈N}={X0→X1,X1→X2,…},

welche der folgenden Ausdrücke beschreiben syntaktisch korrekte Formeln der Aussagenlogik? （

）

6. Welche der folgenden Interpretationen sind Modell der Formel

(¬(X∧Y)∨¬(X∧Z))? Wählen Sie eine oder mehrere Antworten:

7. Es gilt I⊨φ→ψ genau dann, wenn I⊨¬φ→¬ψ.（Falsch） 8. Wenn I⊨φ→ψ und I⊭φ, dann I⊭ψ. （Falsch） 9. Ist I:{Xi∣i∈N}→{0,1},Xi↦imod2 passend für φ=X3∨X56346? （Wahr，同理只要 passend 都是对的）

10. Sei φ=((X∨Y)∧(¬X∨Z)). Dann gilt

11. Welche der folgenden Interpretationen sind passend für

ϕ=(¬(A∧B)∨(C∧D))?

12. Wenn I⊨φ→ψ und I⊭φ, dann I⊭ψ.

13. Ist I:{Xi∣i∈N}→{0,1},Xi↦imod2 passend für φ=X3∨X56346?

14. Sei φ=((X∨Y)∧(¬X∨Z)). Dann gilt:

15. Sei Φ:={φi∣φi=Xi→Xi+1,i∈N}={X0→X1,X1→X2,…}, welche der folgenden Ausdrücke beschreiben syntaktisch korrekte Formeln

der Aussagenlogik?

16. Welche der folgenden Interpretationen sind Modell der Formel

((¬X∨Y∨Z)∧((¬X∨Y)∧Z))

17. Wenn φ eine Tautologie ist, ist auch φ→ψ eine Tautologie.

18. Die Formel X∨¬1 ist erfüllbar.

19. Sei

φ=(¬X→¬Y) und ψ=(X→Y) Dann gilt:Wählen Sie eine

oder mehrere Antworten:

20. Eine Formel heißt nicht-trivial, wenn sie erfüllbar aber keine Tautologie ist. Gibt es nicht-triviale Formeln, deren Negation nicht nicht-trivial ist?

21. Welche der folgenden Interpretationen sind passend für

ϕ=(¬(A∧B)∨(C∧D))?（A↦1,B↦1,C↦0,D↦0； A↦0,B↦0,C↦0,D↦1,E↦0） 22. Ist I⊨¬φ→¬ψ, dann ist auch I⊨ψ→φ.（Wahr）

23. Welche der folgenden Interpretationen sind Modell der Formel

((X→Y)∧(Y→Z))?（Y↦0,X↦0,Z↦1，Modell 需要式子结果为 1） 24. Sei Ψ:={ψi∣ψi=⋀j≤iXj,i∈N}={X0,X0∧X1,X0∧X1∧X2,…}, welche der folgenden Ausdrücke beschreiben syntaktisch korrekte Formeln der Aussagenlogik?

25. Sei φ=(X→Y) und ψ=(¬Y→¬X). Dann gilt: （φ und ψ sind erfüllbarkeitsäquivalent (beide erfüllbar oder beide unerfüllbar)；φ≡ψ 看

定义） 26. Ist I:{X0,X1}→{0,1},Xi↦i passend für Φ={φi∣i∈N}, wobei

φ0:=X0 und φj+1:=φj→X(jmod2)?（Wahr） 27. Welche der folgenden Interpretationen sind passend für

ϕ=((X∧(Y∧Z))∨X)?（X↦0,Y↦0,Z↦0； V↦0,W↦0,X↦1,Y↦1,Z↦0） 28. Sei φ=((X∧Y)∨(¬X∧Z)). Dann gilt: （Es existiert eine zu φ äquivalente Formel in DNF, die verschieden von

φ ist.；φ ist in DNF）

29. Die Formel (X→¬X)∨(¬X→X) ist erfüllbar.（Wahr） 30. Sei φ=(¬X→¬Y) und ψ=(X→Y). Dann gilt:（φ und ψ sind erfüllbarkeitsäquivalent (beide erfüllbar oder beide unerfüllbar)）

31. Ist I⊨φ→ψ, dann ist auch I⊨ψ→φ.（Falsch） 32. Ist I:{Xi∣i∈N}→{0,1},Xi↦imod2 passend für

Φ={Xi→Xi+1∧¬Xi+2∣i∈N}?（Wahr）

33. Sei Φ:={φi∣φi=Xi↔Xi+1,i∈N}={X0↔X1,X1↔X2,…}, welche der folgenden Ausdrücke beschreiben syntaktisch korrekte Formeln der Aussagenlogik?（

）

34. Die Formel (X→¬X)∧(¬X→X) ist erfüllbar.（Falsch） 35. Wenn φ→ψ erfüllbar ist, dann ist auch ψ→φ erfüllbar.（Falsch） 36. Wenn I⊨φ→ψ und I⊨ψ, dann I⊨φ.（Falsch） Etest 2 1. Seien φ,ψ Horn-Formeln. Dann ist φ∧ψ eine Horn-Formel.（Wahl） 2. Welche der folgenden aussagenlogischen Formeln sind äquivalent zu einer Horn-Formel? （(¬X∨Y)∧(¬Y∨X)；(¬X∧Y)∨(¬Y∧¬X)；

X∧¬X∧Y）

3. Wenn eine Formel ein eindeutiges kleinstes Modell hat, ist sie äquivalent zu einer Horn-Formel. （Falsch）

4. Seien φ,ψ Horn-Formeln. Dann ist φ∨ψ eine Horn-Formel.（Falsch）

5. Welche der folgenden aussagenlogischen Formeln sind äquivalent zu einer Horn-Formel?（X∧¬X∧Y；X→(¬Y∧¬Z)）

6. Es ist bekannt, dass das folgende Problem in Polynomialzeit entscheidbar ist: Gegeben eine

AL-Formel φ. Ist ¬φ eine Tautologie?（Falsch）在多项式时间

内都是错误的

7. Das folgende Problem ist algorithmisch entscheidbar: Gegeben eine

AL-Formel φ. Ist φ erfüllbar?（Wahr）在算法时间内都是正确的

8. Seien φ,ψ Horn-Formeln. Dann ist φ→ψ nicht äquivalent zu einer HornFormel.（Falsch）

9. Seien φ,ψ Horn-Formeln. Dann ist φ→ψ eine Horn-Formel.（Falsch） 10. Welche der folgenden aussagenlogischen Formeln sind äquivalent zu einer Horn-Formel? （X→(¬Y∧¬Z)；X∧¬X∧Y）

11. Es ist bekannt, dass das folgende Problem in Polynomialzeit entscheidbar ist: Gegeben eine

AL-Formel φ. Ist φ unerfüllbar?（Falsch）

12. Sei φ eine Horn-Formel. Dann ist ¬φ keine Horn-Formel.（Falsch）

13. Das folgende Problem ist algorithmisch entscheidbar: Gegeben eine Horn-Formel

φ. Ist φ eine Tautologie?（Wahr）

14. Sei φ eine Horn-Formel. Dann ist ¬φ äquivalent zu einer Horn-Formel. （Falsch）

15. Seien φ,ψ Horn-Formeln. Dann ist φ∧ψ eine Horn-Formel.（Wahr） 16. Seien φ,ψ Horn-Formeln. Dann ist φ∨ψ keine Horn-Formel. （Falsch） 17. Sei φ eine Horn-Formel. Dann ist ¬φ keine Horn-Formel. （Falsch） 18. Seien

φ,ψ Horn-Formeln. Dann ist φ→ψ äquivalent zu einer

Horn-Formel.(Falsch) 19. Seien φ,ψ Horn-Formeln. Dann ist φ→ψ eine Horn-Formel（Falsch） 20. Seien φ,ψ Horn-Formeln. Dann ist φ→ψ nicht äquivalent zu einer HornFormel.（Falsch）

Etest3 1. Ist die Klauselmenge K erfüllbar, dann ist Res∗(K) erfüllbar.（Wahr）

2. Ist die Klauselmenge K erfüllbar, dann ist im Resolutionskalkül die leere

Klausel nicht ableitbar.（Wahr）

3. Wenn K eine endliche unerfüllbare Klauselmenge über n Variablen ist, dann kann im Resolutionskalkül in

22n Schritten die leere Klausel

abgeleitet werden.

4. Wir betrachten die Einschränkung der Resolution, bei der nur dann resolviert werden kann, wenn eine der beiden Klauseln eine gerade Anzahl Literale enthält. Diese Einschränkung des Resolutionskalküls ist（korrekt）

5. Sei MaLo-Resolution eine Variante des Resolutionskalküls (z.B. einer Einschränkung oder Erweiterung), die nicht korrekt ist. Das bedeutet:（Es existiert eine erfüllbare Klauselmenge, aus der die leere Klausel abgeleitet

werden kann.）

6.

{X,¬X} ist Resolvente von {X,Y} und {¬X,¬Y}.（Wahr）

7. Wenn □∉Res∗(K), dann ist die Klauselmenge K unerfüllbar.（Falsch） 8. Ist die Klauselmenge K unerfüllbar, dann ist □∈Res∗(K).（Wahr） 9.

{X,Y} ist Resolvente von {X,Y,Y} und {X,¬Y}.（Falsch，因为 XYY 看

做 XY，成分不可重复） 10. Sei MaLo-Resolution eine Variante des Resolutionskalküls (z.B. einer Einschränkung oder Erweiterung), die nicht vollständig ist. Das bedeutet: （Es existiert eine unerfüllbare Klauselmenge, aus der die leere Klausel nicht abgeleitet werden kann.） 11. Wir betrachten die Einschränkung der Resolution, bei der nur dann resolviert werden kann, wenn eine der beiden Klauseln eine gerade Anzahl Literale enthält. Diese Einschränkung des Resolutionskalküls ist（korrekt）

12. Wenn □∉Res∗(K), dann ist die Klauselmenge K unerfüllbar.（Falsch） 13. Ist die Klauselmenge K erfüllbar, dann ist Res∗(K) erfüllbar.（Wahr） 14. Sei K eine Klauselmenge, in der nur die Variablen X1,…,Xn vorkommen. Dann hat Res∗(K) höchstens

22n Elemente.（Wahr）

15. Wenn die leere Klausel im Resolutionskalkül nicht aus der Klauselmenge K ableitbar ist, dann ist K erfüllbar.（Wahr）

Etest 4 1.

X,Y⇒Z,Y ist...（ein Axiom des Sequenzenkalküls）

2. Die Disjunktion über die leere Menge (⋁∅) ist eine Tautologie.（Falsch）

3. Wenn Φ⊨ψ→ϑ, dann ist die Sequenz Φ⇒¬ψ,ϑ gültig.（Wahr）

4. Wenn Φ⊬ϕ, dann Φ⊨¬ϕ.（Falsch）

5. Wir erweitern den Sequenzenkalkül durch zusätzliche Schlussregeln, sodass der so erweiterte Sequenzenkalkül nicht korrekt ist. Dann gilt in jedem Fall:（Es existiert eine gültige Sequenz, die im so erweiterten Sequenzenkalkül abgeleitet werden kann., Es existiert eine Sequenz, die nicht gültig ist und im so erweiterten Sequenzenkalkül abgeleitet werden

kann.）

6.

X∧Y⇒X,Y ist （eine gültige Sequenz, aber kein Axiom）

7. Die Konjunktion über die leere Menge (⋀∅) ist eine Tautologie.（Wahr）

8. Die Sequenz X∨Y,Z∨W⇒Y,Z ist gültig（Falsch，可以找在左边为 1 的情况 下，右边为 0 的情况）

9. Wenn die Sequenz Γ⇒ψ,ϑ gültig ist, dann gilt Γ⊨ψ und Γ⊨ϑ.（Falsch）

10. Wenn Φ⊢ψ für eine endliche Formelmenge

Φ, dann ist Φ,¬ψ⇒∅ im

Sequenzenkalkül ableitbar.（Wahr）

11. Wir entfernen Schlussregeln aus dem Sequenzenkalkül, sodass der so eingeschränkte Sequenzenkalkül nicht vollständig ist. Dann gilt（Es existiert eine gültige Sequenz, die im so eingeschränkten Sequenzenkalkül nicht abgeleitet werden kann.；Es existiert eine Sequenz, die nicht gültig ist und im so eingeschränkten Sequenzenkalkül abgeleitet werden kann.）

12. Die Konjunktion über die leere Menge (⋀∅) ist unerfüllbar.（Falsch） 13. Wenn Φ⊭ψ, dann Φ⊢¬ψ.（Falsch） 14. Wenn Φ⊨¬ϕ und Φ erfüllbar, dann Φ⊬ϕ.（Wahr） 15. Wenn Γ⇒δ für eine Formel δ eine gültige Sequenz ist, dann gilt Γ⊨δ. （Wahr）

16. Die Sequenz X∨Y,Z∨W⇒Y,Z ist gültig.（Falsch） 17. X,¬X⇒∅ ist（eine gültige Sequenz, aber kein Axiom） 18. Wenn Φ⊨ψ→ϑ, dann ist die Sequenz Φ⇒ψ,ϑ gültig.（Falsch） 19. (X∧Y∧Z),X,Y⇒(¬X∧¬Y),(X∧Y∧Z) ist.（ein Axiom des Sequenzenkalküls）

20. Die Sequenz X→Y,Z→X⇒X,¬Z ist gültig.（Wahr） 21. Die Disjunktion über die leere Menge (⋁∅) ist unerfüllbar.（Wahr） 22. Wenn Φ⊢ψ für eine endliche Formelmenge Sequenzenkalkül ableitbar.（Wahr）

Φ, dann ist Φ,¬ψ⇒∅ im

23. Wenn Γ⇒Δ eine gültige Sequenz ist, dann gilt Γ⊨δ für alle Formeln

δ∈Δ.（Falsch） 24. Wenn Φ⊬ϕ, dann Φ⊨¬ϕ.（Falsch） 25. Wenn Φ⊭ψ, dann Φ⊢¬ψ.（Falsch） 26. Wenn Φ⊨¬ϕ, dann Φ⊬ϕ.（Falsch） 27. Die Sequenz X∨Y,Z∨W⇒X,W ist gültig.（Falsch） 28. Wenn Φ⊨¬ψ→ϑ, dann ist die Sequenz Φ⇒ψ,ϑ gültig.（Wahr） 29. Wenn Φ⊨ψ∨ϑ, dann ist Φ⇒ψ,ϑ eine gültige Sequenz.（Wahr） 30. Die Sequenz X→Y,Y→W⇒Y ist gültig.（Falsch） 31. Wenn Φ⊢¬ϕ und Φ erfüllbar, dann Φ⊭ϕ.（Wahr） 32. Wenn Γ⇒Δ eine gültige Sequenz ist, dann gilt Γ⊨δ für alle Formeln

δ∈Δ.（Falsch） 33. Wenn eine endliche Teilmenge

Φ0⊆Φ existiert, sodass Φ0⇒ψ im

Sequenzenkalkül ableitbar ist, dann gilt

Φ⊢ψ.（Wahr）

34. Wenn Φ⊨¬ψ→ϑ, dann ist die Sequenz Φ⇒ψ,ϑ gültig.（Wahr） Etest 5 1. Sei φ∈FO mit frei(φ)={x}. Dann gilt ∀xφ⊨∃xφ.（Wahr）

2. Jede Struktur hat eine echte Substruktur.（Falsch）

3. Sei R ein zweistelliges Relationssymbol. Dann ist A=(∅,R) mit RA=∅

eine Struktur.（Falsch）

4. Wie wird der natürlichsprachliche Ausdruck "für alle

x sodass φ(x) gilt,

gilt ψ(x)" in Prädikatenlogik formuliert?（∀x(φ(x)→ψ(x))）

5. Sei φ=∃x∀y((y...