Frontier Software

Robert Laing's programing notes

Logic and Sets

By Robert Laing

Venn 27

Step 1: Choose your course topic.

Step 2: Define your target student and course goals.

Step 3: Decide how students will practice what you’re teaching.

Step 4: Create your course outline.

Step 5: Script your course.

1. Algebra of sets

Set-builder notation

How logic, sets and relational databases are tied together by set-builder notation, using queries to make a set of student IDs for computer science applicants, electrical engineering applications etc.

2. Complement

Explaining how set complements are done in Prolog. (Creating a set of all the students who haven’t applied for computer science in the example may seem easy, but there are quite a lot of subtle traps most novices will fall into, and there’s a catch in Prolog that + breaks associativity).

3. One lecture devoted to and, showing how it creates joins and intersections in relational databases, how it equates to multiplication in two-valued algebra, and how it’s used for traditional “imperative” programing in Prolog.

4. One lecture devoted to or, how it equates to addition in two-valued algebra. In Prolog, or is a bit more complicated than and in that besides semi-colons, it can also be written as separate rules with neck operators (which one person complained I didn’t explain properly in the Coursera version). Or’s relationship to if p(x) then … else… is generally confusing in programing, so I’ll also explain how cut ! fits in and Prolog’s -> syntactic sugar for ,!, which I previously omitted.

5. How to find all subsets in the application example. It only occurred to me after I used the difference between EE and CS applicants which in Jennifer Widom’s example is an empty set, ie false in Prolog, meant EE ⊆CS. I’d never understood the p ⇒ q rule in classical logic (which can be rewritten ¬p ∨q) before. Playing around with writing a general query to find all subsets of majors in Widom’s application example I found that De Morgan’s law converted my query to the material implication rule, so I found it a very educational example. Furthermore, if one writes the truth table for p ⇒ q using 0 and 1 instead of F and T, it equates to p ≤ q, a handy mnemonic for P ⊆ Q.

6. How to find all equivalent sets. Another bit of enlightenment I got was the algebraic manipulation required to get from P ⊆ Q and Q ⊆ P to (p ∧q) ∨(¬p ∧¬q) involves using algebra’s distribution rule in logic.

7. How to find all disjoint sets.

Symbolic logic: copulatives vs two-valued algebra

1853 George Boole, The Laws of Thought

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. — 1839 Augustus De Morgan, First Notions of Logic

1870 Charles Sanders Peirce, Description of a Notation for the Logic of Relatives

1870 William Stanley Jevons, Elementary Lessons in Logic




1881 John Venn, Symbolic Logic

For two sets A and B, there are 5 possible relations

  1. A ≡ B All A is all B
  2. A ⊆ B All A is some B
  3. B ⊆ A Some A is all B
  4. A ⋂ B Some A is some B
  5. A ≢ B No A is any B

These don’t include the difference between A and B (which might be hat Hamilton included in his eight).

  1. A - B Some A is not some B
  2. B - A Some B is not some A

1918 CI Lewis, A Survey of Symbolic Logic


Alexander MacFarlane

Christine Ladd-Franklin

Inclusion–exclusion principle

Stephen Kleene, Mathematical Logic

The domain, denoted by E, in these examples are the 12 student IDs in the student table. The subsets are taken from the appy table.

%! 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').

Relating sets and logic using Set-builder notation

Sets are defined using curly brackets, a variable name followed by either a colon or pipe bar meaning such that, and then a logical predicate X = {x|Φ(x)}.

It’s often important not to forget the domain E, so the above is shorthand for X = {x ∈ E|Φ(x)}, which can alternatively be written as X = {x| x ∈ E ∧ Φ(x)}.

In Prolog, the set of students who have applied for electrical engineering could be written as:

distinct(SID, apply(SID, _, 'CS', _)).

or alternatively

distinct(SID, (student(SID, _, _, _), apply(SID, _, 'CS', _))).

In the above example it makes no difference, but as we’ll see with complement, it’s important in some cases not to forget the domain.

Set Complement Pc or P', Logic not (or negation) ¬p

A subtlety of negation/complement in Prolog is one might think since apply(SID, _, 'CS', _) gives us the IDs of students who applied for computer science, simply negating that as \+apply(SID, _, 'CS', _) would give us those who didn’t. Instead, we just get false.

Another trap is to think “students who did not apply for CS” can be optained with distinct(SID, (apply(SID, _, _Major, _), _Major \== 'CS')). since it will match students who applied for CS and something else.

