AI Lectures: Logical Agents & First-Order Logic

📑 Lecture 06 · pages 1–11 🔖 Knowledge-Based Agents & Wumpus World

1. Knowledge-Based Agents — Core Concepts

Knowledge Base (KB) = set of sentences in a formal language — contains domain-specific facts and rules

🗣️ Why Formal Language?

Fixed alphabet & strict syntactic rules
Well-defined semantics (truth evaluation)
Eliminates ambiguity, context-dependence
Machines can process & reason with it

🏗️ Declarative Approach

Tell it what it needs to know
Ask itself what to do
Knowledge level — what agent knows
Implementation level — data structures & algorithms

Agent = KB + Inference Rules ⇒ New Conclusions

⚙️ Inference Agent vs Reasoning

Inference Agent = the system
Reasoning = the process it performs
Derives implicit knowledge from explicit facts
Uses: Propositional logic, FOL, Rule-based, Probabilistic models

🔄 Inference Agent Core Loop (Exam Critical)

Step	Operation	Purpose
1	`Tell(KB, Make-Percept-Sentence(percept, t))`	Convert raw sensor data at time t to logical sentence; add to KB
2	`action ← Ask(KB, Make-Action-Query(t))`	Query KB for best action (e.g., "safest step to reach gold")
3	`Tell(KB, Make-Action-Sentence(action, t))`	Record chosen action in KB
4	`t ← t + 1`	Increment time counter
5	`return action`	Execute action in environment

Memory trick: Perceive → Ask → Act → Record → Repeat

وكيل المعرفة: قاعدة المعرفة (KB) تخزن جملًا بلغة رسمية (Syntax + Semantics). النهج التقريري: أخبر الوكيل ما يحتاج معرفته، ثم اسأله عما يجب فعله. حلقة الاستدلال: تحويل المدركات → استعلام KB عن الإجراء → تسجيل الإجراء → زيادة العداد الزمني → تنفيذ الإجراء.

📑 Lecture 06 · pages 15–31 🕳️ Wumpus World — Environment & Exploration

2. Wumpus World — Environment Properties (Exam Favorite)

Observable?

No — only local perception

Agent only senses current square (Breeze, Stench, Glitter, Bump, Scream)

Deterministic?

Yes — outcomes exactly specified

Actions have known, predictable results

Episodic?

No — sequential

Current actions affect future states (long-term planning needed)

Static?

Yes — no movement

Wumpus and Pits do not move

Discrete?

Yes

Finite states, finite percepts, finite actions

Single-agent?

Yes — Wumpus is a natural feature

Not an active opponent

📐 Key Wumpus World Rules

Breeze → Pit adjacent Stench → Wumpus adjacent Glitter → Gold in cell Bump → Hit wall Scream → Wumpus killed Wumpus dies if shot Agent dies in pit/Wumpus

⚠️ Exam Trap: Breeze in (1,2) and (2,1) ⇒ No safe actions! This is a classic Wumpus world tight spot. The agent can deduce pits must be in adjacent squares but cannot safely move.

عالم وامبوس: غير قابل للملاحظة الكاملة (إدراك محلي فقط)، حتمي، تسلسلي (ليس عرضيًا)، ثابت، متقطع، وكيل واحد. النسيم = حفرة مجاورة، الرائحة = وامبوس مجاور، اللمعان = ذهب، صوت الموت = قُتل الوامبوس. لا يوجد إجراء آمن إذا كان النسيم في (1,2) و (2,1) معًا.

📑 Lecture 06 · pages 32–48 🧩 Models · Entailment · Propositional Logic

📑 Definition · Core Concept 🧠 What is Logic?

Logic — A Structured Way to Represent Knowledge

📐 Definition of Logic Exam Foundation

Logic is a structured way to represent knowledge using formal languages with precise syntax and semantics. It provides rules for valid reasoning, allowing us to derive new conclusions from existing facts without ambiguity.

📝 Syntax

