Transcript PPT - Department of Information Engineering and Computer Science

Logics for Data and Knowledge
Representation
Exercise 1: Model and Language
Outline
 Modeling
Logical Modeling
 What and How
 Exercises

 Languages
BNF
 Exercises

2
Modeling
(Abstraction)
Modeling
The
World
Representation
Model
Realization
Interpretation
Language
+
Theory
Monkey
Banana
Box
…
3
Logical Modeling
4
What?
 Domain
(D) = the chosen objects from the world
who can figure out the domain of the LDKR course?
 From
the person point of view:
students, professor;
 Italian, Chinese, …
 white-haired, black-eyed,…

 From
the material point of view:
courseware, homework, exam,…
 logics, modeling, …

 From
5
…?
What else?
 Language

(L) = a logical language
Syntax
1.
2.
L’s alphabet of symbols Σ contains at least one of the logical
symbols: ∧, ∨, ¬, →, ∀, ∃;
L has clear formation rules for formulas.
Formal Syntax: the set of “rules” saying how to construct
the expressions of the language from the alphabet of
symbols, (i.e., the syntax) is a grammar (i.e., formal).
 Semantics



6
Interpretation (I) = a mapping of L into D.
Formal Semantics: the relationship between syntactic
constructs and the elements of an universe of meanings
is a function in mathematical sense.
How?
 Model
(M) = the abstract (mathematical sense)
representation of the intended truths via
interpretation I of language L. M is called Lmodel of D.
M
|=A
reads?
 satisfies, yields, holds, is true.

 Theory
(T, also L-Theory) = set of facts of L.
A fact defines a piece of knowledge (about D),
something true in the model.
 A finite theory T is called a knowledge base (KB).

7
Modeling Exercises
 Select
from the following domain to model (5
minutes preparation)
Classroom
Student, Master & Doctor, Professor, Assistant,…
2. Family
Parent, Grandparent, Male, Female, Sibling,…
3. Friend
Close, Hiking, Chess, Forum, …
1.
8
Possible Solutions 1
 Classroom
PhD
Student
Master
9
Professor
Person
Possible Solutions 2
 Family
Grandparent
Male
Parent
Female
Sibling
Brother
10
Sister
Possible Solutions 3
 Friend
Hiking
Chess
Friend
Close
Forum
11
A Database
 Let’s
look at this sheet in a DB:
ID
Name
Nationality
Hair Color
Affiliation
1
Fausto
Italian
White
Professor
2
Enzo
Italian
Black
PhD
3
Rui
Chinese
Black
T.A.
4
…
5
…
…
…
Italian
Black
Hair
LDKR
Master
 What’s
12
it like?
Closed world vs. Open world
 DB
follows CWA, which assumes negative when no
record found.

Closed word assumption (CWA) is the presumption
that what is not currently known to be true, is false.
 In
contrast, ClassL assumes OWA, which allows
‘new’ knowledge emerges.
Open world assumption (OWA) is the assumption that
the truth-value of a statement is independent of whether
or not it is known by any single observer or agent to be
true.
 NOTE: In general no single agent or observer has
complete knowledge, and therefore cannot make the
closed world assumption.

13
Example
 Recall
the DB table in previous slide:
 A theory
ID
Name
Nationality
Hair Color
Affiliation
1
Fausto
Italian
White
Professor
2
Enzo
Italian
Black
PhD
3
Rui
Chinese
Black
T.A.
4
…
5
…
…
…
of this world in ClassL:
T={}, A={Italian(Fausto), Italian(Enzo), Chinese(Rui),
White-Hair(Fausto), Black-Hair(Enzo), BlackHair(Rui), Professor(Fausto), PhD(Enzo), TA(Rui),
…}
14
Outline
 Modeling
Logical Modeling
 What and How
 Exercises

 Languages
BNF
 Exercises

15
Backus–Naur Form (BNF)
 In
computer science, Backus–Naur Form (BNF) is a
syntax used to express context-free grammars: that
is, a formal way to describe formal languages.
Optional items enclosed in square brackets [].
 Items repeating 0 or more times are enclosed in curly
brackets or suffixed with an asterisk. {} or *
 Items repeating 1 or more times are followed by a '+'
 Terminals may appear in bold and NonTerminals in plain
text rather than using italics and angle brackets <>.
 Alternative choices in a production are separated by the
‘|’ symbol.
 Where items need to be grouped they are enclosed in
simple parentheses ().

16
Example of BNF
 Who
 An
1.
2.
3.
4.
5.
6.
17
can give examples of the above syntaxes?
example of mathematical expression
<expression>::=<value> [<operator> <expression>]
<value >
::= [<sign>] <unsigned> [ .
<unsigned>]
<unsigned> ::=<digit> {<digit>}*
<digit> ::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<sign> ::=+ | <operator> ::=+ | - | * | /
Exercises of BNF
 Is
