A filter allows a request when authenticated AND (hasRole OR isServiceCall); what is the equivalent reject condition with the negation pushed inward?
answer
- negation moves inward, shape changes
- flip the connective, not just the atoms
- NOT of AND is at least one fails
- NOT of OR means all parts fail
- negations on atoms is negation normal form
basics
~20 sReject when NOT authenticated OR (NOT hasRole AND NOT isServiceCall). De Morgan's laws flip each connective as the negation moves inward: the outer AND becomes OR, the inner OR becomes AND, and every atom is negated.
solid answer
~40 sStart from `NOT (authenticated AND (hasRole OR isServiceCall))` and push the negation inward one level at a time. De Morgan's laws say `NOT (P AND Q)` is `NOT P OR NOT Q`, so the outer AND becomes an OR: `NOT authenticated OR NOT (hasRole OR isServiceCall)`. Applying the dual law `NOT (P OR Q)` is `NOT P AND NOT Q` to the remainder gives the final form: `NOT authenticated OR (NOT hasRole AND NOT isServiceCall)`. Read back in words: reject an unauthenticated caller, or an authenticated one that has neither the role nor the service marker. The mistake to avoid is negating the atoms while leaving the connectives alone — `NOT authenticated AND (NOT hasRole OR NOT isServiceCall)` is a strictly different condition that lets requests through.
go deeper
Memorise both directions and say them out loud: NOT of an AND becomes an OR of the negations, NOT of an OR becomes an AND of the negations. Then apply them one level at a time rather than in a single jump.
Show the mechanics: push the negation down step by step, name negation normal form as the stopping point, and give a truth assignment on which the naive negation disagrees with the correct one.
Tie it to the filter's behaviour. Say which requests the wrong negation would let through, and note that the rewrite preserves short-circuit evaluation so a guarded dereference stays guarded.
The judgment call is whether the guard should be expressed as one positive allow condition or as a chain of independent deny reasons. The second form costs duplication but buys a distinct, auditable reason per rejection.
## The guard and the question being asked A request filter holds exactly one boolean expression: `allow = authenticated AND (hasRole OR isServiceCall)`. In review someone asks for the **reject** condition instead — the expression the filter would test if it denied first and allowed by falling through. Mechanically that is `NOT (authenticated AND (hasRole OR isServiceCall))`, and that expression is already correct. It is also unreadable: with the negation sitting on the outside, nobody can see at a glance which of the three atoms is to blame for a rejection, and nobody can attach a distinct rejection reason to each case. The fix is to push the negation inward until it rests only on individual atoms. That rewrite is driven entirely by **De Morgan's laws**: - `NOT (P AND Q)` is equivalent to `NOT P OR NOT Q` - `NOT (P OR Q)` is equivalent to `NOT P AND NOT Q` Applied outside in, one level per step: 1. `NOT (authenticated AND (hasRole OR isServiceCall))` 2. `NOT authenticated OR NOT (hasRole OR isServiceCall)` — the outer AND has become an OR 3. `NOT authenticated OR (NOT hasRole AND NOT isServiceCall)` — the inner OR has become an AND Step 3 is the answer. An expression in which every negation sits directly on an atom is said to be in **negation normal form**, and reaching it is the first move in any conversion toward conjunctive or disjunctive normal form. ## Why the connective has to flip The law is not a convention; it falls straight out of the truth values. The tempting wrong move is to negate each atom and keep the shape — `NOT authenticated AND (NOT hasRole OR NOT isServiceCall)`. Two rows are enough to kill it: | authenticated | hasRole | isServiceCall | allow | correct negation | shape kept (wrong) | |---|---|---|---|---|---| | true | true | false | true | false | false | | false | true | true | false | **true** | **false** | | false | false | false | false | true | true | | true | false | false | false | **true** | **false** | Row 2 is an unauthenticated caller that happens to carry a role: the guard denies it, so the reject condition must be true, and the wrong form says false. Row 4 is an authenticated caller with no role and no service marker: denied again, and again the wrong form says false. In production both rows are requests that should have been rejected and are instead waved through, which is why this is a security-shaped bug rather than a style complaint. The intuition is worth carrying: negating an AND does not mean *both parts fail*, it means **at least one part fails**. Negating an OR does not mean *at least one part fails*, it means **all parts fail**. ## What the rewrite is good for The inward form is the one that maps onto code a reviewer can follow: - Each disjunct of the reject condition is one **independent reason to deny**, so each can carry its own message, metric or log line. - A chain of early-return guard clauses is exactly an OR of reject reasons evaluated in order; getting to negation normal form is how you derive that chain from a single positive condition. - Negations on atoms compose; negations on subexpressions do not. Any further simplification — absorption, distribution, collapsing a duplicated clause — needs the negations pushed down first. ## What the rewrite does not change One worry comes up every time this is proposed in review: does moving the negation change which operands actually get evaluated? With short-circuiting operators, no. Take `NOT (a AND b)`: if `a` is false the AND short-circuits and `b` is never evaluated; in the rewritten `NOT a OR NOT b`, `NOT a` is true so the OR short-circuits and `b` is never evaluated either. If `a` is true, both forms go on to evaluate `b`. The operand order is untouched and the set of evaluated operands is identical, so a dereference guarded by a preceding null test stays guarded. What the rewrite does assume is that each atom denotes **one fixed truth value** during the evaluation. Boolean algebra treats `hasRole` as a truth value, not as a call that might answer differently the second time it is asked. If an atom reads mutable shared state, re-checks a clock, or asks a remote party, the algebra still describes the formula but no longer describes the program, and the honest fix is to evaluate the atom once into a local name before reasoning about it.
- Does pushing the negation inward change which operands get evaluated at runtime?No. With short-circuiting operators the evaluated set is identical. In `NOT (a AND b)`, a false `a` short-circuits the AND; in `NOT a OR NOT b`, a false `a` makes `NOT a` true and short-circuits the OR. Either way `b` is evaluated only when `a` is true, so a test that guards a later dereference keeps guarding it.
- The rewritten reject condition still contains NOT on every atom. When is that worse than the original?When the atoms are themselves negatively named. `NOT isNotExpired` is two negations a reader must cancel mentally. Rename the atom positively first, then rewrite; the laws are indifferent, but the resulting condition is readable only if each literal states a fact rather than the absence of one.
- How do you convince a reviewer the rewrite is correct without a full truth table?Name the witness rows. For a three-atom guard, point at the assignments where the naive negation and the correct one disagree — here an unauthenticated caller carrying a role, and an authenticated caller with neither marker — and say what the filter does on each. One concrete row that flips a deny into an allow ends the argument faster than eight rows of enumeration.
"It is not true that the door is locked and the alarm is armed" does not claim both are off. It claims at least one of them is off — which is exactly why the AND turns into an OR.
saying these in an interview costs you the question
- Negating both operands is enough; the AND can stay an AND
- NOT (a OR b) means the same as NOT a OR NOT b
- De Morgan's laws apply to sets only, not to conditions in code
- Pushing a negation inward can change which branch of the filter runs
- A double negation must be kept because cancelling it alters the guard
- Wrapping the whole condition in NOT is as readable as the inward form