SAVITRIBAI PHULE PUNE UNIVERSITY

Artificial Intelligence
Artificial Intelligence & Data Science
Third Year (2019 Pattern)

Unit-4 (NOTES)
 Unit IV: Knowledge
1. Logical Agents
Definition

A Logical Agent is a type of intelligent agent that makes decisions by using explicit
knowledge about the world, represented in a formal language called logic. These agents
maintain a knowledge base (KB) of logical sentences and use logical inference to derive
new facts and choose appropriate actions. The core principle is that the agent 'thinks' by
reasoning over its stored knowledge to achieve its goals.

Detailed Explanation

●​ Knowledge Representation: The world's state, rules, and constraints are encoded
as logical sentences (e.g., "The street is wet ⟺ it rained").
●​ Inference Mechanism: The agent uses a logical inference mechanism (or theorem
prover) to deduce conclusions from its existing knowledge base.
●​ Rational Decisions: The inferred conclusions help the agent determine the most
rational action that maximizes its performance measure in the current
environment.
●​ Declarative Approach: Logical agents operate on a declarative approach, where
the agent is simply told what is true, and the inference process figures out the
consequences.

Mathematical / Technical Aspect

The state of the knowledge base (KB) and the decision-making process can be
summarized by two primary functions:

●​ TELL(KB,sentence): Adds a new sentence to the knowledge base.

●​ ASK(KB,query): Checks if a query is entailed by the knowledge base. This is
formally represented as: KB⊨query (KB entails query).

Real-World Examples
 1.​ Medical Diagnosis Systems: A system that has knowledge about symptoms and
