COMP4418
⃝c UNSW, 2019
COMP4418: Knowledge Representation and Reasoning
Maurice Pagnucco
School of Computer Science and Engineering University of New South Wales
NSW 2052, AUSTRALIA morri@cse.unsw.edu.au
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 1
Knowledge Representation and Reasoning
A knowledge-based agent has at its core a knowledge base
A knowledge base is a set of facts about the domain in which the
agent finds itself, expressed in a suitable representation
These facts are called sentences
Sentences are expressed in a (formal) knowledge representation language
Question: How do we write down knowledge about a do- main/problem? Once we have written down knowledge, can we automate or mechanise reasoning to deduce new facts?
References:
◮ Ivan Bratko, Prolog Programming for Artificial Intelligence,
Addison-Wesley, 2001. (Chapter 15)
◮ Stuart J. Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, Prentice-Hall International, 1995. (Chapter 6)
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 2
Overview
The need for formal Knowledge Representation Propositions
Formulae in Propositional Logic
Syntax
Semantics
The Notion of Proof Conclusion
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 3
Knowledge Representation and Reasoning
A knowledge-based agent can be described on different levels: ◮ Knowledge level (epistemological level)
◮ Logical level
◮ Implementation level
Knowledge Representation is concerned with expressing knowledge in a computer-tractable way
Reasoning attempts to take this knowledge and draw inferences (e.g., answer queries, determine facts that follow from the knowledge base, etc.)
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 4
Why do we need formal Knowledge Repre- sentation?
You will all be familiar with sentences in English like: “The boy saw a girl with a telescope”
Also:
“Our shoes are guaranteed to give you a fit” (lexical ambiguity) “I heard about him at school” (structural ambiguity)
“As he uttered the all-important word he dropped his voice, but she just managed to catch it” (ambiguity of cross reference)
Natural languages exhibit ambiguity
Not only does ambiguity make it difficult for us to understand what is the intended meaning of certain phrases and sentences but they also make it very difficult to make any inferences
We shall investigate symbolic logic as a form of knowledge representation and reasoning
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 5
Syntax vs Semantics
Syntax Describes the legal sentences in a knowledge representation language (e.g., in the language of arithmetic expressions x < 4).
Semantics Refers to the meaning of sentences. It determines the facts in the world referred to by the sentences in a knowledge representation language. Essentially it relates syntactic descriptions to the “real world”. Semantics talks about truth and falsity. (E.g., x < 4 is true when x is a strictly smaller number than 4 and false otherwise)
Note: a sentence does not mean anything by itself. It is up to the person who wrote the sentence to give it a meaning. To do this the person has to provide an interpretation for the sentence. In English, interpretations are already fixed but they still needed to be supplied at some point in the past.
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 6
Propositions
Propositions are statements of fact.
The English sentence “The sky is blue” expresses the proposition that
the sky is blue
Other propositions:
“Socrates is bald”
“The car is red”
“The text is readable”, etc.
Often we shall use single letters to represent propositions: P: Socrates is bald
(it saves a lot of time!)
This is referred to as a scheme of abbreviation
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 7
Scheme of Abbreviation
COMP4418
⃝c UNSW, 2019
Generated: 15 September 2019
Q: the lectures are dull T : the text is readable P: Alfred will pass
S: the lectures are dull Q: the lectures are dull T : the text is readable P: Alfred will pass
Q: the lectures are dull Q: the text is readable P: Alfred will pass
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 8
Formulae in Propositional Logic
Now that we have propositions it would be nice to combine them into more complex expressions (or sentences)
Similarly to natural languages, we can do so through the use of connectives:
COMP4418
⃝c UNSW, 2019
Generated: 15 September 2019
¬ negation
∧ conjunction
∨ disjunction → implication ↔ bi-implication
¬P
P ∧ Q P ∨ Q P → Q P ↔ Q
“not P”
“P and Q”
“P or Q”
“If P, then Q”
“P if and only if Q”
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 9
From English to Propositional Formulae
“it is not the case that the lectures are dull”: ¬Q (alternatively “the lectures are not dull”)
“thelecturesaredullandthetextisreadable”:Q∧T
“eitherthelecturesaredullorthetextisreadable”:Q∨T
“if the lectures are dull, then the text is not readable”: Q → ¬T
“the lectures are dull if and only if the text is readable”: Q ↔ T
“ifthelecturesaredull,thenifitisnotthecasethatthetextisreadable, then it is not the case that Alfred will pass”: Q → (¬T → ¬P)
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 10
Formulae in Propositional Logic — Syntax
More formally, we can specify a BNF grammar for formulae in propositional logic as follows:
Sentence ::= AtomicSentence ∥ ComplexSentence
AtomicSentence ::= True ∥ False ∥ P ∥ Q ∥ R ∥ ...
ComplexSentence ::= ( Sentence )
∥ Sentence Connective Sentence
∥ ¬ Sentence Connective ::= ∧ ∥ ∨ ∥ → ∥ ↔
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 11
Semantics
The semantics of the connectives can be given by truth tables
P Q ¬P True True False True False False
P∧Q P∨Q P→Q P↔Q
False True True False False True
True False False False
True True True False True True
True False False True
Now we have a way of determining the semantics for complex formulae. Just use the truth tables!
(i.e., truth value)
COMP4418 ⃝c UNSW, 2019
Generated: 15 September 2019
False True
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 12
Semantics — Complex Formulae
R S ¬R R∧S ¬R∨S (R∧S)→(¬R∨S)
True True False
True True True False False True False True True False True True
True False False False True True False False True
COMP4418
⃝c UNSW, 2019
Generated: 15 September 2019
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 13
The Notion of Proof
Question: Now that we can write knowledge down, how do we automate reasoning (i.e., perform inference)?
A proof of a formula from certain premises is a sequence of steps in which any step of the proof is:
1. An axiom or premise
2. A formula deduced from previous steps of the proof via some rule of inference
The last line of the proof should be the formula we wish to prove
This is intended to formally capture the notion of proof that is commonly applied in other fields (e.g., mathematics)
We use the notation λ ⊢ ρ to denote that the formula(s) λ “prove” the formula(s) ρ. Alternatively, we say that ρ follows from (premises) λ
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 14
What is a Logic?
A logic consists of
COMP4418
⃝c UNSW, 2019 Generated: 15 September 2019
1.
A formal system for expressing knowledge about a domain consisting of
2.
A proof theory — rules of inference for deducing sentences from a knowledge base
Syntax Sentences (well formed formulae) Semantics Meaning
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 15
Terminology
A sentence is valid or necessarily true if and only if it is true under all possible interpretations in any possible world (e.g., P ∨ ¬P).
Put another way, a sentence is valid if and only if no matter what truth values are assigned to its constituent parts, the sentence is always true
Valid sentences are also referred to as tautologies
A sentence is satisfiable if and only if in some possible world there is
some interpretation for which the sentence is true
A sentence is unsatisfiable if and only if it is not satisfiable (e.g.,
P∧¬P)
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 16
Provability
λ⊢ρ—wecanconstructaproofforρfromλusingaxiomsandrules of inference
Forexample,P, P→Q⊢Q
This is a syntactic notion involving pure symbol manipulation
In fact, we can capture ⊢ via an inference procedure (several exist)
Ifλisempty(i.e.,0/⊢ρ)andρisasingleformula,thenwesaythatρ is a theorem of the logic
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 17
Entailment
λ |= ρ — whenever the formula(s) λ are true, one of the formula(s) in ρ is true
This is a semantic notion; it concerns the notion of truth
In the case where ρ is a single formula, we can determine whether λ |= ρ by constructing a truth table for λ and ρ. If, in any row of the truth table where all the formulae in λ are true, ρ is also true, then λ|=ρ.
If λ is empty, we say that ρ is a tautology
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 16 September, 2019
Knowledge Representation and Reasoning 18
Entailment
Therefore, P, P → Q |= Q
COMP4418 ⃝c UNSW, 2019
Generated: 15 September 2019
PP→QQ True True True True False False
False True True False True False
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 19
Entailment — Tautologies
R S ¬R R∧S ¬R∨S (R∧S)→(¬R∨S)
True True False
True True True False False True False True True False True True
True False False False True True False False True
T h e r e f o r e , |= ( R ∧ S ) → ( ¬ R ∨ S )
COMP4418 ⃝c UNSW, 2019
Generated: 15 September 2019
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 20
Soundness and Completeness
An inference procedure (and hence a logic) is sound if and only if it preserves truth
Inotherwords⊢issoundiffwheneverλ⊢ρ,thenλ|=ρ
A logic is complete if and only if it is capable of proving all truths
Inotherwords,wheneverλ|=ρ,thenλ⊢ρ
A logic is decidable if and only if we can write a mechanical procedure (computer program) which when asked λ ⊢ ρ it can eventually halt and answer “yes” or answer “no”
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 16 September, 2019 Knowledge Representation and Reasoning 21
Conclusion
Due to the ambiguity in natural languages there is a need to specify knowledge through the use of formal languages
Not only will these formal languages give us a way to remove ambiguity but they will also help to provide methods for automating inference
Propositional logic is a first move in this direction
In the next lecture we look at automating inference using the
resolution rule on which Prolog is based
We shall also investigate first-order predicate calculus
Keep in mind that there are a large number of logics and knowledge representation schemes that we shall not look at
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019