So reasoning allows machines basically to support us in determining the clarity of the semantic representations.

And you have knowledge about all. Today we will talk a bit about description logics. Description logics are the foundation, the logical foundation of ontologies. And then there is a reasoning algorithm

which is used to have learned with RDF and RDF schema, the rule based approach where you can apply certain rules to infer new information, to reveal implicit information from RDF, RDF schema, vocabularies and simple ontologies

with more complex one with all ontologies. This rule based inferencing doesn't work anymore. And their description logic reasoner use Tableau algorithms. And I want to show you a bit how that works, but we will not go too much into detail there

just to give you a bit of an idea how reasoning with more complex ontologies work. But of course that's a topic which could fill its own lecture and it's a very active research field where you have hundreds or even thousands of researchers working on efficient reasoners and implementations there.

And that's particularly important when you have larger ontologies for very simple ones, maybe we humans can discover inconsistencies, but once you have larger ontologies and more complex representation formalisms is used the expressivity of OWL,

then it's not always clear or for humans clear whether something is consistent or inconsistent and reasoners basically can assist us in finding such inconsistencies. So that's the goal for today.

Basically, the semantics of OWL is based on description logics and they have a model theoretic formal semantics. So OWL-DL, for example, corresponds to description logics showing D, which you can see here, OWL-2 corresponds to SROIC-D,

I don't know how it's pronounced. And the letters there, they basically stand for certain features of these description logics. So, and we will look at the simpler one showing D today in the lecture.

So description logics are a family of knowledge representation languages. They are usually fragments of first order logic. First order logics also has the acronym FOL. They are in most cases decidable. So decidable fragments, decidable means you can always answer certain questions

about the logic, whether something is true or false. That means decidable, that you can in finite time decide certain questions. They are comparatively expressive.

So description logics try to maximize this fragment of first order logic. First order logic overall is not always decidable. There are certain questions which you cannot answer in finite time. So description logics try to always stay in this decidable fragment,

but at the same time be as expressive as possible. But of course we have to limit ourselves a bit to stay in this decidable fragment. They are originated from semantic networks. They also have a new syntax,

which is a bit more intuitive. So because it doesn't use variables. So it's a variable free syntax. For example, you write P is a sub class of Q here. For example, in this example,

instead of writing for all X, for all variables X, if P of X holds, then Q of X holds. So that would be the first order logic notation. And the description logic notation is just such a sub class notation.

It's a bit inspired also by subsets. Subset or equal P subset or equal Q, because you can see classes as kind of sets of instances as well. So the basic components of description logics are concept names.

So we have atomic concepts like student, book. So these are also were called resources. Yeah, in the RDF world, instances.

Then we have, I know, sorry, atomic concepts are classes in the RDF and RDF schema world, yeah, classes. In description logics called concepts or concept names or atomic concepts. Then we have role names and role names corresponds to what is called properties

or predicates in the triples like born in or works for. And then we have individual names, also called individuals or objects or in the RDF world, instances or resources like Stephen and Mary, for example, yeah.

So the set of concepts, role and individual names is often denoted as signature or vocabulary of the knowledge base. So a knowledge base, what is a knowledge base? And description logic knowledge base consists of two parts usually.

One part is called T-box and denoted with this tau, for example, and that's information about concepts. And then we have an A-box denoted with A and that denotes information about individuals. And for more expressive description logics,

there's also something called R-box, R, which contains information about roles. In simpler description logics, the roles are just part of the T-box, but in more expressive description logics, you have more axioms also about roles and then you can call or separate that into an R-box.

So one of the simplest description logic is ALC. And ALC stands for attribute language with complement. It's the most simplest propositionally closed

description logic, which subsumes propositional logic basically. And complex or ALC concepts are inductively defined as follows. So every concept name is a concept. So classes are concepts, that's clear.

Then two concepts are added, the top concept and the button concept, and they have the symbols top and the other one here, bottom. Yeah, in our, this corresponds to our thing and our nothing, if you remember from two weeks ago,

yeah, our thing is the class of subsuming everything and our nothing is the class corresponding to an empty set. So that's also relatively simple. And then the third rule is if C and D are concepts and R is a role, then the following are also concepts.

So we can build the negation of C, the complement, yeah. We can build the conjunction of C and D denoted with this symbol here, also the intersection or an end combination of C and D.

So it basically builds the intersection of the sets of instances of those two classes, C and D. For example, if you have the class of humans and the class of students,

yeah, you can build the intersection or that doesn't make so much sense because it actually corresponds to the class of students. You could also take, I don't know, the class of students and the class of employees. And the intersection of that would be the students