diseases (e.g., "If patient has fever AND cough, then patient has flu"). It uses logic to
infer the most likely disease given a patient's symptoms.
2.​ Configuration Software: Programs used to configure complex products (like a
custom computer or car). They use logical rules (e.g., "If Graphics Card is 'A', then
Power Supply must be ≥600W") to ensure all selected components are compatible.
3.​ Database Query Optimization: Advanced database systems use logical agents to
optimize complex SQL queries by applying inference rules to find the most
efficient execution path.

Applications

●​ Expert Systems: Building systems that emulate the decision-making ability of a

human expert.
●​ Formal Verification: Proving the correctness of hardware and software designs.
●​ Intelligent Tutoring Systems: Adapting educational content based on logical rules
derived from a student's performance and knowledge state.

Important Notes / Key Takeaways

●​ The primary challenge is computational complexity of inference, especially in

expressive logics.
●​ Soundness means the inference system derives only true conclusions from true
premises.
●​ Completeness means the inference system can derive every sentence that is
logically entailed by the knowledge base.

2. Knowledge-Based Agents
Definition

A Knowledge-Based Agent (KBA) is a general framework for agents that reason. It stores
its knowledge in a formal language within a Knowledge Base (KB) and employs an
inference mechanism to derive new knowledge from what it perceives and already
knows. This structure allows the agent to reason about the world and act rationally by
explicitly managing and manipulating symbolic representations of information.

Detailed Explanation

●​ Architecture: The agent's architecture separates the knowledge (the KB) from the
reasoning engine (the inference mechanism).
●​ Percepts and Actions: The agent receives percepts from the environment, tells the
KB about the percepts, and asks the KB what action to perform.
●​ KBS⊨Action: The agent chooses the action a such that the current knowledge base
KB logically entails that a is the right action to perform.
●​ Level of Abstraction: KBAs operate at a high level of abstraction, using symbolic
representations that are closer to human thought than simple numeric functions.

Mathematical / Technical Aspect

The operation of a KBA often involves a generic function:

Agent(Percept):Action

The internal workings rely on a sequence of updates and queries:

1.​ TELL(KB,MakeSentence(Percept))
2.​ Action←ASK(KB,MakeQuery(Percept))
3.​ TELL(KB,MakeSentence(Action))

Real-World Examples

1.​ Automated Planning Systems: Used to schedule complex sequences of tasks (e.g.,
robotic assembly). The KB contains knowledge about the robot's capabilities and
the state of the workspace.
2.​ Rule-Based Financial Advisers: Systems that recommend investments based on a
client's risk profile and logical rules about market conditions.
3.​ Semantic Web Applications: Using ontologies (formal knowledge structures) to
understand the meaning of data and perform intelligent searches and linkages.

Applications
 ●​ Automated Theorem Proving: Developing programs that can prove mathematical
theorems from a set of axioms.
●​ Cognitive Modeling: Creating models of human thought and reasoning processes.
●​ Robotics: Allowing robots to reason about their environment, potential risks, and
required steps to complete a task.

Important Notes / Key Takeaways

●​ The knowledge level is distinct from the implementation level; one describes what
the agent knows, the other how that knowledge is processed.
●​ A KBA is defined by the knowledge it contains, not just the way it processes
information.
●​ The agent's success is highly dependent on the completeness and accuracy of the
initial knowledge base.

3. The Wumpus World

Definition

The Wumpus World is a classic, illustrative example in Artificial Intelligence used to

demonstrate the functionality of Logical Agents operating in a partially observable and
non-deterministic environment. It is a simple grid-world environment where an agent
(often a human or a robot) must navigate a dangerous cave to find gold, while avoiding
pitfalls and a deadly creature known as the Wumpus. The agent uses logic to infer the
location of hidden dangers from indirect percepts.

Detailed Explanation

●​ Environment: A 4×4 grid of rooms. The agent starts in (1,1).

●​ Dangers: Pits (which cause instant death) and the Wumpus (which can eat the
agent).
●​ Percepts (Sensors):
○​ Stench: Indicates the Wumpus is nearby (in an adjacent room).
○​ Breeze: Indicates a Pit is nearby (in an adjacent room).
○​ Glitter: Indicates the Gold is in the current room.
 ○​ Scream: Indicates the Wumpus has been killed.
○​ Bump: Indicates the agent has moved into a wall.
●​ Goal: Find the gold and return to the starting position without being killed,
maximizing the score.

Mathematical / Technical Aspect

The Wumpus World is used to illustrate logical inference using Propositional Logic:

●​ Px,y​: "A pit is at (x,y)."

●​ Bx,y​: "A breeze is felt at (x,y)."
●​ The fundamental rule is: B1,2​⟺(P1,1​∨P1,3​∨P2,2​)
○​ This formula states that a breeze is felt at (1,2) if and only if there is a pit in
one of its adjacent rooms.

Real-World Examples

1.​ Mine Sweeping: A logical agent (the human player or an AI) uses local cues
(numbers on cells) to infer the location of global dangers (mines).
2.​ Chemical Spill Cleanup: A robot must enter a hazardous zone. It uses local sensor
readings (e.g., elevated temperature, unusual gas) to logically infer the location and
type of a non-directly observable source of danger.
3.​ Fault Diagnosis in Power Grids: Engineers use readings from various points in the
grid (e.g., low voltage in certain areas) to logically deduce the location of a single,
unobservable fault (e.g., a broken transmission line).

Applications

●​ Teaching Tool: It is the primary pedagogical example for demonstrating logical

inference and search algorithms in AI.
●​ Autonomous Navigation: Developing robots that can navigate unknown
environments and make safe, logical deductions about hidden obstacles or dangers.
●​ Model-Based Reasoning: Demonstrating how an agent can build and use a model
of the world (the map, the rules) to reason and act.

Important Notes / Key Takeaways

 ●​ The Wumpus World highlights the difference between sensing (local information)
and reasoning (global inference).
●​ The core lesson is that the agent must often deal with uncertainty and make
decisions based on what is most likely or guaranteed to be safe.
●​ The agent uses proof by contradiction (e.g., if assuming P2,2​is true leads to a
contradiction with the percepts, then P2,2​must be false).

4. Logic
Definition

Logic in AI is a formal system used for knowledge representation and reasoning. It

provides a precise, unambiguous language for expressing knowledge about the world and
a set of inference rules for determining what logically follows from that knowledge.
Logic allows an AI agent to represent facts symbolically and use computational
procedures to draw valid conclusions.

Detailed Explanation

●​ Syntax: Defines the permissible structure of sentences in the language (e.g., how to
combine symbols and operators).
●​ Semantics: Defines the meaning of sentences, specifying the conditions under
which a sentence is considered true or false in a particular world (or model).
●​ Inference Rules: These are the mechanical procedures used to construct new true
sentences from existing true sentences.
●​ Soundness and Completeness: A good logical system is both sound (only true
conclusions are derived) and complete (all true conclusions can be derived).

Mathematical / Technical Aspect

The central concept is logical entailment (⊨).

KB⊨α

This expression means that in all models where the Knowledge Base (KB) is true, the
sentence α is also true. This is the definition of a query being logically proven.
Real-World Examples

1.​ Software Specification: Using formal logic (like Z notation or temporal logic) to
precisely define what a software program is supposed to do before writing the
code.
2.​ Legal Reasoning: Analyzing laws and cases, which are structured logically, to
determine the necessary and sufficient conditions for a verdict.
3.​ Automated Debugging: Logic programming tools (like Prolog) can use logical rules
to trace back why a system is in a certain state, effectively debugging the system.

Applications

●​ Logic Programming (Prolog): A programming paradigm based entirely on logical

inference.
●​ Constraint Satisfaction Problems (CSPs): Many problems like scheduling and
resource allocation are modeled and solved using logical constraints.
●​ Hardware Verification: Logically proving that a chip design satisfies its
specifications before fabrication.

Important Notes / Key Takeaways

●​ Logic is declarative (it states facts) rather than procedural (it states steps).
●​ The expressiveness of a logic (e.g., Propositional vs. First-Order) dictates the
complexity of the inference process.
●​ The fundamental distinction is between syntax (form) and semantics (meaning).

5. Propositional Logic: A Very Simple Logic

Definition

Propositional Logic (PL) is the simplest formal logic system, where the basic unit of
representation is the proposition. A proposition is a declarative sentence that is either
definitively True (T) or False (F). PL allows for the combination of these simple
propositions using logical connectives (∧,∨,¬,⟹,⟺) to form complex sentences. It is
limited because it cannot express general rules or relationships between objects.
Detailed Explanation

●​ Atomic Sentences (Propositions): Simple, indivisible statements (e.g., "The sun is

shining"). Represented by symbols like P,Q,R.
●​ Logical Connectives: Used to build complex sentences from atomic ones:
○​ Negation (¬): NOT (e.g., ¬P).
○​ Conjunction (∧): AND (e.g., P∧Q).
○​ Disjunction (∨): OR (e.g., P∨Q).
○​ Implication (⟹): IF...THEN (e.g., P⟹Q).
○​ Biconditional (⟺): IF AND ONLY IF (e.g., P⟺Q).
●​ Truth Tables: The meaning (semantics) of PL is defined entirely by truth tables,
which specify the truth value of a complex sentence for every possible assignment
of truth values to its atomic propositions.

Mathematical / Technical Aspect

The semantics of the connectives are defined by truth tables. For example, the truth
table for Conjunction (∧): | P | Q | P∧Q | | :---: | :---: | :---: | | T | T | T | | T | F | F | | F | T | F |
|F|F|F|

A general sentence α is satisfiable if there exists at least one model (truth assignment)
where it is true. A sentence is valid (a tautology) if it is true in all models.

Real-World Examples

1.​ Traffic Light Logic: "If the light is Red (R), then stop (S)." R⟹S.
2.​ Simple Access Control: "You can enter the building (E) if you have a Keycard (K)
AND it is a Business Day (B)." K∧B⟹E.
3.​ Weather Forecasting (Simple): "It will rain (R) OR it will be sunny (S). It will NOT be
both." R∨S and ¬(R∧S).

Applications

●​ Boolean Algebra: The foundation of all digital circuit design and computer
hardware.
●​ Simple Diagnosis Systems: Modeling straightforward cause-and-effect
relationships without needing to quantify objects.
 ●​ Teaching Logic: Used as the initial formal system to introduce concepts like
entailment and logical equivalence.

Important Notes / Key Takeaways

●​ PL is monotonic: Adding new knowledge never invalidates old conclusions.

●​ PL is declarative and context-independent.
●​ Its primary limitation is lack of expressiveness—it cannot talk about objects,
properties, or relations in a general way (e.g., "All cats have fur").

6. Propositional Theorem Proving

Definition

Propositional Theorem Proving is the process of algorithmically determining whether a

given sentence (α) is logically entailed by a knowledge base (KB) consisting of
Propositional Logic sentences. This is achieved by either checking all possible truth
assignments (model checking) or by applying inference rules to transform the KB until
the query α is derived.

Detailed Explanation

●​ Proof by Entailment: We are trying to prove KB⊨α.

●​ Two Main Methods:
○​ Model Checking (e.g., Truth Table Enumeration): Check if α is true in every
model where KB is true. This is sound and complete, but computationally
very expensive (O(2n) where n is the number of propositions).
○​ Inference Rules (e.g., Resolution): Apply a set of inference rules (like Modus
Ponens or Resolution) to the KB until α is generated.
●​ Proof by Refutation: This is a common strategy, especially with Resolution. To
prove KB⊨α, one checks if the sentence KB∧¬α is unsatisfiable (i.e., leads to a
contradiction).

Mathematical / Technical Aspect

Resolution Rule (General Form)

Given two clauses (disjunctions of literals):

(set-difference)∪(set-difference)l1​∨…∨lk​m1​∨…∨mn​​

If li​and mj​are complementary literals (i.e., li​=¬mj​), the rule produces a new clause called
the resolvent.

Example of Modus Ponens:

QP⟹QP​

Real-World Examples

1.​ Formal Verification of Circuits: Proving (or disproving) that a digital circuit's
behavior (KB) is consistent with its design specification (α).
2.​ Constraint Logic Programming: Systems like Prolog use theorem proving
algorithms (usually resolution) to answer queries posed to a database of logical
facts and rules.
3.​ Basic Diagnostic Systems: Using inference rules to quickly deduce a likely fault
(theorem) from a set of observed symptoms (KB).

Applications

●​ Automated Reasoning Systems: The core engine for many AI systems that need to
deduce consequences from facts.
●​ Logic-based Puzzles: Solving puzzles like Sudoku or nonograms by representing
the rules as a KB and the solution as the proven theorem.
●​ Knowledge Consistency Check: Using theorem proving to ensure that a knowledge
base does not contain contradictory information (i.e., that KB⊨False is not
provable).

Important Notes / Key Takeaways

●​ Completeness and Soundness: Resolution is a complete and sound inference rule

for Propositional Logic.
●​ Computational Bottleneck: Theorem proving in PL is in the complexity class
co-NP-complete, meaning it can become computationally intractable for large KBs.
●​ Conjunctive Normal Form (CNF): Resolution requires all sentences to be converted
into CNF, which is a conjunction of clauses (e.g., (¬P∨Q)∧(R∨¬S)).
7. Effective Propositional Model Checking
Definition

Effective Propositional Model Checking refers to the techniques and algorithms

designed to efficiently determine the truth value of a Propositional Logic sentence by
systematically searching the space of possible models (truth assignments). Since the
number of models grows exponentially (2n), "effective" methods employ smart search
strategies to avoid examining the entire space, thus improving performance over simple
truth-table enumeration.

Detailed Explanation

●​ Model vs. Entailment: Model checking directly searches for a model that satisfies a
sentence, whereas inference rule-based proving searches for a sequence of logical
steps.
●​ Search Algorithms: The search for a satisfying model is often formulated as a
Constraint Satisfaction Problem (CSP).
●​ DPLL Algorithm (Davis-Putnam-Logemann-Loveland): The most famous and
effective algorithm for the SAT (Satisfiability) Problem. It is a complete,
backtrack-based search that incorporates heuristics and pruning techniques.
○​ Unit Clause Heuristic: If a clause has only one unassigned literal, assign the
value that makes the clause true (a forced assignment).
○​ Pure Symbol Heuristic: If a symbol always appears with the same sign (e.g.,
always positive, never negative) across all remaining clauses, assign the value
that makes that symbol true.
●​ WALKSAT Algorithm: An incomplete, local-search algorithm that starts with a
random truth assignment and iteratively flips the assignment of a variable to
reduce the number of unsatisfied clauses. It is often faster than complete
algorithms for very large, random SAT problems, though it cannot prove
unsatisfiability.

Mathematical / Technical Aspect

The core problem being solved is SAT (Satisfiability).

Given a PL sentence α in CNF, is there a truth assignment for the propositional variables
that makes α true?

If a sentence α is unsatisfiable, the model checking algorithm will terminate without

finding a satisfying assignment.

Real-World Examples

1.​ Hardware Verification (again): Model checking is crucial for verifying modern
integrated circuits, often involving millions of variables. Specialized SAT solvers are
used to prove or disprove complex logical properties.
2.​ Automated Scheduling and Planning: Scheduling tasks (e.g., flight schedules,
factory production) is often encoded as a massive SAT problem and solved
efficiently using DPLL variants.
3.​ Cryptography (Code Breaking): Certain cryptographic attacks can be formulated
as SAT problems, where finding a satisfying assignment corresponds to finding the
secret key.

Applications

●​ SAT Solvers: The foundation of modern automated reasoning and verification

tools.
●​ Planning and Search: Used to generate a sequence of actions that satisfy a goal
state.
●​ AI Puzzles and Games: Finding solutions to complex logic-based puzzles.

Important Notes / Key Takeaways

●​ The SAT Problem is the canonical NP-complete problem. Solving it efficiently is

critical to many AI tasks.
●​ DPLL is a complete algorithm (it will find a solution if one exists, or prove
unsatisfiability).
●​ Local Search (e.g., WALKSAT) is generally incomplete but can be much faster for
highly constrained problems.

8. Agents Based on Propositional Logic

Definition

Agents Based on Propositional Logic (PL-Agents) are a subset of Logical Agents that use
Propositional Logic as their formal language for knowledge representation and
reasoning. Due to the limitations of PL, these agents are typically suitable only for
environments that are fully observable, deterministic, static, and small, or for tasks that
require only simple, propositional-level inferences like the Wumpus World.

Detailed Explanation

●​ Knowledge Base: The KB consists of sentences that map percepts to states and
states to actions using propositional variables (e.g., Breeze1,2​⟹Pit1,1​∨Pit1,3​∨Pit2,2​).
●​ Action Determination: The agent uses a theorem prover to infer a specific action
At​at time t by asking the query: KB∧Perceptt​⊨Actiont​.
●​ Temporal Reasoning (Limitation): PL struggles with time. To model a changing
world, the agent must use a separate set of propositions for each point in time (e.g.,
Location1,1,t​∧MoveRight⟹Location2,1,t+1​). This leads to a rapidly growing,
unmanageable KB.
●​ Success Conditions: PL-Agents succeed only when the rules of the environment
can be fully and explicitly enumerated in terms of simple propositions.

Mathematical / Technical Aspect

The agent's decision logic involves checking the satisfiability of a constraint on the
action:

Action=argamax​[ASK(KB∧Percepts,Desirable(Result(State,a)))]

Where Desirable(Result(State,a)) represents the logical condition that the state resulting
from action a is a desirable state.

Real-World Examples

1.​ Simple Security System: An agent uses PL to decide if the alarm should sound: "If
the window sensor is tripped (W) AND the house is not disarmed (¬D), THEN sound
the alarm (A)." W∧¬D⟹A.
 2.​ Game AI (Tic-Tac-Toe): A small game can be modeled where each cell at each turn
is a proposition. The winning and blocking moves are determined by checking PL
implications.
3.​ Basic Rule-Based Chatbots: Simple decision-tree chatbots where the conversation
flow is determined by propositional rules (e.g., "If user says 'buy' (B) AND item is
'shoes' (S), THEN show shoe options (O)") B∧S⟹O.

Applications

●​ Building Simple Expert Systems: Modeling shallow knowledge domains with few
objects and simple interactions.
●​ Decision Support Systems: Providing automated, rule-based recommendations.
●​ Educational Demonstrations: Illustrating the principle of logical reasoning in AI.

Important Notes / Key Takeaways

●​ The biggest flaw of PL-Agents is the representational poverty and the explosion of
propositions needed to model a dynamic environment.
●​ PL is generally an inadequate language for environments with multiple objects and
relations between them.
●​ The transition to First-Order Logic (FOL) is necessary to overcome PL's limitations
in expressiveness.

9. First-Order Logic (FOL)

Definition

First-Order Logic (FOL), also known as First-Order Predicate Calculus, is a more

expressive and powerful formal logic system than Propositional Logic. Unlike PL, which
only deals with true/false sentences, FOL allows for the representation of objects, their
properties, and the relationships between them using predicates, functions, and
quantifiers. This capability makes it suitable for representing the complex knowledge
required by real-world intelligent agents.

Detailed Explanation
 ●​ Objects and Relations: FOL explicitly deals with objects (individuals) and
predicates that describe properties of or relations between these objects.
●​ Quantifiers: FOL introduces two critical symbols:
○​ Universal Quantifier (∀): "For all" or "For every" (e.g., ∀x
Cat(x)⟹Mammal(x)).
○​ Existential Quantifier (∃): "There exists" or "There is at least one" (e.g., ∃y
Gold(y)).
●​ Increased Expressiveness: FOL can express general rules that apply to all or some
members of a set, overcoming the limitation of PL which requires enumerating
every specific instance.

Mathematical / Technical Aspect

A typical FOL sentence structure includes:

$$\mathbf{\text{Quantifier} \text{ Variable } \text{ (Sentence)}}$$Example using objects,

predicates, and quantifiers:$$\forall x, y \text{ (Brother}(x, y) \implies \text{Sibling}(x,
y))$$

(For all x and y, if x is the brother of y, then x is the sibling of y).

Real-World Examples

1.​ Family Relationships: "Every person has a father." ∀x∃y Father(y,x).

2.​ General Rules in Science: "All planets orbit a star." ∀p
(Planet(p)⟹∃s(Star(s)∧Orbits(p,s))).
3.​ Database Integrity Constraints: "The age of every employee must be greater than
18." ∀e Employee(e)⟹Age(e)>18.

Applications

●​ Semantic Web and Ontologies: Used to formally define the concepts and
relationships in a domain (e.g., describing all the classes and properties in biology).
●​ Advanced AI Planning: Representing the pre-conditions, actions, and effects of
complex robot movements.
●​ Computational Linguistics: Modeling the underlying logical structure of natural
language sentences.
Important Notes / Key Takeaways

●​ FOL is complete (there exists a complete inference procedure, though it may not
terminate for all valid sentences—it's only semi-decidable).
●​ The primary components are constants (objects), predicates (relations/properties),
functions (mapping objects to objects), and quantifiers.
●​ FOL is the standard representation language for the vast majority of modern
knowledge-based AI systems.

10. Representation Revisited

Definition

The concept of Representation Revisited emphasizes the shift from the simple
propositional view of the world to the richer, more structured, and general view offered
by First-Order Logic (FOL). It highlights how FOL allows for a more compact and
meaningful encoding of knowledge by directly addressing the shortcomings of
Propositional Logic, primarily its inability to express general laws and relationships
concisely.

Detailed Explanation

●​ PL's Limitations (Review): PL requires a separate proposition for every fact

instance across space and time (e.g., Breeze1,1,t1​​,Breeze1,1,t2​​,…). This leads to a
massive, unmanageable KB.
●​ FOL's Solution (The Power of Generalization): FOL uses variables and quantifiers
to state general rules once.
○​ Instead of: (Pit1,1​⟹¬Safe1,1​)∧(Pit1,2​⟹¬Safe1,2​)∧…
○​ We write: ∀x,y Pit(x,y)⟹¬Safe(x,y)
●​ Functions for Objects: FOL uses functions to map objects to other objects (e.g.,
Mother(John) returns the object corresponding to John's mother), which is
impossible in PL.

Mathematical / Technical Aspect

The move from PL to FOL replaces atomic propositions (like P) with predicates (like
Brother(John,Mary)) and introduces the ∀ and ∃ quantifiers.

●​ PL Sentence: Pit1​⟹¬Safe1​(Specific)
●​ FOL Sentence: ∀x(Pit(x)⟹¬Safe(x)) (General)

Real-World Examples

1.​ Library Cataloging:

○​ PL approach: Book1_is_Fiction, Book2_is_Fiction, Book3_is_Fiction, …
○​ FOL approach: ∀b Book(b)∧Genre(b,Fiction)⟹LocatedIn(Aisle,5).
2.​ Manufacturing Rules:
○​ PL approach: If PartA has Defect1, then Reject. If PartB has Defect1, then
Reject. …
○​ FOL approach: ∀p,d HasDefect(p,d)⟹Reject(p).
3.​ Game Physics:
○​ PL approach: Ball1_is_Heavy, Ball2_is_Heavy, …
○​ FOL approach: ∀b Ball(b)∧Heavy(b)⟹Acceleration(b) is Low.

Applications

●​ Scaling AI Systems: Enabling knowledge bases to handle thousands of objects

without requiring exponentially increasing numbers of rules.
●​ Formal Specification: Clearly defining the meaning of terms in large systems.
●​ Natural Language Understanding: Providing the formal mechanism to translate
the structure of human language into a form computers can reason with.

Important Notes / Key Takeaways

●​ The primary gain is expressive power and conciseness.

●​ FOL allows the agent to reason about categories of objects, not just individual
named instances.
●​ The cost of this power is that FOL inference is more complex and less
straightforward than PL model checking.

11. Syntax and Semantics of First-Order Logic

Definition

The Syntax of First-Order Logic (FOL) defines the grammar for constructing
well-formed sentences using symbols like constants, predicates, functions, and logical
connectives. The Semantics of First-Order Logic defines the meaning of these
sentences by specifying how the truth of a sentence is determined in an interpretation
(or model), which involves mapping the symbols to objects, properties, and relations in
the world.

Detailed Explanation

●​ Syntax Components:
○​ Terms (Refer to objects): Can be Constants (KingJohn), Variables (x), or
Functions (e.g., LeftLegOf(John)).
○​ Atomic Sentences (Refer to facts): Formed by a Predicate and its arguments
(terms) (e.g., Brother(Richard,John)).
○​ Complex Sentences: Formed by combining atomic sentences using PL
connectives (∧,∨,¬,⟹,⟺) and Quantifiers (∀,∃).
●​ Semantics (Interpretation/Model):
○​ A Model specifies: a set of objects (the domain), and a mapping
(interpretation) of:
1.​ Constants to objects in the domain.
2.​ Predicate symbols to relations on the domain.
3.​ Function symbols to functions on the domain.
○​ A sentence is true in a model if the relation/property it asserts holds true in
the domain under the given interpretation.

Mathematical / Technical Aspect

The truth of a quantified sentence is defined recursively:

●​ ∀xα is true in a model M if and only if α is true for every possible assignment of
the variable x to an object in the domain.
●​ ∃xα is true in a model M if and only if α is true for at least one assignment of the
variable x to an object in the domain.

Real-World Examples
 1.​ Programming Language Grammar: The formal syntax of C++ defines how code
must be structured. The semantics define what the code actually does when
executed.
2.​ Recipe: The recipe's structure (ingredients list, steps) is its syntax. The actual taste
and result of the cooked food is its semantics.
3.​ Formal Contracts: The legal phrasing and structure of the contract is the syntax.
The actual consequences and obligations defined by the contract are the
semantics.

Applications

●​ AI Knowledge Engineering: Ensuring that the way knowledge is written (syntax)

accurately captures the intended meaning (semantics).
●​ Logic Programming: The underlying framework for how logic programs are
constructed and executed.
●​ Model Theory: The mathematical study of the relationship between formal
languages and their interpretations.

Important Notes / Key Takeaways

●​ A sentence is valid if it is true in all possible models.

●​ A sentence is satisfiable if it is true in at least one model.
●​ The domain of discourse (the set of objects) is a critical part of the FOL semantics.

12. Using First-Order Logic

Definition

Using First-Order Logic (FOL) refers to the practical application of the FOL formalism
for the purpose of constructing a knowledge base, querying it, and deriving conclusions
in an automated way. This involves three steps: Telling (asserting facts and rules into the
KB), Asking (posing questions to the KB), and Inferring (using sound and complete
procedures like Unification and Resolution to answer the queries).

Detailed Explanation
 ●​ Knowledge Acquisition: The process of translating real-world knowledge (e.g., "The
gold is portable") into valid FOL sentences (e.g., Portable(Gold)).
●​ Inference as an Answer: To answer a query Q, the system attempts to prove the
entailment KB⊨Q.
○​ If the proof succeeds, the answer is "Yes, it is true."
○​ If the system uses generalized Modus Ponens, it can also provide the
substitution that makes the query true (e.g., Location(Wumpus,Who)?
→Who=[1,3]).
●​ The Problem of Identity: FOL introduces the ability to state that two terms refer to
the same object using the equality predicate, =(x,y), which adds complexity to
inference.

Mathematical / Technical Aspect

The key mechanism that enables FOL inference is Unification.

UNIFY(p,q)=θ

UNIFY takes two sentences or terms, p and q, and returns a substitution θ (a set of
variable assignments) such that when θ is applied to both p and q, they become identical.
Example: UNIFY(Knows(John,x),Knows(John,Mary)) returns θ={x/Mary}.

Real-World Examples

1.​ Prolog Programming: A declarative programming language where programs are

collections of FOL sentences (Horn clauses) and execution is FOL inference.
2.​ Deductive Databases: Databases that can store not just facts, but also rules,
allowing for complex, logical querying beyond simple SQL.
3.​ Automated Geometric Theorem Proving: Using FOL to represent geometric
axioms and proving complex theorems (e.g., "The angle bisectors of a triangle
intersect at a single point").

Applications

●​ Reasoning under Uncertainty: While FOL is deterministic, it is often combined

with probabilistic methods (like Markov Logic Networks) for more complex
reasoning.
●​ Information Extraction: Logically deducing new facts from unstructured text data.
 ●​ Planning and Diagnostics: Automated systems for figuring out a sequence of steps
to achieve a goal.

Important Notes / Key Takeaways

●​ Unification is the essential pattern-matching algorithm for FOL inference.

●​ FOL inference procedures are sound, but only semi-decidable—a proof will
eventually be found if the sentence is entailed, but the process may not halt if the
sentence is not entailed.
●​ A core difficulty in using FOL is the scaling of the inference process, though
modern theorem provers are highly optimized.

13. Knowledge Engineering in First-Order Logic

Definition

Knowledge Engineering in First-Order Logic (FOL-KE) is the practical discipline of

building an effective knowledge base for a specific domain using First-Order Logic. It
involves identifying the concepts, objects, properties, and relationships within a domain
and then formally encoding them as a set of logical axioms (rules and facts) that can
support automated reasoning and problem-solving by a logical agent.

Detailed Explanation

●​ The Cycle of Knowledge Engineering:

1.​ Identify the Task: Determine what the agent needs to know to solve the
problem (e.g., play chess, diagnose a fault).
2.​ Assemble Relevant Knowledge: Gather the necessary facts, rules, and
constraints.
3.​ Decide on Vocabulary (Ontology): Choose constants, functions, and
predicates (the symbols) to represent the domain.
4.​ Encode General Knowledge: Write the logical axioms (rules) that define the
relationships between the symbols.
5.​ Encode Specific Problem Instance: Add the initial facts for the current
situation.
 6.​ Query and Debug: Test the KB by posing queries and refining the axioms if
incorrect conclusions are drawn.
●​ Choosing Predicates and Functions: This is the most creative and crucial step,
determining the level of detail and abstraction in the KB.

Mathematical / Technical Aspect

A knowledge base for a specific domain (like the Wumpus World) is a conjunction of all
the logical axioms (Ai​):

$$\mathbf{KB = A_1 \land A_2 \land A_3 \land \ldots}$$Each axiom is a statement
about the world, often universally quantified implications:$$\forall c \text{ (Car}(c) \land
\text{RequiresMaintenance}(c) \implies \text{Broken}(\text{Engine}(c)))$$

Real-World Examples

1.​ Designing a Medical Diagnostic Expert System:

○​ Axioms: Rules linking symptoms (predicates) to diseases (predicates).
○​ Example: ∀p (Patient(p)∧HasFever(p)∧HasCough(p)⟹HasFlu(p)).
2.​ Building a Geographic Information System (GIS) Ontology:
○​ Axioms: Rules defining what constitutes a city, river, or mountain, and their
spatial relationships.
○​ Example: ∀x,y (City(x)∧Borders(x,y)∧River(y)⟹LocatedNear(x,y)).
3.​ Formalizing Corporate Policy:
○​ Axioms: Rules about employee access rights, vacation approvals, and budget
limits.
○​ Example: ∀e,d,a (Employee(e)∧InDept(e,d)∧Action(a)⟹Permitted(e,a,d)).

Applications

●​ Building Ontologies: Creating formal conceptualizations of domains for AI systems

(e.g., OWL, the Web Ontology Language, is based on FOL principles).
●​ Expert System Development: The foundational process for creating all rule-based
expert systems.
●​ Cognitive Science Modeling: Formalizing theories of human knowledge and
reasoning.

Important Notes / Key Takeaways

 ●​ The most difficult step is Knowledge Acquisition—getting the information out of
human experts and into a formal, logical representation.
●​ A good vocabulary is expressive (can say everything necessary) and convenient
(makes writing axioms easy and natural).
●​ The final test of knowledge engineering is querying—does the KB answer the right
questions correctly?

Summary Table for Revision

Main Topic Brief Definition (3-4 sentences) 3 Real-World Example
Name

Logical An intelligent agent that uses explicit knowledge, Medical Diagnosis Systems;
Agents represented in a formal logic, to make decisions. It Configuration Software; Database
maintains a Knowledge Base (KB) and employs an Query Optimization.
inference mechanism to derive conclusions and
choose rational actions. This framework allows the
agent to 'think' by reasoning over its stored
symbolic representations of the world.

Knowledge-Ba A general framework for agents whose reasoning Automated Planning Systems;
sed Agents is based on a structured body of knowledge (the Rule-Based Financial Advisers;
KB) and an inference mechanism. Its architecture Semantic Web Applications.
separates the domain knowledge from the
reasoning process, allowing for reasoning about
percepts, states, and actions at a high, symbolic
level.

The Wumpus A classic grid-world environment used to illustrate Mine Sweeping Game; Chemical Spill
World logical agents operating with partial observability. Cleanup; Fault Diagnosis in Power
The agent uses logic to infer the location of hidden Grids.
dangers (Pits and Wumpus) from local percepts
like Stench and Breeze to find gold safely.

Propositional The simplest formal logic where the basic unit is a Traffic Light Logic; Simple Access
Logic (PL) proposition, which is strictly true or false. Control Systems; Simple Weather
Propositions are combined using connectives Forecasting Models.
(∧,∨,⟹) to form complex sentences. PL's
semantics are defined by truth tables, but it lacks
the power to express general rules about objects.
Propositional The process of algorithmically proving that a Formal Verification of Digital Circuits;
Theorem sentence (α) is logically entailed by a knowledge Constraint Logic Programming
Proving base (KB). Methods include complete Model (Prolog); Basic Diagnostic Systems.
Checking (like Truth Table Enumeration) or
applying inference rules, most notably the efficient
and complete Resolution procedure.

First-Order A powerful, expressive logic that allows for the Family Relationship Modeling;
Logic (FOL) representation of objects, their properties General Rules in Scientific Models;
(predicates), and the relationships between them. Database Integrity Constraints.
It uses variables and quantifiers (∀,∃) to state
general laws concisely, overcoming the major
limitations of Propositional Logic.

Knowledge The practical discipline of constructing a robust Designing a Medical Diagnostic

Engineering in and effective First-Order Logic knowledge base for Expert System; Building a Geographic
FOL a specific domain. It involves identifying the Information System (GIS) Ontology;
domain's objects, predicates, and functions, and Formalizing Corporate Policy.
encoding the necessary rules as logical axioms to
enable automated reasoning.