First-Order Logic in Artificial Intelligence Studies

Lecture notes for Principles of Artificial Intelligence (COMS 4720/5720) Yan-Bin Jia, Iowa State University Using First-Order Logic (FOL) Outline I. The wumpus world in FOL II. Knowledge engineering process III. Instantiation and Skolemization * Figures are from the textbook site unless a source is specifically cited.

I. The Wumpus World in FOL First-order logic axioms are much more concise than propositional axioms. No Bump No Scream Predicate for percept Percept([Stench, Breeze, Glitter, None, None], 5) time sensor reading Actions Turn(Right), Turn(Left), Forward, Shoot, Grab, Climb Querying the KB for best action ASKVARS(KB, BestAction(?,5)) A A binding list, e.g., {?/Grab}, is returned.

Input/Output Rules No need for the use of fluents (e.g., Forward?, Bump?+1)! Bump Scream Stench Glitter ?,?,?,?,?Percept([?,Breeze,?,?,?],?) Breeze(?) ?,?,?,?,?Percept([?,None,?,?,?],?) Breeze(?) ?,?,?,?,?Percept([?,?,Glitter, ?,?],?) Glitter(?) ?,?,?,?,?Percept([?,?,None, ?,?],?) Glitter(?) ? Glitter(?) BestAction(Grab,?) // simple reflex behavior

Rules for the Environment Adjacency of two squares square at row ? and column ? ?,?,?,?Adjacent([?,?],[?,?]) (? = ? ? = ? 1 ? = ? + 1 ) (? = ? ? = ? 1 ? = ? + 1 ) // if using proportional logic, we would have to name every square, say, Square?,?, // for 1 ?,? 4, and would need one such fact for 120 different pairs of squares! Unary predicate Pit (no reason to distinguish among pits). Pit ?,? true if and only if the square [?,?] contains a pit. Constants Agent, Wumpus Ternary predicate At to represent changing or non-changing locations ?At(Wumpus, [1,3],?) // fixed location for the wumpus ?,?1,?2,?At(?,?1,?) At ?,?2,? ?1= ?2 // only one location at a time

Rules for Percepts, Actions and Inferences Percepts of breeze, stench, etc. ?,?At(Agent,?,?) Breeze ? Breezy ? Diagnostic (inferring cause from effect) ?Breezy ? ? Adjacent ?,? Pit ? // if using proportional logic, we would need a separate axiom for every square. Causal (inferring effect from cause) ?( ? Adjacent ?,? Pit ? ) Breez? ? Quantification over time ?HaveArrow ? + 1 HaveArrow ? Action Shoot,? The first-order logic formulation is no less concise than the English description.

II. Knowledge Engineering Process Identification of questions and facts. What will the KB support and what facts are available? Knowledge assembly or acquisition. Work with real experts to extract knowledge (not yet formally represented). Decision on a vocabulary (predicates, functions, and constants). In the wumpus world, should pits be represented by objects or by a unary predicate on squares? Encoding of general knowledge (axioms). Formal description of the problem instance. Queries to and answers from the inference procedure. Derive the facts we are interested in knowing. Debugging and evaluation of the KB.

The Electronic Circuits Domain Four types of gates: AND, OR, XOR, NOT. XOR 1 or 2 inputs, and 1 output Represent connections between terminals. OR AND No need to represent wires or their paths. Component sizes, shapes, colors, or costs are irrelevant. A one-bit full adder Objects: actual gates and circuits. E.g., ?1, ?2,?1. Predicates: Gate, Terminal, Circuit Functions Type(?1):type of gate ?1 (which is XOR) In 1,?2: 1st input terminal for gate ?2 Out 2,?1: 2nd output terminal for circuit ?1 Arity ?1,2,1 : two input terminals and one output terminal for the gate ?1 Connectivity predicate: Connected Out 1,?1,In 1,?2 Signal function: Signal(?)has value 1 or 0 at time ?.

Encoding General Domain Knowledge // Two connected terminals have the same signal. ?1,?2Terminal ?1 Terminal ?2 Connected ?1,?2 Signal(?1) = Signal(?2) // Every terminal has signal that is either 1 or 0. ? Terminal ? Signal(?)= 1 Signal ? = 0 // Connectivity is commutative. ?1,?2 Connected(?1,?2) Connected(?2,?1) // Four types of gates. ?,k Gate ? ? = Type ? ? = AND ? = OR ? = XOR ? = NOT // An AND gate outputs 0 if and only if any of its input is 0. ? Gate ? Type ? = AND (Signal Out 1,? = 0 ? Signal In ?,? = 0) // An OR gate outputs 1 if and only if any of its input is 1. ? Gate ? Type ? = OR (Signal Out 1,? = 1 ? Signal In ?,? = 1)

