# Classical Logic

*By Robert Laing*

## {Socrates} ⊆ Human

Learning Prolog got me Googling the classics on logic whereby I discovered the Venn diagrams we learn early at school to associate with sets actually came from a book titled Symbolic Logic. I either wasn’t taught or didn’t pay attention in school and during my tertiary education in electrical engineering that what is commonly termed Boolean algebra is tightly related to set theory and probability theory, and also the workflow of computer programs.

Something that made me chuckle reading the footnotes of John Venn’s book is how back in Victorian times he was engaging in what we’d call a twar today against the chief proponent of syllogistic logic William Hamilton who taught that logic could be boiled down to 8 ways of “quantifying the predicate”:

- 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

Victorian students forced to pass exams on syllogism seem to have really hated it, judging from the vitriol Augustus De Morgan and his disciples like Venn spewed at Hamilton.

I find it amusing that a little Victorian syllogism has survived in SQL with
ANY/SOME (array) and
ALL (array).
The SQL functions *any* and *some* are identical, whereas Hamilton’s rule 5 *Any P is not any Q* and rule 6 *Any P is not some Q*
show he regarded them as different. I’ve put my interpretation of what the distinction may be in the table below
in which I’ve tried to translate these syllogisms into more modern notation.

As an exercise in teaching myself SVG, I’ve redone Venn’s diagram from p6 of the pdf linked to above which he argued proved there are only five ways
that two sets, P and Q, can be *related*, meaning three of Hamilton’s *predicate quantifiers* are redundant duplicates.

Looking at Venn’s diagram, I kinda see where Hamilton’s 8 *predicate quantifiers* fall.

Syllogism | Set notation | |
---|---|---|

1 | All P is all Q | P = Q (Diagram 1) |

2 | All P is some Q | P ⊂ Q (Diagram 2) |

3 | Some P is all Q | P ⊃ Q (Diagram 3) |

4 | Some P is some Q | P ∩ Q (Centre of Diagram 4) |

5 | Any P is not any Q | Disjointed (Diagram 5) |

6 | Any P is not some Q | Q - P ≠ ∅ (Diagram 2 or right side of 4) |

7 | Some P is not any Q | P - Q ≠ ∅ (Diagram 3 or left side of 4) |

8 | Some P is not some Q | (P ∩ Q)^{C} (The left and right sides of Diagram 4) |

What I’ve been wrapping my head around doing various database projects is how sets, logic’s 5 operators, and relational algebra are related,
leading to a couple of *Aha!* moments which I’m elaborating on in these notes. I’ve given each of the 5 logic operators
it’s own section with examples of how they creep up in various guises in computer coding.

If you’re not familiar with the 5 operators of classical logic, I suggest an old 15 page textbook, Mathematical Logic, by Stephen Cole Kleene or Chapter 2 of Michael Genesereth’s free online textbook Introduction to Logic.

Logic is often split into propositional logic and predicate logic. I’ve linked to the respective chapters in Foundations of Computer Science, a textbook kindly made freely available online by its authors Al Aho and Jeff Ullman which I tend to use as my “Oxford Dictionary” for computer jargon.

I’ve personally battled to understand the distinction between predicate logic (often called first order logic or “fol”) and propositional logic,
and have developed my own separation of logic from a code-monkey’s perspective: there’s logic down at the *selector level* (what goes after the
`WHERE`

clause in SQL) and then up at the *set level*.

SQL unfortunately uses the word *select* for what relational algebra calls *project*, using the word
*where* for what should be called *select*. Thinking in terms of lists rather than databases as a computer representation of sets,
selectors are called filters, eg Prolog’s include(:Goal, +List1, ?List2).

In whatever guise they appear, they are built out of predicate calculus’s 5 operators. To give practical examples, I’ve plagiarised the introductory SQL examples from Stanford University dean Jennifer Widom’s Relational Databases and SQL online course, translating them into Prolog and using them to illustrate my interpretation of logic.