who are working in addition to studying, yeah. So that's the intersection. And then we also have the union. That's what you see here below. Also symbolized by this square union symbol. And that's a disjunction, a union

or an or combination of the two concepts. So you could build the class here also of, or the concept and uniting, for example, the students and the employees. And then it would contain all students and all employees. So that's the disjunction where a member

of the new concept needs to be only a member of one of the two constituents, in that case, C or D. Then a third possibility to build new concepts

is an existential restriction. So we, it's denoted with, it exists R and C. So that means it exists an instance or it builds basically a set of instances.

You remember we had in the OWL lecture, the some values, some value of restriction. And that's such an existential restriction. So it builds the set of instances

which have where the instance has the property R and the value of this property belongs to the class C. So it basically selects a set of instances and defines this as being a new concept. It selects all instances which have the property R

as one property with a value and the value belongs to C. What happens, C, for example, can be also the top concept. Then it basically means the value doesn't matter. Then we select all instances which have a property R, yeah?

Doesn't matter what the object of these triples refers to. If we have a concrete C and not the top concept, then the value of R must be the object of the, or the value of this property

must belong to this class C. And the selection of all those instances then is the set of instances belonging to our new concept. And then we have a last construction of new concepts

that's for all R. The values of R must belong to C. So that's a value restriction. And we had an owl, this all value from restriction. So that means all values of instances which have the property R must belong to the class C.

So we built a new concept by selecting basically all these individuals which have the property R and where the values of this property R belong to C. So an example for an extensional restriction, for example,

would be the set of parents, yeah? We could say R is parent off and then C could be human. So we could, that would be actually the set of children

if we select all instances which, or the set of parents, if you have the property is parent off and human. So that would, for example, we could also have animal parents, right? But if we restrict this is parent off property

to only those where the values are belong to the class humans, then we basically define the set or the concept of fathers and mothers. So you can find some more examples for these.

So this is basically the definition of the ALC description logics, very simple. Basically this inductive definition, of course you can apply once you apply it. These rules, you can construct more complex concepts by iteratively applying more of these conditions here.

So here are some examples. For example, we have the concept person and then we have an intersection with a restriction on the property has child and then the top concept here. So these are actually all persons with children.

Animals would be included. Also animals could have the property has child, right? But since we have the intersection with the concept person, this would build us a class basically of parents. So second example here,

we have animal intersection with for all eat. Eat must belong to the class vegetable. So let's assume we have such a concept animal and the property eats, and then you can apply the property multiple times.

Animals can eat leaves, they can eat grass, they can eat other animals, they can eat meat. They can eat insects. And here we select those instances, those individuals,

which have the property eat, but which eat only vegetables. And then we built the conjunction with the animal concept. So these are the vegetarians under the animals, yeah. Another example is professor, union student.

So this basically builds the concept of all, you could say university members, although maybe also employees. So we would have to add another union if we also want to capture employees, but this would be a concept of professors

and students or students. And the last example here, also again, a bit more complex. So we have person and then the intersection or conjunction with for all properties born in,

the value must not belong to a European country. So this basically selects all individuals which have the property born in and where all values of this property born in point to an instance of which do not belong

to the concept European country. So this basically selects persons which are not born in a country in Europe. Now, and you see here, the expression is already a bit more complex. We actually have three combinations.

So we have the negation of European country here. Then we have the all values restrictions there. And then we have a conjunction between person and the second concept definition here.

So that illustrates how we can build concepts, basically new classes out of existing classes or out of selecting instances based on properties in our knowledge base. So what about the T-box? The T-box, also terminology box,

consists of a finite set of terminological axioms. Terminological axioms are basically general concept inclusion axioms. For example, or given a concept C and D, these general concept inclusion axioms

are denoted in this way here. C is a subclass of D. And equality, and basically in OWL, this would be subclass of. C subclass of D. And the concept equality can be expressed

with this equal sign with three dashes here. C equal D. And this corresponds to the OWL property equivalent class. So in OWL, we can use the equivalent class property to indicate equality. But in fact, this is just syntactic sugar.

This equality is just an abbreviation for C is a subclass of D and D is a subclass of C. So you could also write these two instead of the equality. Equality just allows you to write things down a bit more concise.

And even in OWL, this shortcut equivalent class is introduced for that purpose to make it more concise. So what is the A box? The A box is our, a finite set of assertional axioms of the following forms.

So we have basically two things. We have concept assertions. For example, here, C, A belongs to C. This is a concept assertion. This basically means A is of type C, A, the individual A belongs to the class C. This is a concept assertion.