contd // An XOR gate outputs 1 if and only if its inputs are different. ? Gate ? Type ? = XOR (Signal Out 1,? Signal In 2,?) = 1 Signal In 1,? // An NOT gate s output is different from its input. ? Gate ? Type ? = NOT (Signal Out 1,? Signal In 1,?) = 1 Signal Out 1,? // All the gates (except for NOT) have two inputs and one output. ? Gate ? Type ? = NOT Arity ?,1,1 ?,? Gate ? k=Type ? (? = AND ? = OR ? = XOR) Arity ?,2,1 // A circuit has terminals exactly up to its input and output arity. ?,?,? Circuit ? Arity ?,?,? ? (? ? Terminal In ?,? ? (? ? Terminal Out ?,? ? > ? In ?,? = Nothing ) ? > ? Out ?,? = Nothing ) // Gates and terminals are all distinct. ?,?,? Gate(?) Terminal(?) Signal(?) ? ? ? ? ? ? (errors/typos in the text) function not predicate // Gates are circuits. ? Gate(?) Circuit(?)

Encoding a Problem Instance Circuit and component gates: XOR Circuit(?1) Arity(?1,3,2) Gate ?1 Type ?1 = XOR OR Gate ?2 Type ?2 = XOR AND Gate ?1 Type ?1 = AND Gate ?2 Type ?2 = AND Gate ?1 Type ?1 = OR Connections between the circuit and component gates: Connected(In 1,?1,In 1,?1) Connected(Out 1,?1,In 1,?2) Connected(Out 1,?1,In 2,?2) Connected(Out 1,?2,In 1,?1) Connected(In 1,?1,In 1,?1) Connected(In 2,?1,In 2,?1) Connected(In 2,?1,In 2,?1) Connected(Out 1,?1,In 2,?1) Connected(In 3,?1,In 2,?2) Connected(Out 1,?2,Out 1,?1) Connected(Out 1,?1,Out 2,?1) Connected(In 3,?1,In 1,?2)

Queries XOR OR Q. What combinations of inputs would cause the first output of ?1 to be 0 and its second output to be 1? AND ?1,?2,?3Signal In 1,?1 Signal Out 1,?1 = ?1 Signal In 2,?1 = 0 Signal Out 2,?1 = ?2 Signal In 3,?1 = 1 = ?3 ASKVARS will give three substitutions as answers. {?1/1,?2/0,?3/1} {?1/1,?2/1,?3/0} {?1/0,?2/1,?3/1} Debugging: We can also perturb the KB to see what erroneous behaviors would emerge, and then identify missing rules for instance.

III. Propositional vs. First-Order Inference One way of inference is to convert the first-order KB to propositional logic. Eliminate universal quantifiers. // All humans are fallible. ? Human(?) Fallible(?) We can infer sentences like Human(Socrates) Fallible(Socrates) Human(Einstein) Fallible(Einstein) Human(Messi) Fallible(Messi) From // All birds are warm-blooded and have wings. ? Bird(?) WarmBlooded(?) HaveWings(?) We can infer (if Bird(Ostrich) and Bird(Peacock) are in the KB): WarmBlooded(Ostrich) HaveWings(Ostrich) WarmBlooded(Peacock) HaveWings(Peacock)

Universal and Existential Instantiations A ground term in FOL is a term without variables. Substitute a ground term for a universally quantified variable. sentence ? ? SUBST( ?/? ,?) substitution ?, e.g., ? ={?/Socrates} E.g., ? = {?/Ostrich} ? ? Bird(?) WarmBlooded(?) HaveWings(?) SUBST(?,?) Bird(Ostrich) WarmBlooded(Ostrich) HaveWings(Ostrich)

Existential Instantiation Substitute a single new constant symbol for an existentially quantified variable. ? ? SUBST( ?/? ,?) From ? Mother(?,Liam) we can infer Mother(LiamsMom,Liam) as long as LiamsMom does not appear elsewhere in the KB. Skolem constant

Propositionalization (Non-Standard Way) x ? Ancestor(?,?) Parent(?,?) ?(Ancestor ?,? Ancestor ?,? ) KB: Ancestor(John,David) Parent(John,David) Parent(David,Lisa) Ancestor(John,David) Parent(John,David) (Ancestor John,JohnDavidAnc Ancestor JohnDavidAnc,David ) Ancestor(David,John) Parent(David,John) (Ancestor David,DavidJohnAnc Ancestor DavidJohnAnc,John ) Ancestor(John,Lisa) Parent(John,Lisa) (Ancestor John,JohnLisaAnc Ancestor JohnLisaAnc,Lisa )

Skolemization (Standard Way) A more standard way to eliminate an existential quantifier is to introduce a new function symbol, which is, however, not applicable in generating a PL sentence. ? ?(?,?1, .,??) // ? depends on ?1, .,?? eliminate ? by introducing function ? ?(?(?1, .,??),?1, .,??) That? ?,?1, .,?? =true implicitly defines ? as a function of ?1, .,?? (analogous to the implicit function theorem in multivariate calculus). new unary function mom() y Mother(?,Liam) Mother(mom(Liam),Liam) y Mother(?,Sophia) Mother(mom(Sophia),Sophia) Advantage: one function instead of two new constants to denote the moms of Liam and Sophia.