The grammar/rules for constructing valid sentences. Defines what expressions are allowed in the language.

Example: In propositional logic, "P ∧ Q" is syntactically correct; "∧ P Q" is not.

🌍 Semantics

The meaning of sentences — defines truth conditions relative to possible worlds (models).

Example: "P ∧ Q" is true only when both P and Q are true in the world.

🔍 Inference

The process of deriving new sentences (conclusions) from existing ones while preserving truth.

Example: From "P ⇒ Q" and "P", infer "Q" (Modus Ponens).

💡 Why Logic in AI? Logic provides a declarative approach to knowledge representation — separate what the agent knows from how it reasons. This enables automated reasoning, theorem proving, and intelligent decision-making.

تعريف المنطق: المنطق هو طريقة منظمة لتمثيل المعرفة باستخدام لغات رسمية ذات قواعد نحوية (Syntax) دلالات (Semantics) محددة. يوفر قواعد للاستدلال الصحيح، مما يسمح باستنتاج حقائق جديدة من المعرفة الموجودة بدون غموض. التركيب (Syntax): قواعد تكوين الجمل الصحيحة. الدلالات (Semantics): تحديد معنى الجمل وشروط صدقها. الاستدلال (Inference): عملية اشتقاق استنتاجات جديدة مع الحفاظ على الصدق.

KB |= α

Entailment: In every model where KB is true, α must also be true

🔤 Propositional Logic — Connectives

Negation	¬S	"not S"
Conjunction	S₁ ∧ S₂	"S₁ and S₂"
Disjunction	S₁ ∨ S₂	"S₁ or S₂"
Implication	S₁ ⇒ S₂	"if S₁ then S₂"
Biconditional	S₁ ⇔ S₂	"S₁ if and only if S₂"

🕳️ Wumpus World in Propositional Logic

P_i,j = true if pit in [i,j]
B_i,j = true if breeze in [i,j]
Rule: B_1,1 ⇔ (P_1,2 ∨ P_2,1)
"A square is breezy iff there is an adjacent pit"
3 Boolean choices for pits ⇒ 8 possible models
Model checking proves: KB |= α₁ ("[1,2] is safe")

المنطق: Syntax (قواعد تكوين الجمل)، Semantics (تحديد الصدق)، Model (عالم منظم لتقييم الصدق). الاستلزام: KB |= α إذا كانت α صحيحة في كل نموذج تكون فيه KB صحيحة. المنطق الافتراضي: روابط ¬ ∧ ∨ ⇒ ⇔. في عالم وامبوس: B₁,₁ ⇔ P₁,₂ ∨ P₂,₁. فحص النماذج يثبت أن المربع [1,2] آمن.

📑 Lectures 07–08 · pages 1–18 🌐 First-Order Logic — Objects, Relations, Functions, Quantifiers

4. First-Order Logic (FOL) — Beyond Propositional Logic

🧱 Objects

people, houses, numbers, theories, colors

🔗 Relations

Associations between objects (binary, ternary...)

Example: Brother_of(John, Mike)

📐 Functions

Map input(s) to exactly one output

Example: Father_of(John) = Mike

∀ Universal Quantification (∀) — "For All"

⚠️ ALWAYS use ⇒ with ∀!
✅ Correct: ∀x King(x) ⇒ Person(x)
❌ Wrong: ∀x King(x) ∧ Person(x) — This means "Everything is both a king and a person"

∃ Existential Quantification (∃) — "There Exists"

⚠️ ALWAYS use ∧ with ∃!
✅ Correct: ∃x Crown(x) ∧ OnHead(x, John)
❌ Wrong: ∃x Crown(x) ⇒ OnHead(x, John) — Logically too weak; true even if no crown exists!

🔄 Nested Quantifiers — Order Matters!

`∀x ∃y Loves(x,y)`	Everybody loves somebody
`∃y ∀x Loves(x,y)`	There is someone loved by everyone

¬ Quantifier Negation (De Morgan for FOL)

