Semantics and Services

Bijan Parsia

COMP60462

Logic Engineering?

Why Logic At All?

Getting To Logic

ALC: Syntax -- Expressions

ALC: Syntax -- Axioms

ALC: Fun Syntax Tricks

Semantics?

Model Theory

Interpretation Function

ALC: Model Theory -- Expressions

WFF Sort Interpretation (WFF^I )
a a^I \in \Delta
A A^I \subseteq \Delta
P P^I \subseteq \Delta\times\Delta
\neg C \Delta\setminus C^I
C \sqcap D C^I \cap D^I
C \sqcup D C^I \cup D^I
\exists P.C \{x \in \Delta | \exists(y)(<x,y> \in P^I \land y \in C^I)\}
\forall P.C \{x \in \Delta | \forall(y)(<x,y> \in P^I \rightarrow y \in C^I)\}

 

ALC: Model Theory -- Axioms

WFF Sort Interpretation (WFF^I )
C \sqsubseteq D C^I \subseteq D^I
C \sqsubseteq D C^I \subseteq D^I and C^I \subseteq D^I
a:C a^I \in C^I
<a, b>:P <a^I, b^I> \in P^I

NOTE: These all evaluate to True or False!

 

Example Interpretation

What are Models?

Models and Your Domain

A Simple Example: Strings!

String Models

A Ontology2 for 'abba'

Modeling with Logic

Logical Services!

Class Satisfiability

Translation Semantics

FOL

L2

We inherit

Decidability

Complexity

Complexity 2

We can see that, as input, N, grows, 2 raised to the N grows much much faster than 2N or even N squared.

Complexity 3

When graphed with a logrithmic scale y-axis, we see that 2 raised to the N rises as a line, whereas all the other ones plateau quickly.

Basic Considerations