.

 Propositional logic  basic concepts of logic and knowledge based

agents.
DISADVANTAGE:
 weak to represent in complex environment.
First order predicate calculus:
 Logic which is sufficiently expressive
 Commonsense knowledge
REPRESENTATION REVISITED:
 Nature of representation languages
Programming languages
Propositional logic
Natural languages
 Formal languages  C++, java, etc
 Program  computational process

 Data structures  represent facts

DISADVANTAGE:
 General mechanism for deriving facts from other facts.

 Update to data structures  domain specific procedure.

 lack expressiveness  partial information.

B)PROPOSITIONAL LOGIC:
 Compositionality  meaning of sentence.
Advantage:
 Declarative.

 Context-independent.

 Unambiguous.
 Difficult to understand.
FIRST ORDER LOGIC:
 Adopt the foundation of propositional logic
 Borrowing representation ideas from natural languages.

SYNTAX OF NATURAL LANGUAGES:

Nouns & noun phrasesObjects
Verbs & verb phrasesrelations among objects
Objects,relation,function
EXAMPLE:
“one plus two equals three”
 Objectsone,two,three,one plus two
 Relationsequals
 Functionsplus
 Mathematics ,philosophy & AI.
 Express Facts.
 Represent general laws or rules.

DIFFERENCE BETWEEN PL & FOL:

Ontological commitment.
What exist in the world
 Epistemological Commitment

what an agent believes about facts

-the possible states of knowledge with respect to each fact.
SYNTAX & SEMANTICS OF FOL:
 Models for FOL

formal structures that constitute the possible worlds.

 Set of truth values for the propositional symbols.

- objects
- domain  set of objects
- domain elements
EXAMPLE: “ A model containing 5 objects ”
1. Richard the lion heart.
2. His younger brother.
3. The evil john king.
4. The left legs of richard & john.
5. A crown.
 Tuplerelations
{(Richard the lion heart ,king john),(king john,Richard the lion
heart)}
 Onhead relations
(the crown,king john)
 Unary functionleft leg.
(King john)john’s left leg.
(Richard the lion heart)Richard’s left leg.
3 kinds
1. Constant symbols  objects

2. Predicate symbols  relation

3. Function symbol  function

 Intended interpretation.

 syntax of FOL with equality specified in BNF as follows,

Sentence  atomic sentence,

|(sentence connective sentence)
|(quantifier variable ….. Sentence)
|sentence
Atomic sentence  predicate(term….|term=term)
-term  Function(term..)
|constant
| variable
 Connective =>|^|v|
 Quantifiers   | 

 ConstantA|x1|john|….

 Variables  a |x |s |…

 Predicate  Before| Hascolor| raining|….

1.TERMS:
 Logical expression  objects

 Complex term  function symbol followed by parenthesized list of items.

Example: “Left leg function”

(Richard the lion heart)Richard’s left leg.
2. ATOMIC SENTENCE:
 Predicate symbol followed by parenthesized list of terms.

Example: “Brother (Richard, John)”

3.COMPLEX SENTENCE:
 Logical connectives are used

Example:”7 Brother (leftleg (Richard ,

John)^(Brother (John , Richard)))”
4.QUANTIFIERS:
Types:
a) Universal
b) Existential
c) Nested quantifier
1.UNIVERSAL QUANTIFIER:
Example:”All King are persons”
x king(x) => person(x)
2.EXISTENTIAL QUANTIFIER:
 Make a statement about some objects in the universe without naming it.

Example: x crown(x) ^ Onhead (x, john)

3.NESTED QUANTIFIER:
 Used to express more complex sentences.

CASES:
 Quantifiers are of same type.

Example:” Brothers are siblings”

x y Brother(x, y) => sibling( x, y)
 Consecutive quantifiers of the same type.
Example:
x, y sibling(x, y) => sibling(y, z)
 Mixture of quantifiers.
Example:”Everybody likes somebody”
x y Likes(x, y)
Equality:
 Make statements to the effect that two terms refers to the same objects

Example:”Father (John)=Henry”
 Sentence that are added to a knowledge base using TELL.
Example:”John is a King & that kings are persons”.
Queries:
 Questions of the knowledge base can be asked using ASK.

Example:”ASK( KB, King(John))returns true”.

Substitution | binding lists:
 Set for variables | term pairs
 Standard form for an answer of a query with existential variables.

The kingship domain:

 It is a domain of family relationship on kingship.
 Male & female are disjoint categories
x Male(x)  Female(x)
 Parent & child are inverse relations.

p, c Parent( p, c) child( c, p)

Axioms:
 Purely mathematical domains.

Example:”f x, y siblings(x, y) siblings( y, x)”.

Numbers are perhaps that most brilliant example of how a large theory
can be built up from a tiny heart of axioms.
Requirements:
I. A predicate NatNum is needed that will be true of natural numbers.

