Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 46 · Logic and Knowledge Representation

Propositional Logic

Learn propositional logic for AI: syntax, truth tables, models, validity, entailment and logical equivalences, with a model checker you can run and extend in Python.

So far our agents have searched through states. Another way to build an intelligent agent is to give it knowledge in the form of sentences and let it reason its way to new conclusions. A knowledge-based agent keeps a knowledge base (KB), a collection of sentences in a formal language, and answers questions by working out what must follow from them. If the KB says "it is raining" and "if it rains, the street is wet", the agent can conclude the street is wet without ever having seen it.

The simplest such language is propositional logic. It is small enough to understand completely, powerful enough to encode real problems (as you will see when we reach SAT solving), and it is the foundation of the richer first-order logic later in this chapter. In this lesson you will learn its syntax and meaning, and build a model checker that decides entailment by brute force.

Syntax: what a sentence looks like

The building blocks are proposition symbols, such as P, Rain or Pit_1_2. Each stands for a statement that is either true or false. Complex sentences are built with five connectives:

Connective Name Reads as True when
¬P negation not P P is false
P ∧ Q conjunction P and Q both are true
P ∨ Q disjunction P or Q (or both) at least one is true
P → Q implication if P then Q P is false, or Q is true
P ↔ Q biconditional P if and only if Q P and Q have the same truth value

A symbol, or a negated symbol, is a literal. Parentheses group sentences; without them, the usual precedence is ¬ first, then ∧, then ∨, then → and ↔.

graph TD
    I["→"] --> A["∧"]
    I --> R["R"]
    A --> P["P"]
    A --> Q["Q"]

The syntax tree of (P ∧ Q) → R. Evaluating a sentence means evaluating this tree from the leaves up.

In Python we can represent a sentence as a plain string for a symbol, or a tuple whose first item names the connective. That makes the structure explicit and easy to traverse recursively.

Semantics: what a sentence means

Syntax says what is a legal sentence. Semantics says what it means, by defining when it is true. The key notion is the model: an assignment of true or false to every proposition symbol. With n symbols there are 2^n models.

The truth of a sentence in a model is computed from the truth of its parts using the table above. One row deserves attention because it surprises beginners. In logic, P → Q is only false when P is true and Q is false. If P is false the implication is true, whatever Q is. It is a promise that is only broken by a true premise with a false conclusion; it says nothing about causes.

Listing the truth of a sentence in every model gives its truth table. Based on that table, a sentence is:

  • valid (a tautology) if it is true in every model, like P ∨ ¬P;
  • satisfiable if it is true in at least one model;
  • unsatisfiable (a contradiction) if it is true in no model, like P ∧ ¬P.
Python Truth tables and classifying sentences

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second sentence in the list, (P ∧ Q) → (P ∨ ¬R), is true in all 8 models. It is valid: whenever P and Q hold, P certainly holds, so the conclusion P ∨ ¬R cannot fail. Validity is how logic captures "always true, no matter what the world is like".

Entailment: what follows from what

The central question of a knowledge-based agent is whether a sentence α follows from the knowledge base. Logicians say the KB entails α, written KB ⊨ α, when α is true in every model in which the KB is true.

graph LR
    subgraph ALL["All models"]
        subgraph MA["Models where α is true"]
            subgraph MK["Models where KB is true"]
                K["KB ⊨ α"]
            end
        end
    end

Entailment means the models of the KB form a subset of the models of α. Learning more facts shrinks the KB's circle and can only make more things entailed.

This gives a direct algorithm, model checking: enumerate all models, keep those where the KB is true, and check that α is true in each. If you find a model where the KB is true and α is false, that model is a counterexample and the entailment fails.

Two facts help a lot.

  • KB ⊨ α exactly when KB → α is valid.
  • KB ⊨ α exactly when KB ∧ ¬α is unsatisfiable. (This is the idea behind proof by contradiction, and behind resolution and SAT solvers in the next lessons.)

The next program checks entailment and then solves a classic puzzle by pure logic. On an island, knights always tell the truth and knaves always lie. We write KA for "A is a knight". A person's statement is true exactly when they are a knight, so "A says S" becomes the sentence KA ↔ S. Here A says "B is a knave", and B says "A and C are the same kind".

