Chapter 1: Knowledge Graphs

• Data and knowledge are often available in tabular form.

• Information is not only in the rows and columns but also in the column headers and table names.

• Knowledge graphs allow for a more explicit representation of information.

• In a knowledge graph, things are represented as nodes, and attributes or relations are represented as edges.

• The explicit representation in knowledge graphs allows for a better understanding of the data and hidden knowledge.

• Labels in knowledge graphs can represent additional information about the nodes and edges.

• Knowledge graphs provide a way to make implicit information explicit and facilitate inferencing.

Chapter 2.1: Introduction

• Knowledge graphs allow for the representation of information in a more explicit and structured way.

• However, knowledge graphs represented as circles and arrows still require interpretation by machines.

• A more formal and machine-readable representation is needed.

Chapter 2.2: Formal Systems and Logics

• Formal systems, also known as logics, provide a structured way of describing things.

• A logic consists of three elements: syntax, semantics, and calculus.

• Syntax defines the rules for constructing valid sentences (legal expression) in the logic.

• Semantics defines the meaning of the sentences.

• Calculus determines how new information can be derived from the sentences.

Chapter 2.3: Arithmetic Logic

• It involves statements such as "x + 2 >= y".

• Arithmetic logic has a defined syntax, semantics, and calculus.

Conclusion Chapter 2

• Understanding formal systems and logics is essential for designing and working with knowledge graphs.

• RDF is an example of a formalism that can be analyzed and improved upon.

• The study of formal systems helps in developing a better understanding of their properties and potential improvements.

Chapter 3: One Sentence

Syntax

• Syntax determines which statements are well formed

• Well formed sentence consists of 2 terms with a comparator between them

• Terms can be natural numbers, order variables, or complex terms

• Complex terms are operators applied to 2 terms

Valid Sentences

• Example: x plus 2 is greater than or equal to y

  • x plus 2 is a complex term

  • y is a term (variable)

  • Fits the description of a well formed sentence

Invalid Sentences

• Example: x plus x times 2 plus y

  • No comparator, does not fit the form of a well formed sentence

• Example: 5 plus 3 is nothing

  • Does not fit the form of a well formed sentence

• Example: 5 minus equals 4

  • Does not fit the form of a well formed sentence

Ambiguity

• The syntax described is unambiguous

• Example: 7 plus 3 plus 5 equals 2 x minus 3 is not well formed

• A new syntax could be developed to allow such expressions

Semantics

• Semantics is defined by mapping symbols to an external world

• In arithmetic, truth is defined based on assignments for variables

• Assignments are functions that assign natural numbers to variables

• Sentences can be checked for truth with respect to a specific assignment

Chapter 4: Introduction to Interpretation and Models

• Interpretation and assignment as models for sentences and formulas

  • Definition: An interpretation or assignment is a model for a formula if the interpretation of that formula is true

  • Example: The assignments x goes to 7 and y goes to 1 is a model for a certain sentence

Chapter 2: Different Types of Sentences

• Some sentences can be true in some worlds and not true in other worlds

  • Example: The sentence x plus 2 is smaller than x plus 3 can be true in some worlds and not true in others

• Some sentences are always true or always false

  • Example: The sentence x plus 2 is smaller than x plus 3 is always true

  • Example: The sentence 3 is larger than 5 is always false

Chapter 3: Entailments

• Entailment is deriving one formula from a set of other formulas

• Definition of entailment: A formula f entails another formula g if, for all variable assignments that make f true, g is also true

• Example: Deriving the formula x is smaller than 10 from the formula x plus y is smaller than 6

Chapter 4: Models and Entailment

• Rephrasing the definition of entailment using the concept of models

• Definition: f entails g if g is true in all models of f, where models are all assignments that make f true

• Example: Showing that x plus y smaller than 6 entails x is smaller than 10 using models

Chapter 5: Arithmetic as Logic

• Arithmetic can be seen as a logic with syntax and semantics

• Syntax refers to the structure and rules of formulas

• Semantics refers to the meaning and interpretation of formulas

Chapter 6: Interactive Exercise

• Using Mentimeter to engage the audience in a question and answer session

Chapter 3: Set Of Things

Logic with Syntax and Semantics

• There are 3 assignments given for the function x + 2 < y

• The assignments are:

  • x = 5, y = 7

  • x = 2, y = 7

  • x = 7, y = 2

• The goal is to determine which assignment is a model for the function

Concepts and Syntax

• Concepts are abstractions or generalizations from experience

• Concepts can be represented by strings

• A set of concept names is defined as C

• Axioms are legal sentences in the logic

• Axioms are of the form "c1 subclass of c2"

• Only subclass statements are allowed in this logic

