Notes

Outline

First-Order Logic Knowledge Interchange Format (KIF)

KR Language Components A logical formalism Syntax for wffs Vocabulary of logical symbols    (e.g., AND, OR, NOT, =>, <=>) Interpretation semantics for the logical symbols E.g., “(=> A B)” is true if and only if B is true or A is false. An ontology Vocabulary of non-logical symbols Relations, functions, constants Definitions of non-primitive symbols E.g., (<=> (Bachelor ?x) (AND (Man ?x) (Unmarried ?x))) Axioms restricting the interpretations of primitive symbols E.g., (=> (Person ?x) (Gender (Mother ?x) Female)) A proof theory Specification of the reasoning steps that are logically sound E.g., From “(=> S1 S2)” and “S1”, conclude “S2”.

Interlingua for Multi-Use Knowledge Knowledge Interchange Format (KIF) First order predicate logic Includes numbers, lists, and strings Linear ASCII syntax In the process of becoming an ANSI standard

Conceptualization Set of objects about which knowledge is being expressed Universe of discourse Objects can be – Concrete Clyde, my car Abstract Justice, 2 Primitive Resister Composite Electric circuit Fictional Sherlock Holmes Objects always in the KIF conceptualization (i.e., in the ontology) Real and complex numbers All finite lists of objects Words ASCII characters Finite strings of ASCII characters  ^ (bottom) Set of relations and functions on the objects Truth values

Conceptualization Set of objects about which knowledge is being expressed Universe of discourse Set of relations and functions on the objects Relation Set of finite lists of objects E.g., Parent: {(Richard Earl) (Richard Polly)  (Debbie Don) … } Mapping: <list of objects> ® <truth value> Function Relation that has exactly one nth element for any given n-1 elements E.g, +: {(1 3 4)  (17 23 40)  (2 7 10 12 31)  (2 7 A ^) …} Referred to as (arg1, arg2, … , argk, value) Mapping: <list of objects> ® <object> Truth values true and false

Blocks World Objects  -  a,  b,  c,  d,  e,  table

Blocks World Objects a,  b,  c,  d,  e,  table Relations Above: {(a b)  (a c)  (b c)  (d e)} Clear: {(a) (d)} Table: {(c) (e)} Functions On: {(a b)  (b c)  (d e)}

KBs, Sentences, Terms, Words Knowledge Base – Collection of sentences Sentence – Expression denoting a statement Term – Expression denoting an object Words Constant Word not beginning with “?” or “@” E.g., Fred,  Block-A,  Justice Individual Variable Word beginning with “?” E.g, ?x,  ?The-First-Murderer Sequence Variable Word beginning with “@” E.g, @x,  @The-Other-Murderers

Function Terms and Relational Sentences Function Term (<function constant> <term>* [<sequence variable>]) E.g., (plus 2 3)   (Father-Of Richard)   (plus 4 ?x @Other-Addends) Denotes the object denoted by the “value” of the function with the given arguments Relational Sentence (<relation constant> <term>* [<sequence variable>]) E.g, (Parent Richard Earl)   (Clear A)   (Set-Partition Set1 @Sets) Equations  –   (= <term> <term>) E.g, (= (Father Richard) Earl)   (= A B) Inequalities  –   (/= <term> <term>) E.g, (/= (Father Richard) (Father Bob))   (/= A B)

Declarative Semantics Interpretation of a constant – ^ Þ Bottom <object constant other than ^> Þ <object other than Bottom> <logical constant> Þ <truth value> <relation constant> Þ <relation> <function constant> Þ <function> Variable assignment – <individual variable> Þ <object> <sequence variable> Þ <finite sequence of objects> Semantic value of a term  –       <term> Þ <object> Defined in terms of an interpretation and variable assignment Truth value of a sentence  –       <sentence> Þ {true, false} Defined in terms of an interpretation and variable assignment Version of a variable assignment

Semantic Value Denote “semantic value” by “SIV” I is an interpretation V is a variable assignment Semantic value of a constant SIV(<constant>)  =  I(<constant>) Semantic value of a variable SIV(<variable>)  =  V(<variable>) Semantic value of a function term SIV((fn term1 … termn))  = The object O such that áSIV(term1) … SIV (termn) Oñ is a member of set I(fn) SIV((fn term1 … termn @var))  = The object O such that áSIV(term1) … SIV(termn) | V(@var) Oñ is a member of set I(fn)

