TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Prüfung 2019-03-21

Angabe

• Datei:TU Wien-Einführung in wissensbasierte Systeme VU (Egly) - Prüfung 2019-03-21.zip

Beispiele

Beispiel 1: Logikbasierte Wissensrepräsentation

Beispiel 1a

Formulieren Sie folgendes Argument in Prädikatenlogik und zeigen oder widerlegen Sie dessen Gültigkeit mittels TC1. Ist das Tableau geschlossen?

Sollte das Argument nicht gültig sein, dann extrahieren Sie ein Gegenbeispiel aus dem Tableau.

Es gibt Tiere, die nicht fliegen können. Vögel sind Tiere. Somit können Vögel nicht fliegen. (6 Punkte)

Beispiel 1b

Definieren Sie den Begriff einer Interpretationsstruktur in der Prädikatenlogik erster Stufe. Erklären Sie den Unterschied zwischen einer Interpretationsstruktur und einem Modell. Zeigen oder widerlegen Sie mithilfe von Interpretationsstrukturen, dass für beliebige geschlossene Formeln $\phi ,\psi$ und $\rho$ aus $\models \psi \to (\phi \to \rho )$ immer $\models (\psi \wedge \phi )\to \rho$ folgt. Wenn Sie zusätzliche Theoreme aus der Vorlesung verwenden, so müssen Sie diese beweisen. (5 Punkte)

Beispiel 1c

Überprüfen Sie, welche Eigenschaften auf die nachfolgend angeführten auslagenlogischen Formeln zutreffen und kreuzen Sie jeweils alles zutreffenden Eigenschaften an: (2 Punkte)

Multiple Choice-Quiz:

Pluspunkt für eine richtige Antwort:
Punkt für eine falsche Antwort:
Ignoriere die Fragen-Koeffizienten:

1

$\mathrm{\neg }p\to (p\to \mathrm{\neg }p)$

	erfüllbar (satisfiable)
	widerlegbar (refutable)
	Tautologie (tautology)
	Kontradiktion (contradiction)

2

$\mathrm{\neg }(p\vee q)\leftrightarrow (\mathrm{\neg }p\wedge q)$

	erfüllbar (satisfiable)
	widerlegbar (refutable)
	Tautologie (tautology)
	Kontradiktion (contradiction)

3

$\mathrm{\neg }((p\wedge s)\to (q\vee r))\wedge (\mathrm{\neg }q\wedge \mathrm{\neg }s)$

	erfüllbar (satisfiable)
	widerlegbar (refutable)
	Tautologie (tautology)
	Kontradiktion (contradiction)

4

$\mathrm{\neg }p\to (\mathrm{\neg }p\to p)$

	erfüllbar (satisfiable)
	widerlegbar (refutable)
	Tautologie (tautology)
	Kontradiktion (contradiction)

Beispiel 1d

Kreuzen Sie Zutreffendes an: (4 Punkte)

Multiple Choice-Quiz:

Pluspunkt für eine richtige Antwort:
Punkt für eine falsche Antwort:
Ignoriere die Fragen-Koeffizienten:

1

Für eine PL1-Formel $\phi$ gilt in einer Interpretation $I$ entweder $I\models \phi$ oder $I\models \mathrm{\neg }\phi$.

	richtig
	falsch

2

TC1 kann für jede Formel ein Modell erzeugen.

	richtig
	falsch

3

Die leere Konjunktion ist in allen Interpretationen wahr.

	richtig
	falsch

4

Eine Formel ist genau dann erfüllbar wenn ihre Negation nicht gültig ist. (unbewertet)

	richtig
	falsch

5

Nur erfüllbare Formeln sind gültig.

	richtig
	falsch

6

Aus $P\wedge (Q\vee R)$ folgt $P\wedge Q$.

	richtig
	falsch

7

Alle Regeln des TC1 sind deterministisch.

	richtig
	falsch

8

Keine gültige Formel ist ungültig. (unbewertet)

	richtig
	falsch

Beispiel 2: Nichtmonotones Schließen

Beispiel 2a

Gegeben ist eine Default Theorie $T=(W,\Delta )$, mit

$W=\{P(d),R(c),P(c)\},\Delta =\{\frac{R(x):Q(x)}{Q(x)},\frac{P(c):\mathrm{\neg }Q(c)}{\mathrm{\neg }Q(c)},\frac{P(x):R(x)}{R(x)}\}$

Wobei c und d Konstantensymbole sind.

Welche der folgenden Mengen sind Extensionen von T?

(4 Punkte)

Multiple Choice-Quiz:

Pluspunkt für eine richtige Antwort:
Punkt für eine falsche Antwort:
Ignoriere die Fragen-Koeffizienten:

1

$Cn(W\cup \{\mathrm{\neg }Q(c),Q(d)\})$

	Ja
	Nein

2

$Cn(W\cup \{Q(c),\mathrm{\neg }Q(d)\})$

	Ja
	Nein

3

$Cn(W\cup \{R(d),Q(d),Q(c)\})$

	Ja
	Nein

4

$Cn(W\cup \{\mathrm{\neg }Q(c),\mathrm{\neg }Q(d)\})$

	Ja
	Nein

Beispiel 2b

Geben Sie die allgemeine Definition des deduktiven Abschlusses Cn(T) einer Wissensbasis T an. Zeigen bzw widerlegen Sie, dass es eine Theorie $T_0$ gibt sodass $Cn(T_0)$ endlich ist. (4 Punkte)