• The logic is called LCH (Logic of Concept Hierarchies)

Knowledge Base and Inference

• A set of axioms is called a knowledge base

• A simple example knowledge base is given: "Lion subclass of mammals" and "Mammals subclass of animals"

• The goal is to derive the inference "Lion subclass of animals"

Semantics and Models

• Semantics is defined by mapping sentences to an external model

• Set theory is used as the external model for this logic

• A universe is defined as a set of arbitrary objects

• Assignments map concepts to subsets of the universe

• An axiom is true with respect to an assignment if the interpretation of the concept on the left is a subset of the interpretation of the concept on the right

• An assignment is a model for an axiom if the axiom is true with respect to the assignment

• An axiom is entailed by a knowledge base if it is true in all models of the knowledge base

Example Knowledge Base

• A new knowledge base is given with three axioms:

  • Lions subclass of mammals

  • Mammals subclass of animals

  • Lions subclass of animals

• Two assignment functions are defined:

  • Assignment 1: Lions are the first two objects, mammals are the first three objects, and animals are the first four objects

  • Assignment 2: Lions are objects a and b, mammals are objects a and c, and animals are objects a, b, and c

• The question is whether Assignment 1 is a model for the knowledge base

Chapter 4: Possible Interpretation Assignment

• Approach to determining if an assignment is a model for a knowledge base

  • Intuitive way

  • More structured way

• Definition of an assignment being a model for a knowledge base

  • An assignment is a model for a knowledge base if it is a model for all its axioms

• Definition of an assignment being a model for an axiom

  • An axiom is true with respect to an assignment if the interpretation of the left side is a subset of the interpretation of the right side

• Testing if the first assignment is a model for the knowledge base

  • Checking if the assignment is a model for each axiom in the knowledge base

  • Checking the first axiom: "lions are a subclass of animals"

    • Checking if the interpretation of "lions" (12) is a subset of the interpretation of "mammals" (123)

    • Result: 1212 is a subset of 123, so the first axiom is true with respect to the assignment

  • Checking the second axiom: "mammals are a subclass of animals"

    • Checking if the interpretation of "mammals" (123) is a subset of the interpretation of "animals" (1234)

    • Result: 123 is a subset of 1234, so the second axiom is true with respect to the assignment

  • Checking the third axiom: "lions are a subclass of animals"

    • Checking if the interpretation of "lions" (12) is a subset of the interpretation of "animals" (1234)

    • Result: 12 is a subset of 1234, so the third axiom is true with respect to the assignment

  • Conclusion: The first assignment is a model for the knowledge base

• Testing if the second assignment is a model for the knowledge base

  • Checking if the assignment is a model for each axiom in the knowledge base

  • Checking the first axiom: "lions are a subclass of mammals"

    • Checking if the interpretation of "lions" (AB) is a subset of the interpretation of "mammals" (AC)

    • Result: AB is not a subset of AC, so the first axiom is not true with respect to the assignment

  • Conclusion: The second assignment is not a model for the knowledge base

• Importance of finding a model that holds regardless of the specific objects used

• Example of a knowledge base with two axioms and an assignment

  • Axioms: "a is a subclass of b" and "b is a subclass of c"

  • Assignment: Universe consists of a, b, c, small a, small b, small c

    • Interpretation of large a is small a

    • Interpretation of b is empty set

    • Interpretation of c is small c

  • Question: Is this assignment a model for the knowledge base?

• Determining if the assignment is a model for the knowledge base

  • Checking if the interpretation of "b" is empty

    • Result: The interpretation of "b" is empty, so the assignment is not a model for the knowledge base

  • Conclusion: The assignment is not a model for the knowledge base

Chapter 5: Model Checking

• The goal is to check if a given interpretation is a model for a knowledge base

• Two models need to be checked: the first one and the second one

• For the first model, we need to check if the interpretation of Large a is a subset of the interpretation of Large b

  • The interpretation of Large a is a

  • The interpretation of Large b is empty

  • Is a a subset of b? No

• The second model is true because the empty set is a subset of sets that contain c

• The interpretation is not the middle model of the first axiom, so it's not a model for the entire knowledge space

Chapter 5.1: Axioms, Assignments, Models, and Entailments

• There is no correct axiom

• The goal is not to determine which axioms are correct given the interpretation

• There can be an infinite number of axioms that are true in the assignment

Chapter 5.2: Propositional Logic

• Propositional logic is a formal system for declarative sentences that can be true or false

• It allows reasoning about various scenarios

• Propositions can be abstracted to a set of declarative statements

• The form of the argument matters more than the specific content

• Proposition logic can be used to reason about different scenarios with the same structure

Chapter 6: Right Hand Side