II. One constant symbol, O

III. One function symbol, S(successor)

Peano axioms:
 Defines natural numbers and additions

 Natural numbers are defined recursively.

 NatNum(0)

- n NatNum(n) =>NatNum(S(n))
Syntactic sugar:
uses of infix notations
sentence that uses the sugar can be “de-sugared ” to produce an equivalent
sentences in ordinary FOL.
1. Identify the task
2. Assemble the relevant knowledge
3. Decide on a vocabulary of predicates, functions, and constants
4. Encode general knowledge about the domain
5. Encode a description of the specific problem instance
6. Pose queries to the inference procedure and get answers
7. Debug the knowledge base.
The electronic circuits domain
1.Identify the task
Does the circuit actually add properly? (circuit verification)
2. Assemble the relevant knowledge
◦ Composed of wires and gates; Types of gates (AND, OR, XOR,
NOT)
◦ Irrelevant: size, shape, color, cost of gates
3. Decide on a vocabulary
◦ Alternatives:
Type(X1) = XOR
Type(X1, XOR)
XOR(X1)


4. Encode general knowledge of the domain
◦ t1,t2 Connected(t1, t2)  Signal(t1) = Signal(t2)

◦ t Signal(t) = 1  Signal(t) = 0
◦ 1≠0

◦ t1,t2 Connected(t1, t2)  Connected(t2, t1)

◦ g Type(g) = OR  Signal(Out(1,g)) = 1  n Signal(In(n,g)) = 1

◦ g Type(g) = AND  Signal(Out(1,g)) = 0  n Signal(In(n,g)) =
0
◦ g Type(g) = XOR  Signal(Out(1,g)) = 1  Signal(In(1,g)) ≠
Signal(In(2,g))
◦ g Type(g) = NOT  Signal(Out(1,g)) ≠ Signal(In(1,g))
5. Encode the specific problem instance
Type(X1) = XOR Type(X2) = XOR
Type(A1) = AND Type(A2) = AND
Type(O1) = OR

Connected(Out(1,X1),In(1,X2)) Connected(In(1,C1),In(1,X1))
Connected(Out(1,X1),In(2,A2)) Connected(In(1,C1),In(1,A1))
Connected(Out(1,A2),In(1,O1)) Connected(In(2,C1),In(2,X1))
Connected(Out(1,A1),In(2,O1)) Connected(In(2,C1),In(2,A1))
Connected(Out(1,X2),Out(1,C1)) Connected(In(3,C1),In(2,X2))
Connected(Out(1,O1),Out(2,C1)) Connected(In(3,C1),In(1,A2))
6. Pose queries to the inference procedure and get answers
What are the possible sets of values of all the terminals for the adder circuit?
i1,i2,i3,o1,o2 Signal(In(1,C_1)) = i1  Signal(In(2,C1)) = i2  Signal(In(3,C1)) = i3 
Signal(Out(1,C1)) = o1  Signal(Out(2,C1)) = o2
7. Debug the knowledge base.

◦
Forward chaining:
 Start with the atomic sentences in the knowledge base
 Apply modus ponens in the forward direction
 Applying new atomic sentences

Example knowledge base

 The law says that it is a crime for an American to sell weapons
to hostile nations. The country Nono, an enemy of America,
has some missiles, and all of its missiles were sold to it by
Colonel West, who is American.

 Prove that Col. West is a criminal

it is a crime for an American to sell weapons to hostile nations:
American(x)  Weapon(y)  Sells(x, y, z)  Hostile(z)  Criminal(x)
Nono … has some missiles, i.e., x Owns(Nono, x)  Missile(x):
Owns(Nono,M1) and Missile(M1)
… all of its missiles were sold to it by Colonel West
Missile(x)  Owns(Nono, x)  Sells(West, x , Nono)
Missiles are weapons:
Missile(x)  Weapon(x)
An enemy of America counts as "hostile“:
Enemy(x, America)  Hostile(x)
West, who is American …
American(West)
The country Nono, an enemy of America …
Enemy( Nono, America)




 Resemble propositional clause
 Definite classes  disjunction of literals  exactly one is positive

Example:”King(x)^Greedy(x)=>Evil(x)”
“King(John)”
“Greedy(y)”
 “It is a crime for an American to sell weapons to hostile nations”
Example:”American(x)^Weapon(x)^Sells( x, y,
z)^Hostile(z)
=>Criminal(x)”
A simple forward chaining algorithm:
 Triggers all the rule.
 Adding their conclusions to the known facts
 Process repeats until the query is added or new facts are added
 Every sentence  concluded by forward chaining is already contained
explicitly in the KB  fixed point.
 FOL-FC-Ask is easy to analyze