¬∀x P ≡ ∃x ¬P | ¬∃x P ≡ ∀x ¬P

"Not everyone likes math" ≡ ∃x ¬Likes(x, Math)
"Nobody likes parsnips" ≡ ∀x ¬Likes(x, Parsnips) ≡ ¬∃x Likes(x, Parsnips)

= Equality (=)

Father(John) = Henry
Richard has at least two brothers:
∃x,y Brother(x, Richard) ∧ Brother(y, Richard) ∧ ¬(x = y)

📋 FOL Syntax — Complete Reference

Sentence → AtomicSentence | ComplexSentence

AtomicSentence → Predicate | Predicate(Term,...) | Term = Term

Term → Function(Term,...) | Constant | Variable

Constant: A | X₁ | John | ... Variable: a | x | s | ...

Operator Precedence: ¬, =, ∧, ∨, ⇒, ⇔

FOL: كائنات، علاقات، دوال. المحمول الكلي ∀ يستخدم مع ⇒ (كل ملك هو شخص). المحمول الوجودي ∃ يستخدم مع ∧ (يوجد تاج على رأس جون). الترتيب مهم في المحمولات المتداخلة. ¬∀x P ≡ ∃x ¬P. المساواة = للتعبير عن التميز.

📑 Lecture 08 · pages 12–18 🖼️ Frame Problem & Successor-State Axioms

5. The Frame Problem — A Central AI Challenge

🎯 Definition

Difficulty of representing what does NOT change after an action

After Grab: position, pits, Wumpus, walls, breeze — all unchanged
In classical logic: must explicitly state every non-change
Leads to combinatorial explosion

❌ Effect Axiom (only changes)

∀s AtGold(s) ⇒ Holding(Gold, Result(Grab, s))

Describes what Grab does change

❌ Frame Axiom (problematic)

For every property: Position(Result(Grab,s)) = Position(s)

Potentially infinite statements — impractical!

✅ Solution: Successor-State Axioms

One axiom per fluent — combines effects + non-effects:

HaveArrow(Result(a, s)) ⇔ (a ≠ Shoot ∧ HaveArrow(s))

Translation: "You keep the arrow unless you shoot it"

∀t HaveArrow(t+1) ⇔ (HaveArrow(t) ∧ ¬Action(Shoot, t))

Time-based version

مشكلة الإطار: كيفية تمثيل ما لا يتغير بعد الإجراء دون كتابة عدد هائل من البديهيات. الحل: بديهية الحالة اللاحقة (Successor-State Axiom) تجمع التغيير وعدمه في قاعدة واحدة لكل خاصية. مثال: تملك السهم في الحالة التالية ⇔ لم تطلق النار وكنت تملكه سابقًا.

📑 Lecture 09 · pages 1–12 🔗 Unification — The Key to FOL Inference

6. Unification in First-Order Logic

Unify(p, q) = θ where Subst(θ, p) = Subst(θ, q)

📌 Conditions for Unification

Predicate symbol must be identical
Number of arguments must match
No "occurs check" violation (cannot unify x with f(x))
Standardizing apart eliminates variable overlap

📊 Unification Examples (Exam Table)

p	q	θ (Unifier)
`Knows(John, x)`	`Knows(John, Jane)`	`{x/Jane}`
`Knows(John, x)`	`Knows(y, OJ)`	`{x/OJ, y/John}`
`Knows(John, x)`	`Knows(y, Mother(y))`	`{y/John, x/Mother(John)}`
`Knows(John, x)`	`Knows(x, OJ)`	FAILS (overlap)
`Greedy(x)`	`Greedy(f(x))`	FAILS (occurs check)

التوحيد: إيجاد تعويض θ يجعل تعبيرين متطابقين. الشروط: نفس المحمول، نفس عدد الوسائط، لا انتهاك لفحص الوقوع. أمثلة: Knows(John,x) مع Knows(John,Jane) تعطي θ={x/Jane}. يفشل إذا كان هناك تداخل في المتغيرات.