We can’t get the complement of the computer science applicants without first providing the full set of student IDs:

student(SID, _, _, _), \+apply(SID, _, 'CS', _).

Another subtlety is that the order of the above matters. Whereas in maths using associative and commutative and with unitary negation could be done in either order, in Prolog it can’t because SID has to be given a value before it can be crossed off a list.

It set, builder notation:

Pc = {p ∈ E|p ∉ P}

Set Intersection P ∩ Q, Logic conjunction p ∧ q

P ∩ Q = {p|p ∈ P ∧ p ∈ Q}

The intersection of students who have applied for computer science and electrical engineering would be:

distinct(SID, (apply(SID, _, 'CS', _), apply(SID, _, 'EE', _))).

In the example data, the ‘EE’ set happens to be a subset of ‘CS’, meaning the intersection equals the ‘EE’ set, which turns out makes it an example of logical implication.

Code to get all sets from the above example which intersect

distinct([Major1, Major2], 
         ( apply(_SID, _, Major1, _), apply(_SID, _, Major2, _),
           Major1 @< Major2

Set Difference P - Q (or P/Q)

P - Q = {p|p ∈ P ∧ p ∉ Q}

P ∩ Qc = {p|p ∈ P ∧ p ∉ Q}

apply(SID, _, 'CS', _), \+apply(SID, _, 'EE', _).

Essentially the same as complement, where P is now the universal set E.

Subset P ⊆ Q, Logic implication p → q

P ⊆ Q = {p|p ∉ P ∨ p ∈ Q}

This is equivalent to P - Q = {}

P ∩ Qc = {}

Thinking in terms of an analogy with arithmetic, if p + -q = 0, one would think p = q, but p has to be 0 and q has to be 1, so p + ¬q < 0, ie p < q.

For sets, P ∩ Qc ⊆ {} can be changed to P ⊆ Q

p → q is equivalent to ¬p ∨ q, which using De Morgan’s Law can be rewritten ¬(p ∧ ¬q)

p q ¬p ∨ q ¬(p ∧ ¬q)
1 1 1 1
1 0 0 0
0 1 1 1
0 0 1 1

Note the above is is also equivalent to p ≤ q because the only case it is false is 1 ≤ 0.

P ∩ Qc = ∅

{p|p ∈ P ∧ p ∉ Q} = ∅

if x * ¬a = ∅ (a = 0?)

then x * a = x (ie a = 1)

if A ⊂ B then a * b = a

Using the above two sets to illustrate, P is a subset of Q since there are no EE applicants who haven’t also applied for CS.

apply(SID, _, 'EE', _), \+apply(SID, _, 'CS', _).

The above returns false, ie P - Q = {}

A way to get all the subsets in the above example:

distinct([Subset, Superset], 
          (    apply(_, _, Subset, _), apply(_, _, Superset, _), 
               \+ (apply(_SID, _, Subset, _), \+apply(_SID, _, Superset, _)), 
               Subset \== Superset

Venn Diagram of subsets

Another sign that P ⊆ Q is that P ⋃ Q = Q

Set equivalence P ≡ Q, Logic equality p ↔ q

Sets P and Q being the same means P ⊆ Q and Q ⊆ P

(¬p ∨ q) ∧ (¬q ∨ p)

The distributive law, which in algebra means (a + b) * (c + d) = a*c + a*d + b*c + b*d also holds for logic, where we think of ∧ being like multiplication and ∨ being like addition.

So using the distributive law above

(¬p ∧ ¬q) ∨ (¬p ∧ p) ∨ (q ∧ ¬q) ∨ (q ∧ p)

The convention of writing and as *, or as +, and false as zero helps understand the next steps:

(¬p * ¬q) + 0 + 0 + (q * p)

(p * q) + (¬p * ¬q)

(p ∧ q) ∨ (¬p ∧ ¬q)

In the given example,

apply(_, CName, 'marine biology', _).


college(CName, 'MA', _).

are both equivalent, producing a set with the single element ‘MIT’.

Disjoint sets

distinct([Subset, Superset], 
          (    apply(_, _, Subset, _), apply(_, _, Superset, _), 
               \+ (apply(_SID, _, Subset, _), \+apply(_SID, _, Superset, _)),
               \+ (apply(_SID, _, Superset, _), \+apply(_SID, _, Subset, _)),
               Subset \== Superset
Last updated on 4 May 2021
Published on 4 May 2021

Content Footer