論理的に推論 L4. Reasoning Logically Knowledge Representation (知識表現) 　(知識表現) Propositional Logic 　（命題論理） Vumpus World 　（鬼の世界）

knowledge logic propositional logic mean representation infer inference syntax semantics assuming entail breeze　 pit smelly wumpus 　 adjacent cave enumeration fact imply equivalent

entail 〈…を〉必然的に伴う breeze　 微風 pit 落とし穴 smelly 強い［いやな］においのする Wumpus　 鬼 adjacent 隣接した cave 洞穴 enumeration 一覧表 fact 事実 imply 〈…を〉（必然的に）含む, 伴う, equivalent 同等の knowledge 知識 logic 論理学 propositional logic 命題論理 mean 手段 representation 表現 infer 推論する inference 推論, 推理 syntax 文法 semantics 語義論 assuming 仮定して

Logic What is a logic? Two elements constitute what we call a logic. a formal language in which knowledge can be expressed. a means of carrying out reasoning in such a language. e.g. a logic in natural language 　 if the signal is red, then stop the car. a logic in logical sentence 　　　　　　　A1,1  EastA  W2,1   Forward Knowledge base: It is a set of representations of facts about the world. Sentence: It is each individual representation. Knowledge representation language: It is used for expressing sentences.

Wumpus world 4 3 2 1 A p p p A p 1 2 3 4 b b b w b g g b w b b The wumpus world is a grid of squares surrounded by walls, where each square can contain agents and objects. The agent always starts in the lower left corner, a square that we will label [1,1]. The agent’s task is to find the gold, return to [1,1] and climb out of the cave. 4 3 2 1 Agent A s b p b Breeze　微風 s b w p b g Gold　金 g p Pit 穴 b s s Smelly 臭い w Wumpus　鬼 A b p b START 1 2 3 4

PAGE of Wumpus world Percepts: Breeze, Glitter, Smell Actions: Left turn, Right turn, Forward, Grab, Release, Shoot, Climb Goals: Get gold back to start without entering pit or wumpus square Environment: squares adjacent to wumpus are smelly (world) square adjacent to pit are breezy glitter if and only if gold is in the same square shooting kills the wumpus if you are facing it shooting uses up the only arrow grabbing pick up the gold if in the same square releasing drops the gold in the same square climbing leaves the cave A complete class of environment: 4 x 4 Wumpus world the agent starts in the square [1, 1] facing towards the right the location of the gold and the wumpus are chosen randomly with a uniform distribution (1/15 probability, excluding the start square) each square can be pit with probability 0.2 (excluding the start sqaure)

鬼の世界 The wumpus world is a grid of squares surrounded by walls, where each square can contain an agent and objects as in Figure 1. The agent always starts in the lower left corner, a square that we will label [1,1]. The agent’s task is to find the gold, return to the start, the square [1,1]. 鬼が島は壁で囲まれた格子状の正方形群で表されます。それぞれのマスは図１で現れるような情報（注：鬼と穴情報を除く、匂いと風、財宝のみ）を保持します。エージェントは常に左下（ラベル的に[1，1]）から行動を開始します。エージェントの目的は財宝を手に入れ、スタート地点（ラベル的に[1,　1]）に戻ります。 PAGE Description: Percepts: Breeze, Glitter, Smell Actions: go to left, go to right, go up, go down Goals: Get gold back to the start without entering pit or wumpus square Environment: squares adjacent to wumpus are smelly and square adjacent to pit are breezy （鬼の周り4マスは匂いがあり、穴の周り4マスには風がある。エージェントは鬼の場所、穴の場所は知らないが、推測することで回避する）

