I4 · Problem Solving and Reasoning: Classical AI

Propositional Logic

Propositional logic is a formal language for statements that are either true or false, called propositions, combined with connectives: NOT (¬), AND (∧), OR (∨), IMPLIES (→) and IF AND ONLY IF (↔). A knowledge base is a set of such sentences, and inference derives new sentences that must be true whenever the knowledge base is true, using truth tables or rules such as modus ponens.

12 min Intermediate · Sublevel Intermediate Jump to the activity

What you need: The earlier topics of this module.

Definition

"If it is raining, the ground is wet. The ground is not wet. So…?" You conclude it is not raining, without looking at the sky. Can a computer reason like that, with certainty?

Propositional logic is a formal language for statements that are either true or false, called propositions, combined with connectives: NOT (¬), AND (∧), OR (∨), IMPLIES (→) and IF AND ONLY IF (↔). A knowledge base is a set of such sentences, and inference derives new sentences that must be true whenever the knowledge base is true, using truth tables or rules such as modus ponens.

In simple words

Think of switches that are on or off. "Raining" is one switch; "ground wet" is another. Rules connect them, such as "if raining is on, ground wet must be on". Logic works out which switches must be on or off, given the rules and what you know.

Overview

  • Propositional logic reasons with statements that are either true or false, called propositions.
  • Connectives combine them: NOT (¬), AND (∧), OR (∨), IMPLIES (→) and IF AND ONLY IF (↔).
  • A truth table lists the value of a formula for every combination of truth values.
  • A knowledge base entails a sentence if the sentence is true in every world where the knowledge base is true.
  • Inference rules such as modus ponens derive new facts mechanically.
  • SAT solvers decide whether huge propositional formulas can be satisfied and are used in chip verification and scheduling.

Why it matters

Logic was the foundation of early AI and remains essential wherever conclusions must be guaranteed: verifying chip designs and software, configuring products, checking rules and building systems that must explain their reasoning exactly.

Key terms

Proposition
A statement that is either true or false, such as "it is raining".
Connective
An operator combining propositions: ¬, ∧, ∨, → and ↔.
Truth table
A table listing a sentence's truth value for every combination of its propositions.
Entailment
KB ⊨ α: α is true in every world where the knowledge base is true.
Modus ponens
From P → Q and P, conclude Q.
Satisfiability (SAT)
Whether some assignment of true/false values makes a sentence true.

Types

Propositional logic has several types of connective and of sentence, and several inference methods. These are the essentials.

1. Logical connectives

The operators NOT, AND, OR, IMPLIES and IFF that build compound sentences.

  • How it works: P ∧ Q is true only when both are true; P ∨ Q when at least one is; P → Q is false only when P is true and Q false; P ↔ Q when both match.
  • Example: "If it rains (R), the match is cancelled (C)": R → C.
  • When to use it: Use them to write rules precisely; the implication's truth table is the one beginners most often get wrong.

2. Tautologies, contradictions and contingent sentences

Tautologies are always true, contradictions always false, and contingent sentences depend on the facts.

  • How it works: A truth table shows which: a tautology has T in every row, a contradiction F in every row.
  • Example: P ∨ ¬P is a tautology; P ∧ ¬P is a contradiction; P ∧ Q is contingent.
  • When to use it: Use them to check whether rules are always valid or whether a knowledge base contains a contradiction.

3. Inference rules

Patterns that derive a true conclusion from true premises: modus ponens, modus tollens, and-elimination and resolution.

  • How it works: Modus ponens: from P → Q and P, conclude Q; modus tollens: from P → Q and ¬Q, conclude ¬P.
  • Example: "If the alarm rings, there is smoke" and "the alarm rings" give "there is smoke".
  • When to use it: Use them to build chains of reasoning in rule-based systems.

4. Normal forms (CNF and DNF)

Standard shapes for formulas: conjunctive normal form is an AND of ORs; disjunctive normal form is an OR of ANDs.

  • How it works: Any formula can be rewritten into CNF using equivalences such as De Morgan's laws and distribution.
  • Example: P → Q becomes ¬P ∨ Q; (A ∨ B) ∧ (¬B ∨ C) is already in CNF.
  • When to use it: Use CNF as the input format for resolution and SAT solvers.

5. Proof methods: model checking, resolution and chaining

Ways to decide entailment: checking every model, deriving a contradiction by resolution, or forward and backward chaining.

  • How it works: Model checking enumerates truth assignments (2ⁿ of them); resolution proves KB ⊨ α by showing KB ∧ ¬α is unsatisfiable; chaining works on Horn clauses in linear time.
  • Example: Forward chaining in a medical rule base from symptoms to possible diagnoses.
  • When to use it: Use chaining for rule-based expert systems and SAT solvers for large combinatorial problems.

