# Logic & Formal Reasoning

### Using Rewriting Rules for Connection Graphs to Prove Theorems

Essentially, a connection graph is merely a data structure for a set of clauses indicating possible refutations. The graph itself is not an inference system. To use the graph, one has to introduce operations on the graph. In this paper, we shall describe a method to obtain rewriting rules from the graph, and then to show that these rewriting rules can be used to generate a refutation plan that may correspond to a large number of linear resolution refutations. Using this method, many redundant resolution steps can be avoided.

### Prolegomena to a Theory of Mechanized Formal Reasoning

This is an informal description of my ideas about using formal logic as a tool for reasoning systems using computers. Introduction The title of this paper contains both the words'mechanized' and'theory'. I want to make the point that the ideas presented here are not only of interest to theoreticians. I believe that any theory of interest to artificial intelligence must be realizable on a computer. I will not present difficult examples.

Box 98, Palo Alto, California 94302 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means--electronic, mechanical, photocopying, recording, or otherwise--without the prior written permission of the publisher.

### REASONING ABOUT KNOWLEDGE AND ACTION / 473 REASONING ABOUT KNOWLEDGE AND ACTION

The first section discusses the importance of having systems that understand the concept of knowledge, and how knowledge is related to action. Section 2 points out some of the special problems that are involved in reasoning about knowledge, and section \$ presents a logic of knowledge based on the idea of possible worlds. Section 4 integrates this with a logic of actions and gives an example of reasoning in the combined system. Section 5 makes some concluding comments. I. Introduction One of the most important concepts an intelligent system needs to understand is the concept of knowledge.

### EPISTEMOLOGICAL PROBLEMS OF Al / 459

EPISTEMOLOGICAL PROBLEMS OF ARTIFICIAL INTELLIGENCE John McCarthy Computer Science Department Stanford University Stanford, California 94305 Introduction In (McCarthy and Hayes 1969), we proposed dividing the artificial intelligence problem into two parts - an epistemological part and a heuristic part. This lecture further explains this division, explains some of the epistemological problems, and presents some new results and approaches. The epistemological part of Al studies what kinds of facts about the world are available to an observer with given Opportunities to observe, how these facts can be represented in the memory of a computer, and what rules permit legitimate conclusions to be drawn from these facts. It leaves aside the heuristic problems of how to search spaces of possibilities and how to match patterns. Considering epistemological problems separately has the following advantages: I. The same problems of what information is available to an observer and what conclusions ...

### Circumscription--A Form of Non-Monotonic Reasoning

Circumscription formalizes such conjectural reasoning. McCarthy [6] proposed a program with common sense' that would represent what it knows (mainly) by sentences in a suitable logical language. It would decide what to do by deducing a conclusion that it should perform a certain act. Performing the act would create a new situation, and it would again decide what to do. This requires representing both knowledge about the particular situation and general common sense knowledge as sentences of logic.

### PROGRAM SYNTHESIS / 141

Program synthesis is the systematic derivation of a program from a given specification. A deductive approach to program synthesis is presented for the construction of recursive programs. This approach regards program synthesis as a theorem-proving task and relies on a theorem-proving method that combines the features of transformation rules, unification, and mathematical induction within a single framework. MOTIVATION The early work in program synthesis relied strongly on mechanical theoremproving techniques. More recently, program synthesis and theorem proving have tended to go their separate ways.

### P. J. HAYES

Minsky introduced the terminology of'frames' to unify and denote a loose collection of related ideas on knowledge representation: a collection which, since the publication of his paper (Minsky, 1975) has become even looser. It is not at all clear now what frames are, or were ever intended to be. I will assume, below, that frames were put forward as a (set of ideas for the design of a) formal language for expressing knowledge, to be considered as an alternative to, for example, semantic networks or predicate calculus. At least one group have explicitly designed such a language, KRL (Bobrow/ Winograd, 1977a, 19776), based on the frames idea. But it is important to distinguish this from two other possible interpretations of what Minsky was urging, which one might call the metaphysical and the heuristic (following the terminology of (Mc Carthy/Hayes, 1968)).

### PATRICK J. HAYES

The frame problem arises in attempts to formalise problem--solving processes involving interactions with a complex world. It concerns the difficulty of keeping track of the consequences of the performance of an action in, or more generally of the making of some alteration to, a representation of the world. The paper contains a survey of the problem, showing how it arises in several contexts and relating it to some traditional problems in philosophical logic. In the second part of the paper several suggested partial solutions to the problem are outlined and compared. This comparison necessitates an analysis of what is meant by a representation of a robot's environment.

### 202 / PROBLEM-SOLVING AND PLANNING

APPLICATION OF THEOREM PROVING TO PROBLEM SOLVING *t Cordell Green Stanford Research Institute Menlo Park, California Abstract This paper shows how an extension of the resolution proof procedure can be used to construct problem solutions. The extended proof procedure can solve problems involving state transformations. The paper explores several alternate problem representations and provides a discussion of solutions to sample problems including the "Monkey and Bananas" puzzle and the "Tower of Hanoi" puzzle. The paper exhibits solutions to these problems obtained by QA3, a computer program based on these theorem-proving methods. In addition, the paper shows how QA3 can write simple computer programs and can solve practical problems for a simple robot.