📑 Lecture 10 · pages 1–23 ⛓️ Forward & Backward Chaining in Propositional Logic

7. Forward Chaining vs Backward Chaining

➡️ Forward Chaining (Data-Driven)

Starts from known facts
Fires rules whose premises are satisfied
Adds conclusions to KB
Continues until goal reached or no new facts
Direction: Facts → Goal

Bottom-up reasoning

⬅️ Backward Chaining (Goal-Driven)

Starts from the goal to prove
Finds rules whose conclusion matches goal
Sets premises as new subgoals
Continues until all subgoals match known facts
Direction: Goal → Facts

Top-down reasoning

📐 Example Walkthrough — Same KB

KB Rules:

1. P ⇒ Q 2. Q ⇒ R 3. L ∧ M ⇒ P 4. B ∧ L ⇒ M 5. A ∧ P ⇒ L 6. A ∧ B ⇒ L

Facts: A, B

Goal: Q (or R)

Forward Chaining to Q

1. A, B given → Rule 6 fires → L added

2. B, L → Rule 4 fires → M added

3. L, M → Rule 3 fires → P added

4. P → Rule 1 fires → Q reached!

Backward Chaining from R

Goal: R → need Q (Rule 2)

Subgoal Q → need P (Rule 1)

Subgoal P → need L ∧ M (Rule 3)

L → need A ∧ B (Rule 6) — Facts match!

M → need B ∧ L (Rule 4) — Facts match!

Goal R proved!

الاستدلال الأمامي: يبدأ من الحقائق المعروفة ويطبق القواعد حتى الوصول للهدف. الاستدلال الخلفي: يبدأ من الهدف ويبحث عن قواعد تدعمه ثم يتحقق من مقدماتها كأهداف فرعية حتى الوصول للحقائق.

📑 Lecture 08 · pages 8–11 🕳️ FOL Applied to Wumpus World

8. FOL Knowledge Base for Wumpus World

👁️ Perception Rules

∀t,s,g,w,c Percept([s, Breeze, g, w, c], t) ⇒ Breeze(t)

∀t,s,g,w,c Percept([s, None, g, w, c], t) ⇒ ¬Breeze(t)

∀t Glitter(t) ⇒ BestAction(Grab, t)

🏃 Action Query

ASKVARS(KB, BestAction(a,5)) → returns {a/Grab}

Returns bindings of variables that make the sentence true

📋 Action Terms

Turn(Right) Turn(Left) Forward Shoot Grab Climb

قاعدة المعرفة في عالم وامبوس: قواعد الإدراك تحول المدركات إلى حقائق (نسيم، لمعان). استعلام الإجراء: ASKVARS يعيد ربط المتغيرات مثل {a/Grab}. إجراءات: استدر يمين/يسار، تقدم، أطلق، التقط، اصعد.

📑 Lecture 07 · pages 6–7 🌫️ Fuzzy Logic vs Probability Theory

9. Beyond Classical Logic — Fuzzy & Probabilistic Reasoning

🌫️ Fuzzy Logic

Degree of truth between 0 and 1
"Vienna is a large city" → true to degree 0.8
Deals with partial truths

🎲 Probability Theory

Degree of belief (likelihood) 0 to 1
Event has 75% probability of occurring
Deals with uncertainty about a definite truth

🧠 Ontology vs Epistemology

Ontology: What entities exist in the domain
Epistemology: How the system reasons about them
Wumpus agent: believes Wumpus in [1,3] with prob 0.75

المنطق الضبابي: درجة صدق بين 0 و1 (حقائق جزئية). نظرية الاحتمالات: درجة اعتقاد (عدم يقين حول حقيقة محددة). الأنطولوجيا: الكيانات الموجودة. الإبستيمولوجيا: كيفية الاستدلال عليها.

🧠 AI LECTURES: LOGICAL AGENTS & FIRST-ORDER LOGIC