In RDF, you would just write A RDF type C. And then we have a so-called role assertions. And there we write the role and then the two individuals which are connected by the role here, A and B. This is a role assertion. And that means A has the property R with the value B.

In RDF, you would write A R B. That would be the triple. So you can see ontologies on the one hand from the triple perspective. Everything is subject predicate object triples but you can also see them from the logical perspective.

And then there is this description logic notation here. And the A box basically contains of these kinds of assertions, concept assertions. So individuals belonging to classes, to concepts or role assertions connecting two individuals with each other.

So a formal definition of the model theoretic semantics of ALC is given by means of an interpretation. And we had this already in RDF and RDF schema. So an interpretation consists of two things.

Non-empty domain symbolized by this delta. And then a mapping which maps every individual A to a domain element. The interpretation of A from the domain.

Every concept name, capital A to a subset of domain elements. So the concepts are interpreted as subsets. So basically sets of domain elements. Sets of individuals and instances.

And every role to a set of pairs of domain elements. So a role basically is a subset of the Cartesian product of our domain with itself.

So basically a role is a set of tuples where the components of the tuples are belonging to our domain delta. So that's then an interpretation. An interpretation you can imagine or picture yourself

like a concrete resources, RDF resources. The other domain, for example can be a set of RDF resources. And then we have a mapping of our logical concepts and individuals and roles to properties, to classes

and to instances in our concrete knowledge base. So the interpretation is extended to complex concepts by the following. So the interpretation of the top concept

is the domain itself. The domain basically is the set of all things in our knowledge base like our thing, for example, and the our terminology. The bottom concept is the empty set here.

The negation of a concept or the interpretation of the negation of a concept is we take the domain and subtract and remove from the domain basically the concept C. So we remove all things which belong to C from our domain

and that's the compliment. Then we have here this conjunction between C and D. And the interpretation of that is that we built

the intersection of the two sets C, the interpretation of C with the interpretation of D. So basically we just make the sets of instances belonging to the interpretation of C and intersect that with the set of instances belonging

to the interpretation of D. The same we do with this junction here, the interpretation of the disjunction is the union of the interpretation of C and D. So we basically, the logical axioms of what we do here,

the interpretation allows us to see the logical axioms in the light of set theory. On the right-hand side here, you see only sets and set operations, right? On the left-hand side of these equations,

we have a logical axioms. On the right-hand side, we have just set operations, union, this intersection, the minus, the set difference here, yeah? That's how we can apply these interpretations.

So let's look at the last two examples here. We have the existential restriction. How do we interpret that as a set? So we basically select all X in our domain, all individuals or all concepts in our domain, for which there exists a Y in the class C

in the set which belongs to the set of the interpretation of C, such that XY belong to the interpretation of R, yeah? So that the tuple XY belongs to R, yeah? So this basically means we have a triple X or Y,

where Y belongs to the class C, and we select all these Xs, yeah? And that's the new set, a new set of individuals, which is defined basically by this kind of axiom here, by this existential restriction.

And then similarly, we have these all values restriction here, how do we interpret that? Again, we select all X in our domain delta, where the following holds, yeah? For all XY, so for all triples X, R, Y,

or all tuples XY, which belong to the role, interpretation R, RI here, Y must belong to the class C, yeah?

So in the existential restriction up here, just one needed to exist, yeah? And that was sufficient for our X to belong to this class. For our all values restrictions, all properties or all values of this property R,

must have values which belong to C. So we again also here select a set of things, which fulfill basically this restriction, and we construct a new class in that way.

So interpretation is extended to axioms by the following rules. The interpretation I fulfills C sub-class of D, if the interpretation of C is a subset of the interpretation of D, yeah?

The interpretation I fulfills C equal D, if the sets are equal, yeah? If C is exactly the same set as D. An interpretation I holds for C of A,

if A is an element of the interpretation of C, yeah? A belongs basically to the concept C. And an interpretation or RAB holds for an interpretation I,

if the interpretation of A and B, the tuple is an element of the interpretation of R. So again, we basically trace back the interpretations

to set operations, yeah? So we can validate, compare certain sets here, check whether something is an element of a set and based on this checks, set theoretical checks, we can determine if I is an interpretation

for certain axioms. So let's look at some example here. So we have the following T-box. Man equals to not woman and this conjunction with person, yeah?

So we basically select all, or we build here the disjunction between the negation of woman and person and define that to be man. So we define woman to be a sub-concept of person.

