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

From VoWi
Jump to navigation Jump to search

First-order logic & Rules[edit]

Example 1[edit]

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 x R(x,x)

Example 2[edit]

  • 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[edit]

Example 3[edit]

  • 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[edit]

  • 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[edit]

Example 5[edit]

  • 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[edit]

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?