the predicate calculas

Knowledge Representation (KR)
Given the world
• Express the general facts or beliefs using a
language
• Determine what else we should (not) believe3
Example
Given:
• “The red block is above the blue block”
• “The green block is above the red block”
Infer:
• “The green block is above the blue block”
• “The blocks form a tower”4
A KR language needs to be
• expressive
• unambiguous
• flexible5
The inference procedures need to be
• Correct (sound)
• Complete
• Efficient6
Candidates (for now)
• English (natural language)
• Java (programming language)
• Logic (special KR language)7
Logic consists of
• A language
which tells us how to build up sentences
in the language (i.e., syntax), and
and what the sentences mean
(i.e., semantics)
• An inference procedure
which tells us which sentences are valid
inferences from other sentences8
Propositional logic
The symbols of propositional calculus are
the propositional symbols:
P, Q, R, S, …
the truth symbols:
true, false
and connectives:
?, ?, ?, ?, ?9
Propositional Calculus Sentences
Every propositional symbol and truth symbol is
a sentence.
Examples: true, P, Q, R.
The negation of a sentence is a sentence.
Examples: ?P, ? false.
The conjunction, or and, of two sentences is a
sentence.
Example: P ? ?P10
Propositional Calculus Sentences
(cont’d)
The disjunction, or or, of two sentences is a
sentence.
Example: P ? ?P
The implication of one sentence from another is
a sentence.
Example: P ? Q
The equivalence of two sentences is a
sentence.
Example: P ? Q ? R
Legal sentences are also called well-formed
formulas or WFFs.11
Propositional calculus semantics
An interpretation of a set of propositions is the
assignment of a truth value, either T or F to
each propositional symbol.
The symbol true is always assigned T, and the
symbol false is assigned F.
The truth assignment of negation, ?P, where P
is any propositional symbol, is F if the
assignment to P is T, and is T is the assignment
to P is F.
The truth assignment of conjunction, ?, is T
only when both conjuncts have truth value T;
otherwise it is F.12
Propositional calculus semantics (cont’d)
The truth assignment of disjunction, ?, is F only
when both disjuncts have truth value F;
otherwise it is T.
The truth assignment of implication, ?, is F
only when the premise or symbol before the
implication is T and the truth value of the
consequent or symbol after the implication F;
otherwise it is T.
The truth assignment of equivalence, ?, is T
only when both expressions have the same
truth assignment for all possible
interpretations; otherwise it is F.