Assignment of DL and Inheritance in AI

Assignment

1. What do you recall about the description language 𝓐𝓛𝓒 ?

𝓐𝓛𝓒 stands for Atributive Language with Complement.

The syntactic elements are punctuations, concept-forming operators, connectives,
concepts, roles, and constants (aka individuals or objects).

Concept-forming operators are: ¬, ⊓, ⊔, ∀, ∃

Supports two connectives "⊑" and "≡" for making statements about the domain.

Provides variable free notation for writing concept descriptions (concept expressions).

Accepted Answers:

𝓐𝓛𝓒 stands for Atributive Language with Complement.

The syntactic elements are punctuations, concept-forming operators, connectives,
concepts, roles, and constants (aka individuals or objects).

Concept-forming operators are: ¬, ⊓, ⊔, ∀, ∃

Supports two connectives "⊑" and "≡" for making statements about the domain.

Provides variable free notation for writing concept descriptions (concept expressions).

2. Identify the expressions that define or denote a concept in 𝓐𝓛𝓒.

Owner ≡ ∃Owns.⊤

(People ⊓ Rich) ⊑ Owner

⊤ ... top symbol

⊥ ... bottom symbol

¬(Van ⊔ Car)

∀Owns.SportsCar

∃Owns.Van

Accepted Answers:

Owner ≡ ∃Owns.⊤

⊤ ... top symbol

⊥ ... bottom symbol

¬(Van ⊔ Car)

∀Owns.SportsCar

∃Owns.Van

3. Between 𝓓𝓛 and 𝓐𝓛𝓒 :

"Thing" corresponds to ⊤ (top concept)

𝓓𝓛 does not support ⊥ (bottom concept or empty concept)

"[AND C D]" corresponds to "C ⊓ D"

"[ALL :R C]" corresponds to "∀R.C"

"[EXISTS 1 :R]" corresponds to "∃R.⊤"

"A ≐ C" corresponds to "A ≡ C"

"c → D" corresponds to "D(c)"

Accepted Answers:

"Thing" corresponds to ⊤ (top concept)

𝓓𝓛 does not support ⊥ (bottom concept or empty concept)

"[AND C D]" corresponds to "C ⊓ D"

"[ALL :R C]" corresponds to "∀R.C"

"[EXISTS 1 :R]" corresponds to "∃R.⊤"

"A ≐ C" corresponds to "A ≡ C"

"c → D" corresponds to "D(c)"

4. ∀Owns.Car is a concept that:

includes individuals that own only cars

includes the individual that owns every car

includes individuals who do not own anything

includes individuals that own only sports cars, where SportsCar ⊑ Car

all of the above

Accepted Answers:

includes individuals that own only cars

includes individuals who do not own anything

includes individuals that own only sports cars, where SportsCar ⊑ Car

5. The negation normal form (NNF) of ¬[(∀R.¬C) ⊔ ∃R.C] is:

(∃R.C) ⊔ ∀R.¬C

(∃R.C) ⊓ ∀R.¬C

(∃R.¬¬C) ⊓ ∀R.¬C

(¬∃R.C) ⊓ ¬∃R.C

None of the above

Accepted Answers:

(∃R.C) ⊓ ∀R.¬C

6. In 𝓐𝓛𝓒, to show KB ⊨ α we apply tableau on KB ⋃ {¬α}. As 𝓐𝓛𝓒 tableau executes:

It maintains a graph of nodes that are connected by roles.

Each node in the graph is either a constant or a variable (placeholder for constants).

Each node has a label which contains a set of concepts that are satisfied by that node.

𝓐𝓛𝓒 tableau for KB ⋃ {¬α} always terminates with a contradiction if KB ⊨ α

If a tableau path terminates without a contradiction then it proves that KB ⊨ ¬α

Occasionally, 𝓐𝓛𝓒 tableau runs forever when KB ⊭ α

Accepted Answers:

It maintains a graph of nodes that are connected by roles.

Each node in the graph is either a constant or a variable (placeholder for constants).

Each node has a label which contains a set of concepts that are satisfied by that node.

𝓐𝓛𝓒 tableau for KB ⋃ {¬α} always terminates with a contradiction if KB ⊨ α