### What is a predicate?

Before diving into the code, I’d like to give my own simplified definition of predicate since the word has completely different meanings in different fields:

- Grammar
- A predicate is the part of the clause of a sentence which is not the subject, as shown in the above diagram.
- Logic
- Variables in equations such as p ∧ q which can hold one of two values, aka booleans.
There's a Tower of Babel regarding what these two values may be:
*1*or*0*,*true*or*false*,*yes*or*no*,*on*or*off*, ⊤ or ⊥ ... An old convention in maths textbooks is to use p and q as variable names in logic equations, saving x and y for traditional number equations. - C and related programming languages
- A function which returns a boolean. Though C follows the convention 1=true, Unix shell scripts use the convention that that 0=true since having lots of falses in more convenient for dispatching to error handlers. Also in Unix shell scripts, the exit code which returns 0 for true is separate from the text returned.
- Prolog
- A Prolog predicate is akin to what SQL would call a row. In some ways this is similar to the
traditional computer programming definition in that in the following examples
`apply(SID, CName, logic, Decision).`

would return*false*since it doesn't match any row in the`apply`

table whereas`apply(SID, CName, 'CS', Decision).`

matches several rows. So*true*at the set level means some results, while none in Prolog means*false*, in contrast to SQL which would return`NULL`

(making NULL akin to false in some cases)

#### Copulatives ∧ ∨

As is sadly common in maths, a subject most people already find intimidating is made incomprehensible by no two textbooks
using the same symbols. I favour what’s known as *copula notation* of ∧ for *and* and ∨ for *or*. A reason these
are nice is they are handy mnemonics for their set level counterparts, ∩ and ∪.

Another advantage of *copula notation* is it makes remembering De Morgan’s law easy: you simply flip the symbols and
change the negation from the paranthesised group to each individual variable, eg:

(p ∧ q) = p ∨ q

Of the many conventions for negation, I prefer overscores since writing ¬p invites confusion with arithmetic’s minus sign. Negating logic’s 1 produces 0, not -1. And negating 0 produces 1, not -0 which would leave 0 unchanged.

Logic’s *and* and *or* are aggregators,
and a handy trick when manipulating logic equations is to think of *and* as
multiplication and *or* as addition, a concept I initially found weird since the word *and* made me think +, so it’s a bit counter-intuitive
that it’s ×.

An advantage of replacing ∨ with + and ∧ with, uhm, concatenation as in pq to represent multiplication, all the usual rules of algebra apply. I wish I’d known that back in college where I wasted a lot of time labouriously writing out truth tables to check if two logical equations were equivalent. I’ll use this later to show how to derive the equation for equality from reciprocal implication.

As with multiplication and addition, in logic we usually have a long list of pees and queues to get the product or sum of. Thinking of them as
binary operators is often less helpful thank thinking of them as functions which take in a list of arbitrary length.
Some textbooks use ∀ for p_{1} ∧ p_{2} ∧ p_{3}… and
∃ for p_{1} ∨ p_{2} ∨ p_{3}…, which in my view just adds to the clutter
of confusing symbols in symbolic logic.

If we use 0 and 1 as the two possible values of p_{i}, thinking of *anding* as multiplication makes it fairly obvious that if
there’s a single 0, the aggregate value is 0, but thinking of *oring* as addition doesn’t work quite as nicely since in logic, 1 + 1 + 1 + … = 1.

A way round that is to think of *anding* as min(p_{1}, p_{2}, p_{3}, …) and
*oring* as max(p_{1}, p_{2}, p_{3}, …). That also makes understanding game trees easier,
clearing up that and-or trees and minimax trees are exactly the same thing.

SQL has `bool_and ( boolean )`

along with the synonymous `every ( boolean )`

and `bool_or ( boolean ) `

,
but since true is stored as 1 and false as 0, `min(int)`

and `max(int)`

also work.

