Logic

• We have already seen an AI tool which works in a non-logical fashion
• Two different schools of thought:
  • Try to emulate biological processes to solve a problem (GA, ANN)
  • Try to emulate the logical reasoning that the human beings use to solve a problem (Logic).
• Shortcomings in both the approaches
  • we have no idea how the biological processes work
  • we have no idea what logic humans use
• Logics
  • Propositional logic
  • First order logic
    • Horn clause logic
  • Expert systems
  • Probabilistic networks
  • Belief functions
  • Fuzzy sets/logic
• Propositional logic
  • facts and Boolean connectives
  • not very useful
• First order logic
  • objects, predicates, connectives and quantifiers
• Temporal logic
  • introduces the time element
• Probability
  • deals with facts similar to the propositional logic
  • instead of giving true/false/don't know, it gives a degree of belief between [0,1]

Propositional logic

• Constants
  • true and false
  • propositional symbols such as P or Q
  • Boolean connectives
  • We do not need so many Boolean operators
  • We use them for convenience
  • not and the and are enough to describe all the operations.
• Truth table is used for describing the semantics of the connectives (Table 6.1)
• Truth table has another function:
• We can prove the validity of certain sentence
  • For a given logical sentence we can construct a truth table
  • if the column for the sentence has all true's in it (tautology) then it is valid
  • It is valid irrespective of the truth values of the symbols
• We now have a method for proving sentences
  • construct a truth table
  • a table with two symbols has 4 entries, a table with 10 symbols has 1024 entries, 20 variables 1M entries
  • In general, you cannot do better than that
  • But in many cases, you will be able to find a proof in much fewer steps.
• Model
  • We always try to build a model of the real world
  • We do that in everyday life
  • You meet a person, you build a model of the person based on what you know and keep on updating as you know more
  • You cannot write down this model using math
  • Physics
  • Newton gave a mathematical model for physical objects
  • It seemed to work. Everything that we derived from the model was confirmed by observations
  • Until the observations started using more sophisticated technology
  • Since Newton's model didn't work, physicist developed the theory of relativity
  • The general theory of relativity finally explained everything that was known
  • The theory also made predictions which have been proven to be right since then
  • At some point the theory may not hold
  • Every model that we will be dealing with will not hold in all situations
• With propositional logic we are going to model the world with a bunch of facts
• We can use certain rules of inference to come up with previously unknown conclusions
• Figure 6.13 gives inference rules

First order logic

• Facts and Boolean connectives is not enough
• First order logic
  • Constant symbols or Objects
    • By themselves don't specify any facts
  • Predicate symbols
    • Specifies relations
    • used for specifying facts
  • Function symbols
    • Useful for specifying other objects
    • Leftlegof(John)
• terms which are the constant symbols of function predicates on the constant symbol. Terms are not facts. John is not a fact nor is Leftlegof(John)
• Sentences in FOL are the facts.
• Atomic sentences
  • Relations involving objects
  • Brother(John, Jacob).
• Complex sentences
  • Examples given in the book
  • Using the standard logical connectives or quantifiers
• Quantifiers are not used in propositional logic
• for all corresponds to conjunction see page 190
• there exists corresponds to disjunctive operator see page 191
• Nesting of the quantifiers
  • for all x,y is same as for all x and for all y
  • for all x there exists y is different from there exists y for all x
• for all not P is same as saying not there exists P
• This makes sense because for all corresponds to and and there exists corresponds to or
• Equality operator to indicate that both the objects are one and the same
• Page 196 gives an additional quantifier called uniqueness quantifier corresponds to there exists exactly one or there exists one and only one
• Higher order logic
  • The quantifiers can be applied to the predicates as well
  • Examples on page 195
• Lambda calculus
• Specify axioms and prove theorems
• Independent set of axioms
• In our logic programming, we may use redundant axioms to increase the speed of obtaining the proof. Page 198

Chapter 9

• Inference rules
• All the inference rules from the propositional logic still apply
• We need additional rules because we have quantifiers
• Notation SUBST defined on page 265
• New rules on page 266
• The proof on page 267 is very long so we use generalized modus ponen
• See the example in the book and explnation from the board
• UNIFY function
  • Variable names in different sentences should be renamed
• Forward chaining and backward chaining
• Forward chaining
  • Every time we add a new sentence we try to see if we can infer new sentences for the knowledge base
  • We start from the facts and keep on finding new facts
  • The original KB let us say has some rules
  • You add afact and see if we get any new fact(s)
  • If we get new facts, we see if they recursively produce anymore facts (page 273).
  • This process is going to generate a lot of facts some of it may be useless
• Backward chaining
  • We know hat we want and we keep on going through the relevant rules and see if we can satisfy the left hand side of the implication
  • Figure. 9.3 on page 276

Resolution

• Conjunctive Normal Form
• Our KB is a conjunction of all the disjunctions in the KB
• Each sentence in the knowledge base is a disjunction