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	P^c = 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:

“Which students have not applied for CS?” (negation)
“Which students applied for CS and EE?” (conjunction)
“Which students applied for CS or EE?” (disjunction)
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)
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 Π_{a₁,…a_n}(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.

Π_{a₁, a₂,…a_n}(σ_φ(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.

All P is all Q
All P is some Q
Some P is all Q
Some P is some Q
Any P is not any Q
Any P is not some Q
Some P is not any Q
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.

Classical Logic

What is true?

Selection σφ(R)

Projection Πa1,…an(R)

What is false?

Propositional vs Predicate logic

Basic College example

SQL

Prolog

Which students applied for ‘CS’?

SQL

Prolog

Sets vs sorted lists/arrays

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

Selection σ_φ(R)

Projection Π_{a₁,…a_n}(R)