Comprehensive Learning Guide: Search Algorithms & Logic

Detailed Execution Examples with Step-by-Step Tables

---

Table of Contents

1. Search Algorithm Execution Tables
   • Sample Graph
   • Breadth-First Search (BFS)
   • Depth-First Search (DFS)
   • Best-First Search
   • Hill-Climbing Search
   • A* Search
   • Branch and Bound
   • Comparison Results
2. Alpha-Beta Pruning
3. Statement Verification with Inference Rules
4. Resolution Proof

---

Search Algorithm Execution Tables

Sample Graph for All Examples

        S(Start, h=7)
       / \
      /   \
     A(h=6) B(h=4)
    / \      / \
   C(h=5) D(h=3) E(h=2)
    \     /      /
     \   /      /
      \ /      /
       F(h=1) /
        \    /
         \  /
          G(Goal, h=0)

Edge Costs:
S→A: 1, S→B: 2
A→C: 2, A→D: 3
B→D: 1, B→E: 4
C→F: 2, D→F: 1
E→G: 2, F→G: 1

Graph Notation:

• Letters = Nodes
• h(n) = Heuristic estimate to goal
• Edge labels = Actual costs

---

1. Breadth-First Search (BFS)

Strategy: Explores graph level-by-level using a Queue (FIFO)

BFS Execution Table

Step	Current Node	Neighbors Found	Queue (FIFO)	Visited	Path to Current
0	-	-	[S]	{}	-
1	S	A, B	[A, B]	{S}	S
2	A	C, D	[B, C, D]	{S, A}	S→A
3	B	D(skip), E	[C, D, E]	{S, A, B}	S→B
4	C	F	[D, E, F]	{S, A, B, C}	S→A→C
5	D	F(skip)	[E, F]	{S, A, B, C, D}	S→A→D
6	E	G	[F, G]	{S, A, B, C, D, E}	S→B→E
7	F	G(skip)	[G]	{S, A, B, C, D, E, F}	S→A→C→F
8	G	-	[]	{S, A, B, C, D, E, F, G}	S→B→E→G

Result:

• Path found: S→B→E→G
• Total cost: 2 + 4 + 2 = 8
• Nodes expanded: 8
• Complete: ✓ Yes
• Optimal: ✗ No (not considering edge weights)

---

2. Depth-First Search (DFS)

Strategy: Explores as deep as possible using a Stack (LIFO)

DFS Execution Table

Step	Current Node	Neighbors Found	Stack (LIFO)	Visited	Path to Current
0	-	-	[S]	{}	-
1	S	A, B	[A, B]	{S}	S
2	B	D, E	[A, D, E]	{S, B}	S→B
3	E	G	[A, D, G]	{S, B, E}	S→B→E
4	G	-	-	{S, B, E, G}	S→B→E→G

Result:

• Path found: S→B→E→G
• Total cost: 2 + 4 + 2 = 8
• Nodes expanded: 4
• Complete: ✗ No (can get stuck in cycles)
• Optimal: ✗ No

Note: DFS happened to find same path as BFS, but typically finds any path, not necessarily shortest

---

3. Best-First Search (Greedy)

Strategy: Always expands node with lowest heuristic h(n) using Priority Queue

Best-First Execution Table

Step	Current Node	h(n)	Neighbors Found	Priority Queue (min h)	Visited	Path to Current
0	-	-	-	[S:7]	{}	-
1	S	7	A:6, B:4	[B:4, A:6]	{S}	S
2	B	4	D:3, E:2	[E:2, D:3, A:6]	{S, B}	S→B
3	E	2	G:0	[G:0, D:3, A:6]	{S, B, E}	S→B→E
4	G	0	-	-	{S, B, E, G}	S→B→E→G

Result:

• Path found: S→B→E→G
• Total cost: 8
• Nodes expanded: 4
• Complete: ✗ No
• Optimal: ✗ No

Note: Greedy search got lucky and found a path quickly by following the heuristic, but no guarantee of optimality

---

4. Hill-Climbing Search

Strategy: Local search that only keeps current state, always moves to best neighbor

Hill-Climbing Execution Table

Step	Current State	h(Current)	Neighbors	h(Neighbors)	Best Neighbor	Decision
0	S	7	-	-	-	Start
1	S	7	A, B	6, 4	B (h=4)	Move to B
2	B	4	D, E	3, 2	E (h=2)	Move to E
3	E	2	G	0	G (h=0)	Move to G
4	G	0	-	-	-	Goal!

