Spring 2023
Introduction to Artificial Intelligence Exam Prep 3
(a) Prove, or find a counterexample to, each of the following assertions:
(i) If 𝛼 ⊧ 𝛾 or 𝛽 ⊧ 𝛾 (or both) then (𝛼 ∧ 𝛽) ⊧ 𝛾
(ii) If (𝛼 ∧ 𝛽) ⊧ 𝛾 then 𝛼 ⊧ 𝛾 or 𝛽 ⊧ 𝛾 (or both).
(iii) If 𝛼 ⊧ (𝛽 ∨ 𝛾) then 𝛼 ⊧ 𝛽 or 𝛼 ⊧ 𝛾 (or both).
(b) Decide whether each of the following sentences is valid, unsatisfiable, or neither.
(i) 𝑆𝑚𝑜𝑘𝑒 ⟹ 𝑆𝑚𝑜𝑘𝑒
(ii) 𝑆𝑚𝑜𝑘𝑒 ⟹ 𝐹 𝑖𝑟𝑒
(iii) (𝑆𝑚𝑜𝑘𝑒 ⟹ 𝐹 𝑖𝑟𝑒) ⟹ (¬𝑆𝑚𝑜𝑘𝑒 ⟹ ¬𝐹 𝑖𝑟𝑒)
(iv) 𝑆𝑚𝑜𝑘𝑒 ∨ 𝐹 𝑖𝑟𝑒 ∨ ¬𝐹 𝑖𝑟𝑒
(v) ((𝑆𝑚𝑜𝑘𝑒 ∧𝐻𝑒𝑎𝑡) ⟹ 𝐹 𝑖𝑟𝑒) ⟺ ((𝑆𝑚𝑜𝑘𝑒 ⟹ 𝐹 𝑖𝑟𝑒) ∨ (𝐻𝑒𝑎𝑡 ⟹ 𝐹 𝑖𝑟𝑒))
(vi) (𝑆𝑚𝑜𝑘𝑒 ⟹ 𝐹 𝑖𝑟𝑒) ⟹ ((𝑆𝑚𝑜𝑘𝑒 ∧𝐻𝑒𝑎𝑡) ⟹ 𝐹 𝑖𝑟𝑒)
(vii) 𝐵𝑖𝑔 ∨𝐷𝑢𝑚𝑏 ∨ (𝐵𝑖𝑔 ⟹ 𝐷𝑢𝑚𝑏)
(c) Suppose an agent inhabits a world with two states, 𝑆 and ¬𝑆, and can do exactly one of two actions, 𝑎 and 𝑏. Action 𝑎
does nothing and action 𝑏 flips from one state to the other. Let 𝑆𝑡 be the proposition that the agent is in state 𝑆 at time 𝑡,
and let 𝑎𝑡 be the proposition that the agent does action 𝑎 at time 𝑡 (similarly for 𝑏𝑡).
(i) Write a successor-state axiom for 𝑆𝑡+1.
(ii) Convert the sentence in the previous part into CNF.
Q2. First Order Logic
Consider a vocabulary with the following symbols:
• 𝑂𝑐𝑐𝑢𝑝𝑡𝑖𝑜𝑛(𝑝, 𝑜): Predicate. Person 𝑝 has occuption 𝑜.
• 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟(𝑝1, 𝑝2): Predicate. Person 𝑝1 is a customer of person 𝑝2.
• 𝐵𝑜𝑠𝑠(𝑝1, 𝑝2): Predicate. Person 𝑝1 is a boss of person 𝑝2.
• 𝐷𝑜𝑐𝑡𝑜𝑟, 𝑆𝑢𝑟𝑔𝑒𝑜𝑛, 𝐿𝑎𝑤𝑦𝑒𝑟, 𝐴𝑐𝑡𝑜𝑟: Constants denoting occupations.
• 𝐸𝑚𝑖𝑙𝑦, 𝐽𝑜𝑒: Constants denoting people.
Use these symbols to write the following assertions in first-order logic:
(iii) Emily is either a surgeon or a lawyer.
(iv) Joe is an actor, but he also holds another job.
(v) All surgeons are doctors.
(vi) Joe does not have a lawyer (i.e., is not a customer of any lawyer).
(vii) Emily has a boss who is a lawyer.
(viii) There exists a lawyer all of whose customers are doctors.
(ix) Every surgeon has a lawyer.
Q3. [Optional] Local Search
(a) Hill Climbing
(i) Hill-climbing is complete. □ True □ False
(ii) Hill-climbing is optimal. □ True □ False
(b) Simulated Annealing
(i) The higher the temperature T is, the more likely the randomly chosen state will be expanded. □ True □ False
(ii) In one round of simulated annealing, the temperature is 2 and the current state S has energy 1. It has 3 successors:
A with energy 2; B with energy 1; C with energy 1-ln 4. If we assume the temperature does not change, What’s the
probability that these states will be chosen to expand after S eventually?
(iii) On a undirected graph, If T decreases slowly enough, simulated annealing is guaranteed to converge to the optimal
state. □ True □ False
(c) Local Beam Search
The following state graph is being explored with 2-beam graph search. A state’s score is its accumulated distance to the
start state and lower scores are considered better. Which of the following statements are true?
□ States A and B will be expanded before C and D.
□ States A and D will be expanded before B and C.
□ States B and D will be expanded before A and C.
□ None of above.
(d) Genetic Algorithm
(i) In genetic algorithm, cross-over combine the genetic information of two parents to generate new offspring.
□ True □ False
(ii) In genetic algorithm, mutation involves a probability that some arbitrary bits in a genetic sequence will be flipped
from its original state.
□ True □ False
(e) Gradient Descent
(i) Gradient descent is optimal. □ True □ False
(ii) For a function 𝑓 (𝑥) with derivative 𝑓 ′(𝑥), write down the gradient descent update to go from 𝑥𝑡 to 𝑥𝑡+1. Learning
rate is 𝛼.