1.
2.
3.
4.
the following a well-formed formula of expression?
00123
199+299
+20*200
345/(123+456-789)
 Recall
the BNF of PL, and differentiate WFFs from
others below.
1.
2.
3.
4.
5.
18
A⊔B⊒A
A⊓B⊑B
A∧¬B→A
A∧B⊨A∨B
¬A∨B⊢A→B
Something challenging
 Can
we build the BNF of ER diagram?
 What
19
about the BNF of natural language of English?
Recall: ER Diagram
 In
software engineering, an Entity-Relationship
Model (ERM) is an abstract and conceptual
representation of data.
 The basic components of ER in Lecture 2:
Entity
Monkey
 Relation
 Cardinality of Relation
 Cardinality of Attribute
 Attribute
 Primary Key

20
0..1
Climb
Banana
ID
0..n
Box
Height
BNF of ER Diagram
 Build
the Backus–Naur Form (BNF) of ER diagram
system.
<Entity>::=
<Relation>::=
<Attribute>::=
Entity
Relation
Attribute
<Unsigned>”.. “ n | m
<Connector>::=
<Diagram>::={<Entity>}|
<Entity>+[<connector ><Relation><connector>]<Entity>+|
Entity+[<connector>< Attribute>]
21
BNF of Yahoo Directories
 The
Yahoo! Directory is an online guide to the World
Wide Web. It is a catalog of sites created by a staff
of editors who visit and evaluate web sites, and then
organize them into subject-based categories and
sub-categories.
 Yahoo! editors distinguish between a number of
factors when organizing web sites, including
commercial vs. non-commercial, regional vs. global,
and so forth. All of the site listings in the Directory
are contained in an appropriate place within the 14
main categories seen on the front page of the Yahoo!
Directory.
22
So take a look!
23
Preliminaries: Open/Close Word Class
 In
linguistics, an open class (or open word class) is a
word class that accepts the addition of new items,
through such processes as compounding, derivation,
coining, borrowing, etc. Typical open word classes
are nouns, verbs and adjectives.
 A closed class (or closed word class) is a word class
to which no new items can normally be added, and
that usually contains a relatively small number of
items. Typical closed classes found in many
languages are adpositions (prepositions and
postpositions), determiners, conjunctions, and
pronouns.
24
Parts of Speech
Open class
WORD CLASS
EXAMPLE
JJ//Adjective
blue green soft
NN//Noun, singular or mass
apple sugar
NNS//Noun, plural
apples
NNP//Proper noun, singular
Rui
RB//Adverb
slowly
VB//Verb, base form
go
VBD//Verb, past tense
went
VBZ//Verb, 3rd person singular present
goes
25
Parts of Speech (2)
Closed class
WORD CLASS
EXAMPLE
CC//Coordinating conjunction
and or
CD//Cardinal number
DT//Determiner
the an a
IN//Preposition or subordinating conjunction
in for but
POS//Possessive ending
TO//to
26
BNF for Yahoo Directory
(1) ForwardPhrase::= [VB] [IN] DisPhrase {Conn }
DisPhrase
(2) DisPhrase::= Phrase [“(”ProperDis | NounDis“)”]
[“(”Period“)”][“:” Phrase]
(3) Phrase::=[DT] Adjectives [Nouns] | [Proper]
Nouns
(4) Adjectives::= Adjective|CD {[CC] Adjective}
(5) Nouns::= Noun {Noun}
(6) Conn::= ConjunctionConn | PrepositionConn
(7) Noun::= NN [POS] | NNS [POS]
27
BNF for Yahoo Directory (2)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
28
Adjective::= JJ
ConjunctionConn::= CC | “,”
PrepositionConn::= IN | TO
Proper::= NNP {NNP|POS}
NounDis::= Period|Nouns|Adjectives [Nouns]
ProperDis::= ProperSeq [CC ProperSeq]
Period::= [NN] CD [“-”] [CD] [NN]
ProperSeq::= Proper [“,” Proper]
Example: Provinces and Districts
ForwardPhrase
DisPhrase
Phrase
29
Conn
ConjunctionConn
CC
ForwardPhrase
DisPhrase
Phrase
Nouns
Nouns
Noun
Noun
NNS
NNS
Exercises
 Directory
> Science > Computer Science > Artificial
Intelligence > Natural Language Processing > Web
Directories
 Computer Science
NN
NN
 Artificial Intelligence
JJ
NN
 Natural Language Processing
JJ
NN
VBG
 Web Directories
NN
NNS
30