DOC PREVIEW
Berkeley COMPSCI 188 - CS188 Week 5 – Logic

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 brothersx, 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

Berkeley COMPSCI 188 - CS188 Week 5 – Logic

Documents in this Course
CSP

CSP

42 pages

Metrics

Metrics

4 pages

HMMs II

HMMs II

19 pages

NLP

NLP

23 pages

Midterm

Midterm

9 pages

Agents

Agents

8 pages

Lecture 4

Lecture 4

53 pages

CSPs

CSPs

16 pages

Midterm

Midterm

6 pages

MDPs

MDPs

20 pages

mdps

mdps

2 pages

Games II

Games II

18 pages

Load more
Download CS188 Week 5 – Logic
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CS188 Week 5 – Logic and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS188 Week 5 – Logic 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?