We define mother to be equivalent to a woman, which is a conjunction with the restriction on the property has child with the value top concept,

so some value. Everything which has the property has child and that's intersected with the concept woman. Yeah, so this is our T-box. So these are axioms which talk about concepts and roles here.

And then we look at our A-box, the axioms. So we have Steven belongs to the concept man. Monica belongs to the concept not man, so complement of man. Jessica belongs to the concept of woman.

And then we have the role has child on the role axiom and Steven is connected via has child to Jessica. Yeah, this is our A-box here. That's the way how we can build knowledge bases in ALC

and the simple description logic. Yeah, so here we have this equivalent with the all concepts, yeah? So the top, I mentioned that already, top concept is all things, button concept is all nothing. The negation corresponds to our complement of,

the union or this conjunction corresponds to our union of, the disjunction corresponds to our intersection of and the extensional restrictions to our sum values from

and the all values from restriction to all all values from. So basically we can translate this description logic

in OWL or vice versa. We can translate OWL into this description logic and the description logic also into OWL and RDF triples in the end, yeah? And that's a great thing that we can do that

because basically this RDF triples, that's something like a database. Basically we have here a way to connect a data representation with a logic, yeah? So then there is another description logic, ALC plus or ALC or ALC plus inverse roles, yeah?

And that's called ALCI and the I stands for inverse roles, yeah? So basically the names of the description logics are acronyms related to the features. A role can be a role name R or an inverse role R minus.

Semantics of inverse roles is defined by R minus. The interpretation of R minus is all YX where XY belongs to the interpretation of R, yeah? So we basically built the opposite

and the OWL construct for that is inverse of, yeah? So I guess you can all come up with some examples of inverse roles. For example, as parent and as child would be inverse, yeah? Somebody who has a parent, this person who is a parent has somebody as a child, yeah?

So that's a typical example of an inverse role and you can then go in this different directions. So then ALC plus role hierarchy, that's another feature which we can add to this description logic

and the name is then ALCH, H for hierarchy, yeah? So and then if you have roles R and S and role inclusion axiom is denoted by R sub role of S. You see here, it's the same symbol as for concepts,

for sub concepts or subclasses, yeah? So the symbol is here overloaded. So don't be confused, you have to be very careful to understand. Here in that case, we always use for roles small letters, yeah? And for concepts capital letters

and then you basically can see when the symbol is applied to small letters, it's a role inclusion axiom. When it's applied to capital letters, it's a class or concept subsumption axiom. So and then we also have the equivalent R equal S

and that's an abbreviation for R is a sub role of S and S is a sub role of R. Do you remember we discussed this a bit in the old lecture, what could be sub roles? So for example, being married to could be a sub role of being knowing someone, right?

If you are married to someone, then you definitely know this person as well. So that's why being married to could be modeled as a sub role of knowing another person or being married to someone

could also be a sub role of being related. We could have the role being related with someone else and then we have different types of sub roles which could be being married to, being child of and so on as sub roles of being a relative of.

There are different types of family relationships and these could be modeled as sub roles. And that's then a role hierarchy. And in OWL, the OWL construct would be RDFS sub property of, you should remember that.

And basically an interpretation I entails R is a sub role of S. If the role interpretation of R is a subset of the role interpretation of S. What was the role interpretation?

It was the set of tuples, right? The set of tuples of individuals which are connected via this role. And if this set of tuples is a subset of the set of tuples of S, then we have this role inclusion. So it's always important to picture oneself,

this set theoretical foundation, yeah? Roles, properties are basically sets of tuples and the interpretation then, or you can build then subsets of these kinds of tuples and determine if a role is a sub role of another one.

For example, it doesn't have to be always explicitly stated. For example, you can have two roles. You have the role is married to and the role is related to, right? These can be two different roles and then a reasoner can actually discover if the sets of these tuples of the roles are subsets

that is married to is actually a sub role is related to, yeah? So you don't have to have it explicitly stated but the reasoner could figure that out that if in all cases people who are married

with each other are also related with each other, then a reasoner will discover that such a sub role relationship holds or the sub property of relationship. Next feature which we could add is role transitivity. Yeah, so we add to ALC the transitivity

and this is now becomes the symbol S. So because the acronym would become otherwise too long, it just gets the symbol as ALC plus transitivity is the same as S, the description logic S.

So for a role R, a transitive axiom is denoted by trans R. So we basically determine in a role to be transitive

with this. The owl construct is owl transitive property. We have discussed that two weeks ago and the interpretation of I entails trans R if for all X, Y in R and Y, Z is also in R follows that X, Z is in R, right?

