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.

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

Adding a a1.major < a2.major rule filters that down to:

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.

Laws of Equivalence

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

1. Reflexivity of equivalence: p ⇔ p
2. Commutative law for equivalence: (p ⇔ q) ⇔ (q ⇔ p)
3. Transitive law for equivalence: if p ⇔ q ⇔ r, then p ⇔ r
4. 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.