• The validity of arguments is determined by their logical form, not their content

• Propositional logic is a formal language that allows for reasoning

• Propositional logic has syntax and semantics

• Syntax includes propositional variables and connectives (and, or, either or, not, implies, if and only if)

• Valid sentences in propositional logic can be defined using an inductive definition

  • Legal sentences include declarative sentences (p, q, r) and formulas built from proposition variables

  • Formulas can be negated (not p) and negated multiple times (not not p)

  • Formulas can be combined using conjunction (phi and psi) and disjunction (phi or psi)

• Different syntaxes or serializations can be used to write down legal sentences

• Prefix notation and infix notation are two common ways to write down legal sentences

  • Prefix notation is easier for machines to parse, while infix notation is easier for humans to read

  • There is a clear translation between the two notations

• The lecture will continue after a break

Chapter 1: Introduction

• Semantics in propositional logic

• Determining truth using truth tables

• Similarity to mappings in arithmetic

Chapter 2: Truth Tables

• Truth tables used to determine semantics

• Truth values of formulas in propositional logic

• Two values: 1 or 0, true or false

• Determining truth value of composite formulas by analyzing components

Chapter 3: Truth Table for "Not"

• Truth table for "not" operator

• Two cases: true or false

• "Not phi" is false if phi is true, true if phi is false

Chapter 4: Truth Table for "Conjunction"

• Truth table for "conjunction" operator

• Four cases: phi and psi can be true or false

• "Phi and psi" is true only if both phi and psi are true

Chapter 5: Finite Number of Worlds

• Finite number of worlds in propositional logic

• Only true and false values

• Enumerating all possible assignments

Chapter 6: Evaluation and Assignments

• Assignments in truth tables

• Calculating truth values for complex formulas

• Formula with n variables has 2^n lines in truth table

• Calculating truth values for each complex formula in a valuation

Chapter 6: Thing On Right

• Two formulas are semantically equivalent if they have identical notions in the truth table.

  • Example: p implies q and not p or q are semantically equivalent.

  • In every possible world, they have the same truth value.

• A tautology is a formula that is always true regardless of the values of p and q.

  • Example: p or not q is a tautology.

• A contradiction is a formula that can never be true.

  • Example: p and not p is a contradiction.

• Checking semantic entailment involves finding the lines in the truth table where the premises are true and checking if psi is also true in those lines.

Chapter 7: Counterexamples and Invalid Reasoning

• If even one valuation makes all premises true and the consequence false, the conclusion is not valid

• Counterexamples invalidate the conclusion

Chapter 8: The Right Side

Triples and Knowledge Graphs

• Triples are the core concept of building knowledge graphs

• Triples consist of a thing, a relation, and another thing

• Triples can also be called triplets or triples, but the preferred term is triples

• Triples provide a machine-readable way of representing relationships between things

• Triples have a formal syntax used in the web of data

Simple Grounded Graphs

• Simple knowledge graphs are the first step towards RDF

• Vocabulary (v) consists of things we want to talk about

• Predicates are relations between elements in the vocabulary

• Triples connect two items from the vocabulary with predicates

• Two ways to define triples: product of p times p or inductive definition

• Valid sentences in a knowledge graph follow the defined axioms

Semantics of Knowledge Graphs

• Semantics of knowledge graphs are defined by grounding the assignments to graph objects

• Semantics are defined with respect to a graph of true things in the world

• Assign values to triples based on their intended meaning

• Interpretation assigns elements of the domain to words in the vocabulary

Interpretation Function

• Interpretation function assigns an element of the domain to each word in the vocabulary

• Similar to assigning lions and mammals in previous examples

Main Ideas:

Introduction to Axioms and Interpretations

• Axioms are triples that represent relations between concepts in a knowledge base.

• Interpretations map concepts to elements in the domain.

• A function p checks if a relation exists between two concepts.

• A model is an interpretation that satisfies the relation between concepts.

Models and Knowledge Bases

• An interpretation is a model of a knowledge base if it satisfies all the triples.

• A triple is entailed by a knowledge base if it is true in all models.

Example Knowledge Base and Interpretations

• A knowledge base with two triples: Netherlands isNamed Netherlands, and Netherlands hasCapital Amsterdam.

• Interpretations map concepts to elements in the domain.

• Different interpretations can have different sets of interpretations for the relation p.

Determining Models of a Knowledge Base

• To determine if an interpretation is a model of a knowledge base, check if it satisfies all the axioms.

• Check if the relation holds between the concepts in each axiom.

Chapter 9: Simple Knowledge Graphs

• Simple knowledge graphs entail a set of triples

• The subgraph of the knowledge graph determines what can be done

• Can calculate true things and easily extend the knowledge graph