Frontier Software

Robert Laing's programing notes

Logic and Sets

By Robert Laing

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

Terms

35

Propositions

1881 John Venn, Symbolic Logic

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

  1. A ≡ B
  2. A ⊆ B
  3. B ⊆ A
  4. A ⋂ B
  5. A ≢ B

1918 CI Lewis, A Survey of Symbolic Logic

124

Alexander MacFarlane

Christine Ladd-Franklin

Inclusion–exclusion principle

https://pure.uva.nl/ws/files/2685375/166230_07.pdf

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

and

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