Prolog Cookbook

  1. Documenting, testing, and moduling
  2. Classical Logic
    1. Negation
      1. Not
      2. Difference
      3. Fill Values
      4. De Morgan's Law
    2. Conjunction
      1. And
      2. Intersection
      3. Inner Join
      4. Product
      5. Series
    3. Disjunction
      1. Or
      2. Union
      3. Outer Join
      4. Sum
      5. Parallel
    4. Implication
      1. Proofs
    5. Equivalence
  3. Automata
  4. Graph Traversal
    1. Depth First
    2. Breadth First
    3. Transitive Closures
  5. Route Finding
  6. Puzzle Solving

Classical Logic

By Robert Laing

The algebra of logic, in its generally accepted form, is hardly old enough to warrant the epithet "classic". A Survey of Symbolic Logic by Clarence Irving Lewis

As my template for classical logic, I’m going to use an old 15 page textbook, Mathematical Logic, by Stephen Cole Kleene. The basic building blocks, along with how they are written in different maths conventions and programing languages, I’ve summarised in the table below.

Much the same ground as in Kleene’s book is covered in Chapter 2 of Michael Genesereth’s free online textbook Introduction to Logic.

Foundations of Computer Science by Al Aho and Jeff Ullman is another wonderful free resource. It has a chapter on propositional logic.

CNF Set C-family SQL Prolog Product-of-Sums
Negation ¬ ¬p Pc = E - P !p NOT p \+ p p
Conjunction p ∧ q P ∩ Q p && q p AND q p , q p · q
Disjunction p ∨ q P ∪ Q p || q p OR q p ; q p + q
Implication ¬p ∨ q P ⊆ Q p IN Q member(p, Q) p + q
Equivalence (p ∧ q) ∨ (¬p ∧ ¬q) P = Q p == q p = q p == q p · q + p · q

I’ve given each of the above its own section, and those in turn have been split into subsections explaining how they relate to database queries written in SQL and Prolog, and also tried to think above the code by touching on other forms of each in set theory, relational algebra, and flow control.

Something I personally found handy to learn Prolog was translating the introductory SQL examples from Stanford University dean Jennifer Widom’s Relational Databases and SQL online course. I’ve put her original SQL college tables example below in SQL followed by my translation into Prolog, which I originally put on SWI Prolog webfrontend SWISH.

I’ve included the original SQL database creation script and my Prolog translation below: While doing this page, discovered psql’s \H command whereby select * from student; ouputs this:

Student Table
sid sname gpa sizehs
123 Amy 3.9 1000
234 Bob 3.6 1500
345 Craig 3.5 500
456 Doris 3.9 1000
567 Edward 2.9 2000
678 Fay 3.8 200
789 Gary 3.4 800
987 Helen 3.7 800
876 Irene 3.9 400
765 Jay 2.9 1500
654 Amy 3.9 1000
543 Craig 3.4 2000

select * from apply;

Apply Table
sid cname major decision
123 Stanford CS Y
123 Stanford EE N
123 Berkeley CS Y
123 Cornell EE Y
234 Berkeley biology N
345 MIT bioengineering Y
345 Cornell bioengineering N
345 Cornell CS Y
345 Cornell EE N
678 Stanford history Y
987 Stanford CS Y
987 Berkeley CS Y
876 Stanford CS N
876 MIT biology Y
876 MIT marine biology N
765 Stanford history Y
765 Cornell history N
765 Cornell psychology Y
543 MIT CS N

select * from college;

College Table
cname state enrollment
Stanford CA 15000
Berkeley CA 36000
MIT MA 10000
Cornell NY 21000

As the introductory example here, I’ll use “Which students applied for ‘CS’?”, and then addapt that query as follows to illustrate each of the five classical logic operators:

  1. “Which students have not applied for CS?” (negation)
  2. “Which students applied for CS and EE?” (conjunction)
  3. “Which students applied for CS or EE?” (disjunction)
  4. In the example data, a student applying for EE implies they allso applied for CS since EE is a subset of CS. “Which majors are subsets of more popular courses?” (implication)
  5. In the example data, no two majors contain the same set of student IDs, but that could be fixed by say having 678 applying for psychology, or 234 for marine biology. “Which majors attracted exactly the same students?”(equivalence)