Explained in detail

The connectives

PQ¬PP ∧ QP ∨ QP → Q
TTFTTT
TFFFTF
FTTFTT
FFTFFT

The implication P → Q surprises people: it is false only when P is true and Q is false. "If it rains, the match is cancelled" is not broken on a dry day, whatever happens to the match. OR is inclusive in logic: P ∨ Q is true when both are true. These precise meanings are what allow mechanical reasoning, and the rules were set out by George Boole in his 1854 book The Laws of Thought, the origin of the Boolean logic inside every computer.

Inference

A knowledge base entails a sentence if the sentence is true in every possible world where the knowledge base is true. The simplest way to check is model checking: list every combination of truth values, which a truth table does, and confirm. With n propositions there are 2ⁿ rows, which grows quickly. Inference rules are faster: modus ponens says from "P → Q" and "P", conclude "Q"; modus tollens says from "P → Q" and "¬Q", conclude "¬P", exactly the rain argument at the top of this page. Resolution, a single rule that combines clauses, is complete for propositional logic and underlies automated theorem provers.

SAT solvers

  • Satisfiability asks whether any assignment makes a sentence true. It was the first problem proved NP-complete, by Stephen Cook in 1971, so no known algorithm solves every case quickly.
  • Yet modern SAT solvers routinely handle problems with millions of variables, using clever search and learning from conflicts.
  • They verify that microprocessor designs are correct, find bugs in software, plan schedules and even solve hard mathematical questions.
  • Many CSPs can be translated into SAT and solved this way.

Limits

Propositional logic cannot talk about objects in general. To say "every student who passes all subjects is promoted" you would need a separate proposition for every student. It also cannot express degrees of belief: a statement is fully true or fully false. The next page introduces first-order logic, which adds objects and quantifiers, and later pages handle uncertainty with probability and vagueness with fuzzy logic.

How it works

  1. Choose propositions for the basic facts.
  2. Write the rules as sentences with connectives.
  3. Add the facts you observe.
  4. Infer conclusions with truth tables for small cases or rules such as modus ponens.
  5. For large problems, hand the sentences to a SAT solver.

In code

propositional.py
from itertools import product

implies = lambda p, q: (not p) or q

# Knowledge base: Rain -> Wet, Sprinkler -> Wet, and we observe: not Wet
def kb(rain, sprinkler, wet):
    return implies(rain, wet) and implies(sprinkler, wet) and (not wet)

def entails(query):
    worlds = [w for w in product([True, False], repeat=3) if kb(*w)]
    return all(query(*w) for w in worlds), worlds

print("Rain | Sprinkler | Wet | KB true?")
for rain, sprinkler, wet in product([True, False], repeat=3):
    print(f"{rain!s:>5} | {sprinkler!s:>9} | {wet!s:>4} | {kb(rain, sprinkler, wet)}")

ok, worlds = entails(lambda rain, sprinkler, wet: not rain)
print("KB entails 'not Rain'?", ok, " (worlds where KB holds:", worlds, ")")

Output

Rain | Sprinkler | Wet | KB true?
 True |      True | True | False
 True |      True | False | False
 True |     False | True | False
 True |     False | False | False
False |      True | True | False
False |      True | False | False
False |     False | True | False
False |     False | False | True
KB entails 'not Rain'? True  (worlds where KB holds: [(False, False, False)] )

Try it yourself

The dry ground

A rule-based garden assistant knows: "If it rains, the soil is wet" and "If the sprinkler ran, the soil is wet".

Match the connective to its meaning

What does each say?

  • ¬P
  • P ∧ Q
  • P ∨ Q
  • P → Q

Common mistakes

  • Reversing an implication: concluding P from P → Q and Q.
  • Treating OR as exclusive.
  • Using propositional logic where facts are uncertain.

Check yourself

Question 1

1. When is P → Q false?

Question 2

2. From P → Q and ¬Q, you can conclude…

Question 3

3. How many rows does a truth table for 5 propositions have?

Summary

  • Propositional logic combines true/false statements with connectives.
  • Entailment means true in every world where the knowledge base holds; truth tables and rules such as modus ponens check it.
  • SAT solvers scale logic to huge problems, but propositional logic cannot express general rules about objects.

Read it. Now try it yourself.

Open the interactive activity

Finished reading?

Sources: Russell and Norvig, Artificial Intelligence: A Modern Approach (4th edition) · Stanford Encyclopedia of Philosophy: Classical Logic