Artificial Intelligence A Modern Approach 2nd Edition Stuart J. Russell and Peter Norvig - Solutions

Represent the sentence “All Germans speak the same languages” in predicate calculus. Use Speaks (x, 1), meaning that person x speaks language l.
What axiom is needed to infer the fact Female (Laura) given the facts Male (Jim) and Spouse (Jim, Laura)?
Write a general set of facts and axioms to represent the assertion ‘Wellington heard about Napoleon’s death” and to correctly answer the question ‘Did Napoleon hear about Wellington’s death?”
Rewrite the propositional wumpus world facts from Section 7.5 into first-order logic. How much more compact is this version?
Write axioms describing the predicates Grand Child, Great Grandparent, Brother, Sister, Daughter, Son, Aunt, Uncle, Brother In Law, Sister In Law, and First cousin. Find out the proper definition of mth cousin n times removed, and write the definition in first-order logic. Now write down the basic
Write down a sentence asserting that + is a commutative function. Does your sentence follow from the Peano axioms? If so explain why: if not, give a model in which the axioms are true and your sentence is false.
Explain what is wrong with the following proposed definition of the set membership predicate ???:
Using the set axioms as examples write axioms for the list domain, including all the constants, functions, and predicates mentioned in the chapter.
Explain what is wrong with the following proposed definition of adjacent squares in the wumpusworld:
Write out the axioms required for reasoning about the wumpus’s location, using a constant symbol Wumpus and a binary predicate In (Wumpus, Location). Remember that there is only one wumpus.
Extend the vocabulary from Section 8.4 to define addition for n-bit binary numbers. Then encode the description of the four-bit adder in Figure and pose the queries needed to verify that it is in fact correct.
The circuit representation in the chapter is more detailed than necessary if we care only about Circuit functionality. A simpler formulation describes any rn-input, n-output gate or circuit using a predicate with m + n arguments, such that the predicate is true exactly when the inputs and outputs
Prove from first principles that Universal Instantiation is sound and that Existential Instantiation produces an inferentially equivalent knowledge base.
From Likes (Jerry, Ice Cream) it seems reasonable to infer Эx Likes (x, Ice Cream). Write down a general inference rule, Existential Introduction that sanctions this inference. State carefully the conditions that must be satisfied by the variables and terms involved.
Suppose a knowledge base contains just one sentence Эx As High As (x, Everest). Which of the following arc legitimate results of applying Existential Instantiation?a. As High As (Everest, Everest).b. As High As (Kilimanjaro, Everest).c. As High As (Kilimanjaro, Everest) ^ As High As (Ben Nevis
For each pair of atomic sentences, give the most general unifier if it exists:a. P(A, B, B), P(x, y, z).b. Q(y, G (A, B)), Q (G(x, x), y)c. Older (Father (y), y), Older (Father(x), John).d. Knows (Father (y), y), Knows(x, x).
Consider the subscription lattices shown in Figure.a. Construct the lattice for the sentence Employs (Mother (John), Father (Richard)).b. Construct the lattice for the sentence Employs (IBM. y) (“Everyone works for IBM”). Remember to include every kind of query that unifies with the sentence.c.
Suppose we put into a logical database a segment of the U.S. census data listing the age, city of residence, date of birth, and mother of every person, using social security numbers as identifying constants for each person. Thus, George’s age is given by Age (443-65-1282, 56). Which of the
One might suppose that we can avoid the problem of variable conflict in unification during backward chaining by standardizing apart all of the sentences in the knowledge base once and for all. Show that, for some sentences, this approach cannot work.
Explain how to write any given 3-SAT problem of arbitrary size using a single first-order definite clause and no more than 30 ground facts.
Write down logical representations for the following sentences, suitable for use with Generalized Modus Ponens:a. Horses, cows and pigs arc mammals.b. An offspring of a horse is a horse.c. Bluebeard is a horse,d. Bluebeard is Charlie’s parent.e. Offspring and parent are inverse relations.f. Every
In this question we will use the sentences you wrote in Exercise 9.9 to answer a question using a backward-chaining algorithm.a. Draw the proof tree generated by an exhaustive backward-chaining algorithm for the query Эh Horse (h), where clauses arc matched in the order given.b. What do you notice
A popular children’s riddle is ‘Brothers and sisters have I none, but that man’s father my father’s son.” Use the rules of the family domain to show who that man is. You may apply any of the inference methods described in this chapter. Why do you think that this riddle is difficult?
Trace the execution of the backward chaining algorithm in figure when it is applied solves the crime problem. Show the sequence of values taken on by the goals variable, and arrange them into a tree.
The following Prolog code defines a predicate P: P(X, [X | Y]). P (X, [Y| Z]):- P (X, Z).a. Show proof trees and solutions for the queries P (A, [1, 2, 3]) and P (2, [1, A, 3])b. What standard list operation does P represent?
In this exercise, we will look at sorting in Prolog.a. Write Prolog clauses that define the predicate sorted (L), which is true if and only if list L is sorted in ascending order.b. Write a Prolog definition for the predicate perm (L, M), which is true if and only if L is a permutation of M.c.
In this exercise, we will look at the recursive application of rewrite rules, using logic programming. A rewrite rule (or demodulator in OTTER terminology) is an equation with specified direction. For example, the rewrite rule x + O → x suggests replacing any expression that matches x + 0 with
In this exercise, we will consider the implementation of search algorithms in Prolog. Suppose that successor (X, Y) is true when state Y is a successor of state X; and that goal (X) is true when X is a goal state. Write a definition for solve (X, P), which means that P is a path (list of states)
How can resolution be used to show that a sentence is valid un-satisfiable?
From “Horses are animals:’ it follows that “The head of a horse is the head of animal.” Demonstrate that this inference is valid by carrying out the following steps:a. Translate the premise and the conclusion into the language of first-order logic. Use three predicates: Head Of (h, x)
Here are two sentences in the language of first-order logic:a. Assume that the variables range over all the natural numbers 0, 1, 2, . . , ∞ and that “>” predicate means “is greater than or equal to.” Under this interpretation translate (A) and (B) into English.b. Is (A)
Resolution can produce non-constructive proofs for queries with variables, so we had to introduce special mechanisms to extract definite answers. Explain why this issue does not arise with knowledge bases containing only definite clauses.
We said in this chapter that resolution cannot be used to generate all logical consequences of a set of sentences. Can any algorithm do this?
Write sentences to define the effects of the Shoot action in the wumpus world. Describe its effects on the wumpus and remember that shooting uses the agent’s arrow
Within situation calculus, write an axiom to associate time 0 with the situation S0 and another axiom to associate the time t with any situation that is derived from S0 by a sequence of t actions.
In this exercise, we will consider the problem of planning a route for a robot to take from one city to another. The basic action taken by the robot is Go (x, y), which takes it from City x to city y if there is a direct route between those cities. Direct Route (x, y) is true if and only if there
Investigate ways to extend the event calculus to handle simultaneous events. Is it possible to avoid a combinatorial explosion of axioms?
Represent the following seven sentences using and extending the representations developed in the chapter:a. Water is a liquid between 0 and 100 degrees.b. Water boils at 100 degrees.c The water in John’s water bottle is frn7en.d. Perrier is a kind of water.e. John has Perrier in his water
Write definitions for the following:a. Exhaustive Part Decompositionb. Part Partitionc. Part wise DisjointThese should he analogous to the definitions for Exhaustive Decomposition, Partition, and Disjoint. Is it the case that Part Partition (s, Bunch Of(s))? If so, prove it; if not, give a
Write a set of sentences that allows one to calculate the price of an individual tomato (or other object), given the price per pound. Extend the theory to allow the price of a bag of tomatoes to be calculated.
An alternative scheme for representing measures involves applying the units function to an abstract length object. In such a scheme, one would write Inches (Length (L1)) = 1.5. How does this scheme compare with the one in the chapter? Issues include conversion axioms, names for abstract quantities
Construct a representation for exchange rates between currencies that allows fluctuations on a daily basis.
This exercise concerns the relationships between event categories and the time intervals in which they occur,a. Define the predicate T(c, i) in terms of during and Є.b. Explain precisely why we do not need two different notations to describe conjunctive event categories.c. Give a formal definition
Define the predicate Fixed, where Fixed (Location(x)) means that the location of object x is fixed over time.
Define the predicates Before, After, during, and Overlap, using the predicate Meet and the functions Start and End, hut not the function Time or the predicate <.
Section 10.5 used the predicates Link and Link Text to describe connections between web pages. Using the In Tag and Get Page predicates, among others, write definitions for Link and Link Text.
One part of the shopping process that was not covered in this chapter is checking for compatibility between items. For example, if a customer orders a computer, is it matched with the right peripherals? If a digital camera is ordered, does it have the right memory card and batteries? Write a
Add rules to extend the definition of the predicate Name (s, c.) so that a siring such as “laptop computer” matches against the appropriate category names from a variety of stores. Try to make your definition general. Test it by looking at ten online stores, and at the category names they give
A complete solution to the problem of inexact matches to the buyer’s description in shopping is very difficult and requires a full array of natural language processing and information retrieval techniques. (See Chapters 22 and 23) One small step is to allow the user to specify minimum and maximum
Our description of Internet shopping omitted the all-important step of actually buying the product Provide a formal logical description of buying, using event calculus That is, define the sequence of events that occurs when a buyer submits a credit card purchase and then eventually gets billed and
Describe the event of trading something for something else. Describe buying as a kind of trading in which one of the objects traded is a sum of money.
The two preceding exercises assume a fairly primitive notion of ownership. For example, the buyer starts by owning the dollar bills. This picture begins to break down when, for example, one’s money is in the bank, because there is no longer any specific collection of dollar bills that one owns.
You are to create a system for advising computer science undergraduates on what courses to take over an extended period in order to satisfy the program requirements. (Use whatever requirements are appropriate for your institution.) First, decide on a vocabulary for representing all the information,
Figure shows the top levels of a hierarchy for everything. Extend it to include as many real categories as possible. A good way to do this is to cover all the things in your everyday life. This includes objects and events. Start with waking up, and proceed in an orderly fashion noting everything
Recall that inheritance information in semantic networks can be captured logically by suitable implication sentences. In this exercise, we will consider the efficiency of using such sentences for inheritance.a. Consider the information content in a used-car catalog such as Kelly’s Blue Book—
One might suppose that the syntactic distinction between unboxed links and singly boxed links in semantic networks is unnecessary, because singly boxed links are always attached to categories an inheritance algorithm could simply assume that an unboxed link attached to a category is intended to
Describe the differences and similarities between problem solving and planning.
Given the axioms from Figure, what are all the applicable concrete instances of Fly (p, from, to) in the state described by At (P1, JFK) ^ At (P2, SF0) ^ Plane (P1) ^ Plane (P2) A Airport (JFK) ^ Airport(SFO)?
Let us consider how we might translate a set of STRIPS schemata into the successor-state axioms of situation calculus.• Consider the schema for Fly (p, from. to). Write a logical definition for the predicate Fly Precond (p, from. to, s), which is true if the preconditions for Fly (p, from, to)
The monkey-and-bananas problem is faced by a monkey in a laboratory with some bananas hanging out of reach from the ceiling. A box is available that will enable the monkey to reach the bananas if he climbs on it. Initially, the monkey is at A, the bananas at B. and the box at C. The monkey and box
Explain why the process for generating predecessors in backward search does not need to add the literals that are negative effects of the action.
Explain why dropping negative effects from every action schema in a STRIPS problem results in a relaxed problem.
Examine the definition of bidirectional in,a. Would bidirectional state-space search be a good idea for planning?b. What about bidirectional search in the space of partial-order plans?c. Devise a version of partial-order planning in which an action can be added to a plan if its preconditions can be
Prove the following assertions about planning graphs:a. A literal that does not appear in the final level of the graph cannot he achieved.b. The level cost of a literal in a serial graph is no greater than the actual cost of an optimal plan for achieving it.
We contrasted forward and backward state-space search planners with partial-order planners, saying that the latter is a plan-space searcher. Explain how forward and backward state-space search can also be considered plan-space searchers, and say what the plan refinement operators are.
Figure shows a blocks-world problem known as the Sussman anomaly. The problem was considered anomalous because the non interleaved planners of the early 1970s could not solve it. Write a definition of the problem in STRIPS notation and solve it, either by hand or with a planning program. A non
Consider the problem of putting on one’s shoes and socks, as defined in Section 11.3. Apply GRAPHPLAN to this problem and show the solution obtained. Now add actions for putting on a coat and a hat. Show the partial order plan that is a solution, and show that there are 180 different
The original STRIPS program was designed to control Shakey the robot Figure shows a version of Shakey’s world consisting of four rooms lined up along a corridor, where each room has a door and a light switch. The actions in Shakey’s world include moving from place to place, pushing movable
We saw that planning graphs can handle only propositional actions. What if we want to use planning graphs for a problem with variables in the goal, such as At (P1, x) ^ At (P2, x), where x ranges over a finite domain of locations? How could you encode such a problem to work with planning graphs?
Up to now we have assumed that actions arc only executed in the appropriate situations. Let us see what propositional successor-state axioms such as Equation (11.1) have to say about actions whose preconditions are not satisfied.a. Show that the axioms predict that nothing will happen when an
Giving examples from the airport domain, explain how symbol-splitting reduces the size of the precondition axioms and the action exclusion axioms. Derive a general formula for the size of each axiom set in terms of the number of rime steps, the number of action schemata, their antics, and the
In the SATPLAN algorithm in Figure, each call to the satisfiability algorithm asserts a goal g T where T ranges from 0 to Tmax. Suppose instead that the satisfiability algorithm is called only once, with the goal g0 V g1 V…. Vg T maxa. Will this always return a plan if one exists with length
Examine carefully the representation of time and resources in Section 12.1.a. Why is it a good idea to have Duration (d) be an effect of an action, rather than having a separate field in the action of the form DURATION: d?b. Why is RFSOURCE: m a separate field in the action, rather than being an
A consumable resource is a resource that is (partially) used up by an action. For example, attaching engines to cars requires screws. The screws, once used, are not available for other attachments. a. Explain how to modify the representation in Figure so that there are 100 screws initially, engine
Give decompositions for the Hire Builder and Get Permit steps in Figure, and show how the decomposed sub plans connect into the overallplan.
Give an example in the house-building domain of two abstract sub plans that cannot be merged into a consistent plan without sharing steps.
Some people say an advantage of HTN planning is that it can solve problems like “take a round trip from Los Angeles to New York and back” that are hard to express in non-HTN notations because the start and goal states would be the same (At (LA)). Can you think of a way to represent and solve
Show how a standard STRIPS action description can be rewritten as HTN decomposition, using the notation Achieve (p) to denote the activity of achieving the condition p.
Some of the operations in standard programming languages can be modeled as actions that change the state of the world. For example, the assignment operation copies the contents of a memory location, while the print operation changes the state of the output stream. A program consisting of these
Consider the following argument: In a framework that allows uncertain initial stares, disjunctive effects are just a notational convenience, not a source of additional representational power. For any action schema a with disjunctive effect P V Q, we could always replace it with the conditional
Why can’t conditional planning deal with unbounded indeterminacy?
In the blocks world we were forced to introduce two STRIPS actions, Move and Move to Table, in order to maintain the clear predicate properly. Show how conditional effects can be used to represent both of these cases with a single action.
Conditional effects were illustrated for the Suck action in the vacuum world—which square becomes clean depends on which square the robot is in. Can you think of a new set of propositional variables to define states of the vacuum world, such that Suck has an unconditional description? Write out
Write out the full description of Suck for the double Murphy vacuum cleaner that sometimes deposits dirt when it moves to a clean destination square and sometimes deposits dirt if Suck is applied to a clean square.
Find a suitably dirty carpet free of obstacles, and vacuum it. Draw the path taken by the vacuum cleaner as accurately as you can. Explain it, with reference to the forms of planning discussed in this chapter.
The following quotes are from the backs of shampoo bottles. Identify each as an unconditional, conditional, or execution monitoring plan.(a) “Lather, Rinse, Repeat,’(b) “Apply shampoo to scalp and let it remain for several minutes. Rinse and repeat if necessary’(c) “See a doctor if
Specify in full the belief state update procedure for partially observable environments. That is, the method for computing the new belief state representation (as a list of knowledge propositions) from the current belief-state representation and an action description with conditional effects.
Write action descriptions, analogous to Equation (12.2), for the Right and Suck actions. Also write a description for Cheek Location, analogous to Equation (12.3). Repeat using the alternative set of propositions from Exercise 12.11.
Look at the list of things that the re planning agent can’t do. Sketch an algorithm that can handle one or more of them.
Consider the following problem: A patient arrives at the doctor’s office with symptoms that could have been caused either by dehydration or by disease D (but not both). There are two possible actions: Drink, which unconditionally cures dehydration, and Medicate, which cures disease D, but has an
To the medication problem in the previous exercise, add a Jest action that has the conditional effect Culture Growth when Disease is true and in any case has the perceptual effect Know (Culture Growth). Diagram a conditional plait that solves the problem and minimizes the use of the Medicate action.
Show from first principles that P (a│b ^ a) = 1.
Using the axioms of probability prove that any probability distribution on a discrete random variable must sum to 1.
Would it he rational for an agent to hold the three beliefs P (A) = 0.4, P (B) = 0.3, and P (A V B) = 0.5? If so, what range of probabilities would be rational for the agent to hold for A ^ B. Make tip a table like the one in Figure, and show how it supports your argument about rationality. Then
This question deals with the properties of atomic events, as discussed.a. Prove that (lie disjunction of all possible atomic events is logically equivalent to true.b. Prove that any proposition is logically equivalent to the disjunction of the atomic events that entail its truth.
Consider the domain of dealing 5-card poker hands from a standard deck of 52 cards, under the assumption that the dealer is fair.a. How many atomic events are there in the joint probability distribution (i.e., how many 5-card hands are there)?b. What is the probability of each atomic event?c. What
Given the full joint distribution shown in Figure, calculate the following: a. P (toothache) b. P (Cavity) c. P (Toothache ?cavity) d. P (Cavity ? toothache V catch).
Show that the three forms of independence in Equation (13.8) are equivalent.
After your yearly checkup, the doctor has bad news and good news. The bad news is that you tested positive for a serious disease and that the test is 99% accurate (i.e., the probability of testing positive when you do have the disease is 0.99, as is the probability of testing negative when you
It is quite often useful to consider the effect of some specific propositions in the context of some general background evidence that remains fixed, rather than in the complete absence of information. The following questions ask you to prove more general versions of the product rule and Bayes’

Showing 100 - 200 of 976

Artificial Intelligence A Modern Approach 2nd Edition Stuart J. Russell and Peter Norvig - Solutions

Step by Step Answers