Truth Value Denote “truth value” by “TIV” I is an interpretation V is a variable assignment Logical constants Tiv(<constant>)  =  I(<constant>) Tiv(true)  =  true Tiv(false)  =  false Truth value of a relational sentence TIV((rel term1 … termn)) = true  when áSIV(term1), … , SIV (termn)ñ is a member of set I(rel) false  otherwise TIV((rel term1 … termn @var)) = true when áSIV (term1), … , SIV (termn) | SIV (@var)ñ is a member of set I(rel) false  otherwise

Equations and Inequalities Equations TIV((= term1 term2))  = true when SIV(term1) and SIV(term2) are the same object false otherwise Inequalities TIV((/= term1 term2))  =  TIV((not (= term1 term2)))

Logical Sentences:  not, and, or Negation – (not <sentence>) E.g.,  (not (On A D))   (not (On B B)) TIV((not sent))  = true  when TIV(sent) is false false  otherwise Conjunction – (and <sentence>*) E.g.,  (and (On A B) (On B C)) TIV((and sent1 … sentn))  = true  when TIV(senti) is true for all I = 1, … , n false  otherwise Disjunction – (or <sentence>*) E.g.,  (or (On A D) (On A B)) TIV((or sent1 … sentn))  = true  when TIV(senti) is true for some I = 1, … , n false  otherwise

Logical Sentences:  =>  <=  <=> Implication – (=> <sentence>* <sentence>) E.g.,  (=> (On A B) (On B C)) TIV((=> antecedent1 … antecedentn consequent))  = true  when: TIV(antecedenti) is false for some I = 1, … , n;   or TIV (consequent) is true false  otherwise E.g.,  (=> (On A D) (On D D)) TIV((=> a1 … an c))  =  TIV((or  (not a1)  …  (not an)  c)) Implication – (<= <sentence> <sentence>*) Logical equivalence – (<=> <sentence> <sentence>) TIV ((sent1 <=> sent2))  = true  when TIV (sent1) = TIV (sent2) false  otherwise TIV((<=> s1 s2))  =  TIV((and  (=> s1 s2)  (=> s2 s1)))

Logical Terms (if <sentence> <term> [<term>]) E.g, (if  (Above A B)  A  B) SIV((if sent term))  = SIV(term)   when TIV(sent) = true  ^  otherwise SIV((if sent term1 term2))  = SIV(term1)   when TIV(sent) = true SIV(term2)   otherwise (cond  (<sentence> <term>) … (<sentence> <term>)) E.g., (cond   ((Above A B)  A)   ((Above B A)  B)) SIV((cond  (sent1 term1) … (sentn termn)))  = SIV(term1)   when TIV(sent1) = true ... SIV(termn)   when TIV(sentn) = true  ^  otherwise

Declarative Semantics Interpretation of a constant – <object constant> Þ <object> <logical constant> Þ <truth value> <relation constant> Þ <relation> <function constant> Þ <function> Variable assignment – <individual variable> Þ <object> <sequence variable> Þ <finite sequence of objects> Semantic value of a term  –  <term> Þ <object> Defined in terms of an interpretation and variable assignment Truth value of a sentence  –  <sentence> Þ {true, false} Defined in terms of an interpretation and variable assignment Version of a variable assignment V’ is a version of a variable assignment V with respect to variables v1,…,vn if and only if V’ agrees with V on all variables except v1,…,vn.

Universally Quantified Sentences (forall <individual variable> <sentence>) E.g, (forall  ?b  (not (On ?b ?b))) TIV((forall ?var sent)) = true  when TIV’(sent) = true              for all versions V’ of V with respect to variable ?var false  otherwise (forall (<individual variable>*) <sentence>) E.g.,  (forall  (?b1 ?b2)  (=>  (On ?b1 ?b2)  (Above ?b1 ?b2))) TIV ((forall  (?var1 … ?varn)  sent)) = true  when TIV’(sent) = true              for all versions V’ of V with respect to ?var1 … ?varn false  otherwise

Existentially Quantified Sentences (exists <individual variable> <sentence>) E.g,  (exists  ?b  (On ?b table))          (forall    ?b1    (or   (on ?b1 table)   (exists  ?b2  (On ?b1 ?b2)))) TIV((exists ?var sent)) = true  when TIV’(sent) = true              for some version V’ of V with respect to variable ?var false  otherwise (exists (<individual variable>*) <sentence>) E.g.,  (exists   (?b1 ?b2)   (and  (On ?b1 ?A)  (Above ?A ?b2))) TIV ((exists  (?var1 … ?varn)  sent)) = true  when TIV’(sent) = true              for some version V’ of V with respect to ?var1 … ?varn false  otherwise forall not in the scope of an exists may be omitted E.g, (or   (on ?b1 table)   (exists  ?b2  (On ?b1 ?b2)))

