Lesson 13 of 23 · 2:27
Remove shared features with a CM quotient
Compute a quotient as entrywise A∧¬B and preserve its order.
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 · How do we remove cases from a rule?
- 0:25 · Define removal on single bits
- 0:40 · Complement the matrix to be removed
- 0:53 · Compute the retained entries
- 1:09 · Compare with XOR carefully
- 1:28 · Your turn: reverse the quotient
- 1:50 · Answer: nothing remains
- 2:04 · Translate back to logical expressions
Complete transcript
This transcript includes the answers to prediction prompts.
Show transcript
How do we remove cases from a rule? · 0:00
How do we remove cases from a rule? Suppose OR accepts too many input pairs: we want one input or the other, but not both. Removing the cases accepted by AND leaves exclusive-or. The paper calls this operation a quotient. We will calculate that removal entry by entry and learn why reversing its order can change the result.
Define removal on single bits · 0:25
For each pair of entries, retain the left entry only if the right entry is zero. A left zero stays zero. A shared one is removed. We use a set-minus sign for this binary operation so it cannot be confused with unary negation.
Complement the matrix to be removed · 0:40
First complement AND to obtain NAND. Now the both-true cell is zero and the other cells are one. We will AND that array with OR at matching coordinates. The intermediate complement remains visible to make the removal concrete.
Compute the retained entries · 0:53
At the top-left cell, one AND zero removes the both-true case. At each off-diagonal cell, one AND one retains the unequal pair. At the bottom right, zero AND one stays zero. We have recovered exclusive-or by directional removal.
Compare with XOR carefully · 1:09
This result also equals OR exclusive-or AND because every case accepted by AND is already accepted by OR. Outside that containment situation, XOR includes cases that occur only in the right operand. Set difference never adds those right-only cases.
Your turn: reverse the quotient · 1:28
Now reverse the order. Remove everything accepted by OR from the AND matrix. Is there a true cell in AND that OR does not already accept? Predict the complete result before calculating it.
Prediction pause: 8 seconds.
Answer: nothing remains · 1:50
The only one in AND is also a one in OR, so it is removed. All other AND entries were already zero. The result is the zero matrix. Reversing the quotient changes the answer, while reversing the order of XOR does not.
Translate back to logical expressions · 2:04
Place the same bra X and ket Y around the quotient. Its value is X or Y, AND the negation of the entire conjunction X and Y. That is true for exactly one true input, so it is exclusive-or. Next we will combine less obviously related expressions, after aligning their operand order and negations.