To sidestep the problem discussed in fill values that the rows of tables need to be the same type for set operators to work, I’ll only the use the common sID column of student and apply in these examples illustrated by this Venn diagram.

What is true?

For our purposes, anything is true if it’s in the database. In Prolog jargon, each row of a database is a fact and its equivalent of SQL’s insert statement is called assert.

In Boolean algebra variables labelled p and q can have one of two values. These are sometimes called true and false, but also often 1 and 0, I think thanks to APL ⊤ and ⊥, besides yes and no, on and off

Of these, I tend to favour 1 and 0 because they allow us to use the rules of arithmetic with a few exceptions. As explained in product, and can be thought of as multiplication, and in sum that or is nearly the same as addition.

Selection σφ(R)

To find what’s true — ie in the database — we use what relational algebra calls selection statements.

A generalized selection is a unary operation written as σφ(R) where φ is a propositional formula that consists of atoms as allowed in the normal selection and the logical operators ∧ (and), ∨ (or) and ¬ (negation). This selection selects all those tuples in R for which φ holds.Wikepedia entry on relational algebra.

In SQL, σφ(R) looks like this:

SELECT *
FROM R
WHERE φ

Projection Πa1,…an(R)

It is unfortunate that the keyword SELECT in SQL corresponds not to the relational algebra operator called “selection” but to the operator called “projection.” ... The second part of the WHERE-clause is the selection condition. Foundations of Computer Science by Al Aho and Jeff Ullman

Relational algebra’s projection lets us omit or reshuffle columns.

Πa1, a2,…anφ(R))

SELECT a1, a2, ..., an
FROM R
WHERE φ

In Prolog, φ is the rule body. The head portion of a Prolog clause can be thought of as the projection Π.

What is false?

Something that confused me at first in combining logic and set theory is it involves thinking of true and false at two different scales.

First there’s the scale down at propositional formula φ level which involves iterating through every element of R to create a subset σφ(R) for which φ is true. I’ll digress into thinking of sets as either tables or sorted lists shortly. For lists/arrays, φ would be called a filter.

Second there’s the scale up at σφ(R) level. At this scale σφ(R) is true if it contains any elements, and false if it returns the empty set. Prolog makes that explicit by equating no result to false, whereas SQL calls that NOT EXISTS.

Propositional vs Predicate logic

This difference in scale I think ties into the difference between what I’ve called classical logic, also commonly called propositional logic, can be thought of as φ, whereas predicate logic — which is very close to Prolog — is a different syntax for σφ(R).

Basic College example

SQL

drop table if exists College;
drop table if exists Student;
drop table if exists Apply;

create table College(cName text, state text, enrollment int);
create table Student(sID int, sName text, GPA real, sizeHS int);
create table Apply(sID int, cName text, major text, decision text);

insert into Student values (123, 'Amy', 3.9, 1000);
insert into Student values (234, 'Bob', 3.6, 1500);
insert into Student values (345, 'Craig', 3.5, 500);
insert into Student values (456, 'Doris', 3.9, 1000);
insert into Student values (567, 'Edward', 2.9, 2000);
insert into Student values (678, 'Fay', 3.8, 200);
insert into Student values (789, 'Gary', 3.4, 800);
insert into Student values (987, 'Helen', 3.7, 800);
insert into Student values (876, 'Irene', 3.9, 400);
insert into Student values (765, 'Jay', 2.9, 1500);
insert into Student values (654, 'Amy', 3.9, 1000);
insert into Student values (543, 'Craig', 3.4, 2000);

insert into College values ('Stanford', 'CA', 15000);
insert into College values ('Berkeley', 'CA', 36000);
insert into College values ('MIT', 'MA', 10000);
insert into College values ('Cornell', 'NY', 21000);

