# Equivalence

*By Robert Laing*

Equivalence is reciprocal implication. Though I generally find the implication arrow confusing, here p ⇒ q and q ⇒ p makes a handy mnemonic for p ⇔ q

In logic and regular algebra, if p ≤ q and q ≤ p, then we know p = q. Similarly for sets, if P ⊆ Q and Q ⊆ P, then P = Q.

p | q | p = q | p · q + p · q |
---|---|---|---|

1 | 1 | 1 | 1 |

1 | 0 | 0 | 0 |

0 | 1 | 0 | 0 |

0 | 0 | 1 | 1 |

As usual, lets illustrate with the college example tables.

In the starting state of the college example, none of the *major* sets are equivalent.
By having student 678 apply for *psychology*, both *history* and *psychology*
become {678, 765}.

### SQL

We can make *history* and *psychology* the same setwise like so:

```
INSERT INTO Apply VALUES (678, 'Stanford', 'psychology', 'Y');
```

and then addapt SQL code in implication.

```
SELECT DISTINCT a1.major AS P, a2.major AS Q
FROM Apply as a1, Apply as a2
WHERE NOT EXISTS (
SELECT sid FROM Apply WHERE major = a1.major
EXCEPT
SELECT sid FROM Apply WHERE major = a2.major
)
AND NOT EXISTS (
SELECT sid FROM Apply WHERE major = a2.major
EXCEPT
SELECT sid FROM Apply WHERE major = a1.major
)
ORDER BY a1.major, a2.major;
```

Due to the equivalence relation
P = P, every major is listed, and due to the “commutative law for equivalence” (P = Q) = (Q = P)
both *history* = *psychology* and *psychology* = *history* appear in the results

P | Q |
---|---|

bioengineering | bioengineering |

biology | biology |

CS | CS |

EE | EE |

history | history |

history | psychology |

marine biology | marine biology |

psychology | history |

psychology | psychology |

Adding a `a1.major < a2.major`

rule filters that down to:

P | Q |
---|---|

history | psychology |

To reset the database to its starting state, we need to remember to do:

```
DELETE FROM Apply WHERE sid = 678 AND major = 'psychology';
```

### Prolog

In Prolog, the easiest way to modify the database is to edit the college.pl file before using
`consult(college)`

at the repl.

```
%! 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(678, 'Stanford', 'psychology', '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').
implies_(P, Q) :-
apply(_, _, P, _),
apply(_, _, Q, _),
\+ ( apply(SID, _, P, _),
\+apply(SID, _, Q, _)
).
implies(P, Q) :-
distinct([P, Q], implies_(P, Q)).
```

Then in the swipl repl we can write:

```
?- implies(P, Q), implies(Q, P), P @< Q.
P = history,
Q = psychology ;
false.
```

An alternative approach possible in Prolog is to convert each major to an ordered list of its SIDs
to find `[678, 765] == [678, 765]`

. That’s not possible in the C-family where abstract data structures
are seen as memory addresses, so don’t match even if their contents is identical.

```
apply(_, _, P, _),
apply(_, _, Q, _),
P @< Q,
findall(PID, apply(PID, _, P, _), PIDs),
sort(PIDs, OPIDs),
findall(QID, apply(QID, _, Q, _), QIDs),
sort(QIDs, OQIDs),
OPIDs == OQIDs
```

The above returns

```
P = history,
Q = psychology,
PIDs = [678, 765, 765],
OPIDs = QIDs, QIDs = OQIDs, OQIDs = [678, 765] ;
false.
```

multiple times unless we wrap it in distinct([P, Q],(apply(_, _, P, _),…)).

### Logic Algebra

Doing the algebraic substitution to get from *reciprocal implication*

(p + q) · (q + p)

to equivalence’s

p · q + p · q

goes through quite a few of the “Laws Analogous to Arithmetic” and “Ways in Which AND and OR Differ from Plus and Times” listed in Chapter 12 of Al Aho’s and Jeff Ullman’s online textbook.

(p + q) · (q + p) | "Product-of-Sums" version of p ⇒ q ∧ q ⇒ p |

p · q + p · p + q · q + p · q | Distributive property is analogous to arithmetic |

p · q + p · q | p · p = 0 and q · q = 0 |

p · q + p · q | The commutative law is analogous to arithmetic |

## Laws of Equivalence

Chapter 12 of Al Aho’s and Jeff Ullman’s online textbook lists four laws of equivalence:

- Reflexivity of equivalence: p ⇔ p
- Commutative law for equivalence: (p ⇔ q) ⇔ (q ⇔ p)
- Transitive law for equivalence: if p ⇔ q ⇔ r, then p ⇔ r
- Equivalence of the negations: (p ⇔ q) ⇔ (¬p ⇔ ¬q)

The first three seem quite obvious. As can be seen from diagram 1, when P = Q, P - Q = Q - P = Ø, which “Equivalence of the negations” seems a weird way of saying.

Whereas in normal algebra p - q = 0 means p = q, with sets we need to check both P - Q = Ø and Q - P = Ø to ensure P = Q, since P - Q = Ø is also true for diagram 2, P ⊂ Q.

Looking at the truth table for equivalence, all that “Equivalence of the negations” means is p and q are either both 1 or both 0.

Another possible test for equivalent sets is P ∩ Q = P ∪ Q since that’s only the case when P = Q.