Result:

• Path found: S→B→E→G
• Total cost: 8
• States explored: 4
• Memory: O(1) - only stores current state
• Complete: ✗ No (can get stuck at local maxima)
• Optimal: ✗ No

Advantages: Minimal memory usage
Disadvantages: Can get stuck at local maxima, plateaus, or ridges

---

5. A* Search

Strategy: Uses f(n) = g(n) + h(n) where g(n) = cost from start, h(n) = heuristic to goal

A* Execution Table

Step	Current	g(n)	h(n)	f(n)=g+h	Neighbors	Open List (f, node)	Closed	Path
0	-	-	-	-	-	[S:7]	{}	-
1	S	0	7	7	A, B	[B:6, A:7]	{S}	S
2	B	2	4	6	D, E	[D:6, A:7, E:8]	{S,B}	S→B
3	D	3	3	6	F	[F:5, A:7, E:8]	{S,B,D}	S→B→D
4	F	4	1	5	G	[G:5, A:7, E:8]	{S,B,D,F}	S→B→D→F
5	G	5	0	5	-	-	{S,B,D,F,G}	S→B→D→F→G

Detailed f-value calculations:

• S: g=0, h=7, f=7
• A (via S→A): g=1, h=6, f=7
• B (via S→B): g=2, h=4, f=6 ✓ (expanded first)
• D (via S→B→D): g=3, h=3, f=6 ✓
• E (via S→B→E): g=6, h=2, f=8
• F (via S→B→D→F): g=4, h=1, f=5 ✓
• G (via S→B→D→F→G): g=5, h=0, f=5 ✓

Result:

• Path found: S→B→D→F→G
• Total cost: 5 ✓ OPTIMAL
• Nodes expanded: 5
• Complete: ✓ Yes (if h is admissible)
• Optimal: ✓ Yes (if h is admissible)

Key: A* found the optimal path by balancing actual cost and heuristic estimate!

---

6. Branch and Bound

Strategy: Systematically explores search space while pruning branches that exceed best bound

Branch and Bound Execution Table

Step	Current	Cost g(n)	Bound	Neighbors	Queue (cost order)	Best Solution	Action
0	-	-	∞	-	[S:0]	None	-
1	S	0	∞	A:1, B:2	[A:1, B:2]	None	Expand
2	A	1	∞	C:3, D:4	[B:2, C:3, D:4]	None	Expand
3	B	2	∞	D:3, E:6	[C:3, D:3, D:4, E:6]	None	Expand
4	C	3	∞	F:5	[D:3, D:4, F:5, E:6]	None	Expand
5	D	3	∞	F:4	[D:4, F:4, F:5, E:6]	None	Update F
6	D	4	4	F:5	[F:4, F:5, E:6]	None	Prune (≥4)
7	F	4	4	G:5	[F:5, G:5, E:6]	G:5	Found! Bound=5
8	F	5	5	G:6	[G:5, E:6]	G:5	Prune (5≥5)
9	G	5	5	-	[E:6]	G:5	Optimal
10	E	6	5	-	[]	G:5	Prune (6>5), Done

Result:

• Optimal path: S→B→D→F→G
• Total cost: 5 ✓ OPTIMAL
• Nodes expanded: 10
• Complete: ✓ Yes
• Optimal: ✓ Yes

Note: Branch and Bound guarantees optimal solution by systematically pruning suboptimal branches

---

Search Algorithm Comparison

Results on Same Graph

Algorithm	Path Found	Total Cost	Nodes Expanded	Optimal?	Memory
BFS	S→B→E→G	8	8	✗	High
DFS	S→B→E→G	8	4	✗	Low
Best-First	S→B→E→G	8	4	✗	High
Hill-Climbing	S→B→E→G	8	3	✗	Minimal
A*	S→B→D→F→G	5	5	✓	High
Branch & Bound	S→B→D→F→G	5	10	✓	High

Key Insights:

• A* and Branch & Bound found the optimal path (cost = 5)
• Greedy algorithms (BFS, DFS, Best-First, Hill-Climbing) found suboptimal path (cost = 8)
• A* is most efficient among optimal algorithms (5 nodes vs 10 nodes)
• Hill-Climbing uses minimal memory but no guarantee of finding solution

