赞
踩
Knowledge base is a set of sentences in a formal language
Logics are formal languages
Syntax defines the sentence structures in the language
Semantics defines the meanings of the sentences
We use the term model in place of possible world
if a sentence α \alpha α is true in model m:
m satisfied α \text{m satisfied} \alpha m satisfiedα
m is a model of α \text{m is a model of}\alpha m is a model ofα
m ∈ M ( α ) , where M ( α ) is the set of all the models of α m\in M(\alpha),\text{where}M(\alpha)\text{is the set of all the models of }\alpha m∈M(α),whereM(α)is the set of all the models of α
Entailment
Knowledge base (KB) entails sentence α \alpha α if and only if α \alpha α is true in all worlds where KB is true ,denoted as:
K B ⊨ α KB \models \alpha KB⊨α
α ⊨ β iff M ( α ) ⊆ M ( β ) \alpha \models \beta \text{ iff } M(\alpha) \subseteq M(\beta) α⊨β iff M(α)⊆M(β)
Proposition :a declearative sentence that is either true or flase
Atomic propositions are minimun propositions
Literals are atomic propositions or their negations( p or ¬ p p \text{ or } \neg{p} p or ¬p)
The following grammar in Backus-Naur form (BNF) for syntax:
AtomicSentence | ComplexSentence
AtomicSentence -> True|False|P|Q|R
ComplexSentence -> Sentence|Sentence,Sentence ⋀ \bigwedge ⋀Sentence…
∧ \wedge ∧, ∨ \vee ∨, ⇒ \Rightarrow ⇒, ⇔ \Leftrightarrow ⇔
α ≡ β iff α ⊨ β and β ⊨ α \alpha \equiv \beta \text{ iff } \alpha \models \beta \text{ and } \beta \models \alpha α≡β iff α⊨β and β⊨α
( α ⇔ β ) ≡ ( ( α ⇒ β ) ∧ ( β ⇒ α ) ) (\alpha \Leftrightarrow \beta) \equiv ((\alpha \Rightarrow \beta)\wedge (\beta \Rightarrow \alpha)) (α⇔β)≡((α⇒β)∧(β⇒α))
α ⇒ β = ¬ α ∨ β \alpha \Rightarrow \beta = \neg \alpha \vee \beta α⇒β=¬α∨β
K B ⊨ α iff ( K B ∧ ¬ α ) i s u n s a t i s f i a b l e KB \models \alpha \text{ iff } (KB \wedge \neg \alpha )~is unsatisfiable KB⊨α iff (KB∧¬α) isunsatisfiable
Inference i + i_+ i+can derive α \alpha α from KB denoted as
K B ⊢ i α KB \vdash_i \alpha KB⊢iα
Soundness:i is sound if :
( K B ⊢ i α ) ⇒ ( K B ⊨ α ) (KB\vdash_i \alpha) \Rightarrow (KB\models \alpha) (KB⊢iα)⇒(KB⊨α)
Completeness:i is complete if :
( K B ⊨ α ) ⇒ ( K B ⊢ i α ) (KB\models \alpha) \Rightarrow (KB\vdash_i \alpha) (KB⊨α)⇒(KB⊢iα)
For KB consisting of only propositional logic or first-order logic .There exits a sound and complete inference procedure
FOL is expressive enough to express many things in the real world
Horn and Definite Clauses
Definite clause: a disjunction of literals where exactly one is positive
Horn clause : a disjunction of literals where at most one is positive
Horn clause are closed under resolution:
Resolving two Horn clauses yields a Horn clause
Deciding entailment with Horn clauses can be done in linear time!
Resolution for Horn clauses (Modus Ponens):
α 1 , . . . , α n , ( α 1 ∧ . . . ∧ α n ) → β β \frac{\alpha_1,...,\alpha_n~,~(\alpha_1\wedge ... \wedge \alpha_n)~\rightarrow \beta}{\beta} βα1,...,αn , (α1∧...∧αn) →β
Foward vs. Backward Chaining:
Both time complexities are linear to the size of KB
Forward chaining is data-driven
Backward chaining is goal-driven
In general , backward chaining is more appropriate for problem solving
Forward chaining may generate many conclusions irrelevant to the goal
In general , time complexity of backward chaining is much less than linear of the size of KB
Pro
Propositional logic is declarative,pieces of syntax correspond to facts
Propositional logic allows partial/disjunctive/negated information(unlike most data structures and databases)
Propositional logic is compositional
Meaning in Propositional logic is context-independent(unlike natural language , where meaning depends on context)
Con
Propositional logic has very limited expressive power
Con not say "pits cause breezes in adjacent squares"except by writing one sentence for each square
Syntax of FOL
Contants :
Variables:
Functions:
Predicates:
Connectives:
Equality:
Quantifiers:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。