# 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:

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;`

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;`

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 σ— Wikepedia entry on relational algebra._{φ}(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.

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

${\sigma}_{\mathrm{Major}=\mathrm{\text{'}CS\text{'}}}\left(\mathrm{Apply}\right)$### 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:

$\mathrm{CIDs}=\left\{123,345,543,876,987\right\}$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

$\mathrm{CIDs}=\left[123,345,543,876,987\right]$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.