English

not defined

no text concepts found

Knowledge Representation: Logic Wojciech Jaworski Institute of Informatics University of Warsaw Wojciech Jaworski (MIM UW) Logic 1 / 36 What is Knowledge Representation? Expressing knowledge of certain domain in an explicit, organized and computer-readable manner. Knowledge Representation is making use of logic and ontology to construct computable models for given domains. I I I Logic provides the formal structure and rules of inference Ontology defines the kinds of things Computable models (e.g. relational database model) facilitate the implementation of logic and ontology in computers. Application examples I I I I database designing object methods natural language processing knowledge engineering Wojciech Jaworski (MIM UW) Logic 2 / 36 Table of contents 1 Knowledge Representation in logic 2 Varieties of Logic 3 Names, Types, and Measures Wojciech Jaworski (MIM UW) Logic 3 / 36 Knowledge Representation in logic Logic gives processable form to all the information that can be precisely expressed in any other language. Logic allows to express all the information that can be stored in computer memory. If some knowledge is not logic-conveyable it cannot be processed by computers no matter the notation. Wojciech Jaworski (MIM UW) Logic 4 / 36 Propositional Logic Every car has 4 wheels. Representation in propositional logic: p the simplest representation form no details about the cars, the wheels, the number 4 and their interrelationships The loss of details may be an advantage in some applications. Wojciech Jaworski (MIM UW) Logic 5 / 36 First Order Logic Let us consider the following syllogism (ancient inference rule) Every car has 4 wheels. Some Corvettes are cars. Therefore, some corvettes have 4 wheels. We can express it in logic in the following way (∀x)(car(x) ⇒ fourWheeler(x)) (∃x)(Corvette(x) ∧ car(x)) (∃x)(Corvette(x) ∧ fourWheeler(x)) Notice that sentences of the type Every A is B are translated to ∀x(A(x) ⇒ B(x)) and sentences of the type Some A are B are translated to ∃x(A(x) ∧ B(x)) Wojciech Jaworski (MIM UW) Logic 6 / 36 Choice of Predicates The predicate „fourWheeler" doesn’t convey the number 4 nor its relation to wheels. We can replace it with a two-place predicate: numberOfWheeles(x, n), which means „the number of wheels of x is nór „x has n wheels". The sentence Every car has 4 wheels has the logical form (∀x)(car(x) ⇒ numberOfWheeles(x, 4)) which may be read as For every x, if x is a car, the number of wheels of x is 4 Wojciech Jaworski (MIM UW) Logic 7 / 36 Choice of Predicates In the predicate numberOfWheeles(x, n) x refers to cars, n refers to numbers but no variable refers to wheels. The names of the predicates are but meaningless labels for the computer system. If the notion of a wheel is important for some application, a more detailed selection of predicates is necessary. Wojciech Jaworski (MIM UW) Logic 8 / 36 Choice of Predicates Let us consider the predicates: car(x) wheel(x) part(x, y ) set(s) count(s, n) member(x, s) x is a car x is a wheel y is a part of x s is a set The count of elements in s is n x is a member of the set s The car formula then becomes: (∀x)(car(x) ⇒ (∃s)(set(s) ∧ count(s, 4) ∧(∀w)(member(w, s) ⇒ (wheel(w) ∧ part(x, w))))) the formula may be read: For every x, if x is a car, then there exists s, where s is a set of count 4 and for every w, if w is a member of s, then w is a wheel and w is a part of x. Wojciech Jaworski (MIM UW) Logic 9 / 36 Definitions The formula (∃s)(set(s) ∧ count(s, 4) ∧(∀w)(member(w, s) ⇒ (wheel(w) ∧ part(x, w))))) describes the property of having 4 wheels. We can use it to define the predicate fourWheeler(x): fourWheeler(x) = (∃s)(set(s) ∧ count(s, 4) ∧(∀w)(member(w, s) ⇒ (wheel(w) ∧ part(x, w))))) A definition is a notational short-cut and it corresponds to a subroutine or a macro in programming languages. x — the free variable in the defining formula — is called the formal parameter. While expanding a definition we use α-conversion: renaming local variables to unique ones. Wojciech Jaworski (MIM UW) Logic 10 / 36 Logic and Ontology Even simple sentences of a natural language convey much hidden information. Giving all the details leads to difficulties in finding the key information while reading. The overflow of the details is partially caused by making all the variables explicit. the level of detail depends on the choice of predicates, i.e. the choice of an ontology. The predicates in an ontology may be divided in two classes: I I the domain-dependent predicates: car, wheel(x) the domain-independent predicates: part(x, y ), set(s), count(s, n), member(x, s) Wojciech Jaworski (MIM UW) Logic 11 / 36 Special languages Subsets of logic with their own notation and built-in ontology. Examples: musical notation, timetables, maps, plans, schemes. Shorter and more readable than logic (and natural language). Logic is an ontologically neutral notation that can be adapted to any subject by adding one or more domain-dependent predicates. Special languages may be translated to logical formulas in order to automatically process the content they express. Wojciech Jaworski (MIM UW) Logic 12 / 36 Example: A map Wojciech Jaworski (MIM UW) Logic 13 / 36 Example: A map Streets may be represented as segments of straight lines and arcs. Streets intersect at cross-roads and make a graph. Street names are edge labels in the graph. There are also points such as restaurants, bus stops etc. A structural implementation of the map would be done by creating a graph of streets etc. Adding a new component to the map requires some modifications to be introduced to the data structure, so the code must be rewritten. The elements of the map could be associated with object classes divided into point-like, line-like and so on. Addition of a new component may be then achieved by adding a new subclass, but it can be impossible, for example for street names. We may as well express the content of the map using logic and add new components by introducing new predicates. Wojciech Jaworski (MIM UW) Logic 14 / 36 Existential-Conjunctive Logic Allows to convey facts about particular objects. Suffices as the representation for most of the special languages. Represents the information stored in both relational and object-oriented database systems. It cannot represent any generalizations, negations, implications, or alternatives. An example of generalization: The rule A bus stop must be located an a street.. Wojciech Jaworski (MIM UW) Logic 15 / 36 Table of contents 1 Knowledge Representation in logic 2 Varieties of Logic 3 Names, Types, and Measures Wojciech Jaworski (MIM UW) Logic 16 / 36 Varieties of Logic Logics can differ along the following dimensions Syntax: Influences readability, doesn’t change the expressive power Subset: Possible operators and combinations of operators, e.g. the logic ∃∧ or propositional calculus Proof theory: Restrictions on the permissible proofs (e.g. intuitionistic logic, linear logic), or extensions (e.g. non-monotonic logics); In that cases the semantics follows from the proof theory — opposite to FOL. Model theory: Modifications of the notion of truth, e.g. three-valued logic or fuzzy logic. Ontology: the set of predicates and axioms we take for basic and domain-independent, e.g. =, set theory, time theory Metalanguage: The language that is used to talk about another language (e.g. FOL, context-free grammar) Wojciech Jaworski (MIM UW) Logic 17 / 36 Typed Logic We label variables with types: (∀x : t)P(x) ≡ (∀x)(t(x) ⇒ P(x)) (∃x : t)P(x) ≡ (∃x)(t(x) ∧ P(x)) For example: Every car has 4 wheels. (∀x : car)fourWheeler(x) Some Corvettes are cars. (∃x : Corvette)car(x)) Therefore, some Corvettes have 4 wheels. (∃x : Corvette)fourWheeler(x) Wojciech Jaworski (MIM UW) Logic 18 / 36 Typed Logic We can also use special notation for domain-independent predicates. The sentence (∀x)(car(x) ⇒ (∃s)(set(s) ∧ count(s, 4) ∧(∀w)(member(w, s) ⇒ (wheel(w) ∧ part(x, w))))) can be written as (∀x : car)(∃s : set)([email protected] ∧(∀w ∈ s)(wheel(w) ∧ part(x, w))))) Wojciech Jaworski (MIM UW) Logic 19 / 36 Defining new functions and function closures Instead of fourWheeler(x) = = (∃s : set)([email protected] ∧ (∀w ∈ s)(wheel(w) ∧ part(x, w))) we can write fourWheeler = = (λx)((∃s : set)([email protected] ∧ (∀w ∈ s)(wheel(w) ∧ part(x, w)))) The notation (λx)Ψ(x) is a definition of a function closure, where x is the formal parameter and Ψ is the formula that defines the function. Tha application ((λx)Ψ(x))(a) generates the formula Ψ(a). λ will be used among others for defining the function closures. (∃x : fourWheeler) car(x) (∃x : (λx)((∃s : set)([email protected] ∧ (∀w ∈ s)(wheel(w) ∧ part(x, w)))))car(x) Wojciech Jaworski (MIM UW) Logic 20 / 36 Conceptual Graphs car : ∀ / Part / Wheel : {?}@4 Every car has 4 wheels. A notation for logic that eliminates variables The boxes are called concepts and circles are called conceptual relations. Inside the box is the concept description (a label or a definition) and a colon-separated description of reference which consists of either a label, a quantifier ∀ or a specification of quantity. The relations show how the denotations are associated. Wojciech Jaworski (MIM UW) Logic 21 / 36 Conceptual Graphs Semantics Every box is labeled with a unique natural number. A FOL formula is composed step-by-step from the labelled boxes in increasing order: I If you see Concept , append (∃xi : concept) to the formula. i I Concept : ∀ I Concept : {?}@n i translates to (∀xi : concept) i translates to (∃si : set)si @n ∧ (∀xi ∈ si )concept(xi ) where i is the label of the box. Process the circles in any order. For the relations of the form ... i / Relation / ... j generate ∧relation(xi , xj ) and append to the formula (omit „∧” at the first occurrence) Wojciech Jaworski (MIM UW) Logic 22 / 36 Semantic Ambiguity If we’re restricted to Existential-Conjuntive Logic, no order of predicates and quantifiers does matter, so the translation from a graph to a FOL formula is unambiguous. If ∀ occurs, the translation is ambiguous. For example Boy : ∀ / Like / Girl can be interpreted as (∀y : boy)(∃x : girl)like(y , x) or as (∃x : girl)(∀y : boy)like(y , x) The same phenomenon occurs in natural languages (Quantifier Scope Ambiguity). Wojciech Jaworski (MIM UW) Logic 23 / 36 Co-reference Every car ma 4 wheels. (∀x : car)fourWheeler(x) In the example above two concepts have the same referent. We can express it in a graph as: car : ∀ /= / fourWheeler Which corresponds to the formula: (∀x : car)(∃y : fourWheeler)x = y We can also use the shorthand notation: car : ∀ Wojciech Jaworski (MIM UW) fourWheeler Logic 24 / 36 Knowledge Interchange Format (KIF) Typed logic with Lisp-style syntax and restricted to ASCII symbols. Example (forall (?x car) (exists (?s set) (and (count ?s 4) (forall (?w in ?s) (and (wheel ?w) (part ?x ?w))) ))) Wojciech Jaworski (MIM UW) Logic 25 / 36 Modal Logics Logic with operators that express modality. ♦ϕ means that ϕ is possible. ϕ means that ϕ is necessary. Modal operators semantics can be summarized as follows: I I I I we have a set of possible worlds one of which is designated as the actual world; ϕ means that ϕ is true in the actual world; ♦ϕ means that there exists a world where ϕ is true; ϕ means that ϕ is true in every possible world. Different axiomatizations of modality differ in their expressive power. In database theory I I any statement that is stored in the database is assumed true in the actual world constraints are taken to bo necessary true. Wojciech Jaworski (MIM UW) Logic 26 / 36 Higher order logics first order logic allows for quantification over individuals. Second order logic allows for quantification over relations on individuals. Third order logic allows for quantification over relations on relations on individuals etc. ... For example, the axiom of induction for natural numbers: (∀P : Predicate)((P(0)∧(∀n ∈ N)(P(n) ⇒ P(n+1)) ⇒ (∀n ∈ N)P(n)) Higher order logics may be defined as FOL with an ontology for relations (eg. ZFC) Wojciech Jaworski (MIM UW) Logic 27 / 36 Metalanguage A language used to talk about a language. Example: Natural language when used to define first order logic. Let us consider the sentence: The sentence „It is true that John is tall” means the same as „John is tall” Quotation marks indicate the use of metalanguage, the word „true” as well. Thus, whole the utterance belongs to the metametalanguage and the slide that treats about it - to the metametametalanguage. We can introduce a special predicate into a logic to play the role of quotation marks and to connect a language with it’s metalanguage. Wojciech Jaworski (MIM UW) Logic 28 / 36 Table of contents 1 Knowledge Representation in logic 2 Varieties of Logic 3 Names, Types, and Measures Wojciech Jaworski (MIM UW) Logic 29 / 36 Proper names The expression Fluffy is a cat may be represented as cat(Fluffy) This representation is simple but fallible, as I I the name is ambiguous, eg. many cats bear the name „Fluffy”. one entity bears many names, eg. a cat called „Fluffy” by one family is known as „Mittens” to another. The solution are surrogates, i.e. unique identifiers for individuals. Surrogates for Polish citizens are their PESEL numbers. Proper names become plain attributes of objects: Name(„Fluffy”) ∧ (∃x : Cat)hasName(x, „Fluffy”) Wojciech Jaworski (MIM UW) Logic 30 / 36 Unique Name Assumption If two constants a and b have different names then a 6= b. KIF has two types of constants with uniqueness assumed for one of the types but not for the other. The constants in conceptual graphs are not assumed unique but symbols of the form #number are. They serve as surrogates. A node of the form Concept : Name is represented in logic as Concept(Name) and means that an object named „Name” is of type „Concept”. Name : „Fluffy” is the name „Fluffy”. Cat : #2563 is a cat under the record number #2563. Wojciech Jaworski (MIM UW) Logic 31 / 36 Skolemization If we introduce a surrogate for each individual of which we know then we can discard all ∃ and substitute for all the occurrences of bound variables their surrogates. The process is an existential instantiation, also called skolemization. Skolemization changes the meaning slightly, because an existentially quantified variable doesn’t uniquely indicate an object. I If we know that (∃x)cat(x) I then we can answer the question „What is the color of this cat’s fur?” by giving the color of any existing cat. But if our knowledge is that cat(#2563) then the question „What is the color of this cat’s fur?” must be answered with the color of the fur of the object indicated by #2563. Wojciech Jaworski (MIM UW) Logic 32 / 36 Common names The sentence Cats like fish can be represented in logic by (∀x : Cat)(∀y : Fish)like(x, y ) And A cat likes a fish can be represented as (∃x : Cat)(∃y : Fish)like(x, y ) The correlates of common names are types or predicates. Wojciech Jaworski (MIM UW) Logic 33 / 36 Type „Type” First order logic allows to quantify over individuals only. In order to quantify over types we introduce the type „Type”. The variables of type „Type” are types. „Type” is a type of second order. Cats are mammals. The cat is a mammal. (∀x : Cat)mammal(x) Cat is a specie. (∃x : Specie)(type(Cat) ∧ x = Cat) Fluffy is a cat. (∃x : Cat)x = Fluffy Fluffy the cat. cat(Fluffy) Wojciech Jaworski (MIM UW) Logic 34 / 36 Predicate „kind” We introduce the predicate „kind(x, t)” which means that object x is of type t. Using the predicate „kind” to give types is a process called reification: (∀x)(∀y )(kind(x, Cat) ∧ kind(y , Fish)) ⇒ like(x, y ) The names of types may have aliases just as the names of individuals can, so in practice surrogates are used for the names of types as well. Now we can define non-empty types by stating that Every non-empty type contains at least one individual: (∀t : Non-EmptyType)(∃x : Individual)kind(x, t) Wojciech Jaworski (MIM UW) Logic 35 / 36 Representing Measures Tom and Sue each earn a salary whose amount is $30.000. (∃x, y : Earn)(∃z, w : Salary) (Person(Tom) ∧ Person(Sue)∧ agnt(x, Tom) ∧ thme(x, z) ∧ amount(z, 30000$)∧ agnt(y , Sue) ∧ thme(y , w) ∧ amount(w, 30000$)) The formula doesn’t make it clear that the two salaries are distinct, as indicated by the word „each”. This can be conveyed in the following ways: I I append the condition z 6= w to the formula introduce surrogates for the salaries and establish the unique naming convention. Wojciech Jaworski (MIM UW) Logic 36 / 36