How an agent should act and reason In the knowledge level From the fact that the agent does not detect stench and breeze in [1,1], the agent can infer that [1,2] and [2,1] are free of dangers. They are marked OK to indicate this. A cautious agent will only move into a square that it knows is OK. So the agent can move forward to [2,1] or turn left 900 and move forward to [1,2]. Assuming that the agent first moves forward to [2,1], from the fact that the agent detects a breeze in [2,1], the agent can infer that there must be a pit in a neighboring square, either [2,2][3,1]. So the agent turns around (turn left 900, turn left 900) and moves back to [1,1]. The agent has to move towards to [2,1], from the fact that the agent detects a stench in [1,2], the agent can infer that there must be a wumpus nearby and it can not be in [2,2] (or the agent would have detected a stench when it was in [2,1]). So the agent can infer that the wumpus is in [1,3]. It is marked with W. The agent can also infer that there is no pit in [2,2] (or the agent would detect breeze in [1,2]). So the agent can infer that the pit must be in [3,1]. After a sequence of deductions, the agent knows [2,2] is unvisited safe square. So the agent moves to [2,2]. What is the next move?…… moves to [2, 3] or [3,2]??? Assuming that the agent moves to [2,3], from the fact that the agent detects glitter in [2, 3], the agent can infer that there is a gold in [2,3]. So the agent grabs the gold and goes back to the start square along the squares that are marked with OK.

How to represent beliefs that can make inferences initial facts  initial beliefs (knowledge) inferences  actions new beliefs  new facts  How to represent a belief (knowledge)?  Knowledge representation The object of knowledge representation is to express knowledge in computer- tractable form, such that it can be used to help agents perform well. A knowledge representation language is defined by two aspects: Syntax – describes the possible configurations that can constitute sentences. defines the sentences in the language Semantics – determines the facts in the world to which the sentences refer. defines the “meaning ” of sentences Examples: x = y*z + 10; is a sentence of Java language but x =yz10 is not. x+2y is a sentence of arithmetic language but x2+y > is not. “I am a student.” is a sentence in English but “I a student am.” is not

言語は、言語の構文論と意味論がはっきりと定義されている論理学と呼ばれている。 Logic and inference Logic: A language is called a logic provided the syntax and semantics of the language are defined precisely. 言語は、言語の構文論と意味論がはっきりと定義されている論理学と呼ばれている。 Inference: From the syntax and semantics, an inference mechanism for an agent that uses the language can be derived. 構文論と意味論から、言語を使用するエージェントのための推論メカニズムは引き出すことができる Facts are parts of the world, whereas their representations must be encoded in some way within an agent. All reasoning mechanisms must operate on representations of facts, rather than on the facts themselves. The connection between sentences and facts is provided by the semantics of the language. The property of one fact following some other facts is mirrored by the property of one sentence being entailed by some other sentences. Logical inference generates new sentences that are entailed by existing sentences. entail: 〈…を〉必然的に伴う,

Entailment New sentences generated are necessarily true, given that the old sentences are true. This relation between sentences is called entailment. KB |=  Knowledge base KB entails sentence  if and only if  is true in all worlds where KB is true. Here, KB is a set of sentences in a formal language. For example, x > 0 and y > 0 |= x+y > 0

Propositional logic: Syntax Symbols represent whole propositions (facts). The symbols of propositional logic are the logic constants true and false. Logic connectives:  (not),  (and),  (or),  (implies), and  (equivalent) If S is a sentence, S is a sentence. If S1 and S2 is a sentence, S1  S2 is a sentence. If S1 and S2 is a sentence, S1  S2 is a sentence. If S1 and S2 is a sentence, S1 S2 is a sentence. If S1 and S2 is a sentence, S1  S2 is a sentence. The order of the precedence in propositional logic is , , , ,  (from highest to lowest)

Propositional logic: Semantics S is true iff S is false S1  S2 is true iff S1 is true and S2 is true S1  S2 is true iff S1 is true or S2 is true S1 S2 is true iff S1 is false or S2 is true i.e., is false iff S1 is true and S2 is false S1  S2 is true iff S1 S2 is true and S2 S1 is true S1 is true, then S2 is true. S1 is false, then S2 is either true or false S1 S2 S1 S2 S1 S2 S1 S2 S1  S2 S1 S2 S1  S2 S1  S2 grey  true grey  true white  false white  false