insert into Apply values (123, 'Stanford', 'CS', 'Y');
insert into Apply values (123, 'Stanford', 'EE', 'N');
insert into Apply values (123, 'Berkeley', 'CS', 'Y');
insert into Apply values (123, 'Cornell', 'EE', 'Y');
insert into Apply values (234, 'Berkeley', 'biology', 'N');
insert into Apply values (345, 'MIT', 'bioengineering', 'Y');
insert into Apply values (345, 'Cornell', 'bioengineering', 'N');
insert into Apply values (345, 'Cornell', 'CS', 'Y');
insert into Apply values (345, 'Cornell', 'EE', 'N');
insert into Apply values (678, 'Stanford', 'history', 'Y');
insert into Apply values (987, 'Stanford', 'CS', 'Y');
insert into Apply values (987, 'Berkeley', 'CS', 'Y');
insert into Apply values (876, 'Stanford', 'CS', 'N');
insert into Apply values (876, 'MIT', 'biology', 'Y');
insert into Apply values (876, 'MIT', 'marine biology', 'N');
insert into Apply values (765, 'Stanford', 'history', 'Y');
insert into Apply values (765, 'Cornell', 'history', 'N');
insert into Apply values (765, 'Cornell', 'psychology', 'Y');
insert into Apply values (543, 'MIT', 'CS', 'N');

Prolog

My translation into Prolog looks as follows:

%! college(?CName:text, ?State:text, ?Enrollment:integer) is nondet
college('Stanford', 'CA', 15000).
college('Berkeley', 'CA', 36000).
college('MIT',      'MA', 10000).
college('Cornell',  'NY', 21000).

%! student(?SID:text, ?SName:text, ?GPA:float, ?SizeHS:integer) is nondet 
student(123, 'Amy',    3.9, 1000).
student(234, 'Bob',    3.6, 1500).
student(345, 'Craig',  3.5, 500).
student(456, 'Doris',  3.9, 1000).
student(567, 'Edward', 2.9, 2000).
student(678, 'Fay',    3.8, 200).
student(789, 'Gary',   3.4, 800).
student(987, 'Helen',  3.7, 800).
student(876, 'Irene',  3.9, 400).
student(765, 'Jay',    2.9, 1500).
student(654, 'Amy',    3.9, 1000).
student(543, 'Craig',  3.4, 2000).

%! apply(?SID:integer, ?CName:text, ?Major:text, ?Decision:text) is nondet
apply(123, 'Stanford', 'CS',             'Y').
apply(123, 'Stanford', 'EE',             'N').
apply(123, 'Berkeley', 'CS',             'Y').
apply(123, 'Cornell',  'EE',             'Y').
apply(234, 'Berkeley', 'biology',        'N').
apply(345, 'MIT',      'bioengineering', 'Y').
apply(345, 'Cornell',  'bioengineering', 'N').
apply(345, 'Cornell',  'CS',             'Y').
apply(345, 'Cornell',  'EE',             'N').
apply(678, 'Stanford', 'history',        'Y').
apply(987, 'Stanford', 'CS',             'Y').
apply(987, 'Berkeley', 'CS',             'Y').
apply(876, 'Stanford', 'CS',             'N').
apply(876, 'MIT',      'biology',        'Y').
apply(876, 'MIT',      'marine biology', 'N').
apply(765, 'Stanford', 'history',        'Y').
apply(765, 'Cornell',  'history',        'N').
apply(765, 'Cornell',  'psychology',     'Y').
apply(543, 'MIT',      'CS',             'N').

Please note the tablename apply is completely unrelated to Prolog’s builtin apply(:Goal, +List). I cut ’n pasted Widom’s tablename apply without remembering the word already has a common usage.

Which students applied for ‘CS’?

In relational algebra, this query would be written

σ Major = 'CS' Apply

SQL

This is one of the simplest examples of an SQL SELECT query.

SELECT * 
FROM Apply 
WHERE major = 'CS';
sid cname major decision
123 Stanford CS Y
123 Berkeley CS Y
345 Cornell CS Y
987 Stanford CS Y
987 Berkeley CS Y
876 Stanford CS N
543 MIT CS N

Prolog

Now doing the same using the data translated to Prolog:

apply(SID, CName, 'CS', Decision).

