C. Montgomery Editor
Logic and Semantic Networks
Amaryllis Deliyanni University of Athens Robert A. Kowalski University of London
An extended form of semantic network is defined, which can be regarded as a syntactic variant of the clausal form of logic. By virtue of its relationship with logic, the extended semantic network is provided with aprecise semantics, inference rules, and a procedural interpretation. On the other hand, by regarding semantic networks as an abstract data structure for the representation of clauses, we provide a theorem-prover with a potentially useful indexing scheme and pathfollowing strategy for guiding the search for a proof. Key Words and Phrases: logic, semantic networks, theorem-proving, indexing,resolution, deduction, logic programming CR Categories: 3.42, 3.64, 5.21
In this paper we shall define an extended form of semantic network which can be regarded as a syntactic variant of the clausal form of logic. We define top-down and bottom-up inference and resolution more generally for the extended semantic network. In particular, topdown inference gives us a procedural interpretation of reasoningin the network. Not only can the extended semantic network be regarded as a syntactic variant of logic, but it can also be used as an abstract data structure for the representation of clauses in an implementation of a predicate logic proof procedure. The semantic network data structure provides an indexing scheme and helps to guide the search for a solution. In particular, as a data structure foran interpreter of predicate logic programs, it guides the execution of procedure calls. The strategy suggested by the network gives the proof procedure a path-finding flavor.
1. Simple Semantic Networks
A semantic network is a directed graph whose nodes represent individuals and whose arcs represent relationships between individuals. An arc is labeled by the name of the relationship itrepresents. Several arcs can have the same label. However, each individual is represented by only a single node. The English sentences "John gives the book to Mary" and "John and Mary are human" are represented in the following semantic network:
Mary ~el j >human
Introduction Logic and semantic networks are different formalisms for representing information. Several authors haveshown that simple semantic networks can be extended so that they have the same expressive power of predicate logic [5, 15, 16]. Still more recently, deductive inference systems for semantic networks have been investigated [2, 3, 17, 18].
Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, theACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. Authors' Addresses: R.A. Kowalski, Department of Computing and Control, Imperial College of Science and Technology, London SW7 2BZ, England; A.Deliyanni, Division of Electronics, University of Athens, Athens, Greece. © 1979 ACM 0001-0782/79/0300-0184 $00.75 184
Here " e l " names an event which is an act of giving, whose actor is John, object is book, and recipient is Mary. Arcs are not to be confused with access pointers. However, given a node in the network, it is assumed that the network provides direct access to all the relationships inwhich the node participates, independent of the direction of the arc.
2. The Clausal Form of Logic The relationships in the network above can be expressed in the clausal form of logic as follows: Obj (el, book) Act (el, give) ~-Actor (e 1, John) ~-Rec (e 1, Mary) 1. For example the sentence "John gives the book to Mary" might equally well be represented in logic by using a three argument...