Propositional inference: Enumeration method Let  = A  B and KB =(A  C)  (B  C) Is it the case that KB |= ?　　 はKBの論理的帰結 Check all possible models -  must be true whenever KB is true. A B C A  C B  C KB  False True

命題論理の性質： ￢(￢Ｐ) ＝ Ｐ Ｐ∧Ｑ ＝ Ｑ∧Ｐ P∨Ｑ ＝ Ｑ∨Ｐ （Ｐ∧Ｑ）∧Ｒ ＝ Ｐ∧（Ｑ∧Ｒ） 二重否定 ￢(￢Ｐ)　＝　Ｐ 交換則 Ｐ∧Ｑ　＝　Ｑ∧Ｐ P∨Ｑ　＝　Ｑ∨Ｐ 結合則 （Ｐ∧Ｑ）∧Ｒ　＝　Ｐ∧（Ｑ∧Ｒ） （Ｐ∨Ｑ）∨Ｒ　＝　Ｐ∨（Ｑ∨Ｒ） 分配則 Ｐ∧（Ｑ∨Ｒ）　＝　（Ｐ∧Ｑ）∨（Ｐ∧Ｒ） Ｐ∨（Ｑ∧Ｒ）　＝　（Ｐ∨Ｑ）∧（Ｐ∨Ｒ） ド・モルガンの法則 ￢ （Ｐ∧Ｑ）　＝　 (￢Ｐ) ∨ (￢Ｑ) ￢ （Ｐ∨Ｑ）　＝　 (￢Ｐ) ∧ (￢Ｑ) 　ここからは解釈との関連で特別な性質をもつ論理式について見ていこう． 　どんな解釈のもとでも，２つの論理式 P, Q の真偽が一致するとき，この２つの論理式は等価であるといい，P=Q と書く． 　よく知られている等価な論理式をスライドに示してある．いずれも常識的なものだが，特に，分配則の２つめの式においては，or が and に対して分配できることに注意しよう．（orを足し算，andを掛け算だと思っているとこの式は奇妙に感じるかもしれない．） 　ド・モルガンの法則を知らなかった人は，ここで必ず覚えておこう． 　いずれも，「すべての解釈について」，左辺と右辺の計算結果が一致することによって確認できる．（かなりの労苦を伴うが．）

例：真偽値の計算 のとき のとき 　これは論理式の意味（真偽値）の計算例である．

例：恒真 のとき 　どのような解釈のもとでも真である論理式は恒真であるという．このスライドの２つの例のうち，１つめは必ず真となることはすぐわかる．２つめがそうであることはすぐにはわからないので，４通りのすべての解釈に対して，この論理式が真であることを確認する必要がある．スライドでは，その１つだけを示している．

The knowledge base Percept sentences: there is no smell in the square [1,1]  S1,1 there is no breeze in the square [1,1]  B1,1 there is no smell in the square [2,1]  S2,1 there is breeze in the square [2,1]  　B2,1 there is smell in the square [1,2]  S1,2 there is no breeze in the square [1,2]  B1,2

The knowledge base knowledge sentences: If a square has no smell, then neither the square nor any of its adjacent squares can house a wumpus. R1: S1,1  W1,1  W1,2  W2,1 R2: S2,1  W1,1  W2,1  W2,2  W3,1 If there is smell in [1,2], then there must be a wumpus in [1,2] or in one or more of the neighboring squares. R3: S1,2  W1,3  W1,2  W2,2  W1,1 If a square has no breeze, then neither the square nor any of its adjacent squares can have a pit. R4: B1,1  P1,1  P1,2  P2,1 R5: B1,2  P1,1  P1,2 P2,2  P1,3 If there is breeze in [2,1], then there must be a pit in [3,1] or in one or more of the neighboring squares. R6: B2,1  P3,1  P2,1  P2,2  P1,1

Quiz. Complete the following truth table according to propositional syntax. ? S1 S2 S1 S1  S2 S1  S2 S1 S2 S1  S2 False True