A nice thing about SWISH is it provides the option of a table output looking very much like the SQL rows above. At the swipl repl, pressing ; repeatedly to get all results, we get this:

?- apply(SID, CName, 'CS', Decision).
SID = 123,
CName = 'Stanford',
Decision = 'Y' ;
SID = 123,
CName = 'Berkeley',
Decision = 'Y' ;
SID = 345,
CName = 'Cornell',
Decision = 'Y' ;
SID = 987,
CName = 'Stanford',
Decision = 'Y' ;
SID = 987,
CName = 'Berkeley',
Decision = 'Y' ;
SID = 876,
CName = 'Stanford',
Decision = 'N' ;
SID = 543,
CName = 'MIT',
Decision = 'N'.

To keep things simple for the basic illustrative examples for the five basic operators, I’m going to use projection to limit elements in the answer sets to student IDs.

From now I’ll use curly bracketed sets to denote query results to avoid the differences between how the psql and swipl repl show query results. So for “Which students applied for ‘CS’?” the answer is:

CIDs = 123 345 543 876 987

In SQL, projection is done in the SELECT clause, which I need to combine with DISTINCT to remove duplicates. I also need ORDER BY to get sets holding the same elements to be ordered the same way.

SELECT DISTINCT sid 
FROM Apply 
WHERE major = 'CS'
ORDER BY sid;

Projection in Prolog equates to the head in Head :- Body rules. Since I only want the values of SID in these examples, I don’t need to load these rules from foo.pl files, but can instead turn the unwanted columns into anonymous variables coded by underscores.

SWI Prolog offers solution sequences builtins as direct equivalents of SQL’s DISTINCT, LIMIT, OFFSET, ORDER BY and GROUP BY. Here I’m using distinct(?Witness, :Goal) and order_by(+Spec, :Goal).

order_by([asc(SID)], distinct(SID, apply(SID, _, 'CS', _))).

Queries such as this which may match any number of facts are called non deterministic in Prolog jargon.

Deterministic queries are akin to SQL’s aggregate functions in that they return a single result.

Sets vs sorted lists/arrays

It’s often easier in Prolog to work with lists than databases, and facts from a database can be put in a list using the Finding all Solutions to a Goal builtins. I have a bias towards using findall(+Template, :Goal, -Bag) combined with sort(+List, -Sorted). The same could be done in one step with setof(+Template, +Goal, -Set), but it introduces its own minilanguage caret notation whereas findall uses Prolog’s usual underscore notation.

First argument Template lets us do projection without needing to rule head, and Prolog’s sort statement automates DISTINCT and ORDER BY by stripping out duplicates and ordering the result list according to default rules. There’s sort(+Key, +Order, +List, -Sorted) to give finer control to the sort order.

findall(SID, apply(SID, _, 'CS', _), Unsorted),
sort(Unsorted, CIDs).

Which gives us

CIDs = 123 345 543 876 987

A really nice thing about Prolog is that unlike C-family programing languages which see arrays as memory addresses, making it hard to directly compare their content, abstract data structures in Prolog that look the same are the same. This makes equivalence much easier by working with Prolog sorted lists rather than databases.

In these small, illustrative examples, curly bracketed sets and square bracketed lists/arrays are easily interchangeable. But in big databases, moving everything from disk to RAM isn’t practical, and list processing may be much slower.

Venn’s (or Gergonne’s?) 5 Relations

I’ve redone the diagram on p6 of John Venn’s Victorian-era book Symbolic Logic, which I’ve subsequently discovered are attributed Napoleonic-era French mathematician Joseph Diez Gergonne.

In his footnotes, Venn argued the diagram showed three of William Hamilton’s eight syllogism rules were redundant.

  1. All P is all Q
  2. All P is some Q
  3. Some P is all Q
  4. Some P is some Q
  5. Any P is not any Q
  6. Any P is not some Q
  7. Some P is not any Q
  8. Some P is not some Q

Since SQL offers ANY/SOME and ALL builtins for WHERE subqueries, I thought it would be fun to explore how to translate these syllogisms.

Next, lets start our exploration of classical logic’s five operators with negation.