CS50 AI with Python - Lecture 1: Knowledge

Preface

In the process of studying this series of lectures, my goal is not just to follow the course and complete the assignments, but to gradually understand the fundamental ideas and logic behind artificial intelligence.

This Knowledge lecture mainly focuses on Knowledge Representation and Logical Inference, which are essential cornerstones of AI. By formalizing knowledge and applying rule-based reasoning, we can enable computers to “think like humans,” using known information to derive unknown conclusions.

This note systematically organizes the core content of the lecture and lays a solid foundation for future learning.

📖 Knowledge

Humans reason and draw conclusions based on existing knowledge.

The concept of representing knowledge and drawing conclusions from it is also applied in the field of artificial intelligence.

How can we express knowledge (our understanding of the world) in a formalized language, and on that basis perform reliable logical reasoning to derive new conclusions? That is the question we will explore in this lecture.

---

Knowledge-Based Agents

A knowledge-based agent can reason by manipulating an internal representation of knowledge.

Sentence: A sentence is an assertion about the world expressed in a knowledge representation language. Sentences are how AI stores knowledge and uses it to infer new information.

Process:

1. Representation: Write facts/rules as logical sentences.

2. Inference: Use rules to derive new knowledge (logical sentences) from existing knowledge.

3. Action: Draw conclusions from the knowledge base.

Example from the lecture:

1. If it does not rain today, then Harry will visit Hagrid.

2. Harry visited either Hagrid or Dumbledore today, but not both.

3. Harry visited Dumbledore today.

Based on these three sentences, we can ask the question: “Did it rain today?”

Although none of the individual sentences tell us directly whether it rained:

From sentence 2 and 3, we can infer a new sentence:

4. Harry did not visit Hagrid today.

Then, combining sentence 4 with sentence 1, we can infer:

5. It rained today.

To reach this conclusion, we used logic, a uniquely human method of reasoning. The challenge is: how can we enable computers to perform logical reasoning like humans?

---

Propositional Logic

Propositional logic is based on propositions, which are statements about the world that are either true or false.

Propositional Symbols

We often use simple symbols such as P, Q, R to represent propositions.

Logical Connectives

Logical connectives link propositions together, allowing us to reason about the world in more complex ways.

• Not (¬): Negates the truth value of a proposition.

  If P = “It is raining”, then ¬P = “It is not raining.”

• And (∧): Connects two propositions P, Q; true only when both are true.

  P ∧ Q is true if and only if both P and Q are true.

• Or (∨): Inclusive or. True if either P or Q (or both) is true.

  P ∨ Q is true if at least one of P or Q is true (including both).

• XOR (⊕): Exclusive or. True only if exactly one of P, Q is true.

  P ⊕ Q is true if P is true or Q is true, but not both.

• Implication (⇒): Represents “If P, then Q.” P is the premise, Q the conclusion.

  Example:

  • P = “I win the lottery.”

  • Q = “I will buy you dinner.”

  • P ⇒ Q means: If I win the lottery, I will buy you dinner.

Truth table:

• Biconditional (⇔): “If and only if.” Equivalent to (P ⇒ Q) ∧ (Q ⇒ P).

  Example:

  • P = “I am thirsty.”

  • Q = “I drink water.”

  • P ⇔ Q means: If I am thirsty, I drink water AND If I drink water, it means I am thirsty.

Truth table:

---

Models

A model is an assignment of truth values to each proposition, describing a “possible world.” With n propositions, there are 2^n possible models.

Example:

• P = “It is raining.”

• Q = “Today is Tuesday.”

• One model: {P = True, Q = False}, meaning it’s raining but not Tuesday.

---

Knowledge Base

A knowledge base is a set of sentences known to be true by the agent. These sentences, expressed in propositional logic, provide knowledge about the world and allow further reasoning.

---

Entailment (⊨)

Entailment represents a relationship: if α ⊨ β, then in every world where α is true, β is also true.
Note: Entailment differs from implication.

Example:

• α = “Today is a Tuesday in January.”

• β = “Today is in January.”

• We know α ⊨ β.

---

Model Checking and Inference

Inference is the process of deriving new sentences from existing ones.
For example, in Harry’s case, from sentences 1, 2, 3 we inferred sentences 4 and 5.

Model Checking Algorithm

To determine whether KB ⊨ a:

1. Enumerate all possible models.

2. Filter models where KB is true.

3. If a is also true in all those models, then KB ⊨ a.

Consider the following example:

P: Today is Tuesday.
Q: It is raining.
R: Harry will go for a run.
KB: (P ∧ ¬Q) → R (in other words, P and not Q imply R)
P (P is true)
¬Q (Q is false)
Query: R (we want to know whether R is true or false; does KB ⊨ R?)

We enumerate all possible models (all combinations of P, Q, and R being true or false):

Then we check each model and see whether it satisfies our knowledge base.