---

Alpha-Beta Pruning (4-Level Depth)

Game Tree Scenario

Two-player game:

• MAX player wants to maximize score
• MIN player wants to minimize score
• Numbers at leaf nodes = utility values for MAX player

Complete Game Tree

                                MAX (Root - A)
                    ______________|______________
                   /                             \
                 MIN (B)                        MIN (F)
          ________|________              ________|________
         /        |        \            /        |        \
       MAX(C)   MAX(D)   MAX(E)      MAX(G)   MAX(H)   MAX(I)
      / | \     / | \     / | \      / | \     / | \     / | \
     3  5  2   8  1  4   6  7  9    2  3  5   1  8  6   4  3  7
     
Level:  0         1              2                    3

---

Alpha-Beta Execution Table

Step	Node	Type	Depth	α	β	Children Explored	Value	Backed-up	Pruned?	Explanation
1	A	MAX	0	-∞	+∞	-	-	-	-	Start at root
2	B	MIN	1	-∞	+∞	-	-	-	-	Explore left child
3	C	MAX	2	-∞	+∞	[3,5,2]	5	5	-	Returns max(3,5,2)=5
4	B	MIN	1	-∞	5	[5]	5	-	-	Update β=5
5	D	MAX	2	-∞	5	[8]	8	-	-	First child is 8
6	B	MIN	1	-∞	5	[5,8]	5	-	✓ E pruned	8>β(5), prune E
7	B	MIN	1	-∞	5	-	5	5	-	Returns 5 to A
8	A	MAX	0	5	+∞	[5]	5	-	-	Update α=5
9	F	MIN	1	5	+∞	-	-	-	-	Explore right child
10	G	MAX	2	5	+∞	[2,3,5]	5	5	-	Returns max(2,3,5)=5
11	F	MIN	1	5	5	[5]	5	-	-	Update β=5, α=β
12	H	MAX	2	5	5	[1]	1	1	✓ Rest pruned	1<α(5), prune rest
13	F	MIN	1	5	5	[5,1]	1	1	✓ I pruned	Returns min(5,1)=1
14	A	MAX	0	5	+∞	[5,1]	5	5	-	Final: Choose left

---

Visual Step-by-Step Execution

Phase 1: Left Subtree (Node B)

Step 1-3: Evaluate Node C
                    A (α=-∞, β=+∞)
                    |
                    B (α=-∞, β=+∞)
                    |
                    C
                   /|\
                  3 5 2
                  
Result: C returns 5 (maximum)
B updates β = 5

Step 4-5: Evaluate Node D (first child only)
                    A (α=-∞, β=+∞)
                    |
                    B (α=-∞, β=5)
                   / \
                  5   D
                     /|\
                    8 ? ?
                    
Result: D finds 8, but 8 > β(5)
MIN won't choose this path!
Node E is PRUNED (β-cutoff)

After Phase 1:
                    A (α=5, β=+∞)
                   / \
                  5   ?
                  
B returns 5 to A
A updates α = 5

---

Phase 2: Right Subtree (Node F)

Step 6-7: Evaluate Node G
                    A (α=5, β=+∞)
                         \
                          F (α=5, β=+∞)
                          |
                          G
                         /|\
                        2 3 5
                        
Result: G returns 5 (maximum)
F updates β = 5 (now α = β = 5)

Step 8: Evaluate Node H (first child only)
                    A (α=5, β=+∞)
                         \
                          F (α=5, β=5)
                         / \
                        5   H
                           /|\
                          1 ? ?
                          
Result: H finds 1, but 1 < α(5)
This path won't improve MAX's position!
Remaining children of H are PRUNED (α-cutoff)
Node I is PRUNED entirely

Final Result:
                    A = 5
                   / \
                  5   1
                  
MAX chooses left branch (value = 5)

---

Pruning Summary Table

Node	Children	Visited	Pruned	Pruning Type	Reason
C	3	3	0	-	All evaluated
D	3	1	2	β-cutoff	8 > β(5) at MIN
E	3	0	3	β-cutoff	Parent pruned
G	3	3	0	-	All evaluated
H	3	1	2	α-cutoff	1 < α(5) at MAX
I	3	0	3	β-cutoff	Sibling pruned