If a tableau path terminates without a contradiction then it proves that KB ⊨ ¬α

7. An 𝓐𝓛𝓒 knowledge base and its interpretation-domain with six individuals is shown below.

KB7: {
Dean ⊑ Professor,
Author ⊑ WellRead,
(Professor ⊓ WellRead) ⊑ BridgePlayer
}

What is true about the individuals shown in KB7?

All six individuals can be fully described in 𝓓𝓛

Only k can be fully described in 𝓓𝓛

All six individuals can be fully described in 𝓐𝓛𝓒

There is only one bridge player and that is individual i

All of the above

Accepted Answers:

Only k can be fully described in 𝓓𝓛

All six individuals can be fully described in 𝓐𝓛𝓒

8. From figure 1 and KB7, pick the most specific descriptions of individuals.

In 𝓓𝓛: o → WellRead

In 𝓐𝓛𝓒: WellRead(o)

In 𝓐𝓛𝓒: [WellRead ⊓ ¬BridgePlayer ⊓ ¬Professor ⊓ ¬Author](o)

In 𝓓𝓛: n → [AND Author BridgePlayer]

In 𝓐𝓛𝓒: [Author ⊓ BridgePlayer](n)

In 𝓐𝓛𝓒: [Author ⊓ BridgePlayer ⊓ ¬Professor](n)

Accepted Answers:

In 𝓓𝓛: o → WellRead

In 𝓐𝓛𝓒: [WellRead ⊓ ¬BridgePlayer ⊓ ¬Professor ⊓ ¬Author](o)

In 𝓓𝓛: n → [AND Author BridgePlayer]

In 𝓐𝓛𝓒: [Author ⊓ BridgePlayer ⊓ ¬Professor](n)

9. An 𝓐𝓛𝓒 knowledge base KB9 has one role (Owns), three atomic concepts (Vehicle, Van, Car),
and seven concept definitions of the form Name ≡ Description.

The graph below shows a concept-hierarchy (with transitive edges removed) for KB9,
the nodes denote ⟨Name, Description⟩ pairs taken from Name ≡ Description statements,
and edges denote subsumption between Descriptions.

KB9: {

⊤ is top concept,

Vehicle ⊑ ⊤,
Car ⊑ Vehicle,
Van ⊑ Vehicle,

Owner ≡ ∃Owns.⊤,

CarOwner1 ≡ ∃Owns.Car,
CarOwner2 ≡ ∀Owns.Car,
CarOwner3 ≡ Owner ⊓ ∀Owns.Car,

VehicleOwner1 ≡ ∃Owns.Vehicle,
VehicleOwner2 ≡ ∀Owns.Vehicle,
VehicleOwner3 ≡ Owner ⊓ ∀Owns.Vehicle

}

Now, build this graph and determine the node names, for example,
node 1 is ⟨Owner, ∃Owns.⊤⟩, it corresponds to Owner ≡ ∃Owns.⊤.

Question: identify the nodes in the above graph.

Node 6 is CarOwner1

Node 6 is VehicleOwner2

Node 3 is VehicleOwner1

Node 3 is CarOwner1

Node 5 is VehicleOwner3

Node 5 is CarOwner3

Accepted Answers:

Node 6 is VehicleOwner2

Node 3 is CarOwner1

Node 5 is CarOwner3

10. What is true about the graph in question 9?

The two edges between Vehicle, Van and Car are asserted edges

Nodes 2, 4, 6 correspond to car owners

Nodes 2, 4, 6 correspond to vehicle owners

Nodes 3, 5, 7 correspond to vehicle owners

Nodes 3, 5, 7 correspond to car owners

Accepted Answers:

The two edges between Vehicle, Van and Car are asserted edges

Nodes 2, 4, 6 correspond to vehicle owners

Nodes 3, 5, 7 correspond to car owners

11. What is the difference between hierarchies created by frames and that created by DL?

Using frames, a user is free to design the hierarchies manually, whereas,
in description logics the hierarchies are automatically constructed from concept-definitions

Inheritance in frames is defeasible whereas it is not so in description logics

Inheritance in DL taxonomy is defeasible, but not in frames

None of the above

Accepted Answers:

Using frames, a user is free to design the hierarchies manually, whereas,
in description logics the hierarchies are automatically constructed from concept-definitions

