Lesson 12 of 23 · 2:51
Compose and decompose over XOR
Use XOR composition with aligned matrices and explicit overlap checks.
Keyboard: focus the player, then Space or K to play/pause and arrow keys to seek. Tab moves through the controls. Selectable captions replace the video's caption strip with the same timed text below.
In this lesson
- 0:00 · Can smaller rules combine to make OR?
- 0:23 · Calculate the first row
- 0:40 · Complete the second row
- 1:00 · Put the same selectors around both sides
- 1:18 · Why XOR is not simply OR
- 1:37 · Recover a missing piece
- 1:54 · Your turn: cancel an entire matrix
- 2:17 · Answer: every entry becomes zero
- 2:34 · Choose composition or removal deliberately
Complete transcript
This transcript includes the answers to prediction prompts.
Show transcript
Can smaller rules combine to make OR? · 0:00
Can smaller rules combine to make OR? AND accepts the both-true pair, while exclusive-or accepts the two unequal pairs. Together, these three accepted pairs are exactly OR. We will combine the aligned arrays cell by cell, connect the result to measurements, and learn why overlapping ones must be checked rather than simply collected.
Calculate the first row · 0:23
At the top-left position, one exclusive-or zero gives one. At the top-right position, zero exclusive-or one also gives one. This creates the top row of OR. Each operation uses matching coordinates; there is no row-by-column contraction here.
Complete the second row · 0:40
The lower-left position gives zero exclusive-or one, or one. The lower-right position gives zero exclusive-or zero, or zero. The result is one, one above one, zero: the numeric OR matrix. We have checked every input pair, not just one example.
Put the same selectors around both sides · 1:00
With the same bra X and ket Y around every term, the matrix identity becomes an expression identity. Measuring the XOR of the matrices equals XORing their measurements. Boolean AND distributes over exclusive-or, which is why this expansion works.
Why XOR is not simply OR · 1:18
Our first pieces never overlap: AND is true where exclusive-or is false. If pieces overlap, exclusive-or cancels their shared ones. For example, XORing the AND matrix with itself gives the zero matrix. ORing it with itself would preserve AND.
Recover a missing piece · 1:37
If OR equals AND exclusive-or XOR, we can exclusive-or AND into both sides. The two copies of AND cancel, leaving the XOR matrix. This gives a reversible way to recover one unknown piece from the result and the other piece.
Your turn: cancel an entire matrix · 1:54
What remains when the exclusive-or matrix is exclusive-ored with itself? Check a diagonal zero and an off-diagonal one. Decide whether any ones survive. This is cancellation of entire arrays through the same scalar rule in every cell.
Prediction pause: 8 seconds.
Answer: every entry becomes zero · 2:17
Every entry cancels with its identical partner, so the result is the zero matrix. This applies to every Boolean matrix of a fixed shape. Decomposition is therefore about precisely chosen pieces, not just collecting positive entries without checking their overlap.
Choose composition or removal deliberately · 2:34
We have built OR from disjoint pieces and recovered a missing piece by cancellation. Next we will remove accepted cases using a directional operation. That operation agrees with XOR in our particular containment example, but does not behave like XOR in general.