So that's exactly the transitivity. If X, Y is connected, X and Y is connected with or belongs to the role and Y, Z, then also X, Z belongs to the role. If that holds, then R is transitive

or if R is transitive, then this rule must hold and then we can also infer more tuples to belong to R basically based on the transitivity. For example, being related to someone is also transitive, right?

If A is related to B and B is related to C, then also A is related to C. So that's a transitive role and we could then discover new relationships between relatives by just following the path of being related with each other.

So next feature is role functionality. This is the description logic A, L, C, F. So for a role R, a functionality axiom is denoted by func R. So R is functional and interpretation I entails func R

if the following holds. So we have X, Y belongs to the role interpretation and X, Z belongs to the role interpretation, then Y and Z are equal. That means a role can only have one value

or property can have only one value. If it has different values, those different values are actually referring to the same entity, real world entity. In OWL, this was called OWL functional property. So that's the description logic A, L, C, F.

So then we have simple versus complex roles. So if you have a role hierarchy R and then with the following symbol here, we denote its reflexive and transitive closure.

A role R is complex with regard to R if there exists a role S such that the transitive closure of S is an element of R, as an element of the role hierarchy

and S is a sub-role of R. Otherwise the role R is simple. So basically a role is complex if there are other roles, if there are sub-roles of R,

so that R could be constructed as a transitive closure of the sub-role. Otherwise we call a role simple if that doesn't exist. So let's look at some example. So we have a role hierarchy, U is a sub-role of R

and R is a sub-role of S and S is a sub-role of T and Q is a sub-role of T. And then we have the transit and R, the role R is a transitive here in that case,

which ones are complex? In that case, R, S and T are complex. Yeah, R is complex because it has a sub-role U. S is complex because it has a sub-role R and T is complex also because it has a sub-role S

and Q here, yeah? While U and Q are simple because U doesn't have a sub-role and Q also doesn't have a sub-role, right?

So now another extension of our ALC and that's unqualified number restrictions. So this is called ALCN number restrictions. So for a simple role R and the natural number N,

we can have these number restrictions larger or equal NR, smaller or equal NR or equal NR. And these are concepts which are defined,

which semantics is defined as follows. So the interpretation of larger or equal NR, the interpretation of that selects all X in our domain where the number of Ys,

so basically here this means counting, counting the set of elements which are defined here. So we select all individuals of our domain Y

where XY belongs to our role interpretation and if the number of these is larger or equal to N, then we select the X to belong to this restriction.

So that basically means we select all individuals which have the property R more equal or more than N times. So for example, parents of a child

with three or more kids, we could define this as, and then we could, for example, that case R has children or has child, has child would be R and N would be three. So we could say larger or equal three has child.

What would this select? This would select all individuals which have the property has child and where the set of these has child properties is larger or equal than three.

So that's a number restriction. So, and in the same way, we can not only build larger or equal, we can also build a smaller or equal. So we could here say, for example, parents with less than three children, less or equal than three children

or less or equal two, for example. And then we basically select all individuals which have the property R in that case only less or equal N times. And then equal is the same.

So we select those individuals which have the property R exactly N times. So these are the unqualified number restrictions. Why unqualified? Because we don't say what the value of these properties

needs to be from. So we don't indicate that the children needs to be belong to, I don't know, small to the class of concept of small children or adult children or something like that. That's why unqualified. Doesn't matter just the number of properties

or tuples belonging to the interpretation counts. That's why unqualified, there also exists qualified number restrictions, but we don't discuss them here. That's a more complex description logics. And the corresponding owl constructs are owl min-cardinality, owl max-cardinality,

and owl cardinality. You remember these were owl restrictions and you had to, these were several tuples, not just one triple, you had to define the cardinality, you had to define on what property. So that were two or three triples, you needed to define such cardinality restrictions

in owl. Good, then nominals, another feature. And this is called O, A-L-C-O. If we add also nominals, what is nominals? If we have a set of individuals, A1 to AN,

a nominal A1 to AN is a concept which semantics is defined as follows. So we basically take the interpretation is just the set itself. So we define a concept by naming all the individuals

belonging to the concept. We define a class by naming all the instances of the class. You remember we had this, I think, moons of Mars, and they were, we were just listing the moons of Mars and in that way, defining the concept moon of Mars.

The owl construct is one of, owl one of. So that are nominals. Yeah, so this is basically a lot of features which can be added to A-L-C, to them, our simple description logic. So, and if we add all these features together,

