Artificial Intelligence - unit 3
Unit III
Using Predicate Logic:
Proposition is a declarative statement which is either true or false but not both. Truth function is a function to check whether a given statement or expression is true or false. Logic is a set of approach with specific reasoning. The logic that deals with propositions is called a propositional logic.
Let ‘p’ and ‘q’ be two propositions. Then, the converse of ‘p → q’ is ‘q → p’. The inverse of ‘p → q’ is ‘¬p → ¬q’ and the contra positive of ‘p → q’ is ‘¬q → ¬p’.
Tautology is a compound statement which is always true no matter what the truth values of the constituent propositions is. Contradiction is a compound statement which is always false no matter what the truth value of constituent propositions is.
Contingency is a compound statement which is either true or false no matter what the truth value of constituent propositions is. Let ‘p’ and ‘q’ be two compound propositions. Then, ‘p’ is logical equivalence to ‘q’ if the truth values of ‘p’ and ‘q’ are equal.
Representing simple facts in Logic:
It is raining RAINING It is sunny SUNNY
It is windy WINDY
If it is raining, then it is not sunny RAINING → ¬SUNNY
Predicate Logic Syntax
• Theorem proving is decidable
• Cannot represent objects and quantification
• Can represent objects and quantification
• Theorem proving is semi-decidable
• Constant symbols: a, b, c, John, ...
To represent primitive objects
• Variable symbols: x, y, z, ... To represent unknown objects
• Predicate symbols: safe, married, love, ...
To represent relations
· married(John) love(John, Mary)
• Function symbols: square, father, ...
To represent simple objects
• safe(square(1, 2))
• love(father(John), mother(John))
• Terms:
To represent complex objects – Constant symbols – If f is a function symbol, and t1, t 2,... tn are terms, then so is f(t1, t2, ..., tn) love(mother(father(John)), John)
• Logical connectives: ¬, ∧, ∨, ⇒, ⇔
• Universal quantifier: ∀x: p(x) ∀x: love(father(x), mother(x))
• Existential quantifier: ∃x: p(x) ≡ ¬∀x: ¬p(x)∃x: ¬married(x)
• Sentences:
Ø Atomic sentences: p(t1, t2, ..., tn)
Ø If α is a sentence, then so are ¬α and (α)
Ø If α and β are sentences, then so are α ∧ β, α ∨ β, α ⇒ β,and α ⇔β
Ø If α is a sentence, then so are ∀α and ∃α
1. Marcus was a man.
2. Marcus was a Pompeian.
3. All Pompeian were Romans.
4. Caesar was a ruler.
5. All Pompeian were either loyal to Caesar or hated him.
6. Everyone is loyal to someone.
7. People only try to assassinate rulers they are not loyal to.
8. Marcus tried to assassinate Caesar. 9 Using Predicate Logic
1. Marcus was a man. man(Marcus)
2. Marcus was a Pompeian. Pompeian(Marcus)
3. All Pompeian were Romans. ∀x: Pompeian(x) → Roman(x)
4. Caesar was a ruler. ruler(Caesar)
5. All Pompeian were either loyal to Caesar or hated him. (inclusive-or )
∀x: Roman(x) → loyalto(x, Caesar) ∨ hate(x, Caesar) (exclusive-or)
∀x: Roman(x) → (loyalto(x, Caesar) ∧ ¬hate(x, Caesar)) ∨ (¬loyalto(x, Caesar) ∧ hate(x, Caesar))
6. Everyone is loyal to someone.
∀x: ∃y: loyalto(x, y) ∃y: ∀x: loyalto(x, y)
7. People only try to assassinate rulers they are not loyal to.
∀x: ∀y: person(x) ∧ ruler(y) ∧ tryassassinate(x, y)→ ¬loyalto(x, y)
7. People only try to assassinate rulers they are not loyal to.
∀x: ∀y: person(x) ∧ ruler(y) ∧ tryassassinate(x, y)→ ¬loyalto(x, y)
8. Marcus tried to assassinate Caesar. Tryassassinate (Marcus, Caesar)
Was Marcus loyal to Caesar? man(Marcus)
ruler(Caesar) tryassassinate(Marcus, Caesar)
⇓ ∀x: man(x) → person(x) ¬loyalto(Marcus, Caesar)
• Many English sentences are ambiguous.
• There is often a choice of how to represent knowledge.
Reasoning:
1. Marcus was a Pompeian.
2. All Pompeian died when the volcano erupted in 79 A.D.
3. It is now 2008 A.D.
Is Marcus alive? 21 26 March, 2009
1. Marcus was a Pompeian. Pompeian(Marcus)
2. All Pompeian died when the volcano erupted in 79 A.D. erupted(volcano, 79) ∧ ∀x: Pompeian(x) → died(x, 79)
3. It is now 2008 A.D.
now = 2008
===============================================================
1. Marcus was a Pompeian. Pompeian(Marcus)
2. All Pompeian died when the volcano erupted in 79 A.D. erupted(volcano, 79) ∧ ∀x: Pompeian(x) → died(x, 79)
3. It is now 2008 A.D.
now = 2008
∀x: ∀t1: ∀t2: died(x, t1) ∧ greater-than(t2, t1) → dead(x, t2)
• Obvious information may be necessary for reasoning
• We may not know in advance which statements to deduce (P or ¬P). KB |= α (α is a logical consequence of KB)
How to prove it automatically?
Resolution:
Proof by refutation
KB |= α ⇔ KB ∧ ¬α|= false (empty clause)
Resolution inference rule
(α ∨ ¬β) ∧ (γ ∨ β) premise (α ∨ γ) conclusion
Resolution in Propositional Logic:
1. Convert all the propositions of KB to clause form (S). L1∨ L2∨ ...∨ Ln P or ¬P
1. Convert all the propositions of KB to clause form (S).
2. Negate α and convert it to clause form. Add it to S.
3. Repeat until either a contradiction is found or no progress can be made:
a. Select two clauses (α ∨ ¬P) and (γ ∨ P).
b. Add the resolvent (α ∨ γ) to S.
Example:
KB = {P, (P ∧ Q) → R, (S ∨ T) → Q, T} α = R
Example:
KB = {P(a), ∀x: (P(x) ∧ Q(x)) → R(x), ∀y: (S(y) ∨ T(y)) → Q(y), T(a)}
α = R(a)
Unification:
Ø UNIFY(p, q) = unifier θ where θ(p) = θ(q)
Ø ∀x: knows(John, x) → hates(John, x) knows(John, Jane) ∀y: knows(y, Leonid)
∀y: knows(y, mother(y)) ∀x: knows(x, Elizabeth)
Ø ∀x: knows(John, x) → hates(John, x) knows(John, Jane) ∀y: knows(y, Leonid)
∀y: knows(y, mother(y)) ∀x: knows(x, Elizabeth)
Ø UNIFY(knows(John, x), knows(John, Jane)) = {Jane/x} UNIFY(knows(John, x), knows(y, Leonid)) = {Leonid/x, John/y} UNIFY(knows(John, x), knows(y, mother(y))) =
{John/y, mother(John)/x} UNIFY(knows(John, x), knows(x, Elizabeth)) = FAIL 3
Unification: Standardization
UNIFY(knows(John, x), knows(y, Elizabeth)) = {John/y, Elizabeth/x}
Unification: Occur check
UNIFY(knows(x, x), knows(y, mother(y))) = FAIL
Unification: Most general unifier
UNIFY(knows(John, x), knows(y, z)) = {John/y, John/x, John/z} = {John/y, Jane/x, Jane/z} = {John/y, v/x, v/z} = {John/y, z/x, Jane/v} = {John/y, z/x}
Conversion to Clause Form
1. Eliminate →. P → Q ≡ ¬P ∨ Q
2. Reduce the scope of each ¬ to a single term.
¬(P ∨ Q) ≡ ¬P ∧ ¬Q ¬(P ∧ Q) ≡ ¬P ∨ ¬Q ¬∀x: P ≡ ∃x: ¬P ¬∃x: p ≡ ∀x: ¬P ¬¬ P ≡ P
3. Standardize variables so that each quantifier binds a unique variable. (∀x: P(x)) ∨ (∃x: Q(x)) ≡ (∀x: P(x)) ∨ (∃y: Q(y))
4. Move all quantifiers to the left without changing their relative order.
∀x: (P(x) ∨ ∃y: Q(y)) ≡ ∀x: ∃y: (P(x) ∨ (Q(y)) (∀x: P(x)) ∨ (∃y: Q(y)): don’t move!
5. Eliminate ∃ (Skolemization).
∃x: P(x) ≡ P(c) Skolem constant ∀x: ∃y P(x, y) ≡ ∀x: P(x, f(x)) Skolem function
6. Drop ∀. ∀x: P(x) ≡ P(x).
7. Convert the formula into a conjunction of disjuncts. (P ∧ Q) ∨ R ≡ (P ∨ R) ∧ (Q ∨ R)
8. Create a separate clause corresponding to each conjunct.
9. Standardize apart the variables in the set of obtained clauses.
1. Eliminate →.
2. Reduce the scope of each ¬ to a single term.
3. Standardize variables so that each quantifier binds a uniquevariable.
4. Move all quantifiers to the left without changing their relativeorder.
5. Eliminate ∃ (Skolemization).
6. Drop ∀.
7. Convert the formula into a conjunction of disjuncts.
8. Create a separate clause corresponding to each conjunct.
9. Standardize apart the variables in the set of obtained clauses.
Resolution in Predicate Logic
1. Convert all the propositions of KB to clause form (S).
2. Negate α and convert it to clause form. Add it to S.
3. Repeat until a contradiction is found:
a. Select two clauses (α ∨ ¬ p(t1)).
b. θ = mgu(p(t1, t2, ..., tn)) and (γ ∨ p(t’1, t’2, ..., t’n , t2, ..., tn), p(t’1, t’2, ..., t’n))
c. Add the resolvent θ(α ∨ γ) to S.
Example:
KB = {P(a), ∀x: (P(x) ∧ Q(x)) → R(x), ∀y: (S(y) ∨ T(y)) → Q(y), T(a)}
α = R(a)
Example
1. Marcus was a man.
2. Marcus was a Pompeian.
3. All Pompeian were Romans.
4. Caesar was a ruler.
5. All Pompeian were either loyal to Caesar or hated him.
6. Everyone is loyal to someone.
7. People only try to assassinate rulers they are not loyal to.
8. Marcus tried to assassinate Caesar.
Example
1. Man(Marcus).
2. Pompeian(Marcus).
3. ∀x: Pompeian(x) → Roman(x).
4. ruler(Caesar).
5. ∀x: Roman(x) → loyalto(x, Caesar) ∨ hate(x, Caesar).
6. ∀x: ∃y: loyalto(x, y).
7. ∀x: ∀y: person(x) ∧ ruler(y) ∧ tryassassinate(x, y)→ ¬loyalto(x, y).
8. tryassassinate(Marcus, Caesar).
Example
Prove: hate(Marcus, Caesar)
Question Answering
1. When did Marcus die?
2. Whom did Marcus hate?
3. Who tried to assassinate a ruler?
4. What happen in 79 A.D.?.
5. Did Marcus hate everyone?
Soundness and Completeness
• Soundness of a reasoning algorithm/system R: if KB derives α using R, then KB |=|=|=|= α
• Completeness of a reasoning algorithm/system R: if KB |=|=|=|= α, then KB derives α using R
Ø Resolution algorithm is sound and complete
• In general:
– Soundness: any returned answer is a correct answer.
– Completeness: all correct answers are returned.
Programming in Logic
PROLOG:
• Only Horn sentences are acceptable
A ← B1, B2, ..., Bm≡ A ∨ ¬B1∨ ¬B2∨ ...∨ ¬Bm A, B i : atoms PROLOG:
• The occur-check is omitted from the unification: unsound test ← P(x, x) P(x, f(x))
PROLOG:
• Backward chaining with depth-first search: incomplete P(x, y) ← Q(x, y) P(x, x) Q(x, y) ← Q(y, x)
PROLOG:
• Unsafe cut: incomplete
A ← B, C ← A
B ← D, !, E
D ← ← B, C← D, !, E, C← !, E, C PROLOG:
• Negation as failure: ¬P if fails to prove P
Unit III Completed
Unit 3
one mark questions
1. ……………….. is the declarative statement which is either true or false but not both.
2. ………………...is the action of proving statement or theory to be false or wrong.
3. UNIFY(P,Q)= …………………………………….
4. According to Proof by refutation, state that the following
expression is TRUE/FALSE
“KB |= α ⇔ KB ∧ ¬α|= false”
5. “Contingency is a compound statement which is either true or false no matter what the truth value of constituent propositions is.” Say the above statement is true/false.
2 Mark questions
1. What contradiction statement? Write an example?
2. Define Clause form.
3. What is Resolution?
4. Define Predicate Logic.
5. What is reasoning?
15 mark questions
1. Explain the following predicate logics with example
i. Preposition ii Tautology iii. Contingency
2. Explain Resolution in Predicate Logic with example.
3. Explain Predicate Logic with suitable example.
Comments
Post a Comment