# An Introduction to Artificial Intelligence | Week 7

Session: JAN-APR 2024

Course name: An Introduction to Artificial Intelligence

#### Q1. Which of the following is/are the component(s) of a Knowledge Representation Language?SyntaxSemanticsInference ProcedureKnowledge Base

Q2. Choose the CORRECT statements –
Syntax is the mapping between symbols and worlds.
A sentence S is unsatisfiable if it is false in some world(s).
Sentence S1 entails S2 if whenever S1 is false, S2 is also false.
A sentence S is valid if it is true in all worlds.

Answer: A sentence S is valid if it is true in all worlds.

These are An Introduction to Artificial Intelligence Answers Week 7

Q3. Choose the correct CNF form for the expression (¬q → r) ∧ (r → ¬p)
(q ∨ r) ∧ (¬p ∨ ¬r)
(q ∨ p) ∧ (¬q ∨ ¬r)
(p ∨ r) ∧ (q ∨ ¬r)
(r ∨ p) ∧ (¬p ∨ r)

Answer: (q ∨ r) ∧ (¬p ∨ ¬r)

Q4. Which of the following steps are used in the DPLL algorithm?
If expression F contains unit or pure literals, branch immediately on them.
Can apply MOM’s heuristic to select a variable for branching
Can perform local search over complete truth assignment states
Choose a literal and test the expression by setting it both true or false separately.

These are An Introduction to Artificial Intelligence Answers Week 7

Q5. What is the number of INCORRECT statements among the following?

i. If Knowledge Base has only horn clauses and the query is a conjunction of literals, then forward chaining is both sound and complete.
ii. An algorithm that can prove anything and everything is sound.
iii. Sound algorithm is the one that proves nothing but the truth.
iv. An algorithm that proves nothing but one true fact is not a sound algorithm.
v. A complete algorithm is the one that proves some but not all truth.
vi. A sound and complete algorithm is one that proves the truth and nothing but the truth.
vii. The zero of a disjunction operator is False.
viii. The zero of a conjunction operator is True.

Q6. We are given the following set of clauses {(a, ¬b, c), (c), (¬c, d, ¬e), (¬a, ¬b, e), (a, ¬b, ¬c), (d, b), (e, a)}. We repeatedly apply unit propagation and removal of pure literals (till we can no longer do so). What is the number of remaining clauses?

These are An Introduction to Artificial Intelligence Answers Week 7

Q7. Given the following set of clauses ({¬a ∨ b}, {¬b}, {¬c ∨ b}, {a ∨ d}, {c ∨ ¬d}).
Which of the following clause(s) can be derived by resolution using the given clauses?

{¬a}
{¬c}
{¬d}
{} (Empty Clause)

Q8. Given the following boolean expressions
i. a
ii. b ∧ a ⇒ c
iii. a ⇒ b
iv. c ∧ b ⇒ d
v. d ∧ b ⇒ e
How many of the following can be inferred if we apply forward chaining based on the Modus Ponens rule?

i. b
ii. c
iii. d
iv. e

These are An Introduction to Artificial Intelligence Answers Week 7

Q9. Which statements about the ontological and epistemological characteristics of First-order logic (FOL) and Probabilistic Propositional Logic/Bayesian Networks (BN) are correct?
FOL and BN have similar ontological commitments
FOL and BN have different ontological commitments
FOL and BN have similar epistemological commitments
FOL and BN have different epistemological commitments

Q10. Which of the following statements about the WalkSAT algorithm is/are correct?
The number of clauses satisfied increases by at least one in every move.
WalkSAT can detect if the problem is unsatisfiable.
It is asymptotically complete.
It is sound.

These are An Introduction to Artificial Intelligence Answers Week 7

Course Name: An Introduction to Artificial Intelligence

#### Q1. Which of the following statements is correct regarding Conjunction Normal Form?a. It is a conjunction of disjunction clausesb. It is a disjunction of conjunction clausesc. Empty clause indicates trued. Empty clause indicates false

Q2. Which of the following statements are true, according to the definitions of satisfiability, validity and entailment mentioned in the lectures?
a. S is not valid if ¬S is satisfiable
b. S is valid if ¬S is unsatisfiable
c. S is satisfiable if ¬S is unsatisfiable
d. S is valid if ¬S is not valid

These are An Introduction to Artificial Intelligence Answers Week 7

Q3. Which of the following clauses can be entailed by the given set of clauses?
{(a,¬b, c) , (b, ¬c) , (¬b, c) , (b, c)}

a. (a)
b. (b)
c. (c)
d. ()

Q4. Assume you are running the DPLL algorithm, with MOM’s heuristic on the following CNF formula. What is the next variable to be branched on?
{ (a, ¬b, c) , (¬b, c) , (¬c, d, ¬e) , (¬a, ¬b, e) , (a, ¬b, ¬c) , (d, b) , (e, a) }

a
b
c
d

These are An Introduction to Artificial Intelligence Answers Week 7

Q5. In the previous question, assume that you set your selected variable to True. What is the formula you will obtain after the assignment, followed by repetitively eliminating all unit and pure literals?
a. { (a, c) , (¬c, d, ¬e) , (¬a, e) , (a, ¬c) , (e, a) }
b. { (¬c, d, ¬e) , (d, b) , (e, a) }
c. { (d, ¬e) , (¬a, e) , (a, c) , (e, a) }
d. { }

These are An Introduction to Artificial Intelligence Answers Week 7

Q6. Which of the following statements is/are correct about WalkSAT algorithm?
a. The number of clauses satisfied increases by at least one in every move.
b. WalkSAT can detect if the problem is unsatisfiable.
c. It is asymptotically complete.
d. It is sound.

These are An Introduction to Artificial Intelligence Answers Week 7

Q7. GSAT is an example of which of the following:
a. Hill-Climbing with random restarts
b. Random Walk
c. Hill Climbing with random walk
d. Genetic Algorithm

Answer: c. Hill Climbing with random walk

These are An Introduction to Artificial Intelligence Answers Week 7

Q8. Which of the following are correct about the soundness and completeness of Resolution (RE) and Forward Chaining (FC) as proof systems for inference in logic?
a. RE is complete.
b. RE is sound
c. FC is complete.
d. FC is sound

These are An Introduction to Artificial Intelligence Answers Week 7

Q9. Which of the following statements are correct about the ontological and epistemological characteristics of First order logic (FOL) and Probabilistic Propositional Logic/Bayesian Networks (BN)?
a. FOL and BN have similar ontology
b. FOL and BN have different ontology
c. FOL and BN have similar epistemology
d. FOL and BN have different epistemology

These are An Introduction to Artificial Intelligence Answers Week 7

Q10. Which of the following is an equivalent CNF form of the formula (p -> q) -> (p -> r) ?
a. (p ^ ¬q) V (¬p V r)
b. (¬q V ¬p V r)
c. (¬p V q) ^ (¬p V r)
d. r ^ (¬q V ¬p V r)

Answer: b. (¬q V ¬p V r)

These are An Introduction to Artificial Intelligence Answers Week 7