Skip to content

Week1_Knowledge.md

Latest commit

 

History

History
411 lines (294 loc) · 9.4 KB

Week1_Knowledge.md

File metadata and controls

411 lines (294 loc) · 9.4 KB

Knowledge - CS50AI Lecture 1

Knowledge-based agents:

Agents that reason by operating on internal representations of knowledge.

Sentence:

An assertion about the world in a knowledge representation language

Propositional Logic

A type of logic that supports joining and/or modifying entire propositions, statements, or sentences to reach conclusions.

Propositional Symbols:

P, Q, R

Logical Connectives:

¬ (not)
∧ (and)
∨ (or)
→ (implication)
↔ (biconditional)

Not (¬)

P ¬P
false true
true false

And (∧)

P Q P ∧ Q
false false false
false true false
true false false
true true true

Or (∨)

P Q P ∨ Q
false false false
false true true
true false true
true true true

Implication (→)

P Q P → Q
false false true
false true true
true false false
true true true

Ex: Your uncle says,
"If you get a good grade, I will buy you ice cream"
You did not get a good grade, but your uncle was nice and still got you ice cream.
You did not get a good grade, your uncle kept his word and didn't get you ice cream.

Conclusion: If P is false, then Q can be anything.

Biconditional (↔)

P Q P ↔ Q
false false true
false true false
true false false
true true true

Equivalent to: P → Q ∧ Q → P

Biconditionals evaluate to true only if P and Q are the same.

Model:

Assignment of a truth value to every propositional symbol (a "possible world").

Knowledge base:

A set of sentences known by a knowledge-based agent.

Entailment:

α ⊨ β

In every model in which sentence α is true, sentence β is also true.

Inference:

The process of deriving new sentences from old ones.

Ex:

P : It is a Tuesday.
Q : It is raining.
R : Harry will go for a run.

KB: (P ∧ ¬**Q**) → R

Inference: R

Model Checking:

  • To determine if KB entails α:
    • Enumerate all possible models.
    • If in every model where KB is true, α is true, then KB entails α
    • Otherwise, KB does not entail α

P : It is a Tuesday Q : It is raining. R : Harry will go for a run.

Knowledge Base: (P ∧ ¬ Q) → R

P is true.
Q is true.

Query: R

P Q R KB
false false false false
false false true false
false true false false
false true true false
true false false false
true false true true
true true false false
true true true false

Inference Rules

If there is ever an empty clause after applying these rules, it evaluates to false. Ex: P ∧ ¬P leads to a contradiction ∴ false.

Modus Ponens

α → β
  α
―――――
  β

Ex:

If it is raining, then Harry is inside (α → β).
It is raining (α).
Harry is inside (β).

And Elimination

If both α and β are true, then one of them must also be true.

α ∧ β
―――――
  α

Ex:

Harry is friends with Ron and Hermione (α ∧ β).
Harry is friends with Hermione (β).

Double Negation Elimination

If the premise is not(not(α)), then the conclusion is α.

¬(¬α)
―――――
  α

Ex:

It is not true that Harry did not pass the test (¬(¬α)).
Harry passed the test (α).

Implication Elimination

If α implies β, then either not α or β is true.

 α → β
―――――――
¬α ∨ β

Ex:

If it is raining, then Harry is inside (α → β). It is not raining or Harry is inside (¬α ∨ β).

Biconditional Elimination

α is true if and only if β is true, in which case α implies β and β implies α.

        α ↔ β
―――――――――――――――――――――
  (α → β) ∧ (β → α)

Ex:

It is raining if and only if Harry is inside (α ↔ β).
If it is raining, then Harry is inside, and if Harry is inside, then it is raining ((α → β) ∧ (β → α)).

De Morgan's Law

If it is not true that α and β, then either not α or not β.

  ¬(α ∧ β)        Inverse:  ¬(α ∨ β)
―――――――――――――             ―――――――――――――
   ¬α ∨ ¬β                   ¬α ∧ ¬β

Example:

It is not true that both Harry and Ron passed the test (¬(α ∧ β)).
Harry did not pass the test or Ron did not pass the test (¬α ∨ ¬β).

Distributive Property

    (α ∧ (β ∨ γ))
