Essay
Artificial Intelligence - Tests & Exams
- Course
- Artificial Intelligence
- Institution
- North-West University (NWU)
Compilation of class tests and previous exams together with memorandums.
[Show more]
1 review
By: awingray • 7 year ago
Content preview
Stuvia.co.za [ARTIFICIAL INTELLIGENCE II – ITRI 626]ITRI 626 – ARTIFICIAL
INTELLIGENCE
EXAM 2014 – NOTES
CONTENTS
1. Class Tests................................................................................................................................................... 2
a. Test 1 – 2013........................................................................................................................................... 2
b. Test 2 – 2013........................................................................................................................................... 3
c. Test 3 – 2013........................................................................................................................................... 5
d. Test 4 – 2013........................................................................................................................................... 8
e. Test 5 – 2013........................................................................................................................................... 8
2. Examinations ............................................................................................................................................... 9
a. 2009 .......................................................................................................................................................... 9
b. 2012 ........................................................................................................................................................ 14
c. 2013 ........................................................................................................................................................ 16
3. Reference ................................................................................................................................................... 20
EXAM NOTES 2014 1
, Stuvia.co.za [ARTIFICIAL INTELLIGENCE II – ITRI 626]
1. CLASS TESTS
A. TEST 1 – 2013
Question 1: Discuss the outline of a knowledge-based agent program. [8]
Like all our agents, it takes a percept as input and returns an action (1). The agent maintains a
knowledge base, KB, which may initially contain some background knowledge (1). Each time the
agent program is called, it does three things. First, it TELLS the knowledge base what it perceives (1).
Second, it ASKS the knowledge base what action it should perform (1). In the process of answering
this query, extensive reasoning may be done about the current state of the world, about the outcomes
of possible action sequences, and so on (2). Third, the agent records its choice with TELL and
executes the action (1). The second TELL is necessary to let the knowledge base know that the
hypothetical action has actually been executed (1).
Question 2 (Logic in general): Define the following terms:
(a) Logical entailment: ⊨ β [3]
α ⊨ β (1) if and only if in every model in which α is true (1), β is also true (1).
α ⊨ β (1) if and only if M(α) ⊆ M(β) (1), where M(α) denotes the set of all models of α, and
M(β) denotes the set of all models of β (1).
α ⊨ β (1) if and only if the sentence (α ⇒ Β) (1) is valid (1).
α ⊨ β (1) if and only if the sentence (α ⋀ ¬β) (1) is unsatisfiable (1).
(b) Model [3]
Models are mathematical abstractions (1), each of which simply fixes the truth or falsehood (1) of
every relevant sentence (1).
(c) Model checking [3]
With model checking all models are enumerated (1) to check that α is true in all models in which KB is
true (1), that is, that M(KB) ⊂ M(α) (1).
(d) A sound inference algorithm [3]
An inference algorithm that derives (1) only entailed (1) sentences (1) is called sound or truth-
preserving.
(e) A complete inference algorithm [3]
An inference algorithm is complete if it can derive (1) any sentence (1) that is entailed (1).
Question 3 (Logic in general)
Explain the difference between entailment and inference. [5]
EXAM NOTES 2014 2
, Stuvia.co.za [ARTIFICIAL INTELLIGENCE II – ITRI 626]
In understanding entailment and inference, it might help to think of the set of all consequences of KB
(1) as a haystack (1) and of α as a needle (1). Entailment is like the needle being in the haystack (1);
inference is like finding it (1).
Question 4 (Propositional Logic Syntax)
Interpreting the sentence letter “R” as “It is raining” and the letter “S” as “It is snowing”,
express the form of each of the following English sentences in the language of propositional
logic:
(a) It is not both raining and snowing. [2]
(b) It is not the case that if it is raining then it is snowing. [2]
(c) If it is both snowing and raining, then it is snowing. [2]
(a) ¬(R ⋀ S)
(b) ¬(R ⇒ S)
(c) (S ⋀ R) ⇒ S
Question 5 (Propositional Truth Tables)
Construct a truth table for the following well-formed formula: P ⇒ (Q ⋁ ¬R) [7]
P Q R ¬R Q ⋁ ¬R P ⇒ (Q ⋁ ¬R)
T T T F T T
T T F T T T
T F T F F F
T F F T T T
F T T F T T
F T F T T T
F F T F F T
F F F T T T
Each correct column of the truth table counts one mark. If the whole truth table is correct, another
mark is added.
Total [41]
B. TEST 2 – 2013
Question 1 (Propositional Theorem Proving)
By using a truth table, determine whether the following expression is correct. Show all your
reasoning and steps clearly. ((P ⇒ Q) ⋀ (M ⇒ P ⋁ Q)) ⊨ (Q ⇒ M) [14]
According to the deduction theorem, for any sentences α and β, α ⊨ β if and only if the sentence (α ⇒
β) is valid. (2)
∴ Show that ((P ⇒ Q) ⋀ (M ⇒ P ⋁ Q)) ⇒ (Q ⇒ M) is valid by using a truth table (2)
Consider the following truth table:
EXAM NOTES 2014 3
, Stuvia.co.za [ARTIFICIAL INTELLIGENCE II – ITRI 626]
P⇒ ((P ⇒ Q) ⋀ (M ⇒ P ⋁ Q)) ⇒ (Q ⇒ M)
P Q M P⋁Q M ⇒ (P ⋁ Q) Q⇒M (P ⇒ Q) ⋀ (M ⇒ P ⋁ Q)
Q
T T T T T T T T T
T T F T T T F T F
T F T F T T T F T
T F F F T T T F T
F T T T T T T T T
F T F T T T F T F
F F T T F F T F T
F F F T F F T F T
(8)
From the truth table it can be seen that ((P ⇒ Q) ⋀ (M ⇒ P ⋁ Q)) ⇒ (Q ⇒ M) is not valid and
consequently, the expression ((P ⇒ Q) ⋀ (M ⇒ P ⋁ Q)) ⊨ (Q ⇒ M) is not correct. (2)
Question 2 (Propositional Theorem Proving)
By using resolution, prove the following. Show all your steps and reasoning in full.
If Mary loves Pat, then Mary loves Quincy. If it is Monday, Mary loves Pat or Quincy. Prove that,
if it is Monday, then Mary loves Quincy. [20]
Suppose:
P is the proposition Mary loves Pat.
Q is the proposition Mary loves Quincy.
M is the proposition that it is Monday. (3)
The knowledge base has the following two sentences:
P⇒Q
M⇒P⋁Q
Prove: M ⇒ Q (3)
The negation of the goal is:
¬(M ⇒ Q)
¬(¬M ⋁ Q)
M ⋀ ¬Q (1)
This sentence is already in CNF.
Convert (P ⇒ Q) to CNF: ¬P ⋁ Q (2)
Convert (M ⇒ P ⋁ Q) to CNF: ¬M ⋁ P ⋁ Q (2)
This following gives the following four clauses:
1) ¬P ⋁ Q (1)
EXAM NOTES 2014 4
, Stuvia.co.za [ARTIFICIAL INTELLIGENCE II – ITRI 626]
2) ¬M ⋁ P ⋁ Q (1)
3) M (1)
4) ¬Q (1)
Resolution between (1) and (4) gives 5) ¬P
Resolution between (2) and (5) gives 6) ¬M ⋁ Q (5)
Resolution between (4) and (6) gives 7) ¬M
Resolution between (3) and (7) gives 8) The empty clause
Question 3 (First-Order Logic)
How does propositional logic and first-order logic differ in terms of the assumptions about the
nature of reality? [6]
Propositional logic assume that there are facts (1) that either hold (1) or do not hold in the world (1).
First-order logic assumes more; namely, that the world consists of objects (1) with certain relations
among them (1) that do or do not hold (1).
Question 4 (First-Order Logic)
What is the purpose of the interpretation included in each model? [2]
Each model includes an interpretation that specifies exactly which objects, relations, and functions are
referred to (1) by the constant, predicate and function symbols (1).
Total [42]
C. TEST 3 – 2013
Question 1 (Logical Agents)
1.1 Define the following terms:
(a) Logical entailment [4]
(b) The deduction theorem [5]
(c) Satisfiability [3]
(d) Monotonicity [3]
(e) Definitive clause [4]
(a) α ⊨ β (1) if and only if (1), in every model in which α is true (1), β is also true (1).
(b) For any sentences α and β (1), α ⊨ β (1) if and only if (1) the sentence (α ⇒ β) (1) is valid (1).
(c) A sentence is satisfiable (1) if it is true in, or satisfied by (1), some model (1).
(d) The set of entailed sentences (1) can only increase (1) as information is added to the knowledge
base (1). Or, for any sentences α and β (1), if KB ⊨ α (1) then KB ⋀ β ⊨ α (1).
(e) A definite clause is a disjunction (1) of literals (1) of which exactly one (1) is positive (1).
1.2 Give the full resolution rule. [5]
li lk , m1 mn
l1 li 1 li 1 lk m1 m j 1 m j 1 mn
EXAM NOTES 2014 5
, Stuvia.co.za [ARTIFICIAL INTELLIGENCE II – ITRI 626]
Where li and m j are complementary literals.
1.3 Describe the resolution algorithm. [6]
To show that KB ⊨ α, it is shown that (KB ⋀ ¬α) is unsatisfiable. First, (KB ⋀ ¬α) is converted into
conjunctive normal form (CNF). Then, the resolution rule is applied to the resulting clauses. Each pair
that contains complementary literals is resolved to produce a new clause, which is added to the set if
it is not already present. This process continues until one of two things happens:
There are no new clauses that can be added, in which case KB does not entail α; or,
Two clauses resolve to yield the empty clause, in which case KB entails α.
1.4 Use a truth table to show that (Q ⋁ R) ⋀ (Q ⇒ ¬P) ⋀ ¬(R ⋀ P) ⊨ ¬P is correct. Show all
your reasoning and steps clearly. [12]
To proof that that (Q ⋁ R) ⋀ (Q ⇒ ¬P) ⋀ ¬(R ⋀ P) ⊨ ¬P is correct, one must show that that (Q
⋁ R) ⋀ (Q ⇒ ¬P) ⋀ ¬(R ⋀ P) ⇒ ¬P is valid (1).
(Q ⋁ R) ⋀ (Q ⋁ R) ⋀ (Q ⇒
P Q R ¬P Q⋁R Q ⇒ ¬P R⋀P ¬(R ⋀ P) (Q ⇒ ¬P) ⋀ ¬P) ⋀ ¬(R ⋀ P)
¬(R ⋀ P) ⇒ ¬P
T T T F T F T F F T
T T F F T F F T F T
T F T F T T T F F T
T F F F F T F T F T
F T T T T T F T F T
F T F T T T F T F T
F F T T T T F T F T
F F F T F T F T F T
From the last column in the table one can see that (Q ⋁ R) ⋀ (Q ⇒ ¬P) ⋀ ¬(R ⋀ P) ⇒ ¬P is valid
and consequently (Q ⋁ R) ⋀ (Q ⇒ ¬P) ⋀ ¬(R ⋀ P) ⊨ ¬P is correct. Truth table = 11 marks.
1.5 Use the resolution algorithm to show that A ⇔ B ⊨ ¬A ⋁ B is correct. Show all your
reasoning and steps clearly. [15]
To show that A ⇔ B ⊨ ¬A ⋁ B is correct by using the resolution algorithm, it must be shown
that (A ⇔ B) ⋀ ¬(¬A ⋁ B) is unsatisfiable.
∴ Show that (A ⇒ B) ⋀ (B ⇒ A) ⋀ ¬(¬A ⋁ B) is unsatisfiable. [4]
Convert the (A ⇒ B) ⋀ (B ⇒ A) ⋀ ¬(¬A ⋁ B) expression to conjunctive normal form: [4]
∴ (¬A ⋁ B) ⋀ (¬B ⋁ A) ⋀ (A ⋀ ¬B) Implication elimination
∴ (¬A ⋁ B) ⋀ (¬B ⋁ A) ⋀ A ⋀ ¬B Implication elimination
Number the clauses as follows:
1. (¬A ⋁ B)
2. (¬B ⋁ A)
3. A
4. ¬B
Resolution between (1) and (3) gives
5. B
Resolution between (4) and (5) gives
EXAM NOTES 2014 6
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through EFT, credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying this summary from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller GeekyS. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy this summary for R50,00. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
80467 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy summaries for 14 years now