First Order Logic

• Knowledge-based agents use logic to represent the world
  • Deduce the actions to take
• The logic language
  • Propositional logic can´t represent complex environments in concise way
  • Require first-order-logic
• First-order-logic or First-order predicate-calculus
  • Sufficiently expressive
  • Foundation of other representation languages

Programming Languages

• Programming languages are a very common formal language
• With a programming language we represent computational processes
• With data structures in programs we repesent facts
  • An array (matrix) to represent the wumpus world
  • \(World[2,2] \leftarrow Pit\), a pit in square [2,2]

Programming Languages

• With a procedural approach we can’t represent
  • A general mechanism for deriving facts from other facts
  • Updates to data structures done by domain-specific procedure, with knowledge from the programmer
  • The programmer does these changes to the data, derives facts, using her/his knowledge
• With data structures in programs there’s not an easy way to represent
  • There is a pit in [2,2] or [3,1]
  • If the wumpus is in [1,1] then he is not in [2,2]
  • Lack expressiveness to handle partial information

Propositional Logic

• Propositional logic is a declarative language
  • Semantics based on a truth relation between sentences and possible worlds
  • Sufficient expressive to deal with partial information (uses disjunction and negation)
  • Expresses the logic of a computation instead of its control flow
  • Programs are considered as theories in a formal logic
  • Computations are considered as deductions in the logic space
• Has the property named compositionality: the meaning of a sentence is a function of the meaning of its parts
  • The meaning of \(S_{1,4} \land S_{1,2}\) is related to the meaning of \(S_{1,4}\) and \(S_{1,2}\)
  • Makes reasoning more effective

Propositional Logic

• Propositional logic lacks expressive power to concisely describe an environment with many objects
  • \(B_{1,1} \iff (P_{1,2} \lor P_{2,1})\)
  • Need to write separate rule about breezes and pits for each square of the world, not efficient

Natural Language

• In English we would say “Squares adjacent to pits are breezy”
  • Natural languages are very expressive
• Could we take something from natural language to make our representations more expressive?
  • How can we represent context
• Natural languages suffer from ambiguity
  • Apple
  • Bank

Human Knowledge Representations

• Human knowledge representations
  • fMRI (functional magnetic resonance imaging)
  • We can predict in which word our brain is thinking about (with many restrictions)
  • (common representation across people)

Formal Logic Representations

• Representing the same knowledge in different ways makes no difference
  • Same facts will be derivable
  • One representation could reach a conclusion in fewer steps

Combining the Best of Formal and Natural Languages

• Combine propositional logic with natural language
  • Use the foundation of propositional logic
    • Declarative, compositional semantics that is context-independent, unambiguous
  • Use representational ideas from natural language (avoiding drawbacks)
    • Most obvious element are nouns, that refer to objects (squares, pits, wumpuses)
    • Verb phrases that refer to relations among objects (is breezy, is adjacent to, shoots)
    • Some relations are functions (relations in which there is only one value for a given input)

Combining the Best of Formal and Natural Languages

• Some examples
• Objects: people, houses, cars, movies, chairs, books
• Relations
  • Unary relations or properties: red, round, prime, cold
  • n-ary relations: brother of, bigger than, inside
• Functions: father of, best friend, third inning of, highest of

Ontological and Epistemological Commitment

• Ontological commitment
  • What the language assumes about the nature of reality.
• Epistemological Commitment
  • The possible states of knowledge that the language (logic) allows with respect to each fact
  • An agent can believe a sentence is true or false

The Language of First-order Logic

• Built on objects and relations
• Useful to deal with objects and the relations among them
• Can express facts about some or all of the objects in the universe
  • Squares neighboring the wumpus are smelly
• Temporal Logic
  • Assumes that facts hold at particular times, and times are ordered
• Higher-order Logic
  • Views the relations and functions of first-order logic as objects
  • Allows making assertions about \(all\) relations
  • More expressive than first-order logic
• Systems using probability theory
  • Use a degree of belief from 0 to 1, (many possible states)

Ontological and Epistemological Commitments of Different Logics

Models for a Logical Language

• Model of a logical language
  • Corresponds to the formal structures that constitute the possible worlds under consideration
  • The model links the vocabulary of logical sentences with elements of the possible world

Models for First-order Logic

• Models in first-order logic have objects and an interpretation
  • The Domain of a model is the set of objects or domain elements
    • Domain cannot be empty
  • Models have an interpretation that maps
    • Constant symbols to objects
    • Predicate symbols to relations on objects
    • Function symbols to functions on objects

Models for First-order Logic

• Model example

Symbols and Interpretations

• The syntax of first-order logic
  • The symbols used for objects, relations, and functions
• Constant symbols, for objects, Richard, John
• Predicate symbols, for relations, Brother, OnHead, Person, King, Crown
• Function symbols, for functions, LeftLeg
• These symbols begin with an uppercase letter
• Predicates and functions have an Arity that fixes the number of arguments

Symbols and Interpretations

• Interpretation, a model has an interpretation that specifies exactly the meaning of objects, relations and functions
  • Richard refers to Richard the Lionheart and John refers to the evil King John
  • Brother refers to the brotherhood relation
  • OnHead refers to the “on head” relation that holds between the crown and King John
  • Person, King, and Crown refer to sets of objects
  • LeftLeg refers to a function, a mapping
    • \(\langle King John \rangle \rightarrow\) John’s left leg.
• There are other interpretations for this model (i.e. one mapping Richard to the crown)
• In FOL entailment and validity are defined in terms of all possible models

Symbols and Interpretations

• Models vary in the number of objects they contain (from 1 up to \(\infty\)) and the way constant symbols map to objects
• Number of possible models is unbounded (too many)
  • Thus, checking entailment by the enumeration of all models is not feasible in FOL
• There are 137,506,194,466 models with six or fewer objects (in the figure below)

First-order Logic Syntax

Terms

• A term is a logical expression that refers to an object
  • Constant symbols
  • We don’t name all possible objects but use functions instead
    • Name for King Jonh’s left leg: “King John’s left leg”
    • Instead, we use a function (that applies to many objects): \(LeftLeg(John)\).
• A complex term (a complicated kind of name), is formed by a function symbol followed by a parenthesized list of terms as arguments

Terms

• Formal semantics
  • \(f(t_1, \dots, t_n)\)
  • \(f\) refers to some function in the model, \(F\)
  • Argument terms refer to objects in the domain, \((d_1, \dots, d_n)\)
  • The term refers to the value (object) returned by \(F\) when applied to \(d_1, \dots, d_n\)
  • \(LeftLeg(John)\) referst to King John’s left leg

Atomic Sentences

• Atomic sentences are used to put together terms and predicate symbols to state facts
• Atomic sentence (also known as atom), formed by a predicate symbol followed by an optional list of terms
  • \(brother(Richard, John)\)
• Atomic sentences may have complex terms as arguments
  • \(Married(Father(Richard), Mother(John))\)
• An atomic sentence is true (in a model) when the predicate symbol holds according the objects referred to by the arguments

Complex Sentences

• Use logical connectives to construct complex sentences
• Four sentences evaluated as true under an intended interpretation (figure 2)
  • \(\lnot Brother(LeftLeg(Richard), John)\)
  • \(Brother(Richard, John) \land Brother(John, Richard)\)
  • \(King(Richard) \lor King(John)\)
  • \(\lnot King(Richard) \Rightarrow King(John)\)

Quantifiers

• Quantifiers are used to express properties of collections of objects (instead of enumeration)
• Universal quantification (\(\forall\))
  • All kings are persons: \(\forall x King(x) \Rightarrow Person(x)\)
  • \(x\) is a variable
  • A term with no variables is called ground term
  • \(\forall x\) \(King(x)\) \(\Rightarrow Person(x)\)
    • \(x\) is a variable
    • by convention lower case letters
    • a variable can be argument for a function

Quantifiers

• Universal quantification (\(\forall\))
  • \(\forall x\) \(P\) is true given a model if \(P\) is true in all possible extended interpretation
  • Extended interpretation, especifies the domain elements of \(x\)
    • \(x \rightarrow\) Richard the Lionheart
    • \(x \rightarrow\) King John
    • \(x \rightarrow\) Richard’s left leg
    • \(x \rightarrow\) John’s left leg
    • \(x \rightarrow\) the crown

Quantifiers

• Universal quantification (\(\forall\))
  • \(\forall x\) \(King(x) \Rightarrow Person(x)\), this sentence is equivalent to
    • Richard the Lionheart is a king \(\Rightarrow\) Richard the Lionheart is a person
    • King John is a king \(\Rightarrow\) King John is a person
    • Richard’s left leg is a king \(\Rightarrow\) Richard’s left leg is a person
    • John’s left leg is a king \(\Rightarrow\) John’s left leg is a person
    • The crown is a king \(\Rightarrow\) the crown is a person
  • Remember that when we evaluate implication, when the antecedent is false, the whole implication is true
• \(\Rightarrow\) is the natural connective to use with \(\forall\)

Quantifiers

• Existential quantification (\(\exists\))
  • Useful for making a statement about some object in the universe without naming it
  • \(\exists x\) \(Crown(x) \land OnHead(x, John)\), King John has a crown on his head
• Intuitively
  • \(\exists x\) \(P\) says that \(P\) is true for at least one object \(x\)
• Precisely
  • \(\exists x\) \(P\) is true for a model if \(P\) is true in at least one extended interpretation that assigns \(x\) to a domain element

Quantifiers

• Existential quantification (\(\exists\))
• At least one of the following is true
  • Richard the Lionheart is a crown \(\land\) Richard the Lionheart is on John’s head
  • King John is a crown \(\land\) King John is on John’s head
  • Richard’s left leg is a crown \(\land\) Richard’s left leg is on John’s head
  • John’s left leg is a crown \(\land\) John’s left leg is on John’s head
  • The crown is a crown \(\land\) the crown is on John’s head
• The fifth assertion is true
• \(\land\) is the natural connective to use with \(\exists\)

Quantifiers

• Nested quantifiers
  • We can use multiple quantifiers, as in “Brothers are siblings”
    • \(\forall x\) \(\forall y\) \(Brother(x,y) \Rightarrow Sibling(x,y)\)
  • “Everybody loves somebody”
    • \(\forall x\) \(\exists y\) \(Loves(x,y)\)
  • “There is someone who is loved by everyone”
    • \(\exists y\) \(\forall x\) \(Loves(x,y)\)

Connections Between \(\forall\) and \(\exists\)

• \(\forall\) and \(\exists\) are connected with each other through negation
  • \(\forall x\) \(\neg Likes(x, Parsnips)\) is equivalent to \(\neg \exists x\) \(Likes(x, Parsnips)\)
    • Everyone dislikes parsnips, equivalent to there does not exist someone who likes parsnips
  • \(\forall x\) \(Likes(x,IceCream)\) is equivalent to \(\neg \exists x\) \(\neg Likes(x,IceCream)\)
    • Everyone likes ice cream - there is no one who does not like ice cream

Connections Between \(\forall\) and \(\exists\)

• \(\forall\) is really a conjunction over the universe of objects and \(\exists\) is a disjunction
• De Morgan rules for quantified and unquantified sentences:
  • \(\forall x\) \(\neg P \equiv \neg \exists x\) \(P\), \(\neg(P \lor Q) \equiv \neg P \land \neg Q\)
  • \(\neg \forall x\) \(P \equiv \exists x\) \(\neg P\), \(\neg(P \land Q) \equiv \neg P \lor \neg Q\)
  • \(\forall x\) \(P \equiv \neg \exists x\) \(\neg P\), \(P \land Q \equiv \neg(\neg P \lor \neg Q)\)
  • \(\exists x\) \(P \equiv \neg \forall x\) \(\neg P\), \(P \lor Q \equiv \neg(\neg P \land \neg Q)\)
• We don’t really need both \(\forall\) and \(\exists\) but they are important for readability

Equality

• Equality symbol, say that two terms refer to the same object
  • \(Father(John) = Henry\)
  • Richard has at least two brothers
    • \(\exists x,y\) \(Brother(x, Richard) \land Brother(y, Richard) \land \neg(x=y)\).
• \(x \neq y\) is an abbreviation for \(\neg(x = y)\)

An Alternative Semantics?

• Database semantics, makes some assumptions
  • Unique-names assumption, Every constant symbol refer to a distinct object
  • Close-world assumption, Atomic sentences not known to be true are in fact false
  • Domain closure, Each model contains no more domain elements than those named by the constant symbols
  • Database semantics also used in logic programming systems
  • Useful when we are certain about identity of all objects and we have all facts at hand

Using First Order Logic

• We have an expressive logical language
  • How do we use it?
• Domain, some part of the world for which we express knowledge (using a knowledge representation)
• We use the TELL/ASK interface

Assertions and Queries in First Order Logic

• Adding sentences to KB with TELL
  • These sentences are called assertions
  • TELL(\(KB, King(John))\)
  • TELL(\(KB, Person(Richard))\)
  • TELL(\(KB, \forall x\) \(King(x) \Rightarrow Person(x))\)
• Asking questions to KB with ASK
  • ASK(\(KB, King(John))\), returns true
  • Questions are called queries or goals
  • ASK(\(KB, Person(John))\), returns true
  • ASK(\(KB, \exists x Person(x))\), returns true
• Asking questions with substitution or binding list with ASKVARS
  • ASKVARS(\(KB, Person(x))\), returns: {\(x/John\)} and {\(x/Richard\)}

The Wumpus World

• Now we can use more concise axioms, capture in natural way what we want to say
• In the Wumpus world, the agent receives percept with five elements
• KB stores the percepts and the time of occurrence
• A typical percept
  • \(Percept([Stench, Breeze, Glitter, None, None], 5)\)
• Actions
  • \(Turn(Right)\), \(Turn(Left)\), \(Forward\), \(Shoot\), \(Grab\), \(Climb\)

The Wumpus World

• Asking for best action to take
  • ASKVARS(\(\exists a\) \(BestAction(a,5))\)
  • returns: {\(a/Grab\)}
• Reasoning process: perception
  • \(\forall t, s, g, m, c\) \(Percept([s, Breeze, g, m, c],t) \Rightarrow Breeze(t)\),
  • \(\forall t, s, b, m, c\) \(Percept([s, b, Glitter, m, c],t) \Rightarrow Glitter(t)\)
• Simple reflex behavior
  • \(\forall t\) \(Glitter(t) \Rightarrow BestAction(Grab,t)\)

The Wumpus World

• Representing the environment
• Adjacency on any two squares
  \(\forall x, y, a, b\) \(Adjacent([x,y],[a,b]) \iff\) \((x=a \land (y=b-1 \lor y=b+1)) \lor\) \((y=b \land (x=a-1 \lor x=a+1))\)
• Representing a Pit, no reason to distinguish among pits, just unary predicate \(Pit\)
  • \(Pit\) is true in squares with a Pit

The Wumpus World

• Representing the wumpus, there is exactly one wumpus
  • We use a constant Wumpus or a unary predicate
    • Fixing the wumpus location: \(\forall t\) \(At(Wumpus,[2,2],t)\)
• The agent’s location
  • \(At(Agent, s, t)\), the agent is at square \(s\) at time \(t\)
• Objects can be only at one location at a time
  • \(\forall x, s_1, s_2, t\) \(At(x,s_1,t) \land At(x,s_2,t) \Rightarrow s_1 = s_2\)

The Wumpus World

• Agent infers properties of a square from properties of its current percept
• Agent is at a square in which it perceives breeze then square is breezy
• \(\forall s,t\) \(At(Agent,s,t) \land Breeze(t) \Rightarrow Breezy(s)\)
• Breezy has no time argument
• Can also infer about smelly, not breezy, not smelly
• Then can deduce where pits are and where the wumpus is
• \(\forall s\) \(Breezy(s) \iff \exists r\) \(Adjacent(r,s) \land Pit(r)\)
  • Simpler than the representation with propositional logic
• \(\forall t\) \(HaveArrow(t+1) \iff\)
  \((HaveArrow(t) \land \neg Action(Shoot,t))\)
  • Also simpler than with propositional logic

The Wumpus World

• Axioms for location and orientation?
• \(Direction(0,90,180,270)\)
  • \(Orientation(S_0)=0\)
• \(\forall x,y\) \(LocationToward([x,y],0) = [x+1,y]\)
• \(\forall x,y\) \(LocationToward([x,y],90) = [x,y+1]\)
• \(\forall x,y\) \(LocationToward([x,y],180) = [x-1,y]\)
• \(\forall x,y\) \(LocationToward([x,y],270) = [x,y-1]\)

The Wumpus World

• Defining location ahead
• \(\forall l,s\) \(AtAgent(l,s) \Rightarrow\)
  \(LocationAhead(s) = LocationToward(l,Orientation(s))\)