Knowledge and Data - Summary Bachelor Artificial Intelligence Year 2
Module 1: Formal foundations of knowledge graphs
Data, knowledge and information
● Data (raw data) = individual facts that are out of context, have no meaning and are difficult to
understand
● Information = set of data in context with relevance to one or more people at a point in time or for
a period of time
● Knowledge = the factor condition of knowing something with familiarity gained through
experience or association
● Knowledge is information that has been retained with an understanding of the significance of that
information
Knowledge can either be tacit or explicit:
● Tacit (or implicit) knowledge = knowledge that a person retains in their mind
○ intangible, invisible, basic, hidden “underwater” (80%)
● Explicit (or formal) knowledge = knowledge that has been formalized, codified and
stored
○ Tangible, visible, public, can be accessed by third persons, once shared it belongs
to everyone, can be seen “above the water” (20%)
Formal knowledge is necessary to efficiently interpret and reuse data
According to Forbes, data scientists usually spent more time on preparing, linking and cleaning data than
on building the datasets in the first place.
1
,Knowledge and Data - Summary Bachelor Artificial Intelligence Year 2
Knowledge Graphs
● In many cases, the knowledge the data is about should be made more explicit
● More knowledge/semantics:
○ Domain and range
○ Subclasses
Formally representing knowledge graphs
● A language is needed to write down the knowledge graph unambiguously
● Correct “statements” need to be defined precisely in order to interpret them
● What these “statements” are supposed to mean need to be defined
● What can be derived from the graph needs to be defined
→propositional logic
Propositional logic as a formal system
● A declarative sentence or proposition = statement that is true or false
● Three elements:
○ Syntax
○ Semantics
○ Calculus
● Symbols of propositional logic
2
,Knowledge and Data - Summary Bachelor Artificial Intelligence Year 2
● Standard syntax
● Different syntaxes
○ There might be different ways to write down the same formulas
○ Examples:
■ Different symbols for the operators
● (((A | B) & C) -> (-D))
■ Leave out parentheses
● (A | B) & C -> -D
■ Different order
● Prefix
● Prefix syntax = syntax which starts with the operators and then the arguments
○ Inductive definition: a formula is a list starting with the operator and then containing all
the formulas to which the operator applies.
● Truth Value Semantics
○ Formulas of propositional logic are used to express declarative statements which are
either true (T) or false (F)
○ The truth value of a composite formula like Φ ∧ Ψ determined by the truth values of its
components Φ and Ψ.
○ For each connective, this functional behavior is expressed by its truth table.
● For a formula with n variables, 2n lines are in the truth table
● Formulas Φ and Ψ are semantically equivalent, notation Φ ≡ Ψ, if they have identical
columns in their truth tables
● A formula is a tautology if its column in a truth table has T on every line
● A formula is a contradiction if its column in a truth table has F on every line
● Semantic entailment: always if the premises Φ1…., Φn are true, then the conclusion Ψ is
true as well.
○ “Always”: in every line of the corresponding truth table
3
, Knowledge and Data - Summary Bachelor Artificial Intelligence Year 2
Formal systems
● What is a logic?
○ A formal language
○ Syntax: which expressions are legal (well-formed)?
○ Semantics: what legal expressions mean, the meaning of each sentence w.r.t.
interpretation
○ Calculus: how to determine meaning for legal expressions
● A logic of arithmetic: syntax
○ Unambiguous definitions of what sentences are well-formed
■ 2 terms with a comparator between them (=, <, > <=, >=)
■ A term is either a Natural Number, a variable or a complex term
■ A complex term is an operator +, -, *, / applied to two terms
■ Infix notation with parentheses “(term1 operator term2)”
● E.g., X + 2 >= Y and NOT X2 + Y
○ No ambiguity
■ 7+3+5 = 2x - 3 is not well-formed unless there is agreement (convention) that
means (7+3) + 5 = (2*X) - 3
● A logic of arithmetic: semantics
○ Truth is defined in terms of assignment for variables
○ Let V be the set of variables, then Iv: V → N is an assignment, a function that assigns
natural numbers to each variable
○ ! For specific values we say that Iv is a model of a formula F if Iv(F) is true.
○ ! A formula F entails another formula G (F |= G) if for all variable assignments Iv(F) is
true implies that Iv(G) is true. In other words, F entails G if G is true in all models of F.
● A logic of concept hierarchies: syntax
○ A concept is “an abstraction or generalization from experience or the result of a
transformation of existing ideas”.
○ Syntax
■ Let C be a fine set of concept names.
■ If c1 and c2 in C, then (c1 subclassOfc2) is an axiom in LCH
■ An LCH knowledge base is a set of LCH axioms.
● Examples: (Lions subclassOf Mammals) and (Capital subclassOf City) If
(Lions subclassOf Mammals) and (Mammals subclassOf Animals), we
want to derive that (Lions subclassOf Animals)
● A logic of concept hierarchies: semantics
○ Let U be a universe, a set of arbitrary objects. Ic: C → P(U) is a function that assigns
subsets of the domain to concept names.
○ An axiom (c1 subclassOfc2) is true w.r.t. an assignment if Ic (c1) ⊆Ic(c2). Ic is then called
a model for the axiom.
○ An assignment is a model of a knowledge base if it is a model of all its axioms
○ An axiom (c1 subclassOfc2) is entailed by a knowledge base KB if it is true in all models
of KB.
4
Module 1: Formal foundations of knowledge graphs
Data, knowledge and information
● Data (raw data) = individual facts that are out of context, have no meaning and are difficult to
understand
● Information = set of data in context with relevance to one or more people at a point in time or for
a period of time
● Knowledge = the factor condition of knowing something with familiarity gained through
experience or association
● Knowledge is information that has been retained with an understanding of the significance of that
information
Knowledge can either be tacit or explicit:
● Tacit (or implicit) knowledge = knowledge that a person retains in their mind
○ intangible, invisible, basic, hidden “underwater” (80%)
● Explicit (or formal) knowledge = knowledge that has been formalized, codified and
stored
○ Tangible, visible, public, can be accessed by third persons, once shared it belongs
to everyone, can be seen “above the water” (20%)
Formal knowledge is necessary to efficiently interpret and reuse data
According to Forbes, data scientists usually spent more time on preparing, linking and cleaning data than
on building the datasets in the first place.
1
,Knowledge and Data - Summary Bachelor Artificial Intelligence Year 2
Knowledge Graphs
● In many cases, the knowledge the data is about should be made more explicit
● More knowledge/semantics:
○ Domain and range
○ Subclasses
Formally representing knowledge graphs
● A language is needed to write down the knowledge graph unambiguously
● Correct “statements” need to be defined precisely in order to interpret them
● What these “statements” are supposed to mean need to be defined
● What can be derived from the graph needs to be defined
→propositional logic
Propositional logic as a formal system
● A declarative sentence or proposition = statement that is true or false
● Three elements:
○ Syntax
○ Semantics
○ Calculus
● Symbols of propositional logic
2
,Knowledge and Data - Summary Bachelor Artificial Intelligence Year 2
● Standard syntax
● Different syntaxes
○ There might be different ways to write down the same formulas
○ Examples:
■ Different symbols for the operators
● (((A | B) & C) -> (-D))
■ Leave out parentheses
● (A | B) & C -> -D
■ Different order
● Prefix
● Prefix syntax = syntax which starts with the operators and then the arguments
○ Inductive definition: a formula is a list starting with the operator and then containing all
the formulas to which the operator applies.
● Truth Value Semantics
○ Formulas of propositional logic are used to express declarative statements which are
either true (T) or false (F)
○ The truth value of a composite formula like Φ ∧ Ψ determined by the truth values of its
components Φ and Ψ.
○ For each connective, this functional behavior is expressed by its truth table.
● For a formula with n variables, 2n lines are in the truth table
● Formulas Φ and Ψ are semantically equivalent, notation Φ ≡ Ψ, if they have identical
columns in their truth tables
● A formula is a tautology if its column in a truth table has T on every line
● A formula is a contradiction if its column in a truth table has F on every line
● Semantic entailment: always if the premises Φ1…., Φn are true, then the conclusion Ψ is
true as well.
○ “Always”: in every line of the corresponding truth table
3
, Knowledge and Data - Summary Bachelor Artificial Intelligence Year 2
Formal systems
● What is a logic?
○ A formal language
○ Syntax: which expressions are legal (well-formed)?
○ Semantics: what legal expressions mean, the meaning of each sentence w.r.t.
interpretation
○ Calculus: how to determine meaning for legal expressions
● A logic of arithmetic: syntax
○ Unambiguous definitions of what sentences are well-formed
■ 2 terms with a comparator between them (=, <, > <=, >=)
■ A term is either a Natural Number, a variable or a complex term
■ A complex term is an operator +, -, *, / applied to two terms
■ Infix notation with parentheses “(term1 operator term2)”
● E.g., X + 2 >= Y and NOT X2 + Y
○ No ambiguity
■ 7+3+5 = 2x - 3 is not well-formed unless there is agreement (convention) that
means (7+3) + 5 = (2*X) - 3
● A logic of arithmetic: semantics
○ Truth is defined in terms of assignment for variables
○ Let V be the set of variables, then Iv: V → N is an assignment, a function that assigns
natural numbers to each variable
○ ! For specific values we say that Iv is a model of a formula F if Iv(F) is true.
○ ! A formula F entails another formula G (F |= G) if for all variable assignments Iv(F) is
true implies that Iv(G) is true. In other words, F entails G if G is true in all models of F.
● A logic of concept hierarchies: syntax
○ A concept is “an abstraction or generalization from experience or the result of a
transformation of existing ideas”.
○ Syntax
■ Let C be a fine set of concept names.
■ If c1 and c2 in C, then (c1 subclassOfc2) is an axiom in LCH
■ An LCH knowledge base is a set of LCH axioms.
● Examples: (Lions subclassOf Mammals) and (Capital subclassOf City) If
(Lions subclassOf Mammals) and (Mammals subclassOf Animals), we
want to derive that (Lions subclassOf Animals)
● A logic of concept hierarchies: semantics
○ Let U be a universe, a set of arbitrary objects. Ic: C → P(U) is a function that assigns
subsets of the domain to concept names.
○ An axiom (c1 subclassOfc2) is true w.r.t. an assignment if Ic (c1) ⊆Ic(c2). Ic is then called
a model for the axiom.
○ An assignment is a model of a knowledge base if it is a model of all its axioms
○ An axiom (c1 subclassOfc2) is entailed by a knowledge base KB if it is true in all models
of KB.
4