*And*, *or*, and *not* cover what we can do with our pees and queues. The last two rules of classical logic, implication and equality,
boil down the only two ways of creating or generating *predicates*. Instead of using p and q as variable names in these, I think it better to use
a and b since these could be anything, but their result is a boolean as in true or false. So a ≤ b and a = b are how we
create our pees and queues to use with the other three operators. What I’m trying to say is p = a ≤ b or p = (a = b), but that’s very
confusing.

#### The first type of predicate generator — implication: a ≤ b

A convention I’ve adopted that I’ve not seen anywhere else is using ≤ for implication, which again is a spikey version of its set level cousin ⊆. I found the implication truth table completely incomprehensible until I had the epiphany that all it is saying is whether a is less than or equal to b:

a | b | a ≤ b |
---|---|---|

0 | 0 | T |

0 | 1 | T |

1 | 0 | F |

1 | 1 | T |

I’m using 1 and 0 as the *type* for a and b, so note the domain change to T and F for the results of the implication and equality operators.
There’s a way around that by writing implication as p ∨ q, which in turn can be used
to rewrite p = q as (p ∧ q) ∨ (p ∧ q),
but I find this domain change illustrates that implication and equality are the *words* of *predicate calculus*, whereas
*and*, *or*, and *not* are the punctuation.

When I say this is one of the only two ways of creating a predicate, I’m generalising the plethora of boolean functions most programing languages have for various types. If we’re not dealing with numbers, we can think of boolean tests such as some text being a substring (or possibly the same) as some other text, being of a given type being checked, being a member of a set… all these broadly fall into the pattern a ≤ b.

How would you test a < b if the only tools in your box are a ≤ b, b ≤ a and a = b? By turning to the other three logical operators, ie by rewriting a < b as a ≤ b ∧ a = b, or alternatively (b ≤ a).

A sidenote on reordering a and b rather than bringing in a ≥ b, the Venn diagram I redrew above was predated by Napoleonic-era French mathematician Joseph Diez Gergonne who left out Diagram 3 since if you say whatever variable you assign to the left hand set (P in my case) is the subset and the right hand set (I picked Q) is the superset, you only need Diagram 2. But I’d say Venn is correct in adding an extra case because when establishing the relation between two sets, you need to have separate cases where P is the superset of Q, and where P is the subset of Q.

#### The second type of predicate generator — equality: a = b

Logic’s equality table from a code-monkey’s perspective at first seems a bit “duh”: if a and b can only be assigned 0 or 1, the two
rows where they are both 0 or both 1 are true, and the other two false. While testing *atomic types* is fairly straightforward, sets get
tricky, especially if they’re not *enumerable*, and here logic has a neat trick of defining equality as *reciprocal implication*,
ie substituting a = b with a ≤ b ∧ b ≤ a.
As I’ll show in later examples, this is handy for testing if database tables are equivalent.

a | b | a = b |
---|---|---|

0 | 0 | T |

0 | 1 | F |

1 | 0 | F |

1 | 1 | T |

There’s also a way of writing equality algebraically to stay in the realm of 0 and 1 instead of going to
T and F by (p ∧ q) ∨ (p ∧ q).
I found deriving that from reciprocal implication
(p ∨ q) ∧ (q ∨ p)
by first converting *and* to *multiplication* and *or* to *addition*, and then dusting off my algebra quite fun, but not really necessary for the
topic at hand.

A common coding pitfall, unrelated to logic or set theory, is checking equality of abstract data types and getting *false* even
when they look identical. This is because most programing language see, say lists, as memory addresses without looking at their contents.
Prolog is about the only computer language I know which checks if lists are equal without needing them to be converted into
text first or some other hack.

One of the reasons I prefer 1 and 0 to true and false is it avoids straying into philosophy — one minute you’re trying to simplify your code, and the next you’re neck deep in Ludwig Wittgenstein — but let’s do that in the next section by asking what is truth?