Sound-application of generalized modus person
complete-clause knowledge base
Example: NatNum(0)
n NatNum(n)=>NatNum(S(0))
 Forward chaining adds
NatNum(s(0)),NatNum(s(s(0))),NatNum(s(s(s(0)))),….
Efficient forward chaining:
 “Inner loop” of the algorithm-finding all possible unifiers – pattern

matching.
 The algorithm rechecks every rules on every iterations.

 Generate many facts that are irrelevant to the goal.

Matching rules against the known facts:

 Matching the premises of the rule against the facts.

 Missile(x)^Owns(nono,x)=>Sells(west,x,nono)
3 WAYS…
1) Real world knowledge bases are small & simple.
2) Sub classes of rules which matching is efficient
3) Eliminate redundant rule making attempts.
Incremental forward chaining:
 Every new fact inferred on iteration t must be derived from atleast one new
fact inferred on iteration t-1.
 Gradually complete the partial matches as new facts arrive.
 Incremental forward chaining algorithm

Rete:
 Rete algorithm

 pre-processor the set of rules in the knowledge base to construct a

sort of data flow network.
 Cognitive Architecture:

model of human reasoning

ACT,SOAR – working with memory
 Irrelevant facts
Avoid drawing irrelevant conclusions
Use backward chaining
Restrict forward chaining
Deductive database community
Rewrite the rule set, using information from the goal
Only relevant variable bindings  Magic set.
Inference in first order logic:
1.Proposition versus first order inference:
 All greedy kings are evil
 x king(x)^Greedy(x)=>Evil(x)
 King(john)^Greedy(John)=>Evil(John)
2.universal instantiation :
Infer any sentence obtained by substituting a ground term – term without
no variables.
Inference rule-substituting any value to the alpha
for any sentence α,variable v, constant symbol k that does not appear
elsewhere in the knowledge base.
Eg : crown(c1)˄ onhead(c1, john)
process is called as skolemization.
4.inferential equivalence:
Reduction to propositional inference.
5.propositionalization:
Made completely general.
Unification and lifting:
Finding substitutions that make different logical expressions look identical.
A first order inference rule:
 Find some x such that x if a king and x is greedy ,and then inter this x is
evil.
Everyone is Greedy
 Generalization modus ponens

Inference process captured as a single inference rule.

 Lifted inference rule require finding substitution.
 Make different logical expression look identical.

 UNIFY( p, q)=Ө where SUBST(Ө,p)=SUBST(Ө,q)

 UNIFY (knows(john, x),knows( john, jane ))=(x/John)

Occur Check
 When matching a variable against a complex term one must check

variable itself occurs inside the term.

 TELL and ASK function.

 STORE(S) a sentence into the knowledge base.

 FETCH(a) returns all unifiers seen that the query unifies with some

sentence in knowledge .
 keep all the facts in the KB in one long list

 Given a query q, call UNIFY(q, S) for every sentence s in the list

 Predicate indexing puts all the known facts in one bucket and all the
brother facts in another.
 Store in a hash table.

 Many predicate symbols.

 Few clauses of each symbol.

Subsumption lattice:
Example queries

 Employs(x,y)
 Employs(AIMA.org,y)

 Employs(x,richard)

The result fact will be ?

 FOL-BC-ASK – depth first(left to right)
 List of goals containing a single element, the original query and returns the set
of all substituting satisfying the query
 If all satisfied then current branch of the proof succeeds
 Takes the first goal in the list of finds every clause in the knowledge base + the
literals infixes with goal creates a new recursive cell.
 Depth first search algorithm.
 Suffer from problems with respected states in

completeness.
LOGIC PROGRAMMING:
Prolog:
Logic programming language.
Rapid prototyping language for symbol manipulation tasks.
Legal, medical, financial and other domains.
Set of definite classes written in a notation.
Uppercase letter for variables and lowercase for constants.
Example:
criminal(X) :- american(X), Weapon(Y), sells(X,Y,Z),
hostile(Z)
 Some aspects of prolog :
 Set of built-in-function for arithmetic.
 Built in predicates.
 Allows a form of negation called negation or failure.
 Equality operator (=).
 Occur check is omitted.
Efficient implementation of logic programs:
 Interpreted and compiled.
 Removing the FOL-BC-ASK algorithm.
 Designed to maximize speed.
 Generate one answer and promise to generate the rest, solves
the current answers has been fully explored.
 Choice point.
 Good deal of time generating and composing.
SUBSTITUTIONS:
 Keeping track of all variables that have been bound in
stack is called the trial.
 Open code - the unification routine for each different
cell.
 Use of continuations to implement choke points.
Two Principle Sources of parallelism:
1.OR parallelism.
2.AND parallelism.
Redundant inferences and infinite loops:
Consider the following logic program that decides if a
path exists between two points on a directed graph.
Path(X,Z) : link(X,Z)
Path(X,Z) : Path(X,Y) link(Y,Z)
 Path(a,c)

