A tag filter excludes documents tagged draft or internal — which set expression over the two label sets is equivalent, and why?
answer
- the negation must not change the meaning
- a complement needs a stated universe
- the connective flips under negation
- say it as neither, nor
- test a document tagged only draft
basics
~20 sThe intersection of the two exclusions: documents that are not draft AND not internal. De Morgan's law for sets says the complement of a union is the intersection of the complements, so negating the filter flips 'or' into 'and'.
solid answer
~50 sLet `U` be the corpus, `A` the documents tagged `draft` and `B` those tagged `internal`. 'Exclude anything tagged either' is `U \ (A ∪ B)`, and **De Morgan's law for sets** rewrites that as `(U \ A) ∩ (U \ B)` — not draft *and* not internal. The law comes in a pair: the complement of a union is the intersection of the complements, and the complement of an intersection is the union of the complements. The engineering point is that **negation flips the connective**. Writing the exclusion as 'not draft OR not internal' is the classic bug: that expression is `U \ (A ∩ B)`, which hides only documents carrying *both* labels and happily returns everything tagged just one of them. Both forms are legal set algebra, so nothing fails loudly; only the returned documents are wrong.
go deeper
Remember the pair as one rule: negation flips the connective. The complement of a union is the intersection of the complements, and the complement of an intersection is the union of them.
Derive it from the membership test rather than reciting it, and show the failure shape: a wrongly negated exclusion returns a populated, plausible, slightly-too-large result instead of failing.
Bring the universe into the discussion and name the fixture that catches the bug — a document carrying exactly one of the excluded labels — because that is what a test suite is missing when this reaches production.
Exclusion rules written by different teams in different forms are often the same rule; deciding that policies are expressed in one canonical negated form is what makes them reviewable and de-duplicable at all.
## The filter, written as sets Take the corpus as the universe `U`. Let `A` be the set of documents tagged `draft` and `B` the set tagged `internal`. The requirement 'do not show me anything that is draft or internal' is the complement of the union: ``` result = U \ (A ∪ B) ``` De Morgan's law for sets rewrites it without the union: ``` U \ (A ∪ B) = (U \ A) ∩ (U \ B) U \ (A ∩ B) = (U \ A) ∪ (U \ B) ``` Read in words: **the complement of a union is the intersection of the complements**, and the complement of an intersection is the union of the complements. Negation does not distribute quietly over a connective — it *flips* it. ## A worked collection, because the wrong form still returns rows Take `U = {d1, d2, d3, d4, d5}`, with `A = {d1, d2}` tagged draft and `B = {d2, d3}` tagged internal. | Expression | Value | Reading | |---|---|---| | `A ∪ B` | `{d1, d2, d3}` | tagged either label | | `U \ (A ∪ B)` | `{d4, d5}` | the filter that was asked for | | `(U \ A) ∩ (U \ B)` | `{d4, d5}` | the same set — De Morgan holds | | `(U \ A) ∪ (U \ B)` | `{d1, d3, d4, d5}` | the buggy form | | `U \ (A ∩ B)` | `{d1, d3, d4, d5}` | what the buggy form actually means | The buggy expression leaks `d1` (tagged draft) and `d3` (tagged internal) — precisely the documents carrying **exactly one** of the two labels. It correctly hides only `d2`, the one carrying both. That failure shape is worth memorising: an incorrectly negated exclusion does not return nonsense, it returns a plausible, populated, slightly-too-large result, which is why it survives a demo and reaches production. ## Why negation flips the connective The intuition is a membership test rather than a manipulation of symbols. A document `d` is in `U \ (A ∪ B)` exactly when the statement '`d` is in `A` or `d` is in `B`' is false. For an inclusive or to be false, **both** disjuncts must be false: `d` is not in `A` and `d` is not in `B`. That is the definition of `(U \ A) ∩ (U \ B)`. Run the same argument the other way: '`d` is in `A` and `d` is in `B`' is false as soon as **one** of them fails, which is the union of the complements. Stated that way the law is not a trick to memorise but a restatement of what 'or' and 'and' mean, and it is the reason the pair always comes together — you can never flip one connective without flipping the other. ## Complement needs a universe named out loud `U \ A` is only meaningful once `U` is fixed. In a filter, 'not tagged draft' silently means 'in *this* collection and not tagged draft'. Keeping the difference form `U \ A` rather than a bare complement `A'` forces you to write the universe down, which is why query languages and review checklists prefer it. Two services that both implement 'not draft' over different universes implement different filters, however identical the code reads. ## Where this shows up beyond the filter itself - **Rewriting an exclusion for an index.** An engine that can only intersect per-label sets must push the negation inward; that push *is* De Morgan, and getting it wrong changes the result set rather than failing. - **Composing exclusion rules.** A retention rule 'keep nothing tagged draft or internal' composed with another exclusion is three complements deep; expanding them one law at a time is how you check the composite by hand. - **De-duplicating a policy.** Two rules written by different teams — one as a negated union, one as an intersection of negations — are the *same* rule. Recognising that prevents shipping both and paying twice. ## The checks to run before you ship an exclusion 1. Say the filter out loud with 'neither … nor'. 'Neither draft nor internal' is unambiguous in a way that 'not draft or internal' is not; English's own 'or' scope is the root of the bug. 2. Test a document carrying **exactly one** of the labels. That single case separates the correct form from the buggy one; a document carrying both, or neither, passes under either expression and proves nothing. 3. Name the universe in the same sentence as the exclusion. 4. Count the labels. With three exclusions the correct form is an intersection of three complements; the buggy union of complements now hides only documents carrying **all three**, so the leak gets wider as the rule grows.
- Which single test document separates the correct exclusion from the badly negated one?One carrying exactly one of the two labels. A document tagged both is hidden by either form, and a document tagged neither is returned by either form, so both prove nothing. The singly-tagged document is returned only by the buggy union-of-complements form, which is why it is the case a fixture must contain.
- The rule grows to exclude three labels. How does each form behave?The correct form is the intersection of three complements: not draft and not internal and not archived. The buggy union of complements now equals the complement of the three-way intersection, so it hides only documents carrying all three labels and leaks everything else. The wider the rule, the wider the leak.
- Why is a bare complement discouraged in favour of a difference?A complement is only defined against a universe, and a bare notation lets that universe go unstated. Writing the difference form keeps the collection you are subtracting from in the expression, so a reviewer can see whether it is the whole corpus, one tenant's documents, or the current page — three filters that read identically but return different documents.
saying these in an interview costs you the question
- Negates 'draft or internal' as 'not draft or not internal'.
- Believes the two De Morgan forms return the same documents.
- Uses a complement without saying which collection it is taken from.
- Thinks negating a filter leaves the connective unchanged.
- Tests the exclusion only with documents carrying both labels.
- Says the complement of an intersection is the intersection of complements.