Python A model checker: entailment, counterexamples and a knights-and-knaves puzzle

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the first part, Wet and Rain are entailed, but ¬Wet is not, and neither is Cold: the KB says nothing about cold, so there are models of the KB where Cold is false (the counterexample printed). Note that "not entailed" is different from "false". Neither Cold nor ¬Cold is entailed, because the KB is silent on it.

In the puzzle two models survive. In both, C is a knave, so ¬KC is entailed. But A and B swap roles between the two models, so neither KA nor ¬KA is entailed. The logic tells you exactly how much the evidence determines, no more and no less.

Logical equivalences

Two sentences are logically equivalent if they are true in exactly the same models, which is the same as each one entailing the other. Equivalences are the algebra of logic: you rewrite sentences into simpler or more convenient forms without changing their meaning. The important ones:

  • De Morgan: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
  • Implication as disjunction: P → Q ≡ ¬P ∨ Q
  • Contrapositive: P → Q ≡ ¬Q → ¬P
  • Double negation: ¬¬P ≡ P
  • Distribution: P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
  • Biconditional: P ↔ Q ≡ (P → Q) ∧ (Q → P)

Beware two tempting mistakes. The converse Q → P and the inverse ¬P → ¬Q of an implication are not equivalent to it. "If it rains, the street is wet" does not mean "if the street is wet, it rained" (a street cleaner might have passed). The program below tests all of these by brute force, then shows how quickly model checking becomes expensive.

Python Verifying equivalences, and the cost of model checking

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last lines show the catch. The chain x0, x0→x1, x1→x2, ... obviously entails its last symbol, yet model checking has to look at every one of the 2^n models: 64, 1,024 and 16,384 for the three sizes. Add eight symbols and the work multiplies by 256. Propositional entailment is co-NP-complete in general, so no known algorithm avoids exponential worst-case behavior. The next lessons show how to do much better in practice by proving instead of enumerating: resolution and chaining, then clever SAT solvers.

What propositional logic can and cannot say

It is declarative: you state facts and the reasoning machinery is separate. It is compositional: the meaning of a big sentence comes from its parts. It handles partial information, since "P ∨ Q" is a legitimate fact when you don't know which one holds.

But it is also blunt. There are no objects, so to say that every square next to a pit is breezy in a 4 by 4 grid you must write a separate sentence for each of the 16 squares. There are no variables and no quantifiers ("all", "some"). Time is awkward too: "the agent is at (1,1)" is true now and false later, and each time step needs its own symbols. Those limits motivate first-order logic at the end of the chapter.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. In which model is the implication P → Q false?

    An implication is only false when its premise is true and its conclusion is false. When P is false it is true whatever Q is.
  2. 2. What does KB ⊨ α mean?

    Entailment means the models of the KB are a subset of the models of α, so α can never be false while the KB is true.
  3. 3. A sentence is true in 0 of its 4 models. What is it called?

    A sentence that is true in no model is unsatisfiable (a contradiction), such as P ∧ ¬P.
  4. 4. Which sentence is logically equivalent to P → Q?

    The contrapositive ¬Q → ¬P is equivalent. The converse and the inverse are not, and P ∧ ¬Q is the negation of the implication.
  5. 5. Why is simple model checking impractical for large knowledge bases?

    The number of models doubles with every added symbol, so enumerating them becomes infeasible long before a real knowledge base is complete.

Summary

  • Propositional logic builds sentences from symbols and the connectives ¬, ∧, ∨, →, ↔.
  • A model assigns true or false to every symbol; a truth table lists a sentence's value in all models.
  • Sentences can be valid, satisfiable or unsatisfiable; P → Q is false only when P is true and Q is false.
  • KB ⊨ α means α holds in every model of the KB; equivalently, KB ∧ ¬α is unsatisfiable.
  • Equivalences such as De Morgan's laws and the contrapositive let you rewrite sentences; the converse and inverse are not equivalent.
  • Model checking is simple and correct but costs 2^n; later lessons use proofs and SAT solvers instead.

Next: Inference: Resolution, Horn Clauses and Forward/Backward Chaining.