―――――――――――――――――――――
  (α ∧ β) ∨ (α ∧ γ)

and

    (α ∨ (β ∧ γ))
 ―――――――――――――――――――――
  (α ∨ β) ∧ (α ∨ γ)

Example:

Ron is in the Great Hall or Hermione is in the library (P ∨ Q).
Ron is not in the Great Hall (¬P).
Conclusion: Hermione is in the library.

Ron is in the Great Hall or Hermione is in the library (P ∨ Q).
Ron is not in the Great Hall or Harry is sleeping (¬P ∨ R).
Conclusion: Hermione is in the library or Harry is sleeping (Q ∨ R).

Proving Theorems:

  • Initial state: starting knowledge base.
  • Actions: inference rules.
  • Transition model: new knowledge base after inference.
  • Goal test: check statement we're trying to prove.
  • Path cost function: number of steps in proof.

Conjuctive Normal Form:

A logical sentence that is an accumulation of individual clauses using the ∧ connective.
Any sentence can be turned into CNF by applying inference rules.

Example:

(A ∨ B ∨ C) ∧ (D ∨ ¬E) ∧ (F ∨ G)

Conversion to CNF

  • Eliminate biconditionals
    • turn (α ↔ β) into (α → β) ∧ (β → α)
  • Eliminate implications
    • turn (α → β) into ¬α ∨ β
  • Move ¬ inwards using De Morgan's Laws
    • e.g. turn ¬(α ∧ β) into ¬α ∨ ¬β
  • Use distributive law to distribute ∨ wherever possible

Example

  (P ∨ Q) → R
 ¬(P ∨ Q) ∨ R          eliminate implication
(¬P ∧ ¬Q) ∨ R          De Morgan's Law
 (¬P ∨ R) ∧ (¬Q ∨ R)   distributive Law

Inference by Resolution

Factoring:

When there are duplicate variables, we can eliminate them without affecting the meaning of the sentence.

Ex:

   P ∨ Q ∨ S
  ¬P ∨ R ∨ S
――――――――――――――
  (Q ∨ S ∨ R)

Algorithm

To determine if KB ⊨ α:

  • Check if (KB ∧ ¬α) is a contradiction?
    • If so, then KB ⊨ α.
    • Otherwise, no entailment.

To determine if KB ⊨ α:

  • Convert (KB ∧ ¬α) to Conjunctive Normal Form.
  • Keep checking to see if we can use resolution to produce a new clause.
    • If ever we produce the empty clause (equivalent to False), we have a contradiction and KB ⊨ α.
    • Otherwise, if we can't add new clauses, there is no entailment.

Example:

Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A?

(A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A)

then,

(¬B ∨ C) - (¬C) → (¬B)

then,

(A ∨ B) - (¬B) → (A)

then,

(¬A) - (A)

then,

()

When ¬A is true there is a contradiction ∴ ¬A has to be false meaning A is true and (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entails A.

First-Order Logic

Propositional Logic

Constant Symbol:

  • represents objects

Predicate Symbol:

  • represents relations or functions
  • takes an input (e.g. constant symbol) and evaluates to true or false
Constant Symbol Predicate Symbol
Minerva Person
Gryffindor House
Hufflepuff BelongsTo

Example:

  • Person is true for Minerva
  • Person is false for Gryffindor
  • House is false for Minverva
  • House is true for Gryffindor
    Person(Minerva)                 =   Minerva is a Person
    House(Gryffindor)               =   Gryffindor is a House
    ¬House(Minerva)                 =   Minerva is not a house
    BelongsTo(Minerva, Gryffindor)  =   Minerva belongs to Gryffindor

Universal Quantification

∀x = something is true for all values of x

∀x.BelongsTo(x, Gryffindor) → ¬BelongsTo(x, Hufflepuff)

Meaning:

  • For all objects x, if x belongs to Gryffindor, then x does not belong to Hufflepuff.
  • Anyone in Gryffindor is not in Hufflepuff.

Existential Quantification

Ǝx = something is true for some value of x

Ǝx.House(x) ∧ BelongsTo(Minerva, x)

Meaning:

  • There exists an object x such that x is a house and Minerva belongs to x
  • Minerva belongs to a house