# 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

denialof a proposition gives the right toaffirmthe contrary; whereas it should be that theaffirmationof a proposition gives a right todenythe 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

- A ≡ B
- A ⊆ B
- B ⊆ A
- A ⋂ B
- A ≢ B

1918 CI Lewis, A Survey of Symbolic Logic

124

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 P^{c} 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:

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

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 ∩ Q^{c} ⊆ {} 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 ∩ Q^{c} = ∅

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

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