## 1. Introduction
Programming systems in this way has multiple benefits. In writing or reading or modifying logic programs, programmers can get by with little or no knowledge of the capabilities and limitations of the systems executing those programs. As a result, logic programs are easier to produce than traditional programs; they are easier to understand; and they are easier to modify. Logic programs are more versatile than traditional programs - they can be used in multiple ways for multiple purposes without modification. And they are more amenable to programmatic analysis and optimization. Over the years, numerous variations of Logic Programming have been explored (e.g. Disjunctive Logic Programming, Constraint Logic Programming, Abductive Logic Programming, Inductive Logic Programming, and Answer Set Programming), and a variety of languages have been developed (e.g. Datalog and Prolog and Golog). In this paper, we focus on the most basic form of Logic Programming, called This paper is a brief introduction to Basic Logic Programming. In the first section, we talk about sentential databases, i.e. sets of simple facts. After that, we introduce basic logic programs, i.e. definitions of relations in terms of other relations, and we show how to combine datasets and view definitions to form deductive databases. Finally, we introduce transition rules and dynamic logic programs, and we show how they can be used to specify behavioral information. ## 2. Sentential DatabasesWhen we think about the world, we usually think in terms of objects and relationships among these objects. Objects include things like people and offices and buildings. Relationships include things like the parenthood, ancestry, office assignments, office locations, and so forth. In sentential databases, we encode each instance of a relationship in the form of a The A A As an example of these concepts, consider a small interpersonal database. The terms in this case represent people. The relation constants name properties of these people and their relationships with each other. In our example, we use the binary relation constant
The
We can express gender with two unary relation constants
As an example of a ternary relation, consider the data shown below. Here, we use
Note that the order of arguments in such sentences is important. Given the meaning of the ## 3. View DefinitionsThe language of logic programs includes the language of sentential databases but provides some additional features that make it more expressive. One key difference is the inclusion of a new type of symbol, called a An A A
Semantically, a rule is something like a reverse implication. It is a statement that the head of the rule is true whenever the subgoals are true. For example, the rule above states that The expressive power of rules is greatly enhanced through the use of variables. Consider, for example, the rule shown below. This is a more general version of the rule shown above. Instead of applying to just the specific objects
A The principal use of rules is to define new relations in terms of existing relations. The new relations defined in this way are often called To illustrate the use of rules in defining views, consider once again the world of interpersonal relations. Starting with the base relations, we can define various interesting view relations. As an example, consider the sentences shown below. The first sentence defines the
The rule below defines the grandparent relation in terms of the parent relation. A person
Note that the same relation can appear in the head of more than one rule. For example, the
A person
A childless person is one who has no children. We can define the property of being childless with the rules shown below. The first rule states that a person
Note the use of the helper relation In addition to writing definitions of common relations, rules are frequently used to write one-off queries on databases, including cases where the queries do not correspond to common relations. As a simple example, suppose we wanted to know all people who are grandparents of adults. We could ask this question by writing the query shown below.
Another use of rules is encoding constraints on databases. Such constraints often limit the set of possible databases. For example, a person cannot be his or her own parent. In some cases, constraints involve multiple relations. For example, all parents are adults; in other words, if a person appears as the first argument of a In many database texts, constraints are written in direct form - by writing rules that say, in effect, that if certain things are true in an extension, then other things must also be true. The In what follows, we use a slightly less direct approach - we encode limitations by writing rules that say when a database is This approach works particularly well for consistency constraints like the one stating that a person cannot be his own parent. It also works well for Using this technique, we can also write the
Database management systems can use such constraints in a variety of ways. They can be used to optimize the processing of queries. They can also be used to check that updates do not lead to unacceptable extensions. ## 4. Transition RulesIn our discussion thus far, we have been talking about the use of datasets and static logic programs to describe individual states of the world. In many application areas, it is necessary to describe not just individual states but also transitions between states. Transition rules and dynamic logic programs provide the means for us to describe such changes. The language of dynamic logic programming is a superset of the language of ordinary logic programing. Every ordinary logic program is also a dynamic logic program. As in ordinary logic programming, we can write ground atoms and view definitions. However, in dynamic logic programming, we can also write "transition rules", which encode information about how the state of the world changes (over time or in response to external stimuli). A transition rule is an expression of the form shown below. Each rule consists of (1) a literal (an atom or a negation of an atom) or a conjunction of literals, (2) a double shafted forward arrow, and (3) a literal or a conjunction of literals. The literals on the left are called
Intuitively, the meaning of a transition rule is simple. If the conditions of a rule are true in any state, then the effects must be true in the For example, the following rule expresses the fact that, when p(a) is true and q(a) is false, then p(a) becomes false and q(a) becomes true in the next state.
As with view definitions, the conditions and effects of rules may contain variables to express dynamic information in a compact form. For example, we can write the following rule to express the fact that the preceding transition rule holds for all objects.
As with view definitions, transition rules are required to be The transition rule rules shown above are all safe. However, the rules shown below are not. The effect of the first rule contains a variable that does not appear in any condition. In the second rule, there is a variable that appears in a negative condition that does not appear in any positive condition.
If we were to allow the first of these rules, the resulting dataset might contain infinitely many effects (all the instances of the rule's effect). If we were to allow the second rule, we might have to check infinitely many conditions (all of the instances of the negated condition). A dynamic logic program (DLP) is simply a collection of view definitions and transition rules. As with ordinary logic programs, we are interested primarily in dynamic logic programs that are finite. However, in analyzing dynamic logic programs, we occasionally talk about infinite DLPs, e.g. the set of all ground instances of the rules. A deterministic closed dynamic system is one that operates without external input, changing from one state to the next in a deterministic fashion. These are sometimes called closed systems or Markov systems. Note that, in addition to deterministic closed dynamic systems, there are also Transition rules are an effective way of describing the behavior of closed systems. As an example, consider a simple dynamic system like the one shown below There are three conditions that can hold in a state - p, q, and r - meaning that the system has a total of eight possible states. The The following transition rules express the behavior of this system. Given any state in which p is true, p becomes false in the next state; and vice versa. If p is true in a state, then q becomes true in the next state. If p and q are true in a state, then r becomes true in the next state; otherwise it becomes false.
This, of course, is a very simple closed system. There are many examples of closed systems in the real world. In fact, the universe as a whole can be viewed as a closed system (though there are some who would argue that it is really a non-deterministic closed system). An open dynamic system is one in which state changes depend not only on the current state of the system but also on inputs from the system's external environment. The most common example of such inputs are actions performed by one or more agents operating on the system. As an example, consider a variation on the closed system describe in Section 2. Again, the state of the system is based on three conditions p, q, and r. However, in this variation, the behavior of the system is determined not just by the current state but also by the actions on an external agent. In the version shown here, the agent has three possible actions - a, b, and c. Doing action a toggles p; doing action b interchanges p and q; and doing action r interchanges q and r. We can described the behavior of this simple system with the transition rules shown below.
Note that, if the system started in a state in which all three conditions were false, it could achieve a state in which they are true by executing the action sequence a, b, c, a, b, a. Can you think of a different sequence of actions that would do the trick? How many sequences are there that produce the desired state? ## ReadingsMichael Genesereth, Matt Ginsberg: Logic Programmming, Doug DeGroot, Gary Lindstrom: |