# 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 P^{c} or P', Logic not (or negation) ¬p

P^{c} = {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
)).
```

# 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)).
```