Inheritance in frames is defeasible whereas it is not so in description logics

12. Which of the following statements are true about “Inheritance networks”?

An inheritance network is a graph-like structure in which nodes (vertices) can be “concepts” or “categories”

An inheritance network is a graph-like structure in which nodes (vertices) can be “properties”

In a tree-structured inheritance network, nodes at the bottom of the hierarchy always stand for individuals

The edges in an inheritance network represent a transitive relation

Accepted Answers:

An inheritance network is a graph-like structure in which nodes (vertices) can be “concepts” or “categories”

An inheritance network is a graph-like structure in which nodes (vertices) can be “properties”

The edges in an inheritance network represent a transitive relation

13. While choosing an extension (i.e. reasoning over paths in an inheritance network)
what happens when a node has more than one parent node?

Using a credible reasoner a node can inherit from any parent in an ambiguous network

Using a skeptical reasoner a node can inherit from all parents in an ambiguous network

Using a credible reasoner a node can inherit only what is unambiguous in an ambiguous network

Using a skeptical reasoner a node can inherit only what is unambiguous in an ambiguous network

Accepted Answers:

Using a credible reasoner a node can inherit from any parent in an ambiguous network

Using a skeptical reasoner a node can inherit only what is unambiguous in an ambiguous network

14. A negative path in an inheritance hierarchy

can have zero negative edges

can have zero positive edges

can have only one negative edge

the one negative edge can be anywhere in the path

the one negative edge must be the last one in the path

can have more than one negative edge

the negative edges can be anywhere in the path

the negative edges must be the last ones in the path

Accepted Answers:

can have zero positive edges

can have only one negative edge

the one negative edge must be the last one in the path

15. A path in an inheritance hierarchy can support a conclusion of the form

an individual A has a property P

an individual A belongs to a class C

a class C is a subclass of class D

an individual A does not have a property P

an individual A does not belong to a class C

a class C is a not a subclass of class D

Accepted Answers:

an individual A has a property P

an individual A belongs to a class C

a class C is a subclass of class D

an individual A does not have a property P

an individual A does not belong to a class C

a class C is a not a subclass of class D

16. An inheritance hierarchy with a conclusion node C w.r.t. a node A

can have only the conclusion "A is a C"

can have only the conclusion "A is not C"

can have both the conclusions "A is a C" and "A is not a C"

cannot have both the conclusions "A is a C" and "A is not a C"

cannot have an admissible positive path and an admissible negative path from A to C

Accepted Answers:

can have only the conclusion "A is a C"

can have only the conclusion "A is not C"

can have both the conclusions "A is a C" and "A is not a C"

17. The shortest path heuristic in defeasible reasoning

prefers conclusions resulting from shorter paths in the network

inherits from the most specific subsuming class

inherits from the most specific subsumed class

inherits from the least specific subsumed class

Accepted Answers:

prefers conclusions resulting from shorter paths in the network

inherits from the most specific subsuming class

18. A credulous extension of a (possibly ambiguous) inheritance hierarchy with respect to a node A

is a subgraph of the inheritance hierarchy

extends the hierarchy to its transitive closure

has a path from A to every node in the extension

has an admissible path from A to every node in the extension

does not support both a conclusion C and the conclusion ¬C

can support both a conclusion C and the conclusion ¬C

can be extended to a larger subgraph of the hierarchy which is a credulous extension

Accepted Answers:

is a subgraph of the inheritance hierarchy

has a path from A to every node in the extension

has an admissible path from A to every node in the extension

does not support both a conclusion C and the conclusion ¬C

19. Given the following inheritance hierarchy, what can be said about the individual 'a'
based on the criteria of there being an admissible path to support the conclusion?

a is an A

a is not an A

a is a D

a is not a D

a is a B

a is not a B

Accepted Answers:

a is an A

a is a D

a is a B

a is not a B

20. Looking at the inheritance hierarchy in question 19, what can be said about the individual 'b'
based on the criteria of there being an admissible path to support the conclusion?

b is a C

b is a D

b is not a D

b is a B

b is not a B

b is an A

b is not an A

b is an E

b is not an E

Accepted Answers:

b is a C

b is not a D

b is an E