Beispiel 2c

Beweisen oder widerlegen Sie:

$Cn(T_1)\cup Cn(T_2)\subseteq Cn(T_1\cup T_2)$

(4 Punkte)

Beispiel 2d

Welchen Vorteil bietet die Anwendung der closed-world assumption (CWA)? Sei T eine konsistente Theorie. Unter welchen Umständen ist CWA(T) inkonsistent? (2 Punkte)

Beispiel 2e

Was ist ein normaler Default? Was ist eine normale Default Theorie? Welche Eigenschaft gilt für normale Default Theorien, jedoch im Allgemeinen nicht für beliebige? (2 Punkte)

Beispiel 3: Answer-Set Programming

Beispiel 3a

Gegeben ist das folgende logische Programm:

$P=\{p(X)\vee q(X)\leftarrow r(X).s\leftarrow p(X).t\leftarrow q(X).\leftarrow nots.\leftarrow nott.r(a).r(b).\}$

(i) Bestimmen Sie die Grundierung grnd(P) von P. (3 Punkte)

(ii) Welche der folgenden Interpretationen ist ein Answer Set von P? (3 Punkte)

Multiple Choice-Quiz:

Pluspunkt für eine richtige Antwort:
Punkt für eine falsche Antwort:
Ignoriere die Fragen-Koeffizienten:

1

$\{r(a),r(b),p(a),q(b),s,t\}$

	Ja
	Nein

2

$r(a),r(b),q(a),q(b),t$

	Ja
	Nein

3

$r(a),r(b),q(a),q(b),t,s$

	Ja
	Nein

Beispiel 3b

Betrachten Sie die vier unten angegebenen Regeln, wo a und b präpositionale Konstanten und X und Y Variablen sind. Kreuzen Sie alle Eigenschaften an, die für diese Regeln zutreffen. (4 Punkte)

Multiple Choice-Quiz:

Pluspunkt für eine richtige Antwort:
Punkt für eine falsche Antwort:
Ignoriere die Fragen-Koeffizienten:

1

$P(X).$

	fact
	constraint
	normal
	positive
	Horn
	safe
	ground

2

$P(X)\leftarrow notP(Y).$

	fact
	constraint
	normal
	positive
	Horn
	safe
	ground

3

$a\vee c\leftarrow b.$

	fact
	constraint
	normal
	positive
	Horn
	safe
	ground

4

$\leftarrow b,nota.$

	fact
	constraint
	normal
	positive
	Horn
	safe
	ground

Beispiel 3c

Erklären Sie das Guess-and-Check Paradigma der Answer-Set Programmierung anhand eines Programmes, welche alle Dominating Sets eines Graphen berechnet.

Beachte: Sei $G=⟨V,E⟩$ ein Graph, wobei V die Menge der Knoten und E die Menge der Kanten des Graphen sei. Ein Dominating Set ist eine Teilmenge S der Knotenmenge V sodass jeder Knoten in G entweder in S enthalten ist oder mindestens einen Nachbarn besitzt welcher in S enthalten ist. (6 Punkte)

Beispiel 4: Probabilistisches Schließen

Beispiel 4a

Angenommen, ein Test reagiert zu 99% positiv, sollte eine bestimmte Krankheit vorliegen, zeigt aber auch zu 5% ein falsch-positives Resultat. Wenn man davon ausgeht, dass 3% der Bevölkerung von dieser Krankheit betroffen sind, und bei einer zufällig ausgewählten Person der Test positiv reagiert, wie groß ist die Wahrscheinlichkeit, dass die Person erkrankt ist? Hinweis: Der konkrete numerische Wert muss nicht explizit berechnet werden; es genügt die Angabe der Formel mit den entsprechenden Werten. (6 Punkte)

Beispiel 4b

Bestimmen Sie die Richtigkeit oder Falschheit folgender Aussagen, für beliebige Boole'sche Zufallsvariablen A und B: (3 Punkte)

Multiple Choice-Quiz:

Pluspunkt für eine richtige Antwort:
Punkt für eine falsche Antwort:
Ignoriere die Fragen-Koeffizienten:

1

$P(A|B)+P(A|\mathrm{\neg }B)=P(A).$

	richtig
	falsch

2

$P(A|B)=\frac{P(A)}{P(A,B)}.$

	richtig
	falsch

3

$P(A|\mathrm{\neg }B)+P(\mathrm{\neg }A|\mathrm{\neg }B)=1.$

	richtig
	falsch

Beispiel 4c

Leiten Sie das Bayes'sche aus der Produktregel her. (4 Punkte)

Beispiel 4d

Gegeben ist folgender Graph eines Bayes'schen Netzes:

(Siehe Angabe)

Welche der folgenden Eigenschaften folgen aus der Netzwerkstruktur? (3 Punkte)

Multiple Choice-Quiz:

Pluspunkt für eine richtige Antwort:
Punkt für eine falsche Antwort:
Ignoriere die Fragen-Koeffizienten:

1

A ist bedingt unabhängig von D bei Evidenz B und C.

	richtig
	falsch

2

A ist bedingt unabhängig von I bei Evidenz B und F. (unbewertet)

	richtig
	falsch

3

C ist bedingt unabhängig von D bei Evidenz A und B. (unbewertet)

	richtig
	falsch