so role functionality, transitivity, role hierarchy, inverse roles, and so on, we come to a complex, relatively complex description logic. We started with the very simple one right in the beginning and we added now a lot of features

to our description logic. We also always saw how the interpretation of the logic is constructed or can be traced back to the set theoretical constructs. And then we can do reasoning on top. And there are three types of reasoning. Deductive reasoning.

Deductive reasoning starts with the assertion of a general rule and proceeds from there to a guaranteed specific conclusion from the general rule to the specific application, that's deduction. Then we have the opposite is induction. It begins with observations that are specific

and limited in scope and proceeds to a generalized conclusion that is likely, but not certain in light of accumulated evidence. So from the specific to the general, that's inductive reasoning. And finally, we have abductive reasoning.

It begins with an incomplete set of observations and proceeds to the likeliest possible explanation for the set. So now how can we do logical reasoning in description logics? And here you have a small illustration.

So penguins are black and white. Some old TV shows are black and white. Therefore, some penguins are old TV shows. So logic is another thing that penguins aren't very good at. So logic can become quite complex.

And if your knowledge base contains some omissions or some mistakes, you will quickly identify and it happens all the time. If you build a more complex knowledge base, you will definitely make mistakes

and you will figure out that there are some errors and knowledge representation and reasoners can actually help you identifying these errors and then you can fix them. You can come to a more precise knowledge representation and yeah, that is sometimes crucial. For example, these kinds of things

are applied a lot in life sciences. So in life sciences, there are really large ontologies and knowledge bases. And what do you need them for? You need them for, for example, for advisory systems, for physicians in the hospitals, yeah? So that when a patient has certain symptoms

that you could infer what could be the disease the patient is suffering from, yeah? And this of course needs to be correct and that's why reasoning is applied a lot in life science application. In other areas, reasoning is not so important.

For example, I showed you also schema.org and Google's knowledge graph. I think Google's knowledge graph is not very consistent. There are some mistakes and errors. It doesn't really matter if there is something not 100% correct there

because it's not life threatening. And I guess many of you have experienced that already that also some information you get from Google's knowledge graph is wrong or you use the navigation from A to B or the characteristics of some restaurant and maybe the opening hours were not correct or something else.

So there are knowledge graphs which do not need to be 100% correct but there are also knowledge graphs which need to be 100% correct. And for example, life sciences is such an area where it should be in many cases 100% correct. And that's why reasoning for example is applied a lot in that area.

So logical reasoning and description logics is done. If you have an interpretation I and T box, A and A box and K a knowledge base, which consists of T and A

we say then I is a model for T for our terminology box. If I, if all the axioms alpha hold in I for every axiom alpha in the T box and then we write that the interpretation I

fulfills the T box T. So it's denoted in the following way. So it needs to be fulfilled for all individual axioms and then it also holds for the whole set of axioms T.

Similarly, I can be a model for the A box if it holds for every A box axiom alpha and the same way. And then we can say that I is also a model for the whole knowledge base if it's a model for the T box and the A box.

Very simple. And then we can say an axiom alpha is entailed by our knowledge base K written in the following way. K entails alpha if every model I of K is a model for alpha.

So we can infer new axioms alpha if every model every interpretation of K is also a model for alpha. That's the way how reasoners work.

Then there are some reasoning services. So the first one is concept satisfiability. So what does it mean? We want to check whether a concept C is satisfiable with regard to our knowledge base K. So whether there exists a model I of K

such that the concept is not empty. So we want to see or we want that C equals the button concept.

If that does not hold in our knowledge base, yeah then it's satisfiable. When if C is not always the button concept it can actually be that you define a class but the class is not satisfiable. Can we look at some example?

So for example, you can define, for example no, you can define lots of classes. For example, if you define the intersection of parents and not parents, yeah, that will be always then as will be not satisfiable.

If you define parents as having the has child property for example, and not parent of having not the has child property when you then build the intersection the intersection will be always empty, right? So it's easy to define concepts which cannot be fulfilled, yeah.

You can come up yourself with some examples as an exercise and sometimes this happens by accident. Of course, in this simple example which I showed you now, it's very obvious that if I have a class defined as parents and not parents

but in some cases it's not so obvious to see that a class actually cannot contain any instances. And the reasoner can identify this because this usually hints to a modeling mistake because of course we don't want to define empty classes. We want to define concepts and classes which have instances.

So if a reasoner finds out that certain concepts are not satisfiable, that helps us to figure out what mistakes we have done in the modeling, right? Another reasoning service, the second one here is subsumption and basically here a reasoner checks

