Frontier Software

Robert Laing's programing notes

Logic and Sets

By Robert Laing

(A Survey of Symbolic Logic)[http://www.filosoficas.unam.mx/~morado/Cursos/17Modal/Lewis_A_Survey_of_Symbolic_Logic.pdf] by CI Lewis

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)}.

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 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 Complement Pc or P', Logic not (or negation) ¬p

Pc = {p|p ∈ E ∧ p ∉ P}

The are a couple of subtleties with this. Since we could get the student IDs of applicatns for computer science with apply(SID, _, 'CS', _)., I initially guessed I could those students who haven’t applied for computer science with \+apply(SID, _, 'CS', _). but that simply returns false.

Another trap would be apply(SID, _, Major, _), Major \== 'CS'. which returns students who’ve applied for majors besides computer science. Furthermore, we need to also get the four students who haven’t applied for anything yet.

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

Set Difference P - Q (or P/Q)

P - Q = {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}

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

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 = {}

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

is true. So using De Morgan’s Law:

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

Returns all the elements in Q.

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

distinct([Subset, Superset], 
          (    apply(_SID, _, Subset, _), apply(_SID, _, Superset, _), 
               \+ (apply(_SID, _, Subset, _), \+apply(_SID, _, Superset, _)), 
               Subset @> Superset
          )).

Or after using De Morgan’s law

distinct([Subset, Superset], 
          (    apply(_SID, _, Subset, _), apply(_SID, _, Superset, _), 
               (\+apply(_SID, _, Subset, _) ; apply(_SID, _, Superset, _)), 
               Subset @> Superset
          )).

Venn Diagram of subsets

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', _).

and

college(CName, 'MA', _).

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

Disjoint sets

intersections(Set1, Set2) :-
    distinct([Set1, Set2], 
          (    
               apply(SID, _, Set1, _), apply(SID, _, Set2, _), 
               Set1 \== Set2
          )).

disjoint(Set1, Set2) :-
    distinct([Set1, Set2],
             (
             apply(_, _, Set1, _), apply(_, _, Set2, _),
                 \+intersections(Set1, Set2),
                 Set1 \== Set2)).
Last updated on 4 May 2021
Published on 4 May 2021

Content Footer