Artificial intelligence - Logical Foundations and Search

Logical Foundations of Artificial Intelligence Introduction To solve complex problems, artificial intelligence systems need a formal way to represent knowledge and draw conclusions from it. This begins with logic, which provides a systematic framework for representing facts about the world and deriving new facts through inference. The two main approaches—propositional logic and first-order logic—form the foundation for reasoning systems, while specialized inference techniques like resolution enable automated reasoning. Propositional Logic Propositional logic is the simplest form of logical reasoning. It represents knowledge using propositions, which are statements that can be either true or false. Basic Components A proposition is any statement that has a definite truth value. For example, "It is raining" and "The temperature is above 20°C" are both propositions. We typically represent these using symbols like $P$, $Q$, and $R$. Propositions can be combined using logical connectives: AND ($\land$): Both statements must be true. For example, "It is raining AND it is cold" is true only if both conditions hold. OR ($\lor$): At least one statement must be true. "It is raining OR it is windy" is true if either or both conditions hold. NOT ($\neg$): Reverses the truth value. If $P$ is true, then $\neg P$ is false. IMPLIES ($\rightarrow$): A conditional relationship. "$P$ IMPLIES $Q$" means if $P$ is true, then $Q$ must also be true. IF AND ONLY IF ($\leftrightarrow$): Both statements have the same truth value. Limitations While propositional logic is useful for simple reasoning, it has significant limitations. It cannot express relationships between objects or general rules that apply to groups of entities. For instance, you cannot say "all dogs are animals" or "if something is a dog, then it barks." This is where first-order logic becomes necessary. First-Order Logic and Equality First-order logic (also called predicate logic) extends propositional logic by introducing quantifiers, variables, and predicates, allowing us to express complex relationships and general rules. Key Elements Predicates represent relationships or properties. For example, $Dog(x)$ means "$x$ is a dog," and $Parent(x, y)$ means "$x$ is a parent of $y$." Variables (like $x$ and $y$) allow us to refer to arbitrary objects. Quantifiers specify how many objects satisfy a condition: Universal quantifier ($\forall$): "For all" objects. The statement $\forall x. Dog(x) \rightarrow Barks(x)$ means "All dogs bark." Existential quantifier ($\exists$): "There exists" at least one object. The statement $\exists x. Dog(x) \land Smart(x)$ means "There exists at least one dog that is smart." Equality ($=$) allows us to assert that two expressions refer to the same object. For instance, $FatherOf(John) = Robert$ states that Robert is John's father. Expressiveness First-order logic is remarkably expressive. It can represent facts about individuals, general rules, relationships between objects, and even complex logical structures. However, it cannot express statements about all possible properties or rules (which would require second-order logic), and in practice, automated reasoning with first-order logic can be computationally expensive. Logical Inference Inference is the process of deriving new truths from known facts. Rather than storing all possible facts explicitly, we can use inference rules to generate conclusions automatically. Common Inference Rules Modus Ponens is the most fundamental inference rule: $$\text{If we know } P \rightarrow Q \text{ and } P \text{ is true, then } Q \text{ must be true.}$$ For example, if we know "If it rains, the ground is wet" and "It is raining," we can conclude "The ground is wet." Modus Tollens works in reverse: if we know $P \rightarrow Q$ and $Q$ is false, then $P$ must be false. Universal Instantiation allows us to apply universal rules to specific objects. If we know $\forall x. Dog(x) \rightarrow Barks(x)$ and we know $Dog(Fido)$, we can conclude $Barks(Fido)$. Why Inference Matters Rather than explicitly storing "Fido barks," "Buddy barks," "Max barks," and so on for every dog we encounter, we store the general rule and apply it as needed. This makes knowledge representation more efficient and scalable. Resolution and Unification Resolution is a powerful inference technique that can systematically prove statements true or false, and it forms the basis of many automated reasoning systems. How Resolution Works Resolution works by attempting to derive a contradiction. Here's the core idea: To prove that a statement $S$ is true, we assume the opposite ($\neg S$) and show that this leads to a logical contradiction. If $\neg S$ leads to a contradiction, then $S$ must be true. Specifically, resolution repeatedly applies this rule: if we have two clauses that can be combined in a way that eliminates a contradicting term, we produce a new clause. For instance: $$\frac{(P \lor Q), (\neg Q \lor R)}{P \lor R}$$ This says: if we have "either $P$ or $Q$" and "either not $Q$ or $R$," then we can conclude "either $P$ or $R$." We continue applying resolution until we derive the empty clause (a contradiction with no literals), which proves unsatisfiability. If we never reach the empty clause, the original statement cannot be proven. The Role of Unification Resolution becomes much more powerful when combined with unification. In first-order logic, we cannot simply apply modus ponens to general rules—we need a way to find substitutions that make expressions match. Unification is the process of finding a substitution (an assignment of variables to values) that makes two different logical expressions identical. For example, consider: Clause 1: $Dog(Fido)$ Clause 2: $\forall x. Dog(x) \rightarrow Barks(x)$ (which we convert to clauses for resolution) Unification finds that if we substitute $Fido$ for $x$, the general rule becomes specific to Fido, allowing resolution to proceed. Why This Matters Unification enables resolution to work with any substitutions needed to match expressions. Without it, resolution could only work with ground facts (facts with no variables), making it far less powerful. With unification, a single rule can be applied to infinitely many specific cases. Search Techniques in Artificial Intelligence Introduction While logical inference allows us to derive facts from knowledge, search allows us to find solutions to problems by exploring different possible actions and outcomes. AI search techniques range from simple exhaustive approaches to sophisticated methods that use heuristic guidance to find good solutions efficiently. Uninformed Search Methods Uninformed search (also called blind search) explores the space of possible solutions without any guidance about which paths are more promising. These methods differ primarily in the order in which they explore nodes. Breadth-First Search (BFS) Breadth-first search explores all nodes at the current depth level before moving to the next level deeper. Imagine you're searching a tree—BFS looks at all nodes one step away from the start, then all nodes two steps away, and so on. Strengths: Guarantees finding the shallowest solution (optimal for problems where all actions have equal cost) Systematic and complete—will always find a solution if one exists Weaknesses: Requires storing many nodes in memory simultaneously Extremely slow for large search spaces Depth-First Search (DFS) Depth-first search goes as deep as possible along one branch before backtracking to explore other branches. Strengths: Uses less memory than BFS (only needs to store the current path) Can find solutions quickly if they are deep in the tree Weaknesses: May explore very deep branches unnecessarily Does not guarantee finding the shortest solution Can get stuck in infinite loops if not carefully implemented General State-Space Search General state-space search is the overarching framework. It maintains a frontier of nodes to explore and repeatedly: Choose a node from the frontier Check if it's the goal If not, expand it by generating its successors Add successors to the frontier The key difference between BFS and DFS is simply which data structure holds the frontier (a queue for BFS, a stack for DFS). All uninformed methods use this same basic structure. Informed (Heuristic) Search Methods Informed search uses heuristics—estimates of how close we are to the goal—to guide exploration toward promising areas. This makes search far more efficient than uninformed methods. Understanding Heuristics A heuristic is an informed guess about the cost of reaching the goal from a given node. For example, in a navigation problem, the straight-line distance to the destination is a heuristic estimate of the true distance you'll need to travel. Crucially, a good heuristic should: Be easy to compute Provide a reasonable estimate (not random) Never overestimate the true cost (in technical terms, be admissible) Greedy Best-First Search Greedy best-first search selects the next node based solely on the heuristic estimate—it always picks the node that appears closest to the goal. $$\text{Next node} = \arg\minn h(n)$$ where $h(n)$ is the heuristic estimate for node $n$. Strengths: Fast—often finds solutions quickly Uses reasonable memory Weaknesses: Not guaranteed to find the shortest path (or even a solution) Can be fooled by poor heuristics or dead ends Example: In navigation, greedy best-first might take a path that looks closest to the goal but actually leads around an obstacle, while a longer but more direct route exists. A Search A search combines actual path cost with heuristic estimates, evaluating each node using: $$f(n) = g(n) + h(n)$$ where: $g(n)$ is the cost from the start to node $n$ (the actual distance traveled so far) $h(n)$ is the heuristic estimate from node $n$ to the goal A always selects the node with the smallest $f(n)$ value. Why A is Better: Unlike greedy best-first, A accounts for the distance already traveled. This prevents getting lured down expensive paths that merely appear promising. If the heuristic is admissible, A is guaranteed to find the optimal (shortest) path. Practical Impact: A is one of the most widely used search algorithms because it balances optimality (finding the best solution) with practical efficiency. It often explores far fewer nodes than uninformed methods. Adversarial Search Techniques In competitive environments like games, we cannot assume that the world will cooperate with our plans. Instead, we must reason about an opponent trying to defeat us. The Minimax Algorithm Minimax models a two-player game where players alternate turns. The key insight is that: The maximizing player tries to achieve the highest score The minimizing player (the opponent) tries to achieve the lowest score Minimax evaluates positions by assuming both players play perfectly: Assign a value to each terminal position (end-game positions) Work backward through the game tree At maximizing nodes, choose the move leading to the highest value At minimizing nodes, choose the move leading to the lowest value For example, in chess: From our perspective, a position where we're winning has high value Our opponent will try to reach positions with low value (from our perspective) We should choose moves that maximize the minimum value our opponent can force Alpha-Beta Pruning Minimax evaluates the entire game tree, which is computationally expensive. Alpha-beta pruning cuts off branches that provably cannot affect the final decision. The key idea: while evaluating the tree, we track: Alpha ($\alpha$): the best value the maximizer can guarantee so far Beta ($\beta$): the worst value the minimizer can allow so far If at any point $\alpha \geq \beta$, the rest of that branch cannot change the outcome, so we prune it. Impact: Alpha-beta pruning can reduce the number of nodes examined from exponential in the tree depth to exponential in half the depth, making deeper lookahead possible. However, the exact reduction depends on node ordering—examining more promising moves first yields better pruning. Local (Optimization) Search Methods While the previous search methods explore paths systematically, local search takes a different approach: it maintains only a single candidate solution and iteratively improves it by moving to neighboring solutions. When to Use Local Search Local search excels at optimization problems where we want to find the best solution according to some evaluation function, rather than finding any path to a goal. Examples include scheduling, configuration, and many real-world engineering problems. Hill-Climbing Hill-climbing is the simplest local search method: Start with a random candidate solution Evaluate all neighboring solutions (nearby variations) If a neighbor is better, move to it Repeat until no neighbor is better Key Strength: Often finds good solutions quickly. Critical Weakness: Gets stuck in local optima—solutions that are better than all neighbors but not the best overall. For instance, a scheduling algorithm might reach a solution where no single swap improves things, even though many other swaps exist that would lead to better solutions. Simulated Annealing Simulated annealing escapes local optima by sometimes accepting worse moves, especially early in the search: Evaluate neighbors If a neighbor is better, always move to it If a neighbor is worse, accept it with some probability that depends on: How much worse it is A "temperature" parameter that decreases over time $$P(\text{accept worse move}) = e^{-\Delta E / T}$$ where $\Delta E$ is how much worse the move is and $T$ is the temperature. The crucial trick: as temperature decreases, the algorithm becomes more like hill-climbing (accepting only improvements). Early on, when $T$ is high, the algorithm explores widely. Later, when $T$ is low, it focuses on local improvement. Why This Works: By allowing temporary moves away from good solutions, the algorithm can escape shallow local optima and find higher global peaks. The decreasing temperature ensures eventual convergence to the best area found.