CS 188 Sp07 – Week 5 – Logic by Nuttapong ChentanezKnowledge Bases- Set of sentences in a formal languageDeclarative Approach in building an agent - We Tell what it needs to know, put in KB- It Ask what it should do, by inference proceduce- Put new observation into KB- In contrast to procedural approach- Wumpus world exampleModel- “Possible World”- All possible truth assignmentsEntailment- |= - is true in all model where is trueInference Procedures- Generate sentences from existing KB - In this class, refer to the process of checking if a sentence is entailedSoundness- Does not make thing up. Sentence generate is entailed. Completeness- Generate all sentence that entailed. Can be more.Propositional logicAtomic sentence- Stand for a proposition that is either true or false, represented by a single symbolLiteral- Positive or Negative of atomic sentencesLogical Connectives & Complex Sentences- (,~), , , , - Sentences constructed from simpler sentences using logical connectivesTruth Table- Specify truth value of complex sentences for all possible assignments of truth value of atomic sentencesInference- Ask if KB |= , for some Simple algorithm for inference- Enumerate all possible assignment of truth value and checkEquivalence, Validity and Satisfiability - Equivalence – P and Q are equivalent iff P |= Q and Q |= P- Validity – tautologies, true in all model- Satisfiability – NP complete to check- |= iff ^ is not satisfiable- Leads to algorithm for inference!Logical equivalenceReasoning Patterns- Modus Ponens , ------------------ And elimination ^ ------Monotonicity of logic- if KB |= then KB ^ |= - This is the reason that agent based on KB works at all.- The conclusion of the rule must follow regardless of what else in the knowledge base.- Additional knowledge will not invalidate already inferredPropositional Logic Inference algorithmsConjunctive Normal Form- Conjunction of clauses, which are disjunctions of literal- Any sentences can be reduced to CNF- Hard for human to read, but easy for computerk-CNF- CNF where each clauses consist of exactly k literals- Can convert any CNF to 3-CNF, by introducing variableResolution Algorithm- To show KB |= , show that (KB ^ ) is unsatisfiable- The only rule you really need, which was quite a surprise for me l1 … lk, m1….. mn---------------------------------------l1 … li-1 li+1 …. lk m1 … mj-1 mj+1 …. mk Apply the rule until either:1. No new clauses can be generated, KB does not entail 2. Create empty clause, KB entails why? Can only happen from resolving p ^ ~p- Need to remove duplicates literals- Discard those with A ~A … , because always trueDPLL AlgorithmImprovements over truth table enumeration, by backtracking and pruningHeuristics1. Early terminationA clause is true if any literal is true.Eg. (A B) ^ (A C), if A is true, need not care about B, CA sentence is false if any clause is false.Eg. (A B) ^ ….., if both A, B are false, need not care about others2. Pure symbol heuristicPure symbol: always appears with the same "sign" in all clauses.Make a pure symbol literal true.e.g., In the three clauses (A ~B), (~B ~C), (C A), A and B are pure, C isimpure.3. Unit clause heuristicUnit clause: only one literal in the clauseThe only literal in a unit clause must be true.When does it show up? Unit clause show up when all literals but one in a clause are assigned falseFirst Order Logic-Propositional Logic assumes world contains facts-FOL assume world contains Objects – people, houses, numbers, colors, ..Relations – Set of tuple, red, round, prime, brother of, …Functions – relation for which there is one “value” for an input eg. father ofDomain - Set of objects the universe containsSymbols- Constant symbol, stands for object eg. John, Crown, - Predicate symbol, stands for relation, eg. OnHead- Function symbol, LeftLegSyntax of FOL- Term, logical expression that refers to an object, eg. John, LeftLeg(John)- Atomic sentences, states fact eg. Brother(John, Richard), Married(Father(Richard), Mother(John))- Complex sentences, use logical connectives from sentencesEg. ~King(Richard) King(John)- Universal quantifier (), Existential quantifier (), make statements about all or some ofobjectsEg. “There is someone who is loved by everyone”, y x [Love(x, y)]- Equality, makes statement that two terms refer to the same objects Eg. Richard has two brothersx, y [ Brother(x, Richard) ^ Brother(y, Richard) ^ ~(x = y) ]ExercisesPropositional logic1. Inference “If the unicorn is mythical, then it is immortal, but if it is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a mammal, then it is horned. The unicorn is magical if it is horned.” Can you prove it’s mythical? Magical? Horned?Solution:2. Convert to ~( (a b) c) to CNFSolution3. Which of the following are entailed by the sentence (A B) ^ (¬C ¬D E)?i. (A B)ii. (A B C) ^ (B ^ C ^ D E)iii. (A B) ^ (¬D E)SolutionFirst order logic:1. Which of the following is (are) correct translation of “Everyone’s zipcode within a state has the same first digit” to first order logic?Solution:2. A complete representation of the rules of chess in propositional logic would be much larger than first-order logic. Which of the followings are valid reasons why?i. The rules of chess are very complicated.ii. A chess game can go on for hundreds of moves.iii. There are several types of pieces.iv. There are several pieces of each type.v. There are 64 squares on the board.Solution:3. Translate into first order logic the sentence “Everyone’s DNA is unique and is derived from their parents’DNA.” You must specify the precise intended meaning of your vocabulary terms. [Hint: do not use the predicate Unique(x), since uniqueness is not really a property of an object in itself!, relation can be between>
View Full Document