KBs, Sentences, Terms Knowledge Base – Collection of sentences Sentence – Expression denoting a statement Logical constant:  true 8 Individual variable:  ?tv Relational sentence 8 Conjunction (Dad Richard Earl) (and  (Dad Richard Earl)  (Mom Richard Polly)) Implication 8 Disjunction (=>  (Dad ?p ?d)  (Parent ?p ?d)) (or  (Dad Richard Earl)  (Dad Richard Alfred)) Equation 8 Logical equivalence (=  (Dad Richard)  Earl) (<=> (Dad ?p ?d)  (Father ?p ?d)) Inequality 8 Universally quantified sentence (/=  (Dad Richard)  Fred) (forall   ?p   (Parent  ?p  (Dad ?p))) Negation 8 Existentially quantified sentence (not  (Dad Richard Fred)) (exists   ?d   (=>  (Person ?p)  (Dad ?p ?d))) Term – Expression denoting an object Object constant:  Fred 8 Individual variable:  ?The-First-Murderer Function term:  (Father Richard) “If” logical term 8 “Cond” logical term (if (Dad Richard Earl) 1 2) (cond   ((Person Joe)  P)   ((Cat Joe)  C))

Digital Circuit C1 Russell and Norvig, Figure 8.1

Domain Conceptualization Objects Circuits 8 Terminals Signals 8 Gates Gate types 8 Signal values Relations Connected:  (<terminal> <terminal>) Terminal:  (<terminal>) … Functions Type:   <gate>  ®  <gate type> In:   (<index> <gate>)  ®  <input terminal> Out:   (<index> <gate>)  ®  <output terminal> Signal:   <terminal>  ®  <signal value>

Electronic Circuit Domain Theory Connected terminals have the same signal (=> (Connected ?t1 ?t2)       (and   (Terminal ?t1)   (Terminal ?t2)   (=  (Signal ?t1)  (Signal ?t2)))) Relation “Connected” is commutative (<=>  (Connected ?t1 ?t2)  (Connected ?t2 ?t1)) Signals are either on or off and only terminals have signals (or  (Signal ?x On)  (Signal ?x Off)  (Signal ?x ^)) (<=>   (or  (Signal ?t On)  (Signal ?t Off))   (Terminal ?t)) (/= On Off) A gate has at least 1 input terminal and 1 output terminal (=>   (Gate ?g)   (and  (Terminal (In ?g 1))  (Terminal (Out ?g 1))))

OR and AND Gates OR gate’s output is off when both of its inputs are off (=> (Type ?g OR)       (and (Gate ?g)                (<=> (Signal  (Out 1 ?g)  Off)                         (and   (Signal  (In 1 ?g)  Off)   (Signal  (In 2 ?g)  Off))))) AND gate’s output is on when both of its inputs are on (=> (Type ?g AND)       (and (Gate ?g)                (<=> (Signal  (Out 1 ?g)  On)                         (and   (Signal (In 1 ?g)  On)   (Signal  (In 2 ?g)  On)))))

XOR and NOT Gates XOR gate’s output is on when its inputs are different (=> (Type ?g XOR)        (and (Gate ?g)                 (Terminal (In 2 ?g))                 (<=> (Signal  (Out 1 ?g)  On)                          (/=  (Signal (In 1 ?g))  (Signal (In 2 ?g))))) NOT gate’s output is different from its inputs (=> (Type ?g NOT)       (and (Gate ?g)                (not (Signal  (Out 1 ?g)  (Signal (In 1 ?g)))))

Circuit C1 Representation Gates (Type X1 XOR) (Type X2 XOR) (Type A1 AND) (Type A2 AND) (Type O1 OR) Connections (Connected  (Out 1 X1)  (In 1 X2)) (Connected  (In 1 C1)  (In 1 X1)) (Connected  (Out 1 X1)  (In 2 A2)) (Connected  (In 1 C1)  (In 1 A1)) (Connected  (Out 1 A2)  (In 1 O1)) (Connected  (In 2 C1)  (In 2 X1)) (Connected  (Out 1 A1)  (In 2 O1)) (Connected  (In 2 C1)  (In 2 A1)) (Connected  (Out 1 X2)  (Out 1 C1)) (Connected  (In 3 C1)  (In 2 X2)) (Connected  (Out 1 O1)  (Out 2 C1)) (Connected  (In 3 C1)  (In 1 A2))