the problem of checking whether C is subsumed by D with regard to our knowledge base. So we can check whether the set of individuals belonging to the concept of C is a subset of the individuals belonging to the concept D in every.

model interpretation I of K. So we can basically check if some classes are subclasses of each other. Sometimes they might not be defined as subclasses, but we might figure out they are actually subclasses. So for example, you can define the classes of males and females

and humans, and then you figure out, oh, the class of males and the class of females are actually subclasses of the class of humans. And that a reasoner can tell you and discover such subclass relationships. So that's also very helpful. And it sometimes also helps you to

identify also mistakes in your ontology, because if you discover, oh, an animal is a subclass of a human, then apparently something is wrong. That's something which is unintended. And the last reasoning service here on this slide is satisfiability. So consistency,

the problem of checking whether a knowledge base K is consistent, for example, or whether it has a model, whether it is possible actually to create

a model for this knowledge base. That's satisfiability. And of course, we want to create models or we want to create knowledge bases which have models. If it's not satisfiable, it also usually tells us there are some mistakes in our knowledge base.

When the knowledge base is inconsistent, something is wrong. Then we have instance checking another reasoning service. So we can basically check whether an instance belongs to a class,

yeah, whether a belongs to the concept C here in that case, whether this holds, this axiom holds in our knowledge base K. So for every model I of K, so for example, you might not. So this, for example, also happens when you have the

subsumption reasoning, when you have defined somebody as a man or a woman, then a reasoner will determine if men and women are subclasses of humans, that an individual,

Paul, for example, who is a man and Angela, who is a woman, that they are also humans, that they belong to the concept of humans. So this is instance checking what reasoners can do. Also retrieval. So we can use a reasoner a bit like a query engine to retrieve things. So we can basically retrieve all instances A which belong to a concept C in our knowledge base

K. So that's finding all individuals A which belong to a concept C with regard to K. So that's retrieval. It's a bit similar to what a database engine does, right?

The difference is for retrieval using a reasoner, the instance or the individual does not have to be explicitly assigned to a class. For example, if you want to retrieve all humans, a reasoner will retrieve automatically all males and all females if males and females were

defined as subclasses of human, even if the individuals itself were not defined explicitly as belonging to humans. So it would here retrieve Angela, Paul and a lot of others

even if they were not explicitly defined to be humans, but just males and females. And that's what a reasoner can do. This example is of course relatively simple, but you can imagine if you have complex class hierarchies and if you have restrictions, then retrieval is not so simple

and can become very complicated. And another reasoning service is realization. And this is the problem of finding all named classes C which an individual A belongs to with regard to our knowledge base K. So find all C for a given A such that A is an element of the interpretation

of C in every model I of K. So we want for an individual know to which classes it belongs.

For example, if we have Angela and maybe Angela is explicitly said to be a woman, but then the realization will tell us it's also a human because women are a subclass of humans. It's a living being because humans are subclass of living beings

and it's an all thing. Everything is an all thing. So all thing will always be returned here as a named class. So these were reasoning services and there are a few more. We can reduce all services to satisfiability check. That's very important. So a reasoner

actually only does one thing. He does a satisfiability check. So and then you can reduce the other reasoning services to this satisfiability. So concept satisfiability.

So we want to check if the axiom C equal bottom concept does not hold. So we can just check does there exist an X such that K union C X is satisfiable. So we add

or we look for some new individual X and then we add the axiom X belongs to the concept C to our knowledge K graph K or knowledge base K and we check whether this is satisfiable.

If it's satisfiable then the concept C is also satisfiable and this does not hold here. Subsumption. So how can we realize subsumption? So we want to check whether C is subsumed by D

and what can we do? We just check whether we add to our knowledge base K the following axiom C and conjunction complement D of X and we check whether this is unsatisfiable.

So if this is unsatisfiable then the subsumption must hold. So if there is no X which belongs to the complement of D and to C then this cannot

cannot be then it must be a subsumption. So you can also visualize this as a small exercise as a fan diagram. So draw basically the sets of C D and the complement of D and then you can see

that the subsumption only holds in the case when this does not hold. And similarly instance check. Checking whether something is an instance. So we just add the

complement to our knowledge graph and check knowledge base and check whether it's unsatisfiable. So a reasoner only has to provide one reasoning service and that's satisfiability and with this one he can do all the other six which we have actually shown here. Instance

checking, retrieval, realization, subsumption, concept satisfiability. They can all be traced back to a satisfiability check. Good. And how does the reasoner now do that?