First, in our knowledge base, we know P is true and Q is false. Therefore, we can say that in all models where P is false or Q is true, the KB is false.

Finally, two models remain. In both, P is true and Q is false. In one model, R is true; in the other, R is false. Since (P ∧ ¬Q) → R is in our knowledge base, we know that when P is true and Q is false, R must also be true. Thus, in the model where R is false, our KB is false; in the model where R is true, our KB is true.

From the table, we can see that there is only one model where our KB is true. In this model, we find that R is also true. According to our definition of entailment, if R is true in all models where the KB is true, then KB ⊨ R.

---

Code Representation

from logic import *

rain = Symbol("rain")
hagrid = Symbol("hagrid")
dumbledore = Symbol("dumbledore")

knowledge = And(
    Implication(Not(rain), hagrid),
    Or(hagrid, dumbledore),
    Not(And(hagrid, dumbledore)),
    dumbledore
)

This represents the KB: (¬rain ⇒ hagrid) ∧ (hagrid ∨ dumbledore) ∧ (¬(hagrid ∧ dumbledore)) ∧ dumbledore.

---

To run the model checking algorithm, we need the following information:

• KB: The knowledge base used for inference

• Query: The query or proposition we want to know if it is entailed by the KB

• Symbols: A list of all symbols (or propositions, such as rain, hagrid, dumbledore in the example above)

• Model: An assignment of truth values to the symbols, representing a possible world

def check_all(knowledge, query, symbols, model):

    # If model has an assignment for each symbol
    # (The logic below might be a little confusing: we start with a list of symbols. 
    # The function is recursive, and every time it calls itself it pops one symbol 
    # from the symbols list and generates models from it. Thus, when the symbols 
    # list is empty, we know that we finished generating models with every possible 
    # truth assignment of symbols.)
    if not symbols:

        # If knowledge base is true in model, then query must also be true
        if knowledge.evaluate(model):
            return query.evaluate(model)
        return True
    else:

        # Choose one of the remaining unused symbols
        remaining = symbols.copy()
        p = remaining.pop()

        # Create a model where the symbol is true
        model_true = model.copy()
        model_true[p] = True

        # Create a model where the symbol is false
        model_false = model.copy()
        model_false[p] = False

        # Ensure entailment holds in both models
        return(check_all(knowledge, query, remaining, model_true) and check_all(knowledge, query, remaining, model_false))

This function is recursive. That is, it picks a symbol, creates two models—one where the symbol is true and another where it is false—and then calls itself again, with the difference being the truth assignment of that symbol.

The function keeps doing this until all symbols in the model have been assigned truth values, i.e. the list symbols is empty. Once the list is empty (indicated by the line if not symbols), in each instance of the function (each instance corresponds to a different model), it checks whether the knowledge base is true in that model.

If the KB is true in the given model, then the function checks whether the query is also true, as described above.

---

Inference Rules

Model checking is inefficient since it must evaluate all models. Inference rules allow us to derive new information from existing knowledge without enumerating all models.

Examples:

---

Inference can be viewed as a search problem with the following properties:

• Initial state: Initialize the knowledge base (KB)

• Actions: Inference rules

• Transition model: The new knowledge base after inference

• Goal test: Check whether the statement we are trying to prove is in the knowledge base

• Path cost function: The number of steps in the proof

---

Proof by contradiction is also a common tool in computer science. If our knowledge base is true and it contradicts ¬α, then ¬α must be false, which means α must be true. More precisely, the algorithm proceeds as follows:

• To determine whether KB ⊨ α:

  • Convert (KB ∧ ¬α) into conjunctive normal form (CNF).

  • Continue checking to see if we can use resolution to produce new clauses.

  • If we derive the empty clause (equivalent to False), then congratulations! We have found a contradiction, thus proving KB ⊨ α.

  • However, if no contradiction is derived and no further clauses can be inferred, then entailment does not hold.

The following example illustrates how the algorithm works:

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

• First, to prove this by contradiction, we assume A is false. Thus, we get (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A).

• Now we can begin generating new information. Since we know C is false (¬C), the only way for (¬B ∨ C) to be true is if B is also false. Therefore, we can add (¬B) to the knowledge base.

• Next, because we know (¬B), the only way for (A ∨ B) to be true is if A is true. Therefore, we can add (A) to our knowledge base (KB).

• Now our knowledge base contains two complementary literals, (A) and (¬A). Resolving them yields the empty clause (). By definition, the empty clause is false, so we have derived a contradiction.

Reflection

The biggest takeaway from this class is the idea that knowledge representation is the key to enabling machines to reason like humans. By expressing facts and rules in a structured way, we can let computers infer new knowledge. At the same time, I realize that the challenge lies in ensuring that the representation is both expressive and efficient.
In practice, how to balance complexity and tractability is still an open question. This is what I will keep thinking about in the following learning journey.