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

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

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.

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₁ ∧ p₂ ∧ p₃… and ∃ for p₁ ∨ p₂ ∨ p₃…, 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₁, p₂, p₃, …) and oring as max(p₁, p₂, p₃, …). 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:

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.

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?

Truth

By Robert Laing

What is true?

For our purposes, any garbage is true, provided it’s in the database.

Prolog possibly makes that clearer by saying you assert(+Term) “facts” into the database as opposed to SQL’s INSERT.

Furthermore, truth is mutable, something which upset ancient Greek philosopher Cratylus so much, he stopped speaking and would only communicate by wagging his finger.

To back up the assertion I made in the intro that all boolean functions (aka predicates) boil down to either a ≤ b or a = b which can then be strung together with and, or, and not, I’d like to quickly run through the 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.

Conjunction

By Robert Laing

In computer programing, we meet conjunction in various forms: as the and separator between boolean tests, as set intersections, as database table inner joins, as product in 2 value algebra, as as series statements in flow control.

Negation

By Robert Laing

It is a very common mistake to imagine that the denial of a proposition gives the right to affirm the contrary; whereas it should be that the affirmation of a proposition gives a right to deny the contrary. — First Notions of Logic, Augustus De Morgan

In logic, negation is a unary operator which toggles whichever of the two values a variables holds — I’m using 1 or 0, but it could be true or false, ⊤ or ⊥, yes or no, on or off, … — to the other.

Disjunction

By Robert Laing

In computer programing, we meet disjunction in various forms: as the or separator between boolean tests, as set union, as database table outer joins, as sum in 2 value algebra, as as parallel statements in flow control.

Implication

By Robert Laing

Of classical logic’s four binary operators, one whose truth table I initially found incomprehensible, was implication. In contemporary textbooks implication tends to be written using the arrow operator p ⇒ q. Older texbooks use p ⊃ q, making it even more confusing by misleading one to think p is a superset of q. It turns out it’s actually the other way round.

Gottlob Frege’s Begriffsschrift uses a kind of branching wiring diagram for implication.

Equivalence

By Robert Laing

Equivalence is reciprocal implication. Though I generally find the implication arrow confusing, here p ⇒ q and q ⇒ p makes a handy mnemonic for p ⇔ q

In logic and regular algebra, if p ≤ q and q ≤ p, then we know p = q. Similarly for sets, if P ⊆ Q and Q ⊆ P, then P = Q.

As usual, lets illustrate with the college example tables.