Logic & Sets for AI
Classical AI reasons. Before a system can search, plan, or satisfy constraints, it needs a way to represent facts and combine them — and that language is propositional logic and set theory. These two tools underpin Knowledge Representation, Constraint Satisfaction, and Planning later in the course.
Propositions and connectives
A proposition is a statement that is either true or false ("it is raining"). You combine them with logical connectives:
- NOT ($\neg P$) — flips the truth value.
- AND ($P \wedge Q$) — true only when both are true.
- OR ($P \vee Q$) — true when at least one is true (inclusive).
- IMPLIES ($P \rightarrow Q$) — "if P then Q".
A truth table lists the result for every combination. The tricky one is implication:
| P | Q | P -> Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
$P \rightarrow Q$ is false only when P is true and Q is false. When P is false, the implication is vacuously true — it makes no claim. ("If it rains, the ground is wet" isn''t violated on a dry, sunny day.)
De Morgan''s laws
Two identities you''ll use constantly when simplifying conditions:
$$\neg(P \wedge Q) \equiv \neg P \vee \neg Q, \qquad \neg(P \vee Q) \equiv \neg P \wedge \neg Q.$$
Negation flips AND to OR and vice versa. "Not (both A and B)" is the same as "not A or not B".
Sets
A set is a collection of distinct elements: $\{1, 2, 3\}$. The core operations:
- Membership ($x \in A$) — is x in the set?
- Union ($A \cup B$) — everything in either.
- Intersection ($A \cap B$) — elements in both.
- Subset ($A \subseteq B$) — every element of A is in B.
Sets model the state space a search explores, the domain of allowed values for a variable in a constraint problem, and the set of legal actions in a plan.
Why logic and sets power AI
Knowledge Representation encodes facts and rules as logical statements, and an inference engine derives new true statements from them. A Constraint Satisfaction problem expresses each variable''s allowed values as a set and its restrictions as logic. Planning describes an action''s preconditions and effects logically. Symbolic reasoning — the heart of classical AI — is logic over sets.
Worked example: evaluating a rule
Suppose a knowledge base holds the rule $(\neg R \rightarrow S)$ — "if it is not raining, the sprinkler is on" — and the facts $R = \text{False}$ (not raining) and $S = \text{False}$ (sprinkler off). Is the rule satisfied?
Evaluate inside-out: $\neg R = \neg\text{False} = \text{True}$, so the rule becomes $\text{True} \rightarrow \text{False}$. From the truth table, true implies false is False — the rule is violated by these facts. An inference engine uses exactly this mechanical evaluation to check which rules hold and to flag contradictions. Change $S$ to True and the rule becomes $\text{True} \rightarrow \text{True} = \text{True}$, and the knowledge base is consistent again.
Common pitfalls
- Implication feels backwards. $P \rightarrow Q$ is true whenever P is false; it only fails on true-P / false-Q.
- Inclusive OR. $P \vee Q$ is true when both are true, not "one or the other exclusively".
- Sets ignore duplicates and order. $\{1,1,2\}$ is just $\{1,2\}$, and $\{1,2\} = \{2,1\}$.
Why this is your on-ramp
Every reasoning module — Knowledge Representation, Constraint Satisfaction, Planning — assumes you can read a logical rule and manipulate sets. Nail truth tables, De Morgan, and the set operations now, and symbolic AI reads like a language you speak.