WEBVTT

1
00:00:00.180 --> 00:00:03.872
Can smaller rules combine to make OR?

2
00:00:03.872 --> 00:00:09.805
AND accepts the both-true pair, while exclusive-or accepts the two unequal pairs.

3
00:00:09.805 --> 00:00:16.562
Together, these three accepted pairs are exactly OR. We will combine the aligned arrays cell by cell,

4
00:00:16.562 --> 00:00:23.434
connect the result to measurements, and learn why overlapping
ones must be checked rather than simply collected.

5
00:00:23.614 --> 00:00:29.338
At the top-left position, one exclusive-or zero gives one. At the top-right position,

6
00:00:29.338 --> 00:00:34.852
zero exclusive-or one also gives one. This creates the top row of OR.

7
00:00:34.852 --> 00:00:40.088
Each operation uses matching coordinates; there is no row-by-column contraction here.

8
00:00:40.268 --> 00:00:45.086
The lower-left position gives zero exclusive-or one, or one.

9
00:00:45.086 --> 00:00:49.765
The lower-right position gives zero exclusive-or zero, or zero.

10
00:00:49.765 --> 00:00:56.487
The result is one, one above one, zero: the numeric OR matrix.

11
00:00:56.487 --> 00:01:00.318
We have checked every input pair, not just one example.

12
00:01:00.498 --> 00:01:07.673
With the same bra X and ket Y around every term,
the matrix identity becomes an expression identity.

13
00:01:07.673 --> 00:01:12.445
Measuring the XOR of the matrices equals XORing their measurements.

14
00:01:12.445 --> 00:01:18.179
Boolean AND distributes over exclusive-or, which is why this expansion works.

15
00:01:18.359 --> 00:01:23.177
Our first pieces never overlap: AND is true where exclusive-or is false.

16
00:01:23.177 --> 00:01:27.171
If pieces overlap, exclusive-or cancels their shared ones.

17
00:01:27.171 --> 00:01:33.370
For example, XORing the AND matrix with itself gives the zero matrix.

18
00:01:33.370 --> 00:01:37.155
ORing it with itself would preserve AND.

19
00:01:37.335 --> 00:01:44.150
If OR equals AND exclusive-or XOR, we can exclusive-or AND into both sides.

20
00:01:44.150 --> 00:01:48.341
The two copies of AND cancel, leaving the XOR matrix.

21
00:01:48.341 --> 00:01:53.902
This gives a reversible way to recover one unknown piece from the result and the other piece.

22
00:01:54.082 --> 00:01:58.819
What remains when the exclusive-or matrix is exclusive-ored with itself?

23
00:01:58.819 --> 00:02:04.078
Check a diagonal zero and an off-diagonal one. Decide whether any ones survive.

24
00:02:04.078 --> 00:02:16.931
This is cancellation of entire arrays through the same scalar rule in every cell.

25
00:02:17.111 --> 00:02:22.382
Every entry cancels with its identical partner, so the result is the zero matrix.

26
00:02:22.382 --> 00:02:29.638
This applies to every Boolean matrix of a fixed shape.
Decomposition is therefore about precisely chosen pieces,

27
00:02:29.638 --> 00:02:33.631
not just collecting positive entries without checking their overlap.

28
00:02:33.811 --> 00:02:39.639
We have built OR from disjoint pieces and recovered a missing piece by cancellation.

29
00:02:39.639 --> 00:02:43.947
Next we will remove accepted cases using a directional operation.

30
00:02:43.947 --> 00:02:51.214
That operation agrees with XOR in our particular containment
example, but does not behave like XOR in general.