Transcript WHY WOULD YOU STUDY ARTIFICIAL INTELLIGENCE? (1)

ARTIFICIAL INTELLIGENCE
[INTELLIGENT AGENTS PARADIGM]
KNOWLEDGE PROCESSING
IN FIRST ORDER LOGIC
Professor Janis Grundspenkis
Riga Technical University
Faculty of Computer Science and Information Technology
Institute of Applied Computer Systems
Department of Systems Theory and Design
E-mail: [email protected]
Knowledge Processing
in First-Order Logic
The semantics of first-order logic provide a
basis for a formal theory of logical
inference.
The ability to infer new correct expressions
from a set of true assertions is very
important feature of first-order logic.
These new expressions are correct in that
they are consistent with all previous
interpretations of the original set of
expressions.
Knowledge Processing
in First-Order Logic
For a first-order predicate calculus sentence S
and an interpretation I:
• An interpretation I that makes a sentence
(expression) S true is said to satisfy S.
• An interpretation I that satisfies every
member of a set of expressions is said to
satisfy the set.
Knowledge Processing
in First-Order Logic
• An expression X logically follows
from a set of predicate calculus
expressions S if every interpretation
that satisfies S also satisfies X.
• If I satisfies S for all variable
assignments, then I is a model of S.
Knowledge Processing
in First-Order Logic
In the blocks world example, the blocks world
is a model for its logical description because
all sentences are true under this
interpretation.
• When a knowledge base is implemented as
a set of true assertions about a problem
domain, that domain is a model for the
knowledge base.
Knowledge Processing
in First-Order Logic
S is satisfiable if and only if there exist
an interpretation and variable
assignment that satisfy it; otherwise it
is unsatisfiable.
A set of expressions is satisfiable if and
only if there exist an interpretation and
variable assignment that satisfy every
element.
Knowledge Processing
in First-Order Logic
If a set of expressions is not satisfiable, it
is said to be inconsistent. For
example:
X(p(X)  p(X))
If S has a value T for all possible
interpretations, S is said to be valid.
For example:
X(p(X)  p(X))
Knowledge Processing
in First-Order Logic
How to test validity?
• Truth table method
“+” any expression not containing
variables can be tested.
“-” for expressions containing variables
it is not always possible to decide the
validity (process may not terminate).
Knowledge Processing
in First-Order Logic
• Complete proof procedures
“+” can produce any expression that logically
follows from a set of expressions
A predicate calculus expression X logically
follows from a set S of predicate calculus
expressions if every interpretation and
variable assignment that satisfies S also
satisfies X.
Knowledge Processing
in First-Order Logic
Determining what follows from what is
captured in the knowledge base is the
job of the inference mechanism.
The terms “inference” and “reasoning”
are generally used to cover any process
by which conclusions are reached.
Knowledge Processing
in First-Order Logic
Logical inference or deduction is one way of
sound reasoning.
Logical inference is a process that
implements the entailment between
sentences.
The process by which the soundness of an
inference is established using truth tables
can be extended to entire classes of
inference.
Knowledge Processing
in First-Order Logic
There are certain patterns of inferences
that occur many times, but their
soundness can be proved only once and
for all.
The pattern can be captured in an inference
rule.
Once a rule is established, it can be used
infinite times to make inferences without
going validity test.
Knowledge Processing
in First-Order Logic
An inference rule is sound if every
predicate calculus expression
produced by the rule from a set S of
predicate calculus expressions also
logically follows from S.
Knowledge Processing
in First-Order Logic
An inference rule is complete if, given
a set S of predicate calculus
expressions, the rule can infer every
expression that logically follows from
S.
Knowledge Processing
in First-Order Logic
Notations used for inference rules
 |= 
Meaning:  can be derived from  by
inference
α
(Meta-form)
β
, , etc. are intended to match any
sentence, not just individual proposition
symbols.
Knowledge Processing
in First-Order Logic
An inference rule is sound, if the conclusion
is true in all cases where the premises are
true.
To prove the soundness, the truth table must
be constructed with one line for each
possible model of the proposition symbols
in the premises. In all models where the
premise is true, the conclusion must be
also true.
Knowledge Processing
in First-Order Logic
Example:

T
T
F
F

T
F
T
F
α  β, β
α

F
T
F
T

T
T
T
F