Link(a,c) Path(a,y) Link(b,c)

Fail {}
Link(a,y)
(y/b)

Proof that a path exists

from A to C
Path(a,c)

Path(a,y) Link(y,c)

Path(a,y) Link(y’,y)
b) Infinite proof tree:
Incomplete as a theorem proves for definite clauses
 Memorization

catching solutions to sub goals as they are found and resulting

these solutions when the sub goals recurs.
Constraint logic programming:
(CLP) allows variables to be constrained rather than bound.
Most specific set of constraints on the query variables derived
from the knowledge base
Various constraint solving algorithm.

flexible to solving standard logic programming

deductive databases
Resolution: Conversion to CNF
Everyone who loves all animals is loved by someone:
x [y Animal(y)  Loves(x, y)]  [y Loves(y, x)]

1. Eliminate biconditionals and implications

x [y Animal(y)  Loves(x, y)]  [y Loves(y, x)]

2. Move  inwards: x p ≡ x p,  x p ≡ x p

x [y (Animal(y)  Loves(x, y))]  [y Loves(y, x)]
x [y Animal(y)  Loves(x, y)]  [y Loves(y, x)]
x [y Animal(y)  Loves(x, y)]  [y Loves(y, x)]
◦
3. Standardize variables: each quantifier should use a
different one
x [y Animal(y)  Loves(x,y)]  [z Loves(z,x)]
4. Skolemize: a more general form of existential
instantiation.
Each existential variable is replaced by a Skolem function of
the enclosing universally quantified variables:
x [Animal(F(x))  Loves(x, F(x))]  Loves(G(x),x)

5. Drop universal quantifiers:

[Animal(F(x))  Loves(x, F(x))]  Loves(G(x),x)
6. Distribute  over  :
[Animal(F(x))  Loves(G(x),x)]  [Loves(x,F(x)) 
Loves(G(x),x)]
◦
◦
◦
Basic structure of proof
1. Observe that if S is unsatisfiable, particular set of
ground instances of the clauses of S.
2. Ground resolution theorem.
3. A lifting lemma for any propositional resolution
proof using the set of ground sentences.
Structure of Completeness proof for
resolution:
Any set of sentences S is representable in clause
form.

Assume S is unsatisfiable and in clausal form

Her brand's theorem
Some sets of S’ of ground instances is unsatisfiable
 Ground resolution theorem.
Resolutions can find a contradiction in S’
Lifting lemma
There is a resolution proof for the contradiction in S’.
a)Herbrand universe
 If S is a set of clauses and p is a set of ground terms then P(S),the
saturation of S with respect to P
b)Saturation
 If S is a set of clauses and p is a set of ground terms then P(S),the
saturation of S with respect to P
c)Herbrand base
 The saturation of a set S of clauses with respect to its herbrand
universe is called the herbrand base of S written as Hs(S)
 Let c1&c2 be two clauses with no shared variables and left
c1’&c2’ be ground instances c1 & c2.
  Resolution strategies
 Unit Preference:
Resolution where on the top of the sentence is
single literal unit clause.
 Unit Resolution:
Every resolution step must involve a unit clause.
 Set of support:
 Try to eliminate some potential resolutions
altogether.
 Starts by identifying a subset of the sentences called
the set of support.
 Input Solution:
 Every resolution combines one of the input sentences with
some other sentence.
 Subsumption:
 Eliminate all sentences that are subsumed by an existing
sentence in KB.
 Theorem provers
 First most logic programming has handle only horn
clauses.
 Secondly, prolog programs is terminal logic of controls .
Design of a theorem provers:
 OTTER (Organized Techniques for Theorem proving and
Effective Research)
 Set of clauses known as the set of support
 A set of usable axioms
 A set of equation known as rewrites or demodulators
 A set of parameters and clauses that defines the control
strategy
Extending prolog:
◦ Prolog technology theorem proves or PTTP five significant changes
to prolog
◦ Occur check is part back into the unification routine
◦ Depth first search is replaced by a iterative deepening search
◦ Negated literals (7p(x)) are allowed
◦ A clauses with n atoms is stored as n different rule
◦ Inference is made complete (even for non horn – clauses) by addition
of the linear input resolution rule
Drawback of PTTP:
◦ User has relinquish all control over the search for solutions
Theorem provers as assistant:
◦ Proof checker
A Socratic reasoner is a theorem prover whose ASK
function is incomplete
Always arrive at a solution , if asked the right series of
questions
Practical uses of theorem prover:

Robins algebra
Simple set of axioms that appeared to define Boolean
algebra
Verification and synthesis of both hardware and software
Deductive synthesis
Designing several novel and sophisticated algorithms
AURA theorem prover.