I'll give you some study material. Please summarize it and explain it in simple terms. ###Description logic
 • Description logic (DL) is a fragment of first order logic (FOL), the logic 
we have seen until now. This means that DL is less powerful than FOL.
 • However, we will see that it also has some advantages. In particular, it 
is a decidable logic.
 • Web Ontology languages (OWL) are based on DL. 
• DL is used by Linked Data computational linguistics to represent their 
data. The triples used in the Linked Data database are formalized in 
DL. The triples indicate a relation between two individuals or 
concepts.
 22
Model
 • As FOL, DL has a model in which individuals, unary predicates and 
binary predicates are present. However, these are called differently in 
DL:
 FOL
 Individual constant
 Unary predicates
 DL
 Individual
 OWL
 Individual
 Concepts
 Binary predicates
 Role
 Class
 Property
 23
TBox and ABox
 • DL distinguishes between:
 Tbox and other relations among concepts: formulas describing 
the relationships between concepts (es. Every cat is a mammal, 
i.e., the concept of cat is included in that of mammal)
 ABox: formulas stating that a certain individual belongs to a 
certain concept (es. Mary is a poet, i.e., the individual Mary 
belongs to the concept of being a poet)
 • In FOL, there is no comparable distinction. However, in FOL we can 
distinguish between sentences with quantifiers (∀x(cat(x) → 
mammal(x)) and sentences with individual constants, i.e., proper 
names (Poet(Mary)).
 24
TBox and ABox
 • TBox describes the hierarchy of concepts and the relations among 
concepts. ABox describes how individuals are located in this 
hierarchy. 
• The procedures to evaluate the formulas in the TBox and ABox are 
different. To evaluate the formulas in the Tbox, we have to verify the 
goodness of the classification. To evaluate the formulas in the ABox, 
we have to perform an “instance-checking”, i.e., to check whether an 
individual belongs to a certain concept or to certain concepts.
 • We can change the ABox keeping the TBox untouched. In such a case, 
the classification remains the same, but the domain of individuals 
changes.
 25
Symbols
 • C and D are used to designate concepts. 
• a and b are used to designate individuals.
 • R is used to designate a role (relation).
 • If a is R-related to b, then b is called a R-successor of a.
 • In the basic version of DL, negation can be applied only to atomic 
concepts.
 • In the basic version of DL, existential restriction can be applied only to 
the top concept.
 26
27
Semantics
 • Symbols are interpreted on a non-empty domain △ of individuals.
 • The top concept denotes △.
 • The bottom concept denotes the complement of △, i.e., the empty 
set.
 • A concept C denotes a subset of △, i.e., C ⊆ △.
 • A role R denotes a binary relation on △, i.e., R ⊆ △ x △, R is a 
subset of the Cartesian product of the domain by itself.
 • An individual constant a denotes an individual of △.
 • The negation of a concept denotes the complement of that concept: 
¬C denotes △ - C.
 28
Semantics
 • The intersection between concepts denotes the intersection between 
the corresponding sets (I means “interpretation”):
 • The union between concepts denotes the union between the 
corresponding sets: 
29
Semantics
 • The concept inclusion denotes the inclusion between the 
corresponding sets:
 •Concept assertion and role assertion are interpreted in the usual way:
 A concept assertion is true when the individual denoted by the 
individual constant belongs to the set denoted by the concept. A 
role assertion is true when the pair denoted by a and b belongs to 
the relation denoted by R.
 30
Semantics
 Universal restriction ∀R.C denotes the set of individuals x such that for 
every y that is R-related with x, y is in C:
 In English: the set of x belonging to △ such that for every y, if the pair 
<x, y> belongs to relation R, then y belongs to C.
 We can use universal restriction to restrict a concept to only those 
members that have some relation with another concept. 
31
D
 b
 R
 a
 R
 R
 c
 C
 R
 R
 In D every element that has a relation R is R-related with an 
element of C. There is no element of D that it is R-related with 
an element external to C. Therefore, D is denoted by ∀R.C.
 32
Semantics
 Universal restriction serves to express concepts such as: person all of 
whose children are female or person without children. Suppose that 
Person and Female are atomic concepts and that hasChild is a role 
denoting the relation of parenthood. Then:
 denotes the concept whose extension is the set of persons who have 
only female children. Instead,
 denotes the set of persons without children. 
Fourteenth lecture
 9th May 2024
 1
Semantics
 Existential restriction ∃R.C denotes the set of individuals x such that 
there is at least one y that is R-related with x and y is in C:
 In English: the set of x belonging to △ such that there exists at 
least one y such that pair <x, y> belongs to relation R and y belongs 
to C.
 Notice that the elements of the set can be R-related to other 
elements not belonging to C.
 2
D
 b
 R
 a
 R
 R
 c
 R
 R
 C
 In D every element is R-related with at least one element of C. 
There can be some element of D that it is also R-related with an 
element of the complement of C. D is denoted by ∃R.C.
 3
Semantics
 Existential restriction serves to express concepts such as: person some 
of whose children are female or person with children:
 denotes the concept whose extension is the set of persons who have at 
least one female child. Instead,
 denotes the set of persons who have at least one child. 
4
TBox
 • Some formulas describe the relations between concepts and the 
hierarchy of concepts. These statements are called terminological 
axioms. 
• Terminological axioms can be inclusions or equalities. An inclusion has 
the following form:
 where C and D are concepts and R and S are roles. A role R is 
included in a role S if for every pair such that <x, y>∈R, <x, y>∈S. 
Then, C (or R) is a concept (or role) lower in the hierarchy than D (or 
S).
 5
TBox
 • An equality has the form:
 Where C and D are concepts and R and S are roles. A role R is 
equivalent to a role S if for every pair such that <x, y>∈R, <x, y>∈S 
and for every pair such that <x, y>∈S, <x, y>∈R. 
• An equality whose left side is an atomic concept is called definition. 
For instance, the following is a definition of Mother:
 6
TBox
 • In a TBox we can distinguish primitive and defined concepts. Primitive 
concepts are those concepts that occur only on the right-side of the 
formulas of the box. A concept is defined if it occurs at least once on 
the left side of the formulas of the box.
 • A base interpretation I of a TBox is an interpretation of the primitive 
concepts and roles of I. That is, it is a function that associates a set to 
every primitive concept and a relation to every primitive role of the 
TBox. The interpretation of the defined concepts and roles depends 
on the base interpretation.
 7
Description of the world
 • In the world description or ABox , one introduces individuals, by 
giving them names, and one asserts properties of these individuals.
 • In the ABox, there are concept assertions and role assertions:
 The first formula is a concept assertion, the second is a role assertion. 
They correspond to the formulas Father(Peter) and hasChild(Peter, Ann) 
of first order logic.
 8
Description of the world
 • It is assumed that every name denotes only one individual and that 
every individual has at most one name. That is, if a and b are distinct 
names, then aI ≠ bI. This is not usually assumed in FOL.
 • ABox and TBox together abstractly describe a world. Together, they 
are called knowledge base (KB). We can use a KB for knowledge 
representation. For this reason, this system is called Description Logic.
 • However, DL is also a Logic. This is because it is possible to make 
inferences. KB contains implicit knowledge that can be made explicit 
through the use of reasoning. 
• These inferences can concern both the ABox and Tbox. 
9
Inferences
 • Some inferences regarding concepts can concern their satisfiability. A 
concept is satisfiable when it can contain some members, i.e., is not 
contradictory. 
• Other inferences can check if a concept is more general than another 
or not (subsumption problem), or if it is equivalent to another 
concept or if it is disjoint from another concept.
 • Two concepts are disjoint if and only if their intersection is empty. 
• Likewise, it is possible to make inferences regarding individuals. For 
example, we might like to check whether a set of assertions regarding 
individuals is consistent with respect to a certain TBox. 
10
Inferences
 • For instance, if the TBox contains:
 then: {ann : Female, ann : Male} is inconsistent with the TBox.
 • In other cases, one might want to check whether an assertion is entailed 
by a TBox. 
• We say that an assertion α is entailed by TBox A, and we write A |= α, if 
every interpretation that satisfies A also satisfies α. In other words, A |= 
α means that A implies α.
 11
Inferences
 • Retrieval problem: given a Tbox A and a concept C, find all the 
individuals that have the concept C, given A.
 • Realization problem: given a Tbox A and a set of concepts and an 
individual a, find the most specific concept C, given A, such that a : C. 
The most specific concept is that that is minimal with respect to the 
subsumption ordering.
 12
DL and DB
 • Often, an analogy is drawn between databases on the one hand and 
DL knowledge bases on the other hand. 
• The schema of a database is compared to the TBox and the instances 
with the data are compared to the ABox.
 • However, there are also differences: absence of information in a 
database instance is interpreted as negative information, while 
absence of information in an ABox only indicates lack of knowledge.
 • In other words, in a DB, if it is not said that the object a has the 
property P, then a does not have P. But in DL, the fact that it is not 
said that the object a has the property P only means that we do not 
know whether a has P or not.
 13
Algorithm
 • The problems that can be solved by algorithms are computable problems. 
There are therefore important relationships between logic and computer 
sciences. 
• Here we will define some basic notions to appreciate these relationships.
 • Algorithms can be defined as finite sequences of instructions used to 
mechanically solve a problem. Computer programs and apps are algorithms 
written in particular formal languages (the programming languages).
 • However, algorithms are used not only in computer sciences. Cooking 
recipes and instruction manuals (for example, the instruction manual to put 
together the pieces of a new furniture) can be seen as algorithms.
 14
Algorithm
 • Other examples of algorithms are the procedures we have learnt to 
perform some mathematical operations.
 • For instance, we have learnt the procedure to add numbers (line up 
the addends, sum the rightmost digits, write the rightmost digit of the 
result under the rightmost digits of the addends and the leftmost digit 
above the tens, sum the tens, write the rightmost digit of the result 
under the tens and the leftmost digit above the hundreds, etc.).
 • Likewise, we have learnt the procedures to calculate the hypothenuse 
of a right triangle knowing the length of the two other sides (calculate 
the square of one side, calculate the square of the other side, sum the 
squares, calculate the square root of the result).
 15
Algorithm
 • Being mechanic, algorithms are deterministic. This means that there is just 
one right result of the instructions.
 • The sum of two numbers has just one right result. The instructions to put 
together the pieces of some new furniture have just one result (some 
furniture).
 • Other kinds of instructions are not deterministic: for example, “describe 
your evening yesterday” is not a deterministic instruction.
 • Algorithms start from some data or things (numbers, ingredients, pieces of 
some furniture) and end with some results (some other data or things).
 • Here we will consider only algorithms that start from data or pieces of 
information.
 16
Algorithm
 • Algorithms are wholly explicit instructions. Since they must be 
followed mechanically, there must be no room for interpretations.
 • For this reason, it must always be fully explicit the order in which the 
instructions should be followed. Furthermore, it must always be clear 
when the algorithm has come to an end.
 • Algorithms can be represented by flow charts. In flow charts, the 
steps of the algorithm are represented by boxes and the order by 
which the instructions must be followed are represented by arrows. 
• The different kinds of boxes represent the different kinds of steps of 
an algorithm. 
17
Some examples
 Starting/terminal step
 Input/output data
 Operation
 Decision
 18
19
Functions and algorithms
 • Functions and algorithms are naturally connected. Algorithms take 
inputs and give outputs just as functions take arguments and give 
values.
 • Algorithms have just one “right output” because they are mechanic 
instructions. There is just one way to follow the instructions. 
Functions have only one value for any argument: they have only one 
output for every input.
 • Hence, algorithms can be interpreted as strictly connected to 
functions from inputs to outputs. More precisely, for any calculable 
function there is at least an algorithm that calculates that function.
 20
Functions and algorithms
 • Functions are pairs <input, output>. Algorithms are rules that allow to 
calculate, given an input of the function, the corresponding output.
 • Given a function, there can be more than one algorithm that 
calculates it. Some algorithms can be more efficient than others. 
• More formally, we can give the following definitions:
 • An algorithm A calculates the function f: B → C if and only if, for every x ∈ B 
such that f(x) = y, A gives output y if the input is x.
 • A function is calculable (or computable) if there is an algorithm that calculates 
it.  Other synonymous of calculable are “calculable in an effective way” and 
“effectively calculable”.
 21
Functions and algorithms
 • Computers codify information using numbers. For examples, images 
are divided in pixels and the color of every pixel is codified by three 
numbers (the level of Red, Green, and Blue). Sounds are codified by a 
sequence of numbers that indicates the frequency of the sound in the 
various instants of times, etc.
 • Computer programs and apps operates on numbers. They are 
algorithms that take numbers as inputs and give other numbers as 
outputs.
 • Therefore, we can largely restrict the functions we consider in 
computer sciences to the functions from numbers to numbers.
 22
Calculable functions
 • It is demonstrable that there are infinite calculable functions. The 
demonstration is complicate. However, intuitively, since the set of 
natural numbers is infinite, there are infinite functions N → N.
 • Take for example the constant functions. A function is constant if for 
every argument it gives the same value. For instance, f(x)=5 for every 
x is a constant function. There are infinite constant functions because 
there are infinite numbers n such that f(x)=n for every x. Constant 
functions are trivially calculable. Therefore, there are infinite 
calculable functions.
 • Thus, there are infinite algorithms because for every calculable 
function there is at least one algorithm that calculates it.
 23
Calculable functions
 • It can be shown that the set of calculable functions has the same 
cardinality of N. 
• However, it can also be shown that there are infinite non-calculable 
functions. They are the functions for which there is no algorithm that 
can calculable them.
 • Thus, computability has an important limit. There are problems that 
cannot be solved through an algorithm. Infinite problems can be 
solved mechanically but infinite problems cannot. 
• It is therefore interesting to understand which functions can be 
calculated and which functions cannot. It is equivalent to understand 
which are the limits of computability.
 24
Cardinality of the continuum
 • Cantor has demonstrated that not every infinite set has the same “size”. 
• In particular, many infinite sets has the same size of N. For instance, the set 
of odd natural numbers has the same “size” of N. So, N has the same 
cardinality of a proper subset of N. In fact, one of the most peculiar 
features of infinite sets is that they have the same cardinality of some of 
their proper subsets.
 • However, some infinite sets have cardinality greater than N. For example, 
the number of all subsets of N has cardinality greater than N (Cantor’s 
theorem). The cardinality of the power set of N is called the cardinality of 
the continuum. It can be shown that the set of the real numbers R has the 
cardinality of the continuum. An equivalent terminology is: N is countable, 
R is uncountable. 
25
Non-calculable functions
 • It can be shown that the set of non-calculable functions is 
uncountable. Since the set of calculable functions is countable, the 
set of non-calculable functions is larger than the set of calculable 
functions. 
• Therefore, the set of non-computable functions is larger than the set 
of computable functions.
 • Given an arbitrary function, there is some trifling chance that it is a 
computable function.
 26###