For that there is the tableau algorithm and the tableau algorithm helps to prove the satisfiability of a concept. So remember a concept is satisfiable if there exists a model i satisfying it. Now we need to construct a decision procedure for constructing models

and that's exactly what the tableau algorithm does. And the procedure is we transform a given concept into a negational normal form also called NNF. Then we apply completion rules in as long as possible and the concept is satisfiable if and only if a clash-free tableau can be derived

to which no completion rule is applicable. So this clash-freeness is important. We will see in a minute how that works. So let's look at some example. A sample ontology for tableau

algorithm. So we have a T-box. Man is defined to be the complement of woman intersected with person. Woman is a subclass of person. Mother is defined as a woman which has the child property

at least one child property. That's our T-box. Yeah man is a bit complicated defined here as not a woman intersect with person but that's how it is here. And then we have the A-box. We have Stephen is a man. Monica is not a man. Jessica is a woman. And we have Stephen and

Jessica and Stephen has a child Jessica. Maybe instead of woman we should have used female here male and female because Jessica apparently is a child depending on how old she is. She might

not yet be a woman but doesn't matter. This terminological finesse is here. So let i be an interpretation with. So we have man the concept man and we have Stephen in there. Woman we have then Jessica and Monica in there. Mother we have Monica in as an interpretation of the concept

mother. The interpretation of person then corresponds to Jessica, Monica and Stephen and has child Monica, Stephen, Stephen, Jessica. So apparently Monica is the grandmother of Jessica

here in that case right. So Monica has a child Stephen and Stephen has a child Jessica. So then holds this interpretation here fulfills our T-box. Yeah and it also fulfills our A-box.

Yeah so we have an interpretation. Interpretation basically means defining the sets the concept or assigning sets to the concept interpretations. And here these interpretation holds. You can

look carefully you will find that everything like fits for example has child. We have Stephen and Jessica here right. It's in there but there are also different interpretations possible. This

particular interpretation here for example defines Monica to be the mother of Stephen but there could be also a different interpretation. And now we need this negational normal form.

And the negational normal form a concept is a negational normal form if all occurrences of negatives are in front of atomic concepts. Yeah so every A-L-C concept can be transformed into an equivalent one in negational normal form using the following rules. Yeah so if we only

have C then the negational normal form of C is C if C is atomic right. If we have the complement of C then the negational normal form is complement C if C is atomic right. So it's then still

directly in front of an atomic concept here. Yeah so then we have the negational normal form of the double complement of C is the same as the negational normal form of C. The negational normal form of C

disjunction D is the negational normal form of C. Disjunction negational normal form of D. The same with the conjunction here yeah. Then we have the negational normal form of the complement of a disjunction.

And that is then the negational normal form of so we basically take the negation inside yeah. So that's the negational normal form of the complement of C. And then we turn the

con disjunction into a conjunction yeah. So we you see this is also here turned around yeah because the negation from outside can be pulled inside if we turn the conjunction into a disjunction. And vice versa the conjunction is turned into a disjunction

here yeah. We can also pull the negation inside here to build the negational normal form. And then we have the negational normal form for all what is for all role restrictions. So

there we basically take the negational normal form inside right. We apply it on the concept C the same for the extension. We also apply it to the concept C because the negational normal form just tries to push negations inside to the atomic concepts yeah. That's why here

nothing needs to be changed because we don't have a negation in there. If we have a negation around we actually have to switch the all value restriction into an existential value restriction.

And then we can push the negation down to the concept inside yeah. And vice versa with the negation of an extension restriction here we can push that inside by converting it to an all value restriction yeah. So these are the rules and you can apply them if you have a

complex concept expression you can apply these roles as much as you want and then you basically in the end get the negation in normal form. So for example we have this

concept here. We have a negation of a conjunction B, this negation B, this junction negation C yeah. And then what do we do? We build a negational normal form and then we apply the

rules yeah step by step. So first we convert this the negation of this conjunction into a disjunction of the negations right. That's why we add here a negation, here the disjunction,

here a double negation. So then we can resolve the double negation then it becomes only C here and here we can resolve the double negation then it only becomes A disjunction negation B.

So the negational normal form of C is C because it's an atomic concept. The negation normal form of A conjunction complement of B is then the negation a normal form of A conjunction negation normal form of complement of B

disjunction C sorry disjunctions yeah. And then the negation a normal form of A as an atomic concept is just A negation a normal form of complement of B is let's look back here and our rules yeah negation a normal form of complement of C is just the complement of

C if C is atomic and since in our case here B is atomic yeah so and then we have the negation a normal form is this one. A disjunction complement B disjunction C

that's the negation a normal form.