Efficiency:

• Total leaf nodes: 24
• Nodes visited: 16
• Nodes pruned: 8
• Reduction: ~33% fewer nodes explored

---

Alpha-Beta Pruning Rules

Situation	Condition	Action	Type
β-cutoff	At MIN node, if value ≤ α	Stop exploring siblings	MAX found better elsewhere
α-cutoff	At MAX node, if value ≥ β	Stop exploring siblings	MIN found better elsewhere

Key Insight:

• α = Best value MAX can guarantee (lower bound for MAX)
• β = Best value MIN can guarantee (upper bound for MIN)
• When α ≥ β, remaining branches can't affect final decision

---

Statement Verification with Inference Rules

Inference Rules Reference

Rule Name	Form	Notation	Example
Modus Ponens (MP)	P, P→Q ⊢ Q	If P and "P implies Q", then Q	Rain, Rain→Wet ⊢ Wet
Modus Tollens (MT)	¬Q, P→Q ⊢ ¬P	If not Q and "P implies Q", then not P	¬Wet, Rain→Wet ⊢ ¬Rain
Hypothetical Syllogism (HS)	P→Q, Q→R ⊢ P→R	Chain implications	A→B, B→C ⊢ A→C
Disjunctive Syllogism (DS)	P∨Q, ¬P ⊢ Q	If P or Q, and not P, then Q	Hot∨Cold, ¬Hot ⊢ Cold
Conjunction (Conj)	P, Q ⊢ P∧Q	Combine statements	Rain, Cold ⊢ Rain∧Cold
Simplification (Simp)	P∧Q ⊢ P	Extract from conjunction	Rain∧Cold ⊢ Rain
Addition (Add)	P ⊢ P∨Q	Add disjunction	Rain ⊢ Rain∨Snow
Resolution (Res)	P∨Q, ¬P∨R ⊢ Q∨R	Resolve complementary literals	A∨B, ¬A∨C ⊢ B∨C

---

Example 1: Criminal Investigation

Knowledge Base (Clean Notation):

Propositional Variables:

• P = "It rained last night"
• Q = "Ground is wet"
• R = "Footprints are visible"
• S = "Suspect was at scene"
• T = "Suspect is guilty"

Rules:

1. P → Q (If it rained, then ground is wet)
2. Q → R (If ground is wet, then footprints are visible)
3. R ∧ S → T (If footprints visible AND suspect at scene, then guilty)
4. ¬T → ¬S ∨ ¬R (If not guilty, then suspect wasn't there OR no footprints)

Initial Facts: P (It rained), S (Suspect was at scene)

Query: Is T (Suspect guilty) true?

---

Forward Chaining with Inference Rules

Step	Known Facts	Inference Rule	Premises	Conclusion	New KB State	Explanation
0	{P, S}	-	-	-	Initial	Starting facts
1	{P, S, Q}	Modus Ponens	P, P→Q	Q	Ground is wet	Applied rule 1
2	{P, S, Q, R}	Modus Ponens	Q, Q→R	R	Footprints visible	Applied rule 2
3	{P, S, Q, R, R∧S}	Conjunction	R, S	R∧S	Both conditions met	Combined facts
4	{P, S, Q, R, R∧S, T}	Modus Ponens	R∧S, R∧S→T	T	Suspect is guilty! ✓	Applied rule 3

Proof Chain:

P →[MP via rule 1]→ Q →[MP via rule 2]→ R
R + S →[Conjunction]→ R∧S →[MP via rule 3]→ T

Answer: T is PROVEN TRUE - Suspect is guilty!

---

Backward Chaining with Inference Rules

Step	Goal	Rule to Use	Sub-goals Generated	Inference Rule	Status	Explanation
1	T	R∧S → T	R, S	Modus Ponens	Need both	To prove T, need R and S
2	S	-	-	-	✓ Given fact	S is in KB
3	R	Q → R	Q	Modus Ponens	Need Q	To prove R, need Q
4	Q	P → Q	P	Modus Ponens	Need P	To prove Q, need P
5	P	-	-	-	✓ Given fact	P is in KB
6	Q	P → Q	P (proven)	Modus Ponens	✓ Proven	P true, so Q true
7	R	Q → R	Q (proven)	Modus Ponens	✓ Proven	Q true, so R true
8	R∧S	-	R, S (both proven)	Conjunction	✓ Proven	Both R and S true
9	T	R∧S → T	R∧S (proven)	Modus Ponens	✓ PROVEN	Goal achieved!

Proof Chain (backward):

T ←[need R∧S]← R ←[need Q]← P ✓ (fact)
              ← S ✓ (fact)

Answer: T is PROVEN TRUE via backward chaining!

---

Example 2: Extended with Multiple Inference Rules

Extended Knowledge Base:

Additional Variables:

• U = "Alarm rings"
• V = "Security called"
• W = "Police arrive"

Additional Rules: 5. T ∨ U → V (If guilty OR alarm rings, then security called) 6. V → W (If security called, then police arrive) 7. ¬W (Police did NOT arrive) - New fact

Query: What can we conclude? Check for contradictions.

---

Forward Chaining - Extended

Step	Known Facts	Inference Rule	Premises	Conclusion	Rule Used	Explanation
0	{P, S, ¬W}	-	-	-	-	Initial + new fact
1	{P, S, ¬W, Q}	Modus Ponens	P, P→Q	Q	Rule 1	From rain
2	{P, S, ¬W, Q, R}	Modus Ponens	Q, Q→R	R	Rule 2	From wet ground
3	{..., R∧S}	Conjunction	R, S	R∧S	-	Combine facts
4	{..., T}	Modus Ponens	R∧S, R∧S→T	T	Rule 3	Guilty proven
5	{..., T∨U}	Addition	T	T∨U	-	Add disjunction
6	{..., V}	Modus Ponens	T∨U, T∨U→V	V	Rule 5	Security called
7	{..., W}	Modus Ponens	V, V→W	W	Rule 6	Police arrive
8	CONTRADICTION	-	W, ¬W	⊥	-	Inconsistent KB!

Result: The knowledge base is INCONSISTENT. We proved both W and ¬W.

Conclusion: Either the fact ¬W is incorrect, or one of the rules is flawed.

---

Example 3: Using Modus Tollens

Scenario: Working backward from ¬W (police didn't arrive)

Step	Known Facts	Inference Rule	Premises	Conclusion	Explanation
1	{¬W}	-	-	-	Police didn't arrive (fact)
2	{¬W, ¬V}	Modus Tollens	¬W, V→W	¬V	Security NOT called
3	{¬W, ¬V, ¬(T∨U)}	Modus Tollens	¬V, T∨U→V	¬(T∨U)	Neither guilty nor alarm
4	{¬W, ¬V, ¬T∧¬U}	De Morgan's Law	¬(T∨U)	¬T∧¬U	Convert to conjunction
5	{¬W, ¬V, ¬T, ¬U}	Simplification	¬T∧¬U	¬T, ¬U	Extract both parts

Result: If police didn't arrive, then:

• Security was NOT called (¬V)
• Suspect is NOT guilty (¬T)
• Alarm did NOT ring (¬U)

Note: This contradicts our earlier proof that T is true!

---

Example 4: Disjunctive Syllogism

Scenario:

• Fact 1: T ∨ U (Either guilty OR alarm rang)
• Fact 2: ¬T (NOT guilty)
• Query: What can we conclude about U?

Step	Known Facts	Inference Rule	Premises	Conclusion	Explanation
1	{T∨U, ¬T}	Disjunctive Syllogism	T∨U, ¬T	U	Alarm must have rung

Result: U is true (Alarm rang)

---

Example 5: Hypothetical Syllogism (Chain Rules)

Chain of Implications:

1. P → Q (Rain → Wet ground)
2. Q → R (Wet ground → Footprints)
3. R → S (Footprints → Evidence)

Step	Rules Available	Inference Rule	New Rule Created	Explanation
1	P→Q, Q→R	Hypothetical Syllogism	P→R	Rain directly implies footprints
2	P→R, R→S	Hypothetical Syllogism	P→S	Rain directly implies evidence

Result: P → S (If it rained, then there is evidence)

Application:

• Given: P (It rained)
• Apply Modus Ponens: P, P→S ⊢ S
• Conclusion: S (There is evidence)

---

Summary: Inference Rules Usage

Inference Rule	Forward Chaining	Backward Chaining	Most Common Use
Modus Ponens	✓ Primary	✓ Primary	Deriving new facts
Modus Tollens	✓ Sometimes	✓ Common	Backward reasoning
Conjunction	✓ Combine facts	✓ Combine subgoals	Building compound statements
Simplification	✓ Extract info	✓ Break down goals	Separating conjunctions
Disjunctive Syllogism	✓ Eliminate options	✗ Rare	Choosing between alternatives
Hypothetical Syllogism	✓ Build chains	✓ Link goals	Creating rule shortcuts
Addition	✓ Add options	✗ Rare	Expanding possibilities
Resolution	✗ Not used	✗ Not used	Proof by contradiction only

---

Resolution (Comprehensive Example)

Problem: Medical Diagnosis

Domain Statements:

1. If patient has fever, then patient has infection or allergy
2. If patient has infection, then patient needs antibiotics
3. If patient needs antibiotics, then patient visits doctor
4. Patient has fever
5. Patient does not have allergy

Query: Does patient visit doctor?

---

Step 1: Define Propositional Variables

Variable	Meaning
F	Patient has fever
I	Patient has infection
A	Patient has allergy
B	Patient needs antibiotics
D	Patient visits doctor

---

Step 2: Convert to Conjunctive Normal Form (CNF)

#	Statement	Logic Form	CNF Form	Clause
1	Fever → Infection ∨ Allergy	F → (I ∨ A)	¬F ∨ I ∨ A	C1
2	Infection → Antibiotics	I → B	¬I ∨ B	C2
3	Antibiotics → Doctor	B → D	¬B ∨ D	C3
4	Has fever	F	F	C4
5	No allergy	¬A	¬A	C5
6	Query (negated)	¬D	¬D	C6

Note: For resolution proof by contradiction, we negate the query and try to derive a contradiction (empty clause ⊥)

---

Step 3: Resolution Proof Table

Step	Clause 1	Clause 2	Unification	Resolve On	Resolvent	Inference	New Clause
1	C1: ¬F∨I∨A	C4: F	-	F	I∨A	Resolution	C7
2	C7: I∨A	C5: ¬A	-	A	I	Resolution	C8
3	C8: I	C2: ¬I∨B	-	I	B	Resolution	C9
4	C9: B	C3: ¬B∨D	-	B	D	Resolution	C10
5	C10: D	C6: ¬D	-	D	⊥	Resolution	PROOF

---

Step 4: Detailed Resolution Explanation

Resolution Step 1: C1 + C4 → C7

C1: ¬F ∨ I ∨ A    (NOT Fever OR Infection OR Allergy)
C4: F             (Fever is TRUE)
───────────────────────────────────────────────────────
C7: I ∨ A         (Infection OR Allergy)

Explanation: Since F is true, ¬F is false, so we eliminate ¬F

Resolution Step 2: C7 + C5 → C8

C7: I ∨ A         (Infection OR Allergy)
C5: ¬A            (NOT Allergy)
───────────────────────────────────────────────────────
C8: I             (Infection)

Explanation: Since ¬A is true, A is false, so we eliminate A

Resolution Step 3: C8 + C2 → C9

C8: I             (Infection is TRUE)
C2: ¬I ∨ B        (NOT Infection OR Antibiotics)
───────────────────────────────────────────────────────
C9: B             (Antibiotics)

Explanation: Since I is true, ¬I is false, so we eliminate ¬I

Resolution Step 4: C9 + C3 → C10

C9: B             (Antibiotics is TRUE)
C3: ¬B ∨ D        (NOT Antibiotics OR Doctor visit)
───────────────────────────────────────────────────────
C10: D            (Doctor visit)

Explanation: Since B is true, ¬B is false, so we eliminate ¬B

Resolution Step 5: C10 + C6 → ⊥

C10: D            (Doctor visit is TRUE)
C6: ¬D            (Doctor visit is FALSE - negated query)
───────────────────────────────────────────────────────
⊥                 (Empty clause - CONTRADICTION!)

Explanation: We have both D and ¬D, which is impossible

---

Step 5: Resolution Derivation Tree

                            ⊥ (Empty Clause - Contradiction!)
                            |
                    ┌───────┴───────┐
                    |               |
                   D              ¬D
                  [C10]          [C6: Negated Query]
                    |
                ┌───┴───┐
                |       |
                B      ¬B∨D
               [C9]    [C3]
                |
            ┌───┴───┐
            |       |
            I      ¬I∨B
           [C8]    [C2]
            |
        ┌───┴───┐
        |       |
       I∨A     ¬A
       [C7]    [C5]
        |
    ┌───┴───┐
    |       |
   ¬F∨I∨A   F
   [C1]    [C4]

---

Step 6: Logical Reasoning Chain

Forward reasoning (without negated query):

1. Given: F (Fever) and ¬A (No allergy)
2. From F and Rule 1: F → I∨A, therefore I∨A
3. From I∨A and ¬A: Using DS, therefore I
4. From I and Rule 2: I → B, therefore B
5. From B and Rule 3: B → D, therefore D

Conclusion: D is TRUE (Patient visits doctor)

---

Resolution Summary

Clause	Content	Type	Derived From	Step
C1	¬F ∨ I ∨ A	Rule (given)	Statement 1	-
C2	¬I ∨ B	Rule (given)	Statement 2	-
C3	¬B ∨ D	Rule (given)	Statement 3	-
C4	F	Fact (given)	Statement 4	-
C5	¬A	Fact (given)	Statement 5	-
C6	¬D	Negated Query	Query negation	-
C7	I ∨ A	Intermediate	C1 + C4	1
C8	I	Intermediate	C7 + C5	2
C9	B	Intermediate	C8 + C2	3
C10	D	Intermediate	C9 + C3	4
⊥	Empty	Proof	C10 + C6	5

---

Final Answer

Question: Does patient visit doctor (D)?

Answer: YES ✓

Proof Method: Resolution refutation

• Assumed ¬D (patient does NOT visit doctor)
• Derived contradiction (empty clause ⊥)
• Therefore, D must be TRUE

Reasoning Path:

Fever → Infection (since no allergy)
Infection → Antibiotics
Antibiotics → Doctor visit
∴ Patient visits doctor

---

Key Concepts Summary

Search Algorithms

Algorithm	Best For	Guarantee
BFS	Shortest path (unweighted)	Complete, Optimal (unweighted)
DFS	Memory-limited, any solution	Not complete, Not optimal
Best-First	Quick approximation	Not complete, Not optimal
Hill-Climbing	Local optimization, minimal memory	Not complete, Not optimal
A*	Optimal with good heuristic	Complete*, Optimal*
Branch & Bound	Guaranteed optimal, systematic	Complete, Optimal

*If heuristic is admissible (never overestimates)

---

Alpha-Beta Pruning

• Purpose: Optimize minimax search in game trees
• α (alpha): Best value MAX can guarantee (lower bound)
• β (beta): Best value MIN can guarantee (upper bound)
• Pruning: When α ≥ β, remaining branches won't affect decision
• Efficiency: Can reduce search from O(b^d) to O(b^(d/2)) with perfect ordering

---

Inference Rules

Key Rules for Proofs:

1. Modus Ponens: Most common in forward reasoning
2. Modus Tollens: Most common in backward reasoning
3. Resolution: Used in proof by contradiction (CNF required)
4. Others: Support rules for building and manipulating logic

---

Resolution Method

Steps:

1. Convert all statements to CNF
2. Negate the query
3. Apply resolution until:
   • Empty clause (⊥) found → Query is TRUE
   • No more resolutions possible → Query unproven

Key: Resolution is complete - if something is provable, resolution will find it.

---

Practice Recommendations

For Search Algorithms:

1. Implement each algorithm on different graphs
2. Compare performance on same problem
3. Experiment with different heuristics for A*
4. Try graphs with cycles, infinite paths

For Alpha-Beta:

1. Work through trees manually
2. Try different node orderings
3. Count pruned nodes
4. Implement in code for games (Tic-Tac-Toe, Chess)

For Logic:

1. Convert complex statements to CNF
2. Practice both forward and backward chaining
3. Do resolution proofs by hand
4. Identify which inference rule applies when

---

End of Guide

This guide provides detailed step-by-step examples for:

• ✓ 6 Search algorithms with execution tables
• ✓ Alpha-Beta pruning with 4-level tree
• ✓ Statement verification with 8 inference rules
• ✓ Resolution proof with complete CNF conversion

Next Steps:

1. Work through examples with different inputs
2. Create your own problems
3. Implement algorithms in code
4. Apply to real-world scenarios

---

Document Version: 1.0
Last Updated: 2024