TU Wien:Knowledge-based Systems VU (Egly, Eiter, Tompits)/Übungstest 13.06.2018

First-order logic & Rules

Example 1

For the following sentences, where c is a constant, R a binary and P a unary predicate:

• a) Give an interpretation structure under which sentence (1)-(4) become true.
• b) Give a formal definition of Entailment in first-order logic.
  • (1) $\forall x\forall y(R(x,y)\lor \neg R(y,x))$
  • (2) $\forall x\exists y(R(x,y)\land P(y))$
  • (3) $\forall y(P(y)\to R(y,c))$
  • (4) $\neg \exists xR(x,x)$

Example 2

• a) Give a formale definition of a rule. When is a rule applicable?
• b) For the following problem write some rules in CLIPS to model the problem.
  • A person has either a dog or a cat, but not both. If a person is allergic, then he can't have a cat. If a person has a dog, then he needs at least 1 hour of sparetime to take the dog for a walk. A person who doesn't have enough money to pay a vet, can't afford a pet.

Description Logics and Truth Maintenance Systems

Example 3

• Construct a ${\mathcal {SROIQ}}$ knowledge base ${\mathcal {K}}=\langle {\mathcal {T}},{\mathcal {A}}\rangle$ (we do not need an RBox here) expressing the following knowledge concerning employees and their hierarchy.
  • Every person who is an employee is either a supervisor or a worker.
  • A supervisor is a person who manages at least 1 or more workers.
  • No worker manages himself.
  • Alice and Bob have jointsupervisor.

Use the class name $\operatorname {Person} ,\operatorname {Employee} ,\operatorname {Worker} ,\operatorname {Supervisor}$, the role names $\operatorname {manages}$ and the individual names $\operatorname {Alice} ,\operatorname {Bob}$

• What does it mean in ${\mathcal {ALL}}$ that a knowledge base ${\mathcal {K}}=\langle {\mathcal {T}},{\mathcal {A}}\rangle$ is satisfiable.

Example 4

• Using the ${\mathcal {ALL}}$ tableau algorith for concept satisfiability, show that the GCI (didn't remember it :/) is not satisfied by each interpretation.
• What is an ${\mathcal {ALL}}$ interpretation?

Answer Set Programming

Example 5

• a) What is grounding?
• b) The combinatorial graph problem vertex cover is defined as follow:

INSTANCE: Given a graph G = (V,E) and a positive integer k ≤ |V|.
QUESTION: Does there a subset D ⊆ V such that |D| ≤ k and such that for each edge(x,y) ∈ E is either x ∈ D or y ∈ D.

Define all required predicates, rules, and constraints to represent the vertex cover problem as an anser-set program such that

• • each vertex v ∈ V of G is denoted by a fact v(v),
  • each edge(u,v) ∈ E of G is denoted by a fact edge(u,v),
  • the integer k is given by a single fact size(k), and
  • answer sets of c(X) correspond to solutions D.

Example 6

Consider the following normal logic program P, where p,q,r and s are atoms.

• a) Given the program.

$p\leftarrow {\text{not }}q.$
$q\leftarrow {\text{not }}p.$
$r\leftarrow q.$
$r\leftarrow p,{\text{not }}q.$
$s\leftarrow q.$
$s\leftarrow p,r.$

• • Reason if the sets $S_{1}=\{p,r,s\}$, $S_{2}=\{r,q,s\}$ are stable models of P and if so explain why.
• b) Which kind of negation in ASP do you know and what are their differences?