This section presents some basic theory about logic and Prolog. The vocabu-laries on both logic and Prolog are relatively large, and some of the basic terms are introduced here.
In essence the interactions in a domain, and data describing it, are given in Prolog using a set ofrules. These rules are described in one or more files, which
4.2 Basic Theory 39
can be interpreted by a Prolog interpreter. When doing so, the interpreter can answer questions about the domain, in accordance to the rules given. Prolog assumes a closed world, meaning that anything not explicitly declared is per definition non-existing.
Some Prolog systems offer graphical user interfaces, database connectivity, spe-cial constructs for software-based agents, and other features that enhance the usability of the system. For the evaluation of Prolog as the base of a DSS, such constructs are not necessary and they will not be described here.
Programming languages such as C/C++ are classified as imperative, which means that programs written using these languages describes the steps nec-essary for a program to evaluate input and produce output. These steps are described using statements, and the order of execution of these statements is determined by the programmer. As opposed to the imperative languages, Pro-log is a declarative programming language. Here the emphasis is on declaring the relations between input and output, and not on how these relations should be implemented by the programmer.
4.2.1 Logic
Logic is a mathematical discipline working with statements that can be either true or false. This is done using predicates, which are functions mapping their arguments into true/false. A predicate with arguments, or a negation of the predicate, is known as a literal. When using logic in describing a domain, the description may include objects. Variables ranging over the objects of the domain can also be included.
Treating weather as an object, it can be described using a number of vari-ables such as precipitation in millimetres, temperature in centigrade, etc. Some questions about the weather, such as ”is it raining?” or ”is it cloudy?” can be answered using the logical values true and false, while others may need an in-terpretation of the aforementioned variables. The question ”Is it warm?” could relate to the temperature: ”If the temperature is above 15◦C, it is warm”. This would map the temperature in to true/false.
As literals can take the values true and false, so can combinations of literals.
Four of the basic combinations, known as logical connectives, areor (∨), and (∧),not (¬), andimplies (⇒).
When literals are joined using the and-connective, they form a conjunction, where each part is known as a conjunct. Similarly, when joined usingor, they
40 The Prolog Approach
Figure 4.1: Truth tables for four basic connectives. 0 is used to representfalse and 1 representstrue.
form adisjunction, also know as aclause, and the parts are known asdisjuncts.
The values of combinations of literals, using e.g. the logical connectives, can be specified using a truth table. A truth table shows the values, true or false, of all combinations of its arguments. Figure 4.1 show the truth tables for the four mentioned connectives, each connecting two literals,A andB. In these tables the number 1 represents the value true, while 0 represents false.
Logic operations can be defined by their truth tables, and if two operations have identical tables, one may substitute the other. This is known asreversible substitution, and it is expressed using a double arrow (↔). As can be seen from the truth tables in Figure 4.1 the values forA⇒B are the same as the values for¬A∨B. This defines a rule of reversible substitution:
A⇒B↔ ¬A∨B (4.1)
The¬A used in (4.1) is called a negative literal, because of the negation, and B is then a positive literal. Clauses with at most one positive literal are known as Horn clauses1, and they form the cornerstone of the use of logic in Prolog.
Depending on the number of positive literals, two types of Horn clauses exist:
clauses with exactly one positive literal, known asdefinite clauses (see (4.2)), and clauses with no positive literals, known asgoals (see (4.3)).
¬A1∨ ¬A2∨. . .∨ ¬An∨B ↔ A1∧A2∧. . .∧An ⇒B (4.2)
¬A1∨ ¬A2∨. . .∨ ¬An ↔ A1∧A2∧. . .∧An ⇒ (4.3)
The interpretation of the definite clause in (4.2) is thatB is true only if all the literals A1, . . . , An, on the left-hand side of the ”⇒” are true. For the goal in (4.3) a literal should be introduced on the right-hand side of the ”⇒”, before the expression can be evaluated. If this literal is instantiated, i.e. it has the value true or false, the expression itself can be evaluated to either true or false.
1The logician Alfred Horn identified the significance of this type of clauses in 1951.
4.2 Basic Theory 41
If the literal is an un-instantiated variable, it should retrieve the value (true or false), which will make the evaluation of the expression return true.
Consider the special case of (4.3) withn= 2: A1∧A2⇒. HavingA1=trueand A2=f alse, and introducing the literalBon the right-hand side, the expression becomes: true∧f alse ⇒ B. If B itself evaluates to true, the goal is false (true∧f alse;true), while the goal is true if the value ofB is false. IfB is a variable it should therefore receive the valuefalse, since this would make the goal evaluate to true.
4.2.2 Horn Clause Logic
Horn clauses are often written with the positive literal to the left, the direction of the implication arrow reversed, and using commas foror, instead of∧:
B⇐A1, A2, . . . , An (4.4)
The literals on the right-hand side of the ’⇐’ constitute the premises (an-tecedents), and the literal on the left-hand side is the conclusion (consequent).
In Prolog the namesclauses,predicates,rules, andfunctionsare all synonymous with Horn clauses. Here the arrow is substituted by a colon and a dash:
b :- a1, a2, ..., an (4.5)
The clause in (4.5) can be read as ”bis true, if all the values on the right-hand side are true”. In Prolog literals starting with a capital letter are interpreted as variables (described later), and the literals used in (4.5) are thus written using minuscule letters.
If a literal serve as the consequent in multiple clauses in a Prolog program, the antecedents may be concatenated using a semi-colon:
b :- a1, a2; c1, c2 (4.6)
The clause in (4.6) can be read ”bis true ifa1 anda2are both true, or ifc1and c2 are both true”. The semi-colon can be interpreted as anor connective, and it has a higher precedence thanand. Parentheses can be introduced to alter the bindings of the colons and semi-colons.
42 The Prolog Approach
The clauses may be divided intofacts,relations, anddirectives. Common to all of these is that they must be terminated by a full stop. For the readability of this text, the full stop is often omitted.
The building blocks of Prolog areatoms andvariables. An atom is a concrete value, which can be a name (manpads), a string (’Turn left’) or a numerical value (600). All names have a minuscule as the first character.
Variables are used in enquiring about the contents of the facts given (see Section 4.2.2.1). As opposed to atoms variables are always written with a capital as the first character. Variables starting with the underscore (’ ’) is an exception of this. These are known as anonymous variables, since their names can not be referenced. See Section 4.3.2 for an example of questioning with Prolog using atoms and variables.
4.2.2.1 Facts
A fact is a clause with no antecedent, and it is unconditionally true. Facts may be unary, and if so, they are statements about their single argument, such asac type(fighter)oraltitude(600). The interpretation of a fact is deter-mined by the programmer, and these two facts may state that theDSSis used in a fighter aircraft flying at an altitude of 600 m. Hereac typeandaltitudeare the names of the facts, while fighterand 600are arguments to them. When more facts share the same name, each of these are said to be aninstance of the fact.
If a fact has two or more arguments, it describes a relation between these ar-guments. An example of such a fact is guidance(manpads, ir), declaring that MANPADSare using IR guidance. Prolog has no requirements to the or-der of arguments in a relation, and it is up to the programmer to keep the order of the arguments in similar facts. If the first argument in theguidance fact is defined to be a threat, and the second is a guidance system, then the guidance(manpads, ir) is a valid fact, with respect to this definition. Since Command is a guidance system andSA-2 is a threat the guidance(command, sa2)fact is not valid. Prolog has no understanding of guidance and it will not know valid facts from invalid facts. If it is asked about e.g. the guidance systems with these two facts, it would giveirandsa2as answers.
4.2 Basic Theory 43
4.2.2.2 Predicates
A predicate has the antecedents-consequent structure as seen in (4.5) and (4.6).
Whereas a fact is unconditionally true, a consequent in a predicate is only true if the antecedents are true. The antecedents can be either facts or predicates, or they can be comparisons of results from arithmetic operations.
The example below illustrates the use of both facts and predicates in describing the weather:
% Facts about the weather precipitation(rain).
weather(cloudy).
temperature(21).
% Predicates, describing the weather it_is_warm
:-temperature(T), T > 15.
weather_is_good :-it_is_warm, weather(sunny),
not(precipitation(_)).
The predicate it is warm will evaluate to true, since a fact is stating that the temperature is above 15◦C. Since it is raining and not sunny, the predicate weather is goodwill return false. The%mark a comment, and anything placed to the right of this is not interpreted by the Prolog interpreter. notis a standard Prolog-procedure, which is described later.
4.2.2.3 Lists and Structures
In Prolog a list is a data structure containing a number of elements. The list is described within square brackets; the empty list is denoted[], and non-empty lists have a head element and a tail, where the tail itself is a, possibly empty, list.
The head has one or more elements, and it is separated from the tail by using the vertical bar: ([Head|Tail]). To reference e.g. the third element in a list, which is also the third element in the head of the list, one writes[ , ,Third| ], and the element is referenced by the variable named Third. Elements in a list may be atoms, variables, lists, or structures.
44 The Prolog Approach
A structure is a collection of attributes used to describe objects. If a struc-ture is used to describe a person, the attributes may be the person’s name, age, and gender. Describing Tom, who is a 33 year old male, can then be done by person(tom, 33, male). A family consisting of a mother, a fa-ther, and a number of children can be described as a structure of persons family(person( , ,female), person( , ,male), [ | ]). Here the list at the end ([ | ]) describes the children, and since this description has at least one head element, the family has one or more children.
Structures can be used in goals, just like atoms or variables. In the example above, the goal of finding families, where the father’s name is Tom, can be formulated asfamily(person(tom, , ), , ), and finding families with exactly two children is done by: family( , ,[ , ]). As can be seen from these exam-ples, working with structures often deal with the structures of data, rather than the contents of these structures.
4.2.2.4 Directives
Directives are used to make the Prolog interpreter perform various standard operations, such as input/output, generating lists, etc. The number of direc-tives available varies from one Prolog implementation to another. Some of the standard directives, used in the Prolog program described in 4.5, are explained here
The:-include(<filename>)directive is used to include the contents of other Prolog files into an embedding file. When this is met by the interpreter, the content of the file, given as argument, is read and interpreted, as was it part of the embedding file.
findall,bagof, andsetofare procedures that will collect instances, fulfilling certain criteria, into a single list. findall and bagofare equivalent, and will both collect all instances into the list, thus allowing for multiple instances of elements in the list. Thesetofprocedure will produce a set of the instances, where each element of the set is only present once.
To output text to the screen thewriteprocedure is used. If the argument to the procedure is an atom (e.g. a string) it is written as it is, and if it is a variable, the value of this is written. To put a line break in the output thenldirective is used.
Thenotpredicate will return the negated value of its argument. If the argument is a goal that can be fulfilled, using thenotprocedure will return no.