WEBVTT

1
00:00:00.180 --> 00:00:03.466
How do we remove cases from a rule?

2
00:00:03.466 --> 00:00:10.223
Suppose OR accepts too many input pairs: we want one input or the other, but not both.

3
00:00:10.223 --> 00:00:15.099
Removing the cases accepted by AND leaves exclusive-or.

4
00:00:15.099 --> 00:00:18.280
The paper calls this operation a quotient.

5
00:00:18.280 --> 00:00:24.874
We will calculate that removal entry by entry and
learn why reversing its order can change the result.

6
00:00:25.054 --> 00:00:30.139
For each pair of entries, retain the left entry only if the right entry is zero.

7
00:00:30.139 --> 00:00:33.785
A left zero stays zero. A shared one is removed.

8
00:00:33.785 --> 00:00:39.670
We use a set-minus sign for this binary operation so it cannot be confused with unary negation.

9
00:00:39.850 --> 00:00:45.876
First complement AND to obtain NAND. Now the both-true cell is zero and the other cells are one.

10
00:00:45.876 --> 00:00:53.259
We will AND that array with OR at matching coordinates. The intermediate
complement remains visible to make the removal concrete.

11
00:00:53.439 --> 00:00:57.352
At the top-left cell, one AND zero removes the both-true case.

12
00:00:57.352 --> 00:01:04.329
At each off-diagonal cell, one AND one retains the unequal
pair. At the bottom right, zero AND one stays zero.

13
00:01:04.329 --> 00:01:08.598
We have recovered exclusive-or by directional removal.

14
00:01:08.778 --> 00:01:12.783
This result also equals OR exclusive-or AND because

15
00:01:12.783 --> 00:01:18.449
every case accepted by AND is already accepted by OR.

16
00:01:18.449 --> 00:01:24.765
Outside that containment situation, XOR includes cases that occur only in the right operand.

17
00:01:24.765 --> 00:01:28.131
Set difference never adds those right-only cases.

18
00:01:28.311 --> 00:01:34.220
Now reverse the order. Remove everything accepted by OR from the AND matrix.

19
00:01:34.220 --> 00:01:38.621
Is there a true cell in AND that OR does not already accept?

20
00:01:38.621 --> 00:01:50.045
Predict the complete result before calculating it.

21
00:01:50.225 --> 00:01:57.365
The only one in AND is also a one in OR, so it is removed. All other AND entries were already zero.

22
00:01:57.365 --> 00:02:04.470
The result is the zero matrix. Reversing the quotient changes
the answer, while reversing the order of XOR does not.

23
00:02:04.650 --> 00:02:08.806
Place the same bra X and ket Y around the quotient.

24
00:02:08.806 --> 00:02:14.960
Its value is X or Y, AND the negation of the entire conjunction X and Y.

25
00:02:14.960 --> 00:02:19.581
That is true for exactly one true input, so it is exclusive-or.

26
00:02:19.581 --> 00:02:26.604
Next we will combine less obviously related expressions,
after aligning their operand order and negations.