A job board must list the candidates its filter rejected; why is negating a two-part 'and' filter not simply negating both parts?
answer
- negation moves inward
- the joining word flips too
- conjunction becomes disjunction
- failing either test means rejected
- negating both parts selects only the both-fail case
basics
~20 sNegation flips the connective as well as the parts. The complement of 'permit and three years' is 'no permit OR under three years', not 'no permit AND under three years' - the second selects only the candidates who fail both tests.
solid answer
~40 sDe Morgan's laws say the negation of a conjunction is the disjunction of the negations, and the negation of a disjunction is the conjunction of the negations. So the rejected list for a filter of `and(hasPermit, seniorEnough)` is `or(not hasPermit, not seniorEnough)`: a candidate is rejected the moment either test fails. Negating both parts and keeping the `and` asks for candidates who fail *both*, which is a strict subset of the rejected set. With two independent yes/no tests there are four combinations; the filter accepts one and rejects three, while the wrong rewrite picks up only one of those three. The practical rule is: push the negation inward and flip every connective it passes through.
code
pseudocode · 7 linesaccepted = and(hasPermit, seniorEnough)
// correct complement
rejected = or(negate(hasPermit), negate(seniorEnough))
// wrong: selects only candidates failing BOTH tests
rejectedWrong = and(negate(hasPermit), negate(seniorEnough))go deeper
Memorise the flip: negating an 'and' of two tests gives an 'or' of the two negated tests. Be able to name one candidate the wrong rewrite would miss.
Derive it rather than recite it. Enumerate the four combinations of two yes/no tests, show which the filter accepts, and show that the wrong rewrite picks up only one of the three rejected rows.
Talk about the operational consequence: a rejected list quietly missing near-miss candidates, and how you would catch it - enumeration for small filters, generated candidates compared under both spellings for wide ones.
Set the convention: keep named predicates positive, define the accepted condition once, derive its complement, and decide across the team what an unfilled field means before it reaches any combinator.
## The law, stated for a filter When a compound condition is built from small named predicates, negating it is not a matter of negating each piece. **De Morgan's laws** describe what actually happens: - `not( A and B )` is equivalent to `( not A ) or ( not B )` - `not( A or B )` is equivalent to `( not A ) and ( not B )` In combinator form: negating a conjunction gives a **disjunction** of negated parts, and negating a disjunction gives a **conjunction** of negated parts. The negation moves inward and every connective it crosses flips. ## Worked on a candidate filter A job board accepts candidates who **have a work permit** and **have at least three years of experience**. Two independent yes/no tests give exactly four combinations: | Has permit | Three years | Accepted by the filter | In the rejected list | |---|---|---|---| | yes | yes | accepted | no | | yes | no | rejected | yes | | no | yes | rejected | yes | | no | no | rejected | yes | The filter accepts **1** of the 4 cells and rejects **3**. The correct complement, `or(no permit, under three years)`, selects exactly those 3. The tempting wrong rewrite, `and(no permit, under three years)`, selects only the bottom row - **1** of the 3 - and silently loses the two rows where a candidate failed one test but passed the other. Those are precisely the near-misses a recruiter most wants to see, which is why this defect tends to be reported as "the rejected list is missing people" rather than as a logic bug. ## Why it is so easy to get wrong Everyday speech negates the parts and leaves the joining word alone: "they had a permit and the experience" becomes "they had neither". That informal negation is the wrong rewrite. The law is about the **set** the condition selects, not about the sentence. The second trap is nesting. Once a filter is three or four levels deep, the negation has to be pushed all the way down, flipping at every level: 1. Start from `not( A and ( B or C ) )`. 2. Flip the outer conjunction: `( not A ) or not( B or C )`. 3. Flip the inner disjunction: `( not A ) or ( ( not B ) and ( not C ) )`. Stopping after step 2 leaves a negation sitting on a compound condition, which is exactly where the next reader will apply the informal rewrite and get it wrong. ## What the rewrite does and does not change - **The accepted set does not change.** The two spellings select identical candidates; this is an equivalence, not an approximation. - **The order the parts are consulted may change**, because a conjunction and a disjunction stop on different outcomes - a conjunction is settled by the first part that fails, a disjunction by the first that holds. - **Readability changes, often a lot.** Teams usually pick whichever spelling states the business rule in the words the business uses. - **Double negation collapses.** `not( not A )` is `A`, and leaving it in place is how a rewritten filter turns into something nobody can read. ## Boundaries and the honest caveat The laws hold for two-valued logic: every part must answer either yes or no for the candidate in front of it. Where a test can be *unknown* - a field that has never been filled in, an answer the candidate skipped - negation is no longer a clean complement, because "not senior enough" and "we do not know whether they are senior enough" are different populations. Real filters usually resolve this before combining: decide what an absent value means for each individual predicate, so that by the time the combinator sees it, every part really does answer yes or no. Interviewers like this follow-up because it separates a candidate who has read the law from one who has shipped a filter over real, partly-empty data. The practical discipline is small: keep each named predicate positive where you can, build the accepted condition, and derive the rejected condition by negating the whole thing and letting the rewrite flip the connectives - rather than hand-writing a second condition that then drifts from the first.
- How would you convince a reviewer that the rewritten filter selects the same candidates?Enumerate the combinations. Two independent parts give four rows, four parts give sixteen, and checking both spellings against every row is a finite, mechanical argument. For a filter too wide to enumerate, a property test that applies both conditions to generated candidates and asserts equal answers makes the same argument by sampling.
- What happens to the law when a part cannot answer yes or no for a candidate?It stops being a clean complement. With an unknown third outcome, the negation of a test is no longer everything the test did not select, so the accepted and rejected lists can miss candidates between them. The fix is to decide at each individual predicate what an absent value means, so the combinator only ever sees two-valued answers.
- Is one spelling cheaper to evaluate than the other?They can differ, because the two connectives are settled by different outcomes: a conjunction is decided by the first failing part, a disjunction by the first holding part. Which is cheaper depends on how often each part holds, so the choice is about the data, not about the law.
A door that opens only when both keys are turned stays shut if either key is missing - not only when both are missing.
saying these in an interview costs you the question
- Negates each part and leaves the connective unchanged
- Says the complement is candidates who fail both tests
- Claims the rewrite changes which candidates are selected
- Pushes negation one level and stops at a nested compound
- Leaves a doubled negation in place as if it were harmless
- Assumes the law holds unchanged when a test answers 'unknown'