AI Unit 2 PDF

Ai unit 2 Equality The first approach is to axiomatize equality--- to write down sentences about the equality relation in the knowledge base. We need to say that equality is reflexive, symmetric, and transitive, and we also have to say that we can substitute equals for equals in any predicate o...

Ai unit 2 Equality The first approach is to axiomatize equality--- to write down sentences about the equality relation in the knowledge base. We need to say that equality is reflexive, symmetric, and transitive, and we also have to say that we can substitute equals for equals in any predicate or function. for each predicate and function: ∀ x x = x ∀ x, y x = y ⇒ y = x ∀ x, y, z x = y ∧ y = z ⇒ x = z ∀ x, y x = y ⇒ (P1(x) ⇔ P1(y)) ∀ x, y x = y ⇒ (P2(x) ⇔ P2(y))... ∀ w, x, y, z w = y ∧ x = z ⇒ (F1(w, x) = F1(y, z)) ∀ w, x, y, z w = y ∧ x = z ⇒ (F2(w, x) = F2(y, z)) Demodulation These axioms will generate a lot of conclusions, most of them not helpful to a proof. So there has been a search for more efficient ways of handling equality. One alternative is to add inference rules rather than axioms. The simplest rule, demodulation, takes a unit clause x = y and some clause α that contains the term x, and yields a new clause formed by substituting y for x within α. It works if the term within α unifies with x; it need not be exactly equal to x. Note that demodulation is directional; given x = y, the x always gets replaced with y, never vice versa. That means that demodulation can be used for simplifying expressions using demodulators such as x +0= x or x1 = x. Father (Father (x)) = PaternalGrandfather (x) Birthdate(Father (Father (Bella)), 1926) we can conclude by demodulation Birthdate(PaternalGrandfather (Bella), 1926) Demodulation: For any terms x, y, and z, where z appears somewhere in literal mi and where UNIFY(x, z) = θ, x = y, m1 ∨···∨ mn SUB(SUBST(θ, x), SUBST(θ, y), m1 ∨···∨ mn). where SUBST is the usual substitution of a binding list, and SUB(x, y, m) means to replace x with y everywhere that x occurs within m. FIRST ORDER LOGIC FOL-Exercise Write down logical representations for the following sentences: a\. Horses, cows, and pigs are mammals. b\. An offspring of a horse is a horse. c\. Bluebeard is a horse. d\. Bluebeard is Charlie's parent. e\. Offspring and parent are inverse relations. Horse(x) ⇒ Mammal(x) Cow(x) ⇒ Mammal(x) Pig(x) ⇒ Mammal(x) Offspring(x,y) ∧ Horse(y) ⇒ Horse(x) Horse(Bluebeard) Parent(Bluebeard,Charlie) Offspring(x,y) ⇒ Parent(y,x) Parent(x,y) ⇒ Offspring(y,x) (Note we couldn't do Offspring(x,y) ⇔ Parent(y,x)) Suppose a knowledge base contains just one sentence, ∃ x AsHighAs(x,Everest). Which of the following are legitimate results of applying Existential Instantiation? a\. AsHighAs(Everest,Everest). b\. AsHighAs(Kilimanjaro,Everest) c\. AsHighAs(Kilimanjaro,Everest) ∧ AsHighAs(BenNevis,Everest) Both b and c are sound conclusions; a is unsound because it introduces the previouslyused symbol Everest. Note that c does not imply that there are two mountains as high as Everest, because nowhere is it stated that BenNevis is different from Kilimanjaro (or Everest, for that matter). Here are two sentences in the language of first-order logic: \(A) ∀ x ∃ y (x ≥ y) \(B) ∃ y ∀ x (x ≥ y) a\. Assume that the variables range over all the natural numbers 0, 1, 2,\...,∞ and that the "≥" predicate means "is greater than or equal to." Under this interpretation, translate (A) and (B) into English. b\. Is (A) true under this interpretation? c\. Is (B) true under this interpretation? d\. Does (A) logically entail (B)? e\. Does (B) logically entail (A)? a\. (A) translates to "For every natural number there is some other natural number that is smaller than or equal to it." \(B) translates to "There is a particular natural number that is smaller than or equal to any natural number." b\. Yes, (A) is true under this interpretation. You can always pick the number itself for the "some other" number c\. Yes, (B) is true under this interpretation. You can pick 0 for the "particular natural number." d\. No, (A) does not logically entail (B). e\. Yes, (B) logically entails (A). Knowledge Base The central component of a knowledge-based agent is its knowledge base, or KB. A knowledge base is a set of sentences. (Here "sentence" is used as a technical term. It is related but not identical to the sentences of English and other natural languages.) Each sentence is expressed in a language called a knowledge representation language and represents some assertion about the world. Sometimes we dignify a sentence with the name axiom, when the sentence is taken as given without being derived from other sentences. Operations There must be a way to add new sentences to the knowledge base and a way to query what is known. The standard names for these operations are TELL and ASK, respectively. Both operations may involve inference---that is, deriving new sentences from old. Inference must obey the requirement that when one ASKs a question of the knowledge base, the answer should follow from what has been told (or TELLed) to the knowledge base previously. Knowledge Base Each time the agent program is called, it does three things: First, it TELLs the knowledge base what it perceives. Second, it ASKs the knowledge base what action it should perform. In the process of answering this query, extensive reasoning may be done about the current state of the world, about the outcomes of possible action sequences, and so on. Third, the agent program TELLs the knowledge base which action was chosen, and the agent executes the action. Wumpus World The wumpus world is a cave consisting of rooms connected by passageways. Lurking somewhere in the cave is the terrible wumpus, a beast that eats anyone who enters its room. The wumpus can be shot by an agent, but the agent has only one arrow. Some rooms contain bottomless pits that will trap anyone who wanders into these rooms (except for the wumpus, which is too big to fall in). The agent's initial knowledge base contains the rules of the environment, as described previously; in particular, it knows that it is in \[1,1\] and that \[1,1\] is a safe square; we denote that with an "A" and "OK," respectively, in square \[1,1\]. The first percept is \[None, None, None, None, None\], from which the agent can conclude that its neighboring squares, \[1,2\] and \[2,1\], are free of dangers---they are OK. Simple Knowledge Base Using semantics for propositional logic, we can construct a knowledge base for the wumpus world. We focus first on the immutable aspects of the wumpus world, leaving the mutable aspects for a later section. For now, we need the following symbols for each \[x, y\] location: Px,y is true if there is a pit in \[x, y\]. Wx,y is true if there is a wumpus in \[x, y\], dead or alive. Bx,y is true if the agent perceives a breeze in \[x, y\]. Sx,y is true if the agent perceives a stench in \[x, y\]. The sentences we write will suffice to derive ¬P1,2 (there is no pit in \[1,2\]) Inference and Proofs inference rules that can be applied to derive a proof---a chain of conclusions that leads to the desired goal. The best-known rule is called Modus Ponens (Latin for mode that affirms) and is written The notation means that, whenever any sentences of the form α ⇒ β and α are given, then the sentence β can be inferred. For example, if (WumpusAhead ∧WumpusAlive) ⇒ Shoot and (WumpusAhead ∧ WumpusAlive) are given, then Shoot can be inferred. Inference and Proofs Another useful inference rule is And-Elimination, which says that, from a conjunction, any of the conjuncts can be inferred: For example, from (WumpusAhead ∧ WumpusAlive), WumpusAlive can be inferred. Nested Quantifiers "Brothers are siblings" ∀ x ∀ y Brother (x, y) ⇒ Sibling(x, y) If siblinghood is a symmetric relationship ∀ x, y Sibling(x, y) ⇔ Sibling(y, x). "Everybody loves somebody" - means that for every person, there is someone that person loves ∀ x ∃ y Loves(x, y). Nested Quantifiers "There is someone who is loved by everyone" ∃ y ∀ x Loves(x, y) The order of quantification ∀ x (∃ y Loves(x, y)) Everyone has a particular property, namely, the property that they love someone. ∃ y (∀ x Loves(x, y)) says that someone in the world has a particular property, namely the property of being loved by everybody. Confusion over two quantifiers with same variable ∀ x (Crown(x) ∨ (∃ x Brother (Richard, x))) x in Brother (Richard, x) is existentially quantified The rule is that the variable belongs to the innermost quantifier that mentions it; then it will not be subject to any other quantification. Another way to think of it is this: ∃ x Brother (Richard, x) is a sentence about Richard (that he has a brother), not about x; so putting a ∀ x outside it has no effect. Connection between ∀ and ∃ Everyone dislikes parsnips ∀ x ¬Likes(x,Parsnips ) There does not exist someone who likes them. ¬∃ x Likes(x,Parsnips) "Everyone likes ice cream" ∀ x Likes(x,IceCream) ¬∃ x ¬Likes(x,IceCream) The De Morgan rules ∀ x ¬P ≡ ¬∃ x P ¬(P ∨ Q) ≡ ¬P ∧ ¬Q ¬∀ x P ≡ ∃ x ¬P ¬(P ∧ Q) ≡ ¬P ∨ ¬Q ∀ x P ≡ ¬∃ x ¬P P ∧ Q ≡ ¬(¬P ∨ ¬Q) ∃ x P ≡ ¬∀ x ¬P P ∨